ExpertAlmost
07-13-2009, 11:30 PM
A Different Drunkard’s Walk
In short: Imagine a drunk waking up in the middle of a thin rope bridge. He can only go in one of two directions. Given his average step size and his number of steps: what is the farthest the drunk may travel to one side? We want to be 80%, 90%, 95% and 99% sure of that maximum distance.
In detail: Given a mean step size, each of the drunk’s step sizes are normally distributed. Big or small steps in one of two directions. Usually the drunkard’s walk is in any direction (Brownian Motion). There, the expectation of the distance is 0 and the average travel distance for any direction is the square root of the number of steps. That does not apply here.
This walk has only two directions and asks what is the maximum range in one direction (always a positive value) with an 80%, 90%, 95% and 99% confidence interval? With the understanding that on the next drunk night, that maximum distance might be in the other direction.
I have a number of very large spreadsheets simulating thousands of steps, summing them (1-30 steps), finding ranges of 80%, 90%...etc… of the sums and then curve fitting a formula to the results (if anyone would like to see one, ). But I would like to find a calculated result if there is one.
Thank you for all your insights and expertise !
In short: Imagine a drunk waking up in the middle of a thin rope bridge. He can only go in one of two directions. Given his average step size and his number of steps: what is the farthest the drunk may travel to one side? We want to be 80%, 90%, 95% and 99% sure of that maximum distance.
In detail: Given a mean step size, each of the drunk’s step sizes are normally distributed. Big or small steps in one of two directions. Usually the drunkard’s walk is in any direction (Brownian Motion). There, the expectation of the distance is 0 and the average travel distance for any direction is the square root of the number of steps. That does not apply here.
This walk has only two directions and asks what is the maximum range in one direction (always a positive value) with an 80%, 90%, 95% and 99% confidence interval? With the understanding that on the next drunk night, that maximum distance might be in the other direction.
I have a number of very large spreadsheets simulating thousands of steps, summing them (1-30 steps), finding ranges of 80%, 90%...etc… of the sums and then curve fitting a formula to the results (if anyone would like to see one, ). But I would like to find a calculated result if there is one.
Thank you for all your insights and expertise !