Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


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?

share|cite|improve this question
up vote 1 down vote accepted

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.

share|cite|improve this answer
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
Got it. Thanks – Anand Apr 27 '11 at 0:21

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.