# Random Walk - If $m$ is odd, probability of no equalization in the last $m$ steps in path of length $2m$ is 1/2

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?

-

Let $T$ be a r.v. denoting the time of last equalization. You calculated in part (a) that $$\Pr[T = 2k] = u_{2k} u_{2(m-k)}.$$
Part (b) asks you for $$\Pr[T < m] = \Pr[T \leq 2\cdot \tfrac{m-1}{2}].$$ Now $$\sum_{r=0}^m \Pr[T = 2r] = 1$$ and moreover $$\Pr[T = 2r] = \Pr[T = 2m - 2r].$$ You can probably conclude the problem from here.
I didn't get how $$\sum_{r=0}^m \Pr[T = 2r] = 1$$ Other than this step I can follow the argument. Thanks. – Anand Apr 27 '11 at 0:09
I'm going over all the possible values for $T$. When $r = 0$ then it certainly equalizes, and it can't equalize at any odd time (because of parity issues). – Yuval Filmus Apr 27 '11 at 0:18