Random Walk on graph with five vertices 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.
 A: 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}.
$$
A: 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).
