# Simple Random Walk: Unrestricted Random Walk

A simple random walk on a line or in one dimension occurs with probability $p$ when walker step forward (+1) and/or has probability q=1-p if walker steps back (-1). For ith step, the modified Bernoulli random variable Wi (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 X0=k, but here we assume (without loss of generality) that walks starts from the origin so that Xo=0.

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 Xn=Xn-1 ±1

and the transition probabilities from one position to another is
P(Xn=j|Xn-1=j-1)=p, and P(Xn=j|Xn-1=j+1)=q are independent of the number of plays in the game or steps in the represented by n.

Mean and Variance of Xn can be calculate 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 Wi are independent and identically distributed (iid) random variables and where W is the common or typical Bernoulli random variable in the sequence {Wi}. 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 mean E(Xn)=n(p-q) and variance V(Xn)=4npq.

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

If p>½ then a drift is expected away from the origin in a positive direction and if p<½ it would be expected that the drift would be in the negative direction.

Since V(Xn) 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 walk at the 100th step between 15 and 25 pace/step 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 Φ(Z) is the standard normal distribution function.

### Download pdf file: Unrestricted Random Walks 101.09 KB Unrestricted Random Walks

Updated: Aug 7, 2014 — 11:31 pm

#### The Author

1. Gambler’s ruin”: Suppose that two gamblers are given $10 and on each throw of a dice, one gambler must win$1 and the other must loose \$1. How long can they play in average until the capital of the loser is exhausted