I am trying to solve the problems in the Chapter 12 Random Walks of Introduction to Probability by Grinstead and Snell. I am stuck at Problem 6(b) which I quote below (page 482)
- Problem 6 (a) Show that the probability that a random walk of length $2m$ has a last return to the origin at time $2k$, where $0 \le k \le m$, equals $ \frac{{2k \choose k} {2m-2k \choose m-k}}{2^{2m}} = u_{2k} u_{2m-2k} $.
(The case $k = 0$ consists of all paths that do not return to the origin at any positive time.) Hint: A path whose last return to the origin occurs at time $2k$ consists of two paths glued together, one path of which is of length $2k$ and which begins and ends at the origin, and the other path of which is of length $2m - 2k$ and which begins at the origin but never returns to the origin. Both types of paths can be counted using quantities which appear in this section.
Solution
I could solve this part. The proof follows from the hint. We know the probability of equalization at $2k$ is $u_{2k} = {2k \choose k}$.
The probability of no equalization in $2k$ steps is = $1 - \sum_{m=1}^{k} f_{2m}$ where $f_{2m}$ is the probability of first equalization happening at $2m$. From Problem 2(a), we know $f_{2m} = u_{2m-2} - u_{2m}$. Using this result we get,
$1 - \sum_{m=1}^{k} f_{2m} = 1 - [(u_{0}-u_{2}) + (u_{2}-u_{4}) + \ldots + (u_{2k-2} - u_{2k})]$ which on telescoping leads to $1 - u_{0} + u_{2k} = u_{2k}$ since $u_{0} = 1$ by definition.
Thus the probability of no equalization in $2k$ steps is $u_{2k}$ which is same as the probability of equalization in $2k$ steps.
Thus in $2m$ steps the probability of equalization in $2k$ and no equalization in the remaining $2m-2k$ steps is $u_{2k} u_{2m-2k}$.
- Problem 6(b) Using part (a), show that if $m$ is odd, the probability that a walk of length $2m$ has no equalization in the last $m$ outcomes is equal to $1/2$, regardless of the value of $m$.
Hint: The answer to part a) is symmetric in $k$ and $m-k$.
I don't understand the hint in this part and I am not sure how to go about solving this problem.
I tried the brute force and could not generalize it. This is what I did. I wrote down the sample paths for $2m=6$ and found that at $m=3$ the sum can either be $S_{3} = \{3,1,-1,-3\}$. There are $3$ paths whose sum is either $\{1,-1\}$ and a path each whose sum is either $\{3,-3\}$. The path whose sum is either $\{3,-3\}$ can combine with $7$ paths without equalizing and the paths whose sum is either $\{1,-1\}$ can combine with $3$ paths without equalizing. Thus total number of paths which do not equalize in the latter half ($k = 4,5,6$) of $2m=6$ is = $7 \times 1 + 3 \times 3 + 3 \times 3 + 7 \times 1 = 32$. Thus $32$ out of possible $64$ paths do not equalize the latter half ($k = 4,5,6$) of the sample path. I tried to generalize this to get an answer of $2^{2m-1}$ but I could not make any headway.
I think there must be an easier way based on the hint. Can someone give me more hints on how to solve this problem?