0

enter image description here

I think I managed to solve a;

Write P as

$$\begin{pmatrix} 0 & \frac{1}{2} & \frac{1}{2} & 0 & 0\\ \frac{1}{2} & 0 & \frac{1}{2} & 0 & 0\\ \frac{1}{4} & \frac{1}{4} & 0 & \frac{1}{4} & \frac{1}{4}\\ 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2}\\ 0 & 0 & \frac{1}{2} & \frac{1}{2} & 0 \end{pmatrix},$$

and then find the stat dist, $\pi_1=\pi_2=\pi_4=\pi_5=\frac{1}{6}, \pi_3=\frac{1}{3}.$ Using this and the knowledge that $\pi_1=\frac{1}{\text{E(return to A)}} \implies E=\frac{1}{\pi_1} \implies E=6$.

For b) and c) I was thinking I could make A absorbing, and use $M=(I-P_0)^{-1}$ but then you're supposed to sum the starting row which would be A and that row is not in the $P_0$ matrix. I have no idea what to do on d).

Any help will be greatly appreciated!

mrrobot
  • 41
  • Hint for (b) and (c). The mean number of visits to $M$ before returning to $A$ (call it $\nu_A(M)$) defines an invariant measure w.r.t. $P$. So $\nu_A$ must be a constant multiple of $\pi$. – nejimban Oct 26 '21 at 13:58
  • @nejimban How do I find the multiple of $\pi$? Is it supposed to be $x \cdot \pi_3$ and $y \cdot \pi_4$? Then how do I know what to multiply with? – mrrobot Oct 26 '21 at 16:34
  • The eigenvalue $1$ for the matrix $P$ is simple (by Perron-Frobenius, or your lecture notes). This means that any finite measure $\nu$ fulfilling $\nu P=\nu$ (i.e., an invariant measure) must be of the form $\nu = C\pi$ for some constant $C$. – nejimban Oct 26 '21 at 16:37
  • I'm sorry, but we've not talked about eigenvalues at all in the course --it's only an intro to Markov chains. And that's the formula I used to find the stationary distribution, $\pi_i=P\pi_i$. I am lost. – mrrobot Oct 26 '21 at 16:56
  • So you can perhaps take for granted that $$\frac{\nu_A(M)}{\nu_A(A)}=\frac{\pi(M)}{\pi(A)}$$ for any $M\in{A,B,C,D,E}$. What's $\nu_A(A)$? – nejimban Oct 26 '21 at 17:35
  • I'm a little confused by your notation, but for b), number of visits to C, the right hand side is $$\frac{\pi_3} {\pi_1}=2$$ right? I don't recognize v at all. Is v(A) the answer from a), 6? – mrrobot Oct 26 '21 at 22:01
  • $\nu_A$ is the expectation I defined in my first comment. – nejimban Oct 27 '21 at 07:09
  • Then $\nu_A(A)$ would be the mean number of visits to $A$ before returning to $A$ and that makes no sense? Can I find $\nu_A(A)$ through P or the stationary distribution? Please give me an extended explanation if you have the time. – mrrobot Oct 27 '21 at 07:47
  • $\nu_A(A)=1$, and $\nu_A(C)$ is what you are looking for. – nejimban Oct 27 '21 at 09:20
  • So $\nu_A(C)=2$ and $\nu_A(D)=1$? Is $\nu_A(A)$ always $1$? – mrrobot Oct 27 '21 at 09:27
  • See my answer. Normally you would use $\nu_A(M):=\mathbb E_A[N_M]=\frac{\pi_M}{\pi_A}$ directly from a theorem in the course, but since you haven't seen it… – nejimban Oct 27 '21 at 09:40

1 Answers1

1

Since apparently you have not seen invariant measures and the Perron-Frobenius theorem, here is a more elementary approach. We note $\mathbb P_M:=\mathbb P(\:\cdot\mid X_0=M)$ (that is under $\mathbb P_M$, the chain starts at $M$).

b. Let $N_C$ be the number of visits to $C$ before returning to $A$. Then from the dynamics of the Markov chain (reading the graph), $$\left\{\begin{aligned}\mathbb E_A[N_C]&=\frac12\Bigl(\mathbb E_B[N_C]+\mathbb E_C[N_C]\Bigr),\\[.4em] \mathbb E_B[N_C]&=\frac12\,\mathbb E_C[N_C],\\[.4em] \mathbb E_C[N_C]&=1+\frac14\Bigl(\mathbb E_B[N_C]+\mathbb E_D[N_C]+\mathbb E_E[N_C]\Bigr),\\[.4em] \mathbb E_D[N_C]&=\frac12\Bigl(\mathbb E_C[N_C]+\mathbb E_E[N_C]\Bigr),\\[.4em] \mathbb E_E[N_C]&=\frac12\Bigl(\mathbb E_C[N_C]+\mathbb E_D[N_C]\Bigr).\end{aligned}\right. $$ This solves to $$\mathbb E_A[N_C]=2,\quad\mathbb E_B[N_C]=\frac43,\quad\mathbb E_C[N_C]=\mathbb E_D[N_C]=\mathbb E_E[N_C]=\frac83.$$ So the answer is $\mathbb E_A[N_C]=2$. (Note that this equals $\frac{\pi_C}{\pi_A}$.)

c. Similarly, let $N_D$ be the number of visits to $D$ before returning to $A$. Then (again, reading the graph), $$\left\{\begin{aligned}\mathbb E_A[N_D]&=\frac12\Bigl(\mathbb E_B[N_D]+\mathbb E_C[N_D]\Bigr),\\[.4em] \mathbb E_B[N_D]&=\frac12\,\mathbb E_C[N_D],\\[.4em] \mathbb E_C[N_D]&=\frac14\Bigl(\mathbb E_B[N_D]+\mathbb E_D[N_D]+\mathbb E_E[N_D]\Bigr),\\[.4em] \mathbb E_D[N_D]&=1+\frac12\Bigl(\mathbb E_C[N_D]+\mathbb E_E[N_D]\Bigr),\\[.4em] \mathbb E_E[N_D]&=\frac12\Bigl(\mathbb E_C[N_D]+\mathbb E_D[N_D]\Bigr).\end{aligned}\right. $$ This solves to $$\mathbb E_A[N_D]=1,\quad\mathbb E_B[N_D]=\frac23,\quad\mathbb E_C[N_D]=\frac43,\quad\mathbb E_D[N_D]=\frac83,\quad\mathbb E_E[N_D]=2.$$ So the answer is $\mathbb E_A[N_D]=1$. (Note that this equals $\frac{\pi_D}{\pi_A}$.)

nejimban
  • 3,663