wilmott.com

Hi all, I have been reading this forum for a while and I always found intriguing questions/answers here. I have a random walk problem for you guys now, hopefully no similar problem has been asked before.A drunk man is standing at the center of a bridge, every step he has 1/2 probability going left, and 1/2 going right. It is known that in the next 1 hour, the drunk man will arrive either left end, or right end of the bridge at least once. So the problem is: we want to find out as early as possible that which end of the bridge the drunk man is going to arrive. In other words, find out a probability function with variables of time and distance from the center of the bridge.Hopefully I made my question understandable.Thanks,

Sounds like a PDE or MC problem, first exit time, with appropriate boundary conditions?The drunk man cannot jump off the bridge? http://homepages.ulb.ac.be/~ppatie/fpt_md.pdf QuoteIt is known that in the next 1 hour, the drunk man will arrive either left endHow do we know this? If the bridge is very long or the man is very drunk? We need to prove that ther is a (unique?) solution.

A few issues need clarification:1. The condition "every step he has 1/2 probability going left, and 1/2 going right" is incompatible with the condition "known that in the next 1 hour, the drunk man will arrive ...". Unless the bridge is exactly 2 steps wide (so that the first step takes the drunk to one end or the other), there's always a non-zero probability that a true random walk will never reach either end within any fixed time limit.2. The problem does not specify length of bridge or the stepping rate. These have a tremendous effect on the answer. For example, if the bridge is 7202 steps long and the drunk takes only 1 step per second, then the drunk can never reach either side in 1 hour. Both parameters affect the answer in a non-linear way so there's general solution (e.g., a function of only % distance along the bridge) or a one-dimension parameterization (e.g. expressing the drunk's velocity in bridge-lengths per hour).3. The problem isn't well-formed because it seems to allude to multiple arrivals ("at least once") which implies the drunk could visit both ends of the bridge. Are you asking for the first arrival time or probability of ever arriving at the ends? And what is the statistical process at the bridge end?

QuoteOriginally posted by: Traden4AlphaA few issues need clarification:1. The condition "every step he has 1/2 probability going left, and 1/2 going right" is incompatible with the condition "known that in the next 1 hour, the drunk man will arrive ...". Unless the bridge is exactly 2 steps wide (so that the first step takes the drunk to one end or the other), there's always a non-zero probability that a true random walk will never reach either end within any fixed time limit.2. The problem does not specify length of bridge or the stepping rate. These have a tremendous effect on the answer. For example, if the bridge is 7202 steps long and the drunk takes only 1 step per second, then the drunk can never reach either side in 1 hour. Both parameters affect the answer in a non-linear way so there's general solution (e.g., a function of only % distance along the bridge) or a one-dimension parameterization (e.g. expressing the drunk's velocity in bridge-lengths per hour).3. The problem isn't well-formed because it seems to allude to multiple arrivals ("at least once") which implies the drunk could visit both ends of the bridge. Are you asking for the first arrival time or probability of ever arriving at the ends? And what is the statistical process at the bridge end?In the continuous case, PDE/probability theory would arrive at a similar conclusion. Is there a similar foundation in the discrete case?

QuoteOriginally posted by: CuchulainnQuoteOriginally posted by: Traden4AlphaA few issues need clarification:1. The condition "every step he has 1/2 probability going left, and 1/2 going right" is incompatible with the condition "known that in the next 1 hour, the drunk man will arrive ...". Unless the bridge is exactly 2 steps wide (so that the first step takes the drunk to one end or the other), there's always a non-zero probability that a true random walk will never reach either end within any fixed time limit.2. The problem does not specify length of bridge or the stepping rate. These have a tremendous effect on the answer. For example, if the bridge is 7202 steps long and the drunk takes only 1 step per second, then the drunk can never reach either side in 1 hour. Both parameters affect the answer in a non-linear way so there's general solution (e.g., a function of only % distance along the bridge) or a one-dimension parameterization (e.g. expressing the drunk's velocity in bridge-lengths per hour).3. The problem isn't well-formed because it seems to allude to multiple arrivals ("at least once") which implies the drunk could visit both ends of the bridge. Are you asking for the first arrival time or probability of ever arriving at the ends? And what is the statistical process at the bridge end?In the continuous case, PDE/probability theory would arrive at a similar conclusion. Is there a similar foundation in the discrete case?In the discrete case, the easiest proof that some drunks never reach either end of the bridge is the "left,right,left, right, ...." or "right,left,right,left, ...." center-oscillation case which can happen with p = 2/(2^n). Although this one case grows vanishingly small and one might think one can ignore it, the combinatorics of other potential paths that wander around the middle of any non-trivial-sized bridge is large. To a first approximation based on the linear growth of variance of the drunk's location, steps/hour must be many times the value of (bridge_length_in_steps)^2 before we can ignore the case of the drunk that stays in the middle of the bridge during the entire hour.

Can it be modelled as a heat equation with boundaries given by the length of the bridge L and initial conditions being two Dirac delta functions located at -L/2 and +L/2? This should be solvable analytically... but not at 3am I would have to assume that time is measured in velocity units. If I couldn't do this, it would be a random walk with stochastic volatility?

This sounds like a gamblers ruin problem. The answer is he has a 50/50 chance of getting to either side. In gamblers ruin when the probability of losing is equal to the probability of winning (in this case prob of going left or right) the probability of winning is just the distance from the winning position divided by the total distance. Since the man is in the center of the bridge it is equally likely he gets to the left or right side first. Read up on the gamblers ruin as well as stopping times.

If you can make the extra assumptions (Cuch and T4A discuss it above) to solve OKCWBY's problem as the gambler's ruin problem, it indeed gets much simpler.