[math] \newcommand{\NA}{{\rm NA}} \newcommand{\mat}[1]{{\bf#1}} \newcommand{\exref}[1]{\ref{##1}} \newcommand{\secstoprocess}{\all} \newcommand{\NA}{{\rm NA}} \newcommand{\mathds}{\mathbb}[/math]

• Show that the probability that a random walk of length [math]2m[/math] has a last return to the origin at time [math]2k[/math], where [math]0 \le k \le m[/math], equals
  [[math]] {{{2k}\choose k}{{2m-2k}\choose {m-k}}\over{2^{2m}}} = u_{2k}u_{2m - 2k}\ . [[/math]]
  (The case [math]k = 0[/math] 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 [math]2k[/math] consists of two paths glued together, one path of which is of length [math]2k[/math] and which begins and ends at the origin, and the other path of which is of length [math]2m - 2k[/math] 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.
• Using part (a), show that if [math]m[/math] is odd, the probability that a walk of length [math]2m[/math] has no equalization in the last [math]m[/math] outcomes is equal to [math]1/2[/math], regardless of the value of [math]m[/math]. Hint: The answer to part a) is symmetric in [math]k[/math] and [math]m-k[/math].