How to elegantly predict average number of zero crossings for cumulative sum plot for N flips of a coin where heads is +1 and tails is -1 I believe the same question was asked in question 1338097, but I think the answer might be flawed. However, I'm not familiar with the terms and have only the most basic understanding of probability theory. I know that if you create a sequence of +1s and -1s by flipping a fair coin N times (e.g. heads for +1, tails for -1) the number of possible sequences, ranging from all +1s to all -1s is 2^N. And assuming the sequence is truly random, each of the possible sequences will have the same probability of occurring. Therefore, if you generated each of the 2^N possible sequences, performing the cumulative summation process for each and counting the number of times the sum crosses 0 (i.e. 1 -> 0 -> -1 or -1 -> 0 -> 1), then dividing that count by 2^N gives the answer I'm looking for. And for N = 5 or less, you could even figure it out on a piece of paper in a few minutes if you weren't a computer programmer or didn't have a computer. But I wrote a program to do it and here's my table of answers for N = 2 to 10:
 N    average 0 crossings
 2    none (takes at least 3 moves to cross 0)
 3    .25 
 4    .25
 5    .4375
 6    .4375
 7    .59375
 8    .59375
 9    .730469
 10   .730469

And since the process to come up with these answers involves nothing more than simple arithmetic, I believe these answers are as exact as single-precision floating point operations can give. Of course, the problem with this method is that the computer is brought to its knees for values of N higher than about 30. But I don't care about being that exact. Approximations to, say, 5 decimal places would be fine. Is there an elegant solution that would have my computer spitting out the answer for values of N greater than 100 or even 1000?
 A: Let $X_n$ be the number of zero crossings for a sequence of $n$ coin flips. We note that $\mathbb{E}X_n = \mathbb{E}X_{n-1}$ when $n$ is even, since the last step can't complete a zero crossing and therefore can be ignored.
Assume $n$ is odd. Let $S_k$ be the total after the $k$ steps and let $Z_k$ be an indicator for whether there is a zero crossing at index $k$, i.e. $$Z_k = \mathbb{1}\{S_{k-1}=\pm 1, S_{k}=0, S_{k+1}=\mp 1\}.$$
We can write the number of zero crossings, $X_n$, as the sum of these indicators:
$$X_n =\sum_{i=1}^{\frac{n-1}{2}}Z_{2i}.$$
By linearity of expectation:
$$\mathbb{E}X_n =\sum_{i=1}^{ \frac{n-1}{2}}P(S_{2i-1}=\pm 1, S_{2i}=0, S_{2i+1}=\mp 1)=2\sum_{i=1}^{\frac{n-1}{2}}P(S_{2i-1}= 1, S_{2i}=0, S_{2i+1}=-1),$$
where the last line follows because the random walk is symmetric.
Since $S_{k}\sim 2\text{Binom}(k,\frac{1}{2})-k,$ we get
\begin{align*}P(S_{2i-1}= 1, S_{2i}=0, S_{2i+1}=-1)&=P(S_{2i-1}=1)P(S_{2i}=0, S_{2i+1}=-1\vert S_{2i-1}=1)\\
&=\frac{1}{4}\binom{2i-1}{i}\frac{1}{2^{2i-1}},
\end{align*}
so for odd $n$, we have
$$\mathbb{E}X_n = \mathbb{E}X_{n+1} =\sum_{i=1}^{\frac{n-1}{2}}\binom{2i-1}{i}\frac{1}{2^{2i}}.$$
Wolfram Alpha gives a closed form for this sum:
$$\frac{1}{2}\left(-1 + 2^{-n} (n+1) \binom{n}{ \frac{n+1}{2}}\right).$$
