Bill Cordwell (oops, I called him "Bill Cardwell" in my previous message; sorry, Bill!) wrote:
I'm looking for a simple derivation of the probability that a random walk starting at 0, with unit steps, will ever end up to the left of 0. Probability that the person goes to the left (towards the negative) at any step is p.
I'll mention that for p = 1/3 (and for other nice values of p, but let's stick with p = 1/3) there's a cute way to "derive" the answer to Bill's question with a gadget that derandomizes random walk (although one needs to support this derivation with a proof showing that the derandomized procedure always gives the correct answer). The states of the gadget are infinite strings of 0's, 1's, and 2's. Image a bug that does a walk on such a string. It goes to the left when it sees a 2 and it goes to the right when it sees a 0 or a 1, and after a bug leaves a location, the number in that location increments by 1 mod 3. So if the initial string is 2 2 2 2 2 ... ^ with the bug at the left (as marked by the "^"), then the bug will fall off to the left at the next step, giving 0 2 2 2 2 ... ^ Now add a second bug at the leftmost location: 0 2 2 2 2 ... ^ It moves to the right (and the leftmost symbol increments): 1 2 2 2 2 ... ^ Then the bug moves to the left: 1 0 2 2 2 ... ^ Then the bug moves to the right: 2 0 2 2 2 ... ^ At this stage, we recognize that we're in the same situation as we were when we added the second bug (shifted over one position), so we can see what the second bug will do from now on: right-left-right, right-left-right, right-left-right, etc. After the second bug has wandered off to infinity, the state of the system looks like 2 2 2 2 2 ... again. So if we add a third bug at the far left, it'll do what the first bug did, and a fourth bug will do what the second bug did, etc. Since half of the non-randomly walking bugs fall off to the left, we conclude that the probability of a randomly walking bug falling off to the left is 1/2. (As I said above, this conclusion needs to be supported by a proof, but the proof isn't hard.) If you start with a different initial string of 0's, 1's, and 2's, the result is almost the same: the second bug might not do the opposite of what the first bug did, but the third bug will do the opposite of what the second bug did, and the fourth bug will do the opposite of what the third bug did, etc. So it's still true that the proportion of the bugs that fall off to the left goes to 1/2, and the error in our derandomized estimate of the probability L falls like O(1/n). In contrast, a truly random simulation would give estimates of the probability L with error like O(1/sqrt(n)). For more about bugs walking on an infinite string of 0's, 1's, and 2's, see pages 81 and 91-93 of Peter Winkler's book "Mathematical Puzzles: A Connoissuer's Collection" (though the statement of the problem given in the book deliberately hides some of the structure by replacing the three numbers by three colors). To learn about a related but harder problem that also illustrates the link between random walk and "derandomized walk with rotor- routers", see Michael Kleber's very nice article "Goldbug Variations": http://people.brandeis.edu/~kleber/Papers/rotor.pdf For more on the rotor-router approach to derandomization (which I'm developing jointly with Ander Holroyd and Lionel Levine), see http://faculty.uml.edu/jpropp/quasirandom.html If you're in the Boston area, you can attend a talk by Levine this coming Friday, described at http://www-math.mit.edu/~combin/ Jim Propp