Probability of getting the same vector result This is part of a mathematical puzzle I was given to me by a friend a while ago and I can't work out how to solve it. Does anyone have any ideas?
For a given vector $v \in \{-1,1\}^n$ we consider the following $n$ sums. $$S_j=\sum_{i=0}^j v_i - \sum_{i=j+1}^{n-1} v_i \text{ for } 0 \leq j \leq n-1.$$
For example if $v = (-1,1,1)$ then $S=(-3,-1,1).$
Now let $f(S)_j = 1$ if $S_j>0$ and $0$ otherwise. So for our example vector $v$ we have that $f(S)=(0,0,1)$

For two uniformly randomly selected vectors $v,w \in \{-1,1\}^n$ what
  can we say about $$P(f(v) = f(w)).$$

We know that $P(f(v) = f(w)) \geq 2^{-n}$ as this is the probability that $v=w$.  This gives a lower bound, but what upper bound can one find?
 A: The probability is in $\Omega\left(n^{-2}\right)$, and apparently also in $O\left(n^{-2}\right)$ (and thus in $\Theta\left(n^{-2}\right)$).
I'll focus on odd $n$ because it makes things easier, but I believe with some slight complications similar considerations apply to even $n$.
If we add another entry for $j=-1$ to $S$, we have $S_{-1}=-S_{n-1}=:\sigma$. Moving from $j=-1$ to $j=n-1$, we successively transfer each entry of $v$ from the negative sum to the positive sum, with a change of $\pm2$ in each step. Two such sequences lead to the same $f$ vector iff they have the same zero crossings. Thus the probability can be obtained as $2^{-2n}$ times the sum, over all possible zero crossing sets, of the square of the number of sequences with exactly those zero crossings.
For odd $n=2k+1$, there are an odd number of zero crossings (since $\sigma\ne0$). Consider the term with one zero crossing. Imagine $S_j$ plotted against $j$, and reflect the part of the graph under the $j$ axis at the axis to flip it above the axis. Since $S_{-1}=-S_{n-1}$, that makes the graph match up at $-1$ and $n-1$, so we can now consider it cyclically. If we fix the position of the one zero crossing, that fixes the two values adjacent to it, and the number of possibilities for the remaining values, given that they must not cross the axis, is given by $C_k$, the $k$-th Catalan number. We need to square this to get the contribution to the probability, and then multiply by $2n$ ($n$ for the position of the zero crossing and $2$ because the negative part can be on either side of the zero crossing). Thus the contribution to the probability for one zero crossing is
$$
2^{-2n}\cdot2n\cdot\left(\frac1{k+1}\binom{2k}k\right)^2
$$
The asymptotic behaviour of the Catalan numbers is
$$
C_k \sim \frac{4^k}{k^{3/2}\sqrt{\pi}}\;,
$$
so that contribution is asymptotic to
$$
\frac4\pi\frac1{n^2}\;.
$$
The remaining terms can be calculated likewise – for all odd $m$, we'd have to sum, over all possible positions of $m$ zero crossings, the square of a product of $m$ Catalan numbers counting the numbers of non-zero-crossing connections between the zero crossings. While there are of the order of $n^m$ ways to choose the positions of the zero crossings, almost all of these involve $m$ factors of the order of $(n/m)^{-3}$ from the Catalan numbers, so not much is gained. This is of course not a rigorous argument for the probability being in $O\left(n^{-2}\right)$, but it could perhaps be turned into one, and in any case the numerical results confirm that the term for one zero crossing is the dominant one.
Here's a doubly logarithmic plot of the probabilities up to $n=30$ (right-click for options to display it in full resolution):

The pink boxes are for even $n$, the red crosses are for odd $n$, the green line is a fit to the results for odd $n$ with slope $-2$ (corresponding to $n^{-2}$), and the blue line is the above result for the dominant term, $(4/\pi)n^{-2}$.
