4
$\begingroup$

Consider a random walk on the following graph:

enter image description here

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – wece Oct 7 '16 at 14:52
  • $\begingroup$ 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}$. $\endgroup$ – user148692 Oct 7 '16 at 14:55
  • 1
    $\begingroup$ 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. $\endgroup$ – Ian Oct 7 '16 at 15:23
  • 1
    $\begingroup$ 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]} $\endgroup$ – user940 Oct 7 '16 at 15:50
  • 1
    $\begingroup$ @user144697 A better way is to calculate the fourth power of the matrix $P$ and look at the entry at $(i,j)=(1,1)$. $\endgroup$ – user940 Oct 7 '16 at 16:06
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – user148692 Oct 7 '16 at 15:55
  • $\begingroup$ 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$. $\endgroup$ – Math1000 Oct 7 '16 at 16:22
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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}$? $\endgroup$ – user148692 Oct 7 '16 at 15:43
  • $\begingroup$ And I also think that $P_{v_2} = \frac{1}{3} + \frac{1}{3} P_{v_3}$, I am confused. $\endgroup$ – user148692 Oct 7 '16 at 15:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.