A Drunk Man Will Find His Way Home, But A Drunk Bird May Get Lost Forever

Our goal in this section is to prove the above statement. If your probability is rusty (or nonexistent) this review might be useful. We start by describing the behavior of our drunkards mathematically. 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). As our walkers are allowed to retrace their steps we always have that q(2n) > 0, so this probability can't be what Prof. Kakutani was referring to. Before we continue there is another important fact to mention. If the walker or bird is moving on a finite graph then there's no way to get lost forever; there are simply not enough places to go. For more information, visit http://pi.math.cornell.edu/~mec/Winter2009/Thompson/randomwalks.html