Drunkard's walk in a 2-dimensional box Apr 9 18:00:55 PDT 2002 A drunkard is confined to a walled hexagonal patio two miles in diameter, thus one mile on each side. Each corner is marked with a white or black flag, alternating around the boundary. The patio is paved with hexagonal flagstones. Each flagstone is marked with three arrows, colored red, blue, and green. All the arrows of a given color are parallel. The arrows on the center stone point to the white corners. At each black corner, one arrow points toward the the white corner two miles away on the opposite side, and the other two point toward the adjacent walls. At each white corner, one arrow points into the corner, and the other two are parallel to the adjacent walls, that is, point toward the neighboring black corners one mile away. The drunkard's walk is in phases, where in each phase he walks for a while in one direction. At the beginning of each phase, he picks a color at random, each with probability 1/3, and follows the arrows of that color throughout that phase. Also at the beginning of each phase, the drunkard picks a positive number d, using an exponential distribution with mean 1; i.e., for any given t >= 0, the probability that he chooses d > t is e^{-t}. The drunkard then attempts to walk d miles in the chosen direction. When he has walked that distance he stops, ending the phase. If the drunkard encounters a wall during a phase, he doesn't notice, but just keeps marching in place for the appropriate number of steps, then stops, ending the phase. Problems. 1. Let pi^i be the distribution of the drunkard after i phases. Prove that, as i goes to infinity, pi^i converges to a unique stationary distribution pi that does not depend on the initial distribution pi^0. 2. For any given flagstone, how often, in the long run, does the drunkard step on that stone? The answer must be in the form of a positive constant times a power of epsilon, where epsilon is the diameter of one flagstone. Since we are interested in the limiting behavior as epsilon goes to zero, only the highest order term counts. If the stone is at a corner, the answer will be a positive constant. If the stone is along a wall but not in a corner the answer will be a positive constant times epsilon. If the stone is in the interior of the patio, the answer will be a positive constant times either epsilon or epsilon^2. 3. As a specific instance of the above question, prove that the drunkard will be at a black corner 2e^{4/3} times as often as at a white corner. 4. In the long run, what proportion of the time is the drunkard is trying to walk into a wall? 5. Derive a simple formula for the randomized competitiveness of the UMTS problem for k = 3, as a function of the answer to problem 4 above. 6. Generalize the drunkard's walk in a box so that it applies to the UMTS problem for arbitrary k.