3
$\begingroup$

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?

1 Answers 1

1

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.

  • 0
    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).2011-04-27