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$).
Table of Contents
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
- The position of the walk after a number of steps and
- 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 $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.
Symmetric Random Walk
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 the drift is expected away from the origin in a positive direction, and if $p<\frac{1}{2}$, it is expected that the drift will 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. That is,
\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.
Unrestricted Random Walk Example
Consider an 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 paces/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.
Real-Life Examples of Simple Random Walk
A simple random walk is a mathematical model where an object moves in discrete steps with equal probability in different directions. Some of the real-world applications of random walks are:
- Stock Market Prices: Daily stock price movements can be modeled as a random walk because future price changes are unpredictable and follow a random pattern.
- Brownian Motion: Pollen grains suspended in water move erratically due to collisions with water molecules. Similarly, a dust particle zigzags unpredictably in the air due to random molecule impacts.
- Gambling (Casino Games): A gambler’s net profit over time can be modeled as a random walk.
- Animal Foraging (Biology): Animals like albatrosses or ants search for food in a random direction. A lost ant moves left or right randomly until it finds a food trail.
- Computer Algorithms: Some Artificial Intelligence (AI) and optimization algorithms use random walks to explore solutions.
Read more about Simple Random Walk: Random-Walks-Model
FAQs about Random Walk
- What is meant by a simple random walk?
- How mean and variance of a simple random walk be computed?
- Give an example of a simple random walk.
