First Returns of the Symmetric Random Walk when p=q

As we know that a related probability is the one for the event in which the first visit to position x occurs at the nth step given that the walk starts at the origin, i.e. the first passage through x. For case x=0 we will find the probability of the first return to the origin. Let A be the event that $X_n=0$, let $B_k$ be the event that the first visit to the origin occurs at the kth step. By the law of total probability
\[P(A)=\sum_{k=1}^n P(A|B_k)P(B_k) \tag{1}\label{eqn2.341}\]
Let $f_k=P(B_k)$. The conditional probability $P(A|B_k)$ is the probability that the walk returns to the origin after n–k steps i.e. $P(A|B_k)=p_{n-k}$. Note that $p_n$ is the probability that the walk is at the origin at step n and $p_n=0$ if n is odd. Hence (\ref{eqn2.341}) can be written as
\[p_n=\sum_{k=1}^n p_{n-k}f_k \tag{2}\label{eqn2.342}\]
Multiplying both sides of (\ref{eqn2.342}) by $s^n$ and summing for $n\geq1$, we have
\[\sum_{n=1}^\infty p_ns^n =\sum_{n=1}^\infty \sum_{k=1}^n p_{n-k}f_k s^n \tag{3}\label{eqn2.343}\]
as
\[H(s)=\sum_{n=0}^\infty p_ns^n=1+\sum_{n=1}^\infty p_ns^n\]
\[H(s)-1=\sum_{n=1}^\infty p_ns^n\qquad \]
Therefore from (\ref{eqn2.343})
\begin{align*}
H(s)-1&=\sum_{n=1}^\infty p_n s^n\\
&=\sum_{n=1}^\infty \sum_{k=1}^n p_{n-k}f_ks^n\tag{4}\label{eqn2.344}
\end{align*}
Since $p_0=1$ and $f_0=0$, we can replace (\ref{eqn2.344}) by
\begin{align*}
H(s)-1&=\sum_{n=1}^\infty p_ns^n\\
&=\sum_{n=0}^\infty \sum_{k=0}^n p_{n-k}f_ks^n = \sum_{n=0}^\infty p_ns^n \sum_{k=0}^\infty f_k s^k \tag{5}\label{eqn2.345}
\end{align*}
the product of two power series, also known as Convolution of the distribution.

Now if $Q(s)=\sum_{n=0}^\infty f_ns^n$ is the probability generating function of the first return distribution, then
$H(s)-1=H(s)Q(s)$.

From equation (8) of lecture “Probability Distribution after n steps” we have
\begin{align*}
Q(s)&=\frac{H(s)-1}{H(s)}=1-\frac{1}{H(s)}\\
&=1-\frac{1}{(1-s^2)^{-\frac{1}{2}}}\qquad \because H(s)=(1-s^2)^{-\frac{1}{2}}\\
&=1-(1-s^2)^{\frac{1}{2}} \tag{6}\label{eqn2.346}
\end{align*}
The probability that the walk will, at some step, return to the origin is $\sum_{n=1}^\infty f_n=Q(1)=1$;
i.e. the return is certain. In this walk the origin or any point by translation is persistent. However, the mean number of steps until this return occurs is
\begin{align*}
\sum_{n=1}^\infty nf_n &=\lim_{s \rightarrow 1-} Q'(s)\\
&=\lim_{s \rightarrow 1-} \frac{s}{(1-s^2)^{\frac{1}{2}}}=\infty
\end{align*}
In this walk which starts at the origin is certain to return there in the future, but on average, it will take an infinite number of steps.

Example:  Find the probability that a symmetric random walk starting from the origin returns there for the first time after 6 steps.

solution:  We require the coefficient of $s^6$ in the power series expansion of the pgf Q(s), which is
\begin{align*}
Q(s)&=1-(1-s^2)^{\frac{1}{2}}\\
&=1-\left[\frac{1^{\frac{1}{2}}}{0!}-\frac{\frac{1}{2}{(-s^2)}^1}{1!}-\frac{\frac{1}{2}(\frac{1}{2}-1){(-s^2)}^2}{2!}-\frac{\frac{1}{2}(\frac{1}{2}-1)(\frac{1}{2}-2){(-s^2)}^3}{3!}\right]\\
&=1-1+\frac{1}{2}s^2+\frac{1}{8}s^4+\frac{1}{16}s^6+0s^8
\end{align*}
Hence the probability of a first return at step 6 in symmetric random walk example is $\frac{1}{16}$.

Read about Simple Random Walk: Unrestricted Random Walks

Muhammad Imdad Ullah

Currently working as Assistant Professor of Statistics in Ghazi University, Dera Ghazi Khan. Completed my Ph.D. in Statistics from the Department of Statistics, Bahauddin Zakariya University, Multan, Pakistan. l like Applied Statistics, Mathematics, and Statistical Computing. Statistical and Mathematical software used is SAS, STATA, GRETL, EVIEWS, R, SPSS, VBA in MS-Excel. Like to use type-setting LaTeX for composing Articles, thesis, etc.

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.