Can anyone help me with this? Consider the random walk on the finite simple graph, with the transition matrixm P and starting in a.
P= \begin{pmatrix} 0 & 1 & 0 & 0 \\ 1/3 & 0 & 1/3 &1/3 \\ 0 & 1/2 & 0 & 1/2 \\ 0 & 1/2 & 1/2 & 0 \end{pmatrix}
Find the expected number of steps to return to a. Find the probability that the walk hits c before d.
For the first question i was thinking to change the first row, as a wil be absorbed and then find the Q matrix. And for the second i would change the 3rd and 4rth row as they will be absorbed.
If $\ e_a, e_b, e_c\ $, and $\ e_d\ $ are the expected number of steps taken to return to $\ a\ $ from each of the states $\ a,b,c\ $ and $\ d\ $, respectively, then $\ e_a, e_b, e_c, e_d\ $, satisfy the linear equations $$ \pmatrix{e_a\\e_b\\e_c\\e_d}=P\pmatrix{1\\1+e_b\\1+e_c\\1+e_d}=\pmatrix{1\\1\\1\\1}+P \pmatrix{0\\e_b\\e_c\\e_d}\ , $$ which can be solved by Gaussian elimination.
From the transition matrix it's easy to see that the first step on which the chain enters state $\ c\ $ or $\ d\ $ must be even, after it has oscillated back and forth between states $\ a\ $ and $\ b $. The probability that it oscillates from $\ a\ $ to $\ b\ $ and back again $\ n\ $ times without entering states $\ c\ $ or $\ d\ $ is $\ \frac{1}{3^n}\ $ $(\ n=0,1,2\dots\ )$. Thus, the probability that it enters $\ c\ $ on the $\ (2n+2)^\text{th}\ $ step without ever having entered state $\ d\ $ is $\ \frac{1}{3^{n+1}}\ $, and the probability that it vists state $\ c\ $ before state $\ d\ $ is therefore $$ \sum_{n=1}^\infty \frac{1}{3^{n+1}}=\frac{1}{3\left(1-\frac{2}{3}\right)}=\frac{1}{2}\ . $$ This could also be deduced from the symmetry of states $\ c\ $ and $\ d\ $ relative to $\ a\ $ and $\ b\ $ (i.e. swapping the third and fourth columns and the third and fourth rows of the transition matrix leaves it unchanged).