Stochastic Processes

Random Walk Probability of Returning to Origin

Assume that the walk starts at $x=0$ with steps to the right or left occurring with probabilities $p$ and $q=1-p$. We can write the position $X_n$ after $n$ steps as
\[X_n=R_n-L_n \tag{1}\]
where $R_n$ is the number of right or positive steps (+1) and $L_n$ is the number of left or negative steps ($-1$).

Therefore the Total steps can be calculated as:  \[n=R_n+L_n \tag{2}\]
Hence
\begin{align*}
L_n&=n-R_n\\
\Rightarrow X_n&=R_n-n+R_n\\
R_n&=\frac{1}{2}(n+X_n) \tag{3}
\end{align*}
The equation (3) will be an integer only when $n$ and $X_n$ are both even or both odd (eg. To go from $x=0$ to $x=7$ we must take an odd number of steps).

Now, let $v_{n,x}$ be the probability that the walk is at state $x$ after $n$ steps assuming that $x$ is a positive integer. Then
\begin{align*}
v_{n,x}&=P(X_n=x)\\
&=P(R_n=\frac{1}{2}(n+x))
\end{align*}
$R_n$ is a binomial random variable with index $n$ having probability $p$, since the walker either moves to the right or not at every step, and the steps are independent, then
\begin{align*}
v_{n,x}&=\binom{n}{\frac{1}{2}(n+x)}p^{\frac{1}{2}(n+x)}q^{n-\frac{1}{2}(n+x)}\\
&=\binom{n}{\frac{1}{2}(n+x)}p^{\frac{1}{2}(n+x)}q^{\frac{1}{2}(n-x)} \tag{4}
\end{align*}
where $(n,x)$ are both even or both odd and $-n \leq x \leq n$. Note that a similar argument can be constructed if $x$ is a negative integer.

Example

For a total number of steps is 2, the net displacement must be one of the three possibilities: (1) two steps to the left, (2) back to the start, (3) or two steps to the right. These correspond to values of $x = -2, 0,+2$. It is impossible to get more than two units away from the origin if you take only two steps and it is equally impossible to end up exactly one unit from the origin if you take two steps.

For a symmetric case ($p=\tfrac{1}{2}$), starting from the origin, there are $2^n$ different paths of length $n$ since there is a choice of right or left move at each step. Since the number of steps in the right direction must be $\tfrac{1}{2}(n+x)$ and the total number of paths must be the number of ways in which $\frac{1}{2}(n+x)$ can be chosen from $n$: that is
\[N_{n,x}=\binom{n}{\tfrac{1}{2}(n+x)}\]
provided that $\tfrac{1}{2}(n+x)$ is an integer.

By counting rule, the probability that the walk ends at $x$ after $n$ steps is given by the ratio of this number and the total number of paths (since all paths are equally likely). Hence
\[v_{n,x}=\frac{N_{n,x}}{2^n}=\binom{n}{\tfrac{1}{2}(n+x)}\frac{1}{2^n}\]
The probability $v_{n,x}$ is the probability that the walk ends at state $x$ after $n$ steps: the walk could have overshot x before returning there.

Related Probability/ First Passage through x

A related probability is the probability that the first visit to position x occurs at the $n$th step. The following is a descriptive derivation of the associated probability-generating function of the symmetric random walk in which the walk starts at the origin, and we consider the probability that it returns to the origin.

From equation (4), the probability that a walk is at the origin at step $n$ is
\begin{align*}
v_{n,x}&=\binom{n}{\frac{1}{2}(n+x)}p^{\frac{1}{2}(n+x)}q^{n-\frac{1}{2}(n+x)}\\
&=\binom{n}{\tfrac{1}{2}(n+0)} \left(\frac{1}{2}\right)^{\tfrac{1}{2}n} \left(\frac{1}{2}\right)^{\tfrac{1}{2}n}\\
&=\binom{n}{\tfrac{1}{2}n}\frac{1}{2^n}=p_n \,\,\,\text{(say)}, \quad (n=2,4,6,\cdots) \tag{5}
\end{align*}
Here $p_n$ is the probability that after $n$ steps the position of the walker is at the origin. We also assume that $p_n=0$ if $n$ is odd. From equation (5) we can construct a generating function.
\begin{align*}
H(s)&=\sum_{n=0}^\infty p_n s^n\\
&=\sum_{n=0}^\infty p_{2n}s^{2n}=\sum_{n=0}^\infty \frac{1}{2^{2n}}\binom{2n}{n}s^{2n} \tag{6}
\end{align*}
Note that $p_0=1$, and H(s) is not a probability generating function since $H(1)\neq1$.

The binomial coefficient can be re-arranged as follows:
\begin{align*}
\binom{2n}{n}&=\frac{(2n)!}{n!n!}=\frac{2n(2n-1)(2n-2)\cdots3.2.1}{n!n!}\\
&=\frac{2^nn!(2n-1)(2n-3)\cdots3.2.1}{n!n!}\\
&=\frac{2^{2n}}{n!}\frac{1}{2}\frac{3}{2}\cdots(n-\tfrac{1}{2})\\
&=(-1)^n \binom{-\tfrac{1}{2}}{n}2^{2n} \tag{7}
\end{align*}
Using equation (6) in (7)
\[H(s)=\sum_{n=0}^\infty \frac{1}{2^{2n}}(-1)^n \binom{-\tfrac{1}{2}}{n}s^{2n}2^{2n}=(1-s^2)^{-\tfrac{1}{2}} \tag{8}\]
by binomial theorem, provided $|s|<1$. Note that this expansion guarantees that $p_n=0$ if $n$ is odd.

Note that the equation (8) does not sum to one. This is called defective distribution which still gives the probability that the walk is at the origin at step n.

We can estimate the behavior of $p_n$ for large n by using Stirling’s Formula (asymptotic estimate for $n!$ for large $n$), $n!\approx\sqrt{2\pi} n^{n+\tfrac{1}{2}}e^{-n}$

From equation (5)
\begin{align*}
p_{2n}&=\frac{1}{2^{2n}}\binom{2n}{n}=\frac{1}{2^{2n}}\frac{(2n)!}{n!n!}\\
&\approx\frac{1}{2^{2n}}\frac{\sqrt{2\pi}(2n)^{2n+\tfrac{1}{2}}e^{-2n}}{[\sqrt{2\pi}(n^{n+\tfrac{1}{2}}e^{-n})]^2}\\
&=\frac{1}{\sqrt{\pi n}}; \qquad \text{for large $n$}
\end{align*}
Hence $np_n\rightarrow \infty$ confirming that the series $\sum\limits_{n=0}^\infty p_n$ must diverge.

Random Walk Probability of Returning to Origin after $n$ Steps Some EXAMPLES

Example: Consider a random walk starting from $x_0=0$ and find the probability that after 5 steps the position is 3. i.e. $X_5=3$, $p=0.6$.

Solution: Here the number of steps is $n=5$ and the position is $x=3$. Therefore positive and negative steps are

$R_n= \frac{1}{2}(n+x)=\frac{1}{2}(5+3)=4$ and $X_n=R_n-L_n \Rightarrow 3=4+L_n=1$

The probability that the event $X_5=3$ will occur in a random walk with $p=0.6$ is
\[P(X_5=3)=\binom{5}{\frac{1}{2}(5+3)}(0.6)^{\tfrac{1}{2}(3+5)}(0.4)^{\tfrac{1}{2}(5-3)}=0.2592\]

Click the links to learn Stochastic Processes Introduction, Random Walk Models, Simple Random Walk

Matrices in R Language

A simple random walk (or unrestricted random walk) on a line or in one dimension occurs with probability $p$ when the walker steps forward (+1) and/or has probability $q=1-p$ if the walker steps back ($-1$). For ith step, the modified Bernoulli random variable $W_i$ (takes the value $+1$ or $-1$ instead of {0,1}) is observed and the position of the walk at the nth step can be found by
\begin{align}
X_n&=X_0+W_1+W_2+\cdots+W_n\nonumber\\
&=X_0+\sum_{i=1}^nW_i\nonumber\\
&=X_{n-1}+W_n
\end{align}
In the gambler’s ruin problems $X_o=k$, but here we assume (without loss of generality) that walks start from the origin so that $X_0=0$.

Simple Random Walk

Several derived results for random walks are restricted by boundaries. We consider here random walks without boundaries called unrestricted random walks. We are interested in

1. The position of the walk after a number of steps and
2. The probability of a return to the origin, the start of the walker.

From equation (1) the position of the walker at step $n$ simply depends on the position at $(n-1)$th step, because the simple random walk possesses the Markov property (the current state of the walk depends on its immediate previous state, not on the history of the walks up to the present state)

Furthermore, $X_n=X_{n-1}\pm 1$ and the transition probabilities from one position to another is $P(X_n=j | X_{n-1}=j-1)=p$, and $P(X_n=j|X_{n-1}=j+1)=q$ is independent of the number of plays in the game or steps is represented by $n$.

The mean and Variance of $X_n$ can be calculated as:
\begin{align*}
E(X_n)&=E\left(X_0+\sum_{i=1}^n W_i\right)\\
&=E\left(\sum_{i=1}^n W_i\right)=nW_n\\
V(X_n)&=V\left(\sum_{i=1}^n W_i\right)=nV(W)
\end{align*}
Since $W_i$ are independent and identically distributed (iid) random variables and where $W$ is the common or typical Bernoulli random variable in the sequence$\{W_i\}$. Thus
\begin{align*}
E(W)&=1.p+(-1)q=p-q\\
V(W)&=E(W^2)-[E(W)]^2\\
&=1^2p+(-1)^2q-(p-q)^2\\
&=p+q-(p^2+q^2-2pq)\\
&=1-p^2-q^2+2pq\\
&=1-p^2-(1-p)^2+2pq\\
&=1-p^2-(1+p^2-2p)+2pq\\
&=1-p^2-1-p^2+2p+2pq\\
&=-2p^2+2p+2pq\\
&=2p(1-p)+2pq=4pq
\end{align*}
So the probability distribution of the position of the random walk at stage $n$ has to mean $E(X_n)=n(p-q)$ and $V(X_n)=4npq$ and variance.

For the symmetric random walk (where $p=½$) after $n$ steps, the expected position is the origin, and it yields the maximum value of $V(X_n)=4npq=4np(1-p)$.

If $p>\frac{1}{2}$ then drift is expected away from the origin in a positive direction and if $p<\frac{1}{2}$ it would be expected that the drift would be in the negative direction.

Since $V(X_n)$ is proportional to $n$, it grows with increasing n, and we would be increasingly uncertain about the position of the walker as $n$ increases.
i.e.
\begin{align*}
\frac{\partial V(X_n)}{\partial p}&=\frac{\partial}{\partial p} {4npq}\\
&=\frac{\partial}{\partial p} \{4np-4np^2 \}=4n-8np \quad \Rightarrow p=\frac{1}{2}
\end{align*}
Just knowing the mean and standard deviation of a random variable does not enable us to identify its probability distribution. But for large $n$, we can apply the CLT.
\[Z_n=\frac{X_n-n(p-q)}{\sqrt{4npq}}\thickapprox N(0,1)\]
Applying continuity correction, approximate probabilities may be obtained for the position of the walk.

Example : Consider unrestricted random walk with $n=100, p=0.6$ then
\begin{align*}
E(X_n)&=E(X_{100})=nE(W)=n(p-q)\\
&=100(0.6-0.4)=20\\
V(X_n)&=4npq=4\times 100\times 0.6 \times 0.4=96
\end{align*}
The position of the walk at the 100th step between 15 and 25 pace/steps from the origin is
\[P(15\leq X_{100}\leq30)\thickapprox P(14.5<X_{100}<25.5)\]
\[-\frac{5.5}{\sqrt{96}}<Z_{100}=\frac{X_{100}-20}{\sqrt{96}}<\frac{5.5}{96}\]
hence
\[P(-0.5613<Z_{100}<0.5613)=\phi(0.5613)-\phi(-0.5613)=0.43\]
where $\phi(Z)$ is the standard normal distribution function.

Read more about Simple Random Walk: Random Walks Model

FAQs about Simple Random Walk

1. What is meant by a simple random walk?
2. How mean and variance of a simple random walk can be computed?
3. Give an example of a simple random walk.

References

1. https://www.encyclopediaofmath.org/index.php/Random_walk
2. https://mathworld.wolfram.com/RandomWalk1-Dimensional.html