Skip to content
Quantoros

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

Related questions