Problem Of the Week: 28th June 2024
A drunk performs a random walk along a street. At one end of the street is a river, and at the other end is a police station. If he gets to either of these ends, he remains there. He starts n steps from the river, and there are N total steps between the river and the police station. What is the prob
Legacy articles aren't reviewed and may be incorrectly formatted.
Problem Of the week: 28th June 2024
Michael Wu
A drunk performs a random walk along a street. At one end of the street is a river, and at the other end is a police station. If he gets to either of these ends, he remains there. He starts n steps from the river, and there are N total steps between the river and the police station.
What is the probability that he ends up at the river? At the police station?
Imagine a large number of copies of the given setup proceeding simultaneously. After each drunk takes his first step in all of the copies, the average position of all of them remains the same (namely, n steps from the river), because each one had a 50-50 chance of moving either way. Likewise, the average position remains unchanged after each successive step. This is true because the drunks who are still moving won’t change the average position (because of their random motion), and the drunks who have stopped at an end of the street certainly won’t change the average position (because they aren’t moving). Therefore, the average position is always n steps from the river.
Let the drunks keep moving until all of them have stopped at either end. Let Pr(n) and Pp(n) be the probabilities of ending up at the river and police station, respectively, having started n steps from the river. Then after all the drunks have stopped, their average distance from the river is 0·Pr(n)+N·Pp(n). But this must equal n. Hence, Pp(n) = n/N, and so Pr(N) = 1 − (n/N).
