Consider standard random walk on integer line. (probabilities $\frac{1}{2}$ to go left or right, start at $0$).
I am reading probability and random processes book and I came across following theorem:
Mean number of visits of the walk to point $b$ before returning to origin equals $1$.
I don't get it intuitively. How is it possible that no matter how big is $b$, expected value is still $1$, how on earth it is expected that random walk will visit $999999999999999$ before returning to $0$ again.
How to understand this theorem? Is it even true? Is it known theorem? If you run random walk on computer many times it is really the case that no matter what $b$ is most of the times random walk will visit it once before returning to $0$?
Best Answer
Wlog assume $b > 0$. It's a standard result that the probability that the walk goes to $b$ before it returns to $0$ is $1/2b$, for instance see this.
Now, suppose the walk did get to $b$. Then note by the Markov property and symmetry that the chance that it comes back to $b$ before it reaches the origin is again $1/2b$. This lets us compute the mean number of time we hit $b$ before coming back to $0$.
Indeed, to get exactly one hit at $b$ before return, we have the chance $1/2b \cdot 1/2b$: first get to $b$, and then come to $0$ before hitting $b$ again. To get exactly two hits, we have the chance $1/2b \cdot (1-1/2b) \cdot 1/2b$: get to $b$, come back to $b$ without hitting $0$, and then go to $0$ without hitting $b$ again. This pattern clearly continues.
In general, if $N$ is the number of visits to $b$ before returning to $0$, then for $k \ge 1,$ $$ P(N = k) = \frac{1}{4b^2} \left( 1 - 1/2b\right)^{k-1}.$$ This gives the mean number of hits of $$ \mathbb{E}[N] = \frac{1}{4b^2} \sum_{k \ge 1} k (1-1/2b)^{k-1} = \frac{1}{4b^2} \cdot -\partial_\pi \sum (1-\pi)^k|_{\pi = 1/2b} \\ = \frac{1}{4b^2} \cdot - \partial_\pi \left.\frac{1}{1-\pi} \right|_{\pi = 1/2b} = \frac{1}{4b^2} \cdot \frac1{(1/2b)^2} = 1.$$
The basic intuition to carry is that it is very rare indeed to get to a very far out position before coming back to $0$ once, but equivalently, if the walk does get to that very far position, then it's very rare to come back to $0$. Once the walk gets to $b$, it'll tend to spend a long time near $b$, and will keep hitting $b$ again and again, many times, before it can make it back to $0$. Indeed, note that the conditional mean of the number of hits at $b$ before return given that the walk does visit it at least once is $2b$. The exact balance, of course, is coming from the symmetry of this random walk.