Unexpected answer to an expected value problem

Question

Suppose you start on the zero notch of the line of integers. You flip a coin. If you get heads, you move to the integer on the right (+1), and if you get tails, you move to the integer on the left (-1). It turns out that the expected number of flips to reach +1, from 0, is infinity. Why?

Answer 1

Suppose $X$ be Number of flips to reach $+1$ from $0$ as starting point,

$Y$ be Number of flips to reach $0$ from $-1$ as starting point,

$Z$ be Number of flips to reach $+1$ from $0$ as starting point,

and $W$ be Number of flips to reach $+1$ from $-1$ as starting point.

Now if we start from $0$, we have two: $$E(X)= \frac{1}{2}.1 + \frac{1}{2}.E(W)$$ Now obviously for reaching $+1$ from $-1$ we must pass the $0$, So we have: $$E(W)= E(Y+Z)=E(Y)+E(Z)$$ By symmetry we know: $$E(X)= E(Y)= E(Z)$$ So by: $$E(W)= 2E(X)$$ And therefor: $$E(X)= \frac{1}{2}.1 + \frac{1}{2}.2E(x) \Longrightarrow E(X)= \frac{1}{2} +E(X)$$ That has no finite solution!

Answer 2

Let's try to calculate this expected value. First of all, observe that, by parity, one can only reach $+1$ in an odd amount of flips, as the parity of the integer you're at is always equal to the number of flips you've done. Now, notice that, in order to reach $+1$ in $2k+1$ flips, we must stay at $0$ or below for $2k-1$ flips, then cross $0$, and cross to $+1$. If we write our sequence of heads and tails down, encoding each tails with a left parenthesis '(', and each heads with a right parenthesis ')', our first $2k$ flips must encode a balanced sequence of brackets, and furthermore, there must be a bijection between these bracket sequences of length $2k$ and our sequences of $2k+1$ flips that get us to $+1$.

The number of balanced bracket sequences of length $2k$ can be calculated as the $k$-th Catalan number $C_k$, and the number of ways to flip our coin $2k+1$ times equals $2^{2k+1}$, which means that our expected value equals $$\sum_{k=0}^\infty \frac{C_k(2k+1)}{2^{2k+1}}.$$ $$=\sum_{k=0}^\infty \frac{(2k+1)!}{k!(k+1)!2^{2k+1}}.$$ For $k=3$, it turns out that the inequality $$\frac{(2k+1)!}{k!(k+1)!2^{2k+1}}<\sqrt{k+1}-\sqrt{k}$$ holds. Furthermore, for all positive $k$, $$\frac{\sqrt{k+2}-\sqrt{k+1}}{\sqrt{k+1}-\sqrt{k}}<\frac{2k+3}{2k+4}.$$ By combining both inequalities, and by a simple induction, we can conclude that $$\sum_{k=0}^\infty \frac{(2k+1)!}{k!(k+1)!2^{2k+1}}>\sum_{k=3}^\infty \frac{(2k+1)!}{k!(k+1)!2^{2k+1}}>\sum_{k=3}^\infty \sqrt{k+1}-\sqrt{k},$$ but this last sum is telescopic and clearly diverges. This implies that our expected value is infinite.

EDIT: There's a better way to do the last part. Notice first that $$\sum_{k=0}^\infty \frac{(2k+1)!}{k!(k+1)!2^{2k+1}}>\sum_{k=0}^\infty \frac{(2k)!}{k!^22^{2k+1}}.$$ The $n$-th partial sum of the latter sum can be proven by a simple induction to equal $$\frac{\Gamma(n+\frac{3}{2})}{\sqrt{\pi}\Gamma(n+1)}.$$ It's not hard to convince yourself that this diverges.