Random Walk on graph with five vertices

Question

Consider a random walk on the following graph:

The random walk starts from the vertex $V_1$ and moves to one neighbouring vertex (each is reached with the same probability) in the next step. For example $P(V_2 \to V_5) = 1/3$ and $P(V_3 \to V_4)=1/4$.

I want to calculate the following probabilities:

• $P$(the random walk returns to $V_1$ after exactly $3$ steps)

• $P$(the random walk returns to $V_1$ after exactly $4$ steps)

• $P$(the random walk returns to $V_1$ before it reaches $V_5$)

• What is the average number of steps until the random walk reaches $V_5$?

The first two questions are straight forward, I got $1/9$ and $13/162$. For the last question I had do solve a linear system and got $16/3$ as solution.

I would appreciate it if anybody could tell me if my calculations are right and can help me with the third question.

Answer 1

Let $P_{v_i}^k$ denote the probability to reach $v_1$ in k steps from $v_i$.

Obviously $P_{v_1}^0=1$ and $P_{v_i}^0=0$ if $i\neq 1$. Also $P_{v_1}^k=1/3P_{v_2}^{k-1}+1/3P_{v_3}^{k-1}+1/3P_{v_4}^{k-1}$ and so on you can write the other equation.

Using this you can compute $P_{v_1}^3$ and $P_{v_1}^4$ which will answer your 2 first question. (This is what you did I believe).

Now lets denote $P_{v_i}$ denote the probability that the random walk returns to $v_1$ before it reaches $v_5$ from $v_i$.

Using the same idea as above you can write equations. For example $$P_{v_2}=1/3+P_{v_3}$$ since there is probability 1/3 to reach $v_1$, 1/3 to reach $v_3$, and the last third is not coined since it reaches $v_5$.

$P_{v_1}$ will give you the answer.

And finally for the last answer you gave the right equation system (I didn't check your computation, but the equation is right).

Answer 2

Let $X_n$ be the vertex visited at time $n$, then $\{X_n:n=0,1,\ldots\}$ is a Markov chain with transition matrix $$P=\begin{pmatrix} 0&\frac13&\frac13&\frac13&0\\ \frac13&0&\frac13&0&\frac13\\ \frac14&\frac14&0&\frac14&\frac14\\ \frac13&0&\frac13&0&\frac13\\ 0&\frac13&\frac13&\frac13&0 \end{pmatrix}. $$

For any pair of states $i,j$ and positive integer $n$, we have $$\mathbb P(X_n=j\mid X_0=i) = P^n_{ij}. $$

For each pair of states $i,j$, define $$\tau_{ij} = \inf\{n>0: X_n=j\mid X_0=i\}. $$ By symmetry it is clear that $$\mathbb P(\tau_{11}<\tau_{15}) = \mathbb P(\tau_{11}>\tau_{15}) = \frac12. $$

The Markov chain is irreducible and aperiodic on a finite state chain, and so has a unique limiting distribution $\pi$, that is, $$\pi_i = \lim_{n\to\infty}\mathbb P(X_n=i). $$ By symmetry, again, it is clear that $\pi_1=\pi_2=\pi_4=\pi_5$, and that $\pi_3=\frac43\pi_1$. Since $\sum_{i=1}^5 \pi_i = 1$, we find that $$\pi = \left(\frac3{16},\frac3{16},\frac14,\frac3{16},\frac3{16} \right). $$

To compute $\mathbb E[\tau_{15}]$ we have the system of equations \begin{align} \mathbb E[\tau_{15}] &= 1 + \frac13\mathbb E[\tau_{25}] + \frac13\mathbb E[\tau_{35}] + \frac13\mathbb E[\tau_{45}]\\ \mathbb E[\tau_{25}] &= 1 + \frac13\mathbb E[\tau_{15}] + \frac13\mathbb E[\tau_{35}]\\ \mathbb E[\tau_{35}] &= 1 + \frac14\mathbb E[\tau_{15}] + \frac14\mathbb E[\tau_{25}] + \frac14\mathbb E[\tau_{45}]\\ \mathbb E[\tau_{45}] &= 1 + \frac13\mathbb E[\tau_{15}] + \frac13\mathbb E[\tau_{35}]\\ \end{align} with unique solution $$ \mathbb E[\tau_{15}] = \frac{16}3,\quad \mathbb E[\tau_{25}] = \frac{64}{15},\quad \mathbb E[\tau_{35}] = \frac{67}{15},\quad \mathbb E[\tau_{45}] = \frac{64}{15}. $$