Introduction to Probability · Problem 12.1.5

Random Walks — Grinstead & Snell

Mathematics — Probability · random-walks-lead-changes

Problem

A lead change in a random walk occurs at time 2k2k if S2k−1S_{2k-1} and S2k+1S_{2k+1} are of opposite sign. (a) Give a rigorous argument which proves that among all walks of length 2m2m that have an equalization at time 2k2k, exactly half have a lead change at time 2k2k. (b) Deduce that the total number of lead changes among all walks of length 2m2m equals 12(g2m−u2m).\frac{1}{2}(g_{2m} - u_{2m}). (c) Find an asymptotic expression for the average number of lead changes in a random walk of length 2m2m.

Related theory

Browse the problem library