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

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?

References

• Markov chain (Wikipedia)
• Polygon (Wikipedia)
• Matrix (Wikipedia)