A fair walk starts at 0 and moves ±1 at each of t independent steps. Give P(position=k), including impossible endpoints.
Quant ResearchLevel: IntermediateRandom walk endpoint
A fair walk starts at 0 and moves ±1 at each of t independent steps. Give P(position=k), including impossible endpoints.
Hints
- Solve for the number of right steps.
- Choose their positions among all t steps.
Answer
If |k|>t or t+k is odd, probability is zero. Otherwise exactly (t+k)/2 steps must be +1, giving C(t,(t+k)/2)/2^t. Parity is a reachability constraint, not a rounding issue.
Source and licence: Lehman, Leighton & Meyer — Mathematics for Computer Science (2018-06-06) · CC-BY-SA-3.0 · answer: Quantoros editorial