I have always been fascinated by the idea of random walk. Recently, jiraya_ and I observed some new ideas in this domain. Thus, I wanted to share the same with you and get your insights regarding the same.

Assumptions

1. The initial position of the person is assumed to be $$$X$$$ (positive integer) on the number line
2. The walk is not absolutely random, i.e., the probability of person moving from position $$$Y$$$ to position $$$Y+1$$$ is $$$p$$$, and the probability of person moving from position $$$Y$$$ to position $$$Y-1$$$ is $$$q$$$. Obviously, $$$p + q = 1$$$.
3. There is a pit at position 0, therefore a person who reaches the position 0 does not move further.

Pre-requisites

The proof regarding the pre-requisites used in this blog can be found here.

I have used the following results for this blog:

1. The probability of person to reach position $$$Y=0$$$ from position $$$Y=1$$$ after infinite number of moves is 1 if $$$p<=q$$$, and $$$q / p$$$ if $$$p>q$$$.
2. The expected number of moves for a person to reach position $$$Y=0$$$ from position $$$Y=1$$$ is $$$1/(q-p)$$$ if $$$p <= q$$$.

In this blog, we only consider the scenario for various cases after very large (or maybe infinite) number of moves.

Case 1: $$$p=q$$$

The expected position, $$$E[X]$$$, is X and the expected change in position in a move, $$$E[\Delta X]$$$, is 0.

In each move we will disintegrate the person at position $$$Y$$$ into two halves, each having a probability weight as half the value of the probability weight of the original person. A person at position $$$Y$$$ will then represent half a person at position $$$Y+1$$$, and half a person at position $$$Y-1$$$. Therefore, the expected position of person after each move will be $$$\sum_{i=0}^\infty W_i * i$$$. Initially, $$$W_i=1$$$ for $$$i=X$$$ and 0 otherwise.

Now, let's assume a person is at position $$$Y > 0$$$. Therefore, his current contribution to the expected position is $$$W_Y*Y$$$. After a move, his contribution will change to $$$W_Y/2*(Y+1) + W_Y/2*(Y-1) = W_Y*Y$$$. Therefore, his contribution to the expected position does not change if $$$Y>1$$$. If $$$Y=0$$$, the current contribution of the person to the expected position is 0. After a move, the person does not change his current position, and his contribution does not change as well.

Since, the contribution to the expected value does not change for a person at any position, the expected position remains the same after any number of moves.

Special Note : Even though a person at any position $$$X$$$ attains the position $$$X=0$$$ in a random walk if $$$p=q$$$ with probability 1, the expected position of the person always remains $$$X$$$.

Case 2: $$$p<q$$$

The expected position, $$$E[X]$$$, is 0 and the expected change in position in a move, $$$E[\Delta X]$$$, is 0.

For $$$X = 1$$$, the expected number of moves to reach $$$X=0$$$ is $$$1/(q-p)$$$, and for a value of $$$X$$$ greater than 1, the expected number of moves to reach to position $$$X=0$$$ is $$$X/(q-p)$$$ (using independence or the linearity of expectation).

Let's assume a person is at position $$$Y > 0$$$. After a move, his position will change to $$$p*(Y+1)+q*(Y-1)$$$ that is equal to $$$Y+(p-q)$$$. The decrease in expected position of the person is $$$q-p$$$. So we conclude that whenever a person is at a position $$$Y > 0$$$ on the number line, he will change his expected position by $$$-(q-p)$$$ in one move. We already know the expected number of moves to reach position 0 from position $$$X$$$ is $$$X/(q-p)$$$, Therefore, total decrease in value is $$$(X/(q-p))*(-(q-p))=-X$$$. Therefore, the position of the person after infinite number of moves is 0.

Case 3: $$$p>q$$$

The expected position, $$$E[X]$$$, will tend to infinity and the expected change in position in a move, $$$E[\Delta X]$$$, will tend to $$$(1-(q/p)^X)*(p-q)$$$.

We will use the concept of disintegration again. Let's assume a person is at position $$$Y > 0$$$. Therefore, his current contribution to the expected position is $$$W_Y*Y$$$. After a move, his contribution will change to $$$W_Y*p*(Y+1)+W_Y*q*(Y-1)$$$ that is equal to $$$W_Y*Y+W_Y*(p-q)$$$. Therefore, the increase in expected value for a person at position $$$Y>0$$$ is $$$W_Y*(p-q)$$$.

If $$$Y=0$$$, the current contribution of the person to the expected position is 0. After a move, the person does not change his current position, and his contribution does not change as well. Therefore, if a disintegrated portion of the person reaches the position $$$Y=0$$$, it will no longer contribute to the increase in expected value.

From the pre-requisites, we know the probability that a person at position $$$X=1$$$ will ever reach the position $$$X=0$$$ is $$$q/p$$$. Using independence and Markov Chains, we know the probability that a person at a position $$$X>=1$$$ will ever reach $$$X=0$$$ is $$$(q/p)^X$$$. From this, we conclude that the portion of the person that always stay on the number line with position $$$Y>0$$$, irrespective of the number of moves, is $$$(1-(q/p)^X)$$$. Therefore, the expected increment in value will tend to $$$(1-(q/p)^X)*(p-q)$$$ as the number of moves tend to infinity. Since the minimum increment in expected position after each move is a finite value, the expected position will tend to infinity as the number of moves tend to infinity.

Hope you liked it! :)