# 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}.$$

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?

## References

##### Isaque Pimentel
###### Quantitative Analyst, Consultant

Ph.D. in Applied Mathematics interested in Quantitative Finance and Data Science.