## 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 *n*th 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 *k*th 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