Random Walks (2009)

Random Walks A drunk man will find his way home, but a drunk bird may get lost forever. Conceptually a random walk is exactly what it sounds like. Our drunkard starts at a "Home" vertex, 0, and then choses at random a neighboring vertex to walk to next. We let X(n) denote the walkers position at time n. The drunkard returns home when X(n) = X(0). Frequently we can accurately calculate the probability that the walker returns home in n steps, and we denote this probability of return as q(n). For our purposes we will show that q(2n) is approximately n-r for some positive r. If r > 1 the sum is finite and so the walker is transient; otherwise it is infinite and the walker is recurrent. At each step the walker will move either up, down, left or right, each with probability 1/4. For a taste of what the walker's path might look below are sample walks of 50, 500, 5000 and 50000 steps. Activity 4 Check that X(n) has the same transition probabilities as the walk determined by+Z(n /2. This means that we have decomposed our walk on Z2 into two copies of the walk on Z that we already understand.