A problem introduced to me by Professor Peter Yum. Consider random walk on integers. The simplest one is on
and we start on 0 at step 0. The random walk proceed y flipping a coin at each step to decide to go left or right.
We can also define the counterpart on a higher dimensional lattice , which we decide on each step one of the possible direction to go. We always start with the position 0 in such lattice and concern whether we will return to 0 (aka equalization) in some future step. Formally, the random walk is defined as
where is the position of the random walk at step and . is the direction taken at each step where is the -dimensional standard basis vector, i.e. only the -th element of the vector is 1 and all other elements are 0.
If at each step, all direction can be taken at equal probability, i.e.
the random walk is called symmetric.
Polya studied this and some of the following are developed:
We define to be the probability that the random walker returned to 0 at step . For any lattice, only makes sense as no random walk can return to 0 in odd number of steps. We define as the random walk starts at 0.
We further define to be the probability that the random walk returns to 0 for the first time. And we define for notational convenience (and at step 0 is not really a return). With this, we can define the probability that a random walk will ever return to 0 as
Considering the definition of and , we have the following relations are established:
where represents the probability that the random walker returned to 0 for the first time after steps and then returned to 0 again in more steps. And if we define the generator functions
then we have:
The above we substituted the coefficients of each with , according to the relations enumerated above. And from this we have:
The equation above, is the probability that equalization occurs and is the expected number of visits to 0. Rearranging, we also have:
- Always for any ,
- If , then and
- If , then and
or the probability of returning to 0 is one iff .
Case of specific dimensions
We now apply the above result to a particular dimension. For , a symmetric random walk can have possible routes in steps. But there are only routes will have equal number of left and right moves, i.e., return to 0 at step . Therefore,
The approximation above is using Stirling’s formula, . And so,
The last equality can be found by considering:
Asymmetric random walk
The case of asymmetric random walk on : If we assume the probability of going right at each step is and that of going left is , then we have , which the above derivation becomes:
which will converge iff . In other words, there is a probability greater than zero that the random walk will never return to 0.
If , at each step we may go in one of the four directions. Therefore, there are possible routes in steps and for equalization, the number of steps going up and down must equal as well as left and right must equal, which enumerated to be
Considering the multinomial expression, we have:
and the probability
Using similar argument,
The last inequality is due to if and sum to 1 (due to it is a distribution). Using Stirling’s formula here, together with the result of ,
This makes the sum
The probability of equalization is the Pólya’s Random Walk Constants and in 3D, it is found to be 0.3405373296
On higher dimension, Polya’s result is that the probability of equalization is always less than one. Consider that the random walk is on dimension and represent the position with a vector. If we restrict the -th element to be always 0, that becomes a random walk on dimension. Denote to be the probability of equalization on a -dimensional random walk. And also we define to be the event that a random walk on dimension is at a position that the vector has first elements 0. Obviously so does their probability. Hence by induction, we proved
This is already established for and .
- Chapter 4 of “Probability. Theory and examples”, 4th edition, by Durrett, Cambridge, 2010
- Chapter 12 of “Introduction to probability”, 2nd edition, by Grinstead and Snell, AMS, 1997
- C. N. Moore, Random Walks, 2007
- Derek Johnston, “An Introduction to Random Walks”, 2011
- Proving that 1- and 2-d simple symmetric random walks return to the origin with probability 1