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

• Can you show us how you solved the 2 first questions? It will be easier for us to see what you didn't understand in the 3rd – wece Oct 7 '16 at 14:52
• For the first I have $\frac{1}{3}\frac{1}{3}\frac{1}{4} + \frac{1}{3}\frac{1}{4}\frac{1}{3} + \frac{1}{3}\frac{1}{4}\frac{1}{3} + \frac{1}{3}\frac{1}{3}\frac{1}{4}$ and for the second $\frac{1}{3}\tfrac{1}{3}\tfrac{1}{3}\frac{1}{3} + \frac{1}{3}\tfrac{1}{3}\frac{1}{3}\frac{1}{3} + \frac{1}{3}\frac{1}{3}\frac{1}{3}\frac{1}{4} + \frac{1}{3}\frac{1}{4}\frac{1}{3}\frac{1}{3} + \frac{1}{3}\tfrac{1}{3}\frac{1}{3}\frac{1}{4} + \frac{1}{3}\frac{1}{4}\frac{1}{3}\frac{1}{3} + \frac{1}{3}\frac{1}{3}\frac{1}{4}\frac{1}{3} + \frac{1}{3}\frac{1}{3}\frac{1}{4}\frac{1}{3}$. – user148692 Oct 7 '16 at 14:55
• In general, one can compute the probability of a Markov process hitting $A$ before hitting $B$ by solving the system $(Lq)(x)=0$ for $x \not \in A \cup B$, $q(x)=1$ for $x \in A$, $q(x)=0$ for $x \in B$, where $L$ is the generator of the process. In discrete time+discrete space, $L=P-I$ where $P$ is the transition matrix. (This requires a minor modification if you wish to speak of returning to $A$ before hitting $B$.) In discrete time+discrete space, this follows directly from the total probability formula, but it is true in all four combinations of discrete/continuous time and space. – Ian Oct 7 '16 at 15:23
• Your calculation for question 2 is missing a lot of paths with four transitions that start and end at state 1. Here is a complete list: {[1, 2, 3, 2, 1], [1, 2, 3, 4, 1], [1, 2, 5, 2, 1], [1, 2, 5, 3, 1], [1, 2, 5, 4, 1], [1, 3, 2, 3, 1], [1, 3, 2, 4, 1], [1, 3, 4, 2, 1], [1, 3, 4, 3, 1], [1, 3, 5, 2, 1], [1, 3, 5, 3, 1], [1, 3, 5, 4, 1], [1, 4, 3, 2, 1], [1, 4, 3, 4, 1], [1, 4, 5, 2, 1], [1, 4, 5, 3, 1], [1, 4, 5, 4, 1]} – user940 Oct 7 '16 at 15:50
• @user144697 A better way is to calculate the fourth power of the matrix $P$ and look at the entry at $(i,j)=(1,1)$. – user940 Oct 7 '16 at 16:06

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

• Great! I also have $16/3, 64/15$ and $67/15$ as solutions to the linear system I wrote in a comment. But this was only trivial thinking and easy calculus. Is there a way to calculate $P$(the random walk returns to $V1$ before it reaches $V5$) with your method? – user148692 Oct 7 '16 at 15:55
• You could compute the generating functions of $\tau_{11}$ and $\tau_{15}$, and from there the probability $\mathbb P(\tau_{11}<\tau_{15})$. Or you can observe by symmetry that it is $\frac12$. – Math1000 Oct 7 '16 at 16:22

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).

• Should not it be $P_{v_1}^k=1/3P_{v_2}^{k-1}+1/4P_{v_3}^{k-1}+1/3P_{v_4}^{k-1}$? – user148692 Oct 7 '16 at 15:43
• And I also think that $P_{v_2} = \frac{1}{3} + \frac{1}{3} P_{v_3}$, I am confused. – user148692 Oct 7 '16 at 15:49