# What is the probability of returning to the starting vertex after n steps?

Given a transition matrix on a triangle $\triangle ABC$, compute $\mathbb{P}_{X_0=A} [X_n=A] $.

**Quantitative Finance Interviews** are comprised of
*finance*, *programming* and *probability* questions, as well as,
some logic questions, known as *brainteasers*.
In this post series, I share some frequently asked questions from
**Quantitative Finance Interviews**
for quantitative analysts with
*junior*
level of experience.

Here, I present a question on probability. The purpose with this question is to assess your knowledge on the conditional probability (possibly on Markov chains).

## Interview Question

Here is the question about the probability of returning to the initial point after $n$ steps:

Let $\triangle ABC$ be a triangle with vertices $A$, $B$ and $C$. Suppose that you have a frog at any of its vertices, that jumps with probability $1/2$ towards the vertex on its left and with probability $1/2$ towards the vertex on its right. What is the probability of returning to the starting vertex after $n$ steps?

## Question Explanation

First, you need to understand the parameters of the problem. Let $X_k$ be the vertex where the frog is after $k$ jumps, where $X_k \in \{A,B,C\}$. In fact, for any vertex $x$ and any $k > 0$, the problem states that $$ \mathbb{P} [ X_k = L_x | X_{k-1}=x ] = 1/2, \quad \mathbb{P} [ X_k = R_x | X_{k-1}=x ] = 1/2, $$ where $L_x$ (resp. $R_x$) is the vertex on the left (resp. right) of vertex $x$. For example, for the vertex $B$, the vertex on the left $L_B$ is equal to $A$, and the vertex on the right $R_B$ is equal to $C$.

So, you need to use appropriately the previous property to obtain the transition matrix $\mathbf{Q}_{k}$ given by
$$
(\mathbf{Q}_{k})_{i,j}
:= \mathbb{P} [ X_k = i | X_{k-1}=j ],
$$
for any $(i, j) \in \{A,B,C\}^2$.

Note that, for a given column $j$, the probability of jumping towards itself is zero and the probability of jumping towards others vertices is equally probable (i.e., 1/2 for the triangle)
Therefore, we get the following homogenous transition matrix $\mathbf{Q}$:
$$
\mathbf{Q}:=
\mathbf{Q}_{k}\equiv
\begin{pmatrix}
0 & 1/2 & 1/2\\

1/2 & 0 & 1/2\\

1/2 & 1/2 & 0
\end{pmatrix}.
$$

## Answer I

Assume, without loss of generality, that the starting vertex is $A$. Now, for any vertex $x$, we define $$ \mathbb{P}_{X_0=A} [ X_n = x ] := \mathbb{P} [ X_n = x | X_0=A ]. $$ In the following, $\mathbb{P}_{X_0=A} [ X_n = x ]$ is also denoted by $p_n(x)$. Then, you need to compute $p_n(A)$.

By using the **law of total probability** backwards with respect to $n$,
we get:
\begin{align}
\mathbb{P}_{X_0=A} [ X_n = A ]
&= \mathbb{P}_{X_0=A} [ X_n = A | X_{n-1} = B]
\times \mathbb{P}_{X_0=A} [ X_{n-1} = B] \\
&+ \mathbb{P}_{X_0=A} [ X_n = A | X_{n-1} = C]
\times \mathbb{P}_{X_0=A} [ X_{n-1} = C],
\end{align}
which can be rewritten as:
\begin{align}
p_n(A) &=
\mathbb{P}_{X_0=A} [ X_n = A | X_{n-1} = B] \, p_{n-1}(B) \\

&+
\mathbb{P}_{X_0=A} [ X_n = A | X_{n-1} = C] \, p_{n-1}(C).
\end{align}

Using conditional probabilities in the transition matrix $\mathbf{Q}$, we simplify: $$ p_n(A) = 1/2 \times ( p_{n-1}(B) + p_{n-1}(C) ). $$

By reapplying the **law of total probability** once again, we have:
\begin{align}
p_{n-1}(B) &=
1/2 \times ( p_{n-2}(A) + p_{n-2}(C) ),\\

p_{n-1}(C) &=
1/2 \times ( p_{n-2}(B) + p_{n-2}(A) ).
\end{align}
Therefore, we get:
\begin{align}
p_n(A)
&=
(1/2)^{2} \times ( 2 p_{n-2}(A) + p_{n-2}(B) + p_{n-2}(C) ) \\

&= (1/2)^{2} \times ( 1 + p_{n-2}(A) )
\end{align}
where $p_{n-2}(A) + p_{n-2}(B) + p_{n-2}(C) = 1$.

### Remark

At this point, we could the limit of $p_n(A)$ if it exists, i.e., $p(A) = \lim_{n\to \infty} p_n(A)$.
By taking the limit in the previous equation, we get:
\begin{align}
p(A)
&= (1/2)^{2} \times ( 1 + p(A) ) \Rightarrow \\

p(A)

&= \frac{ (1/2)^{2} }{(1 - (1/2)^{2})} = 1/3.
\end{align}
At the infinity, the frog will return to the starting point 1/3 of the time.

### Recurrence

Now, you need to solve the recurrence
\begin{align}
p_0(A) &= 1,\\

p_1(A) &= 0,\\

p_n(A) &= 2^{-2} + 2^{-2} \, p_{n-2}(A)), \quad n > 1.
\end{align}
Multiplying the previous recurrence relation by $2^n$ leads to
$2^n \, p_n(A) = 2^{n-2} + 2^{n-2} \, p_{n-2}(A)$.
By denoting $b_n= 2^n \, p_n(A) $, we get
$$
b_n = 2^{n-2} + b_{n-2}, \quad n > 1.
$$

Note that the recurrence relation on $b_n$ preserves the parity of the indices, meaning that
\begin{align}
b_{n} &= 2^{n-2} + b_{n-2},\\

b_{n-2} &= 2^{n-4} + b_{n-4},\\

&…\\

b_{4} &= 2^{2} + b_{2},\\

b_{2} &= 2^{0} + b_{0},\\

\end{align}
when $n$ is even.
Therefore, $b_n = b_0 + 2^{n-2} + 2^{n-4} +\ldots + 2^{2} + 2^{0}$.
By taking $S_n := 2^{n-2} + 2^{n-4} +\ldots + 2^{2} + 2^{0}$, we multiply it by $2^2$:
$$
2^2 S_n = 2^{n} + 2^{n-2} +\ldots + 2^{4} + 2^{2}.
$$
Then, by subtracting $S_n$, we get:
$$
2^2 S_n - S_n = 2^{n} - 2^{0} \Rightarrow
S_n = \frac{2^{n} - 2^{0}}{2^2 - 1} = \frac{2^n - 1}{3},
$$
which leads $b_n = b_0 + (2^n-1) / 3 $.

Analogously, for $n$ odd, $b_n = b_1 + 2^{n-2} + 2^{n-4} +\ldots + 2^{3} + 2^{1}$. Then, $b_n = b_1 + (2^n-2) / 3 $.

Finally, from $p_n(A)=b_n/2^n$, we obtain
\begin{align}
p_n(A) =
\begin{cases}
\frac{1}{3} + \frac{2}{3} \, 2^{-n}, \quad n = 2k,\\

\frac{1}{3} - \frac{2}{3} \, 2^{-n}, \quad n = 2k+1,
\end{cases}
\end{align}
for some integer $k \ge 0$.

## Applications

Using the idea of the solution presented above, the interview question could be extended to:

Let $\triangle ABC$ be a triangle with vertices $A$, $B$ and $C$. Suppose that you have a frog at any of its vertices, that jumps with probability $p$ towards the vertex on its left and with probability $1-p$ towards the vertex on its right. What is the probability of returning to the starting vertex after $n$ steps?

By generalizing the triangle, the interview question could be

Let $P$ be a simple polygon with vertices $A_0$, $A_1$, …, $A_K$ for some integer $K > 3$. Suppose that you have a frog at any of its vertices, that jumps with probability $p$ towards the vertex on its left and with probability $1-p$ towards the vertex on its right. What is the probability of returning to the starting vertex after $n$ steps?