Will two wandering friends ever stand together?

Question

Two friends walk along the same infinite street (the integer number line). Each second, both of them independently step one block left or right with probability $\tfrac12$ . Alice starts at block $0$ ; Bob starts at block $d$ (an integer distance away).

For which starting distances $d$ are they certain to eventually stand on the same corner at the same moment?

Accepted Answer

Track the gap Dt = (	ext{Bob's position}) - (	ext{Alice's position}). They share a corner exactly when Dt = 0. Each second, Alice moves \pm 1 and Bob moves \pm 1 independently, so the gap changes by: - +2 (Bob right, Alice left) with probability 	frac14, - -2 (Bob left, Alice right) with probability 	frac14, - 0 (both same direction) with probability 	frac12. Two things follow. First, the gap only ever changes by even amounts, so its parity (odd/even) never changes. - If d is odd, the gap stays odd forever and can never equal 0. The friends pass through each other on adjacent corners but…

Will two wandering friends ever stand together?

Your answer

More Probability questions