I'm having a bit of trouble with a question involving a random walk with five vertices. The graph is shown below.
The problem I can't figure out reads:
Suppose a walker starts in vertex C. What is the expected number of visits to B before the walker reaches A?
I've done a bit of work on this problem already, but I can't seem to put it all together. First, I made my transition matrix
$$P = \begin{bmatrix} 0&\frac{1}{3}&\frac{1}{3}&\frac{1}{3}&0 \\\\ \frac{1}{3}&0&\frac{1}{3}&0&\frac{1}{3} \\\\ \frac{1}{2}&\frac{1}{2}&0&0&0 \\\\ \frac{1}{2}&0&0&0&\frac{1}{2} \\\\ 0&\frac{1}{2}&0&\frac{1}{2}&0 \end{bmatrix}$$
where the columns and rows go in the order A, B, C, D, then E. My textbook describes a method to find the expected number of steps from i to j that involves designating the destination state as an absorbing state and redefining the matrix as such, in this case resulting in this matrix:
$$P = \begin{bmatrix} 1&0&0&0&0 \\\\ \frac{1}{3}&0&\frac{1}{3}&0&\frac{1}{3} \\\\ \frac{1}{2}&\frac{1}{2}&0&0&0 \\\\ \frac{1}{2}&0&0&0&\frac{1}{2} \\\\ 0&\frac{1}{2}&0&\frac{1}{2}&0 \end{bmatrix}$$
Next, it says to extract a matrix Q that includes the rows and columns of only the transient states. Here, Q would be
$$Q = \begin{bmatrix} 0&\frac{1}{3}&0&\frac{1}{3} \\\\ \frac{1}{2}&0&0&0 \\\\ 0&0&0&\frac{1}{2} \\\\ \frac{1}{2}&0&\frac{1}{2}&0 \end{bmatrix}$$
where the columns and rows go in the order B, C, D, then E. We're trying to attain a matrix M, where
$$M = (I – Q)^{-1}$$
I calculated M to be
$$M = \begin{bmatrix} \frac{18}{11}&\frac{-6}{11}&\frac{4}{11}&\frac{-8}{11} \\\\ \frac{-9}{11}&\frac{14}{11}&\frac{-2}{11}&\frac{4}{11} \\\\ \frac{6}{11}&\frac{-2}{11}&\frac{16}{11}&\frac{-10}{11} \\\\ \frac{-12}{11}&\frac{4}{11}&\frac{-10}{11}&\frac{20}{11} \end{bmatrix}$$
As I understand it, I can ignore the negatives in this matrix and just make those entries positive. Now here is where I get stumped. I can easily find the expected number of steps to get from C to A, but the inclusion of vertex B in the question really throws me off. I calculated the invariant probability vector to be
$$\pi = (\frac{1}{4}, \frac{1}{4}, \frac{1}{6}, \frac{1}{6}, \frac{1}{6})$$
but I'm not sure that has anything to do with this problem. Any chance you all could help me out? This isn't homework; the semester hasn't begun yet and I'm just trying to get a bit of a head start. Thanks!
Best Answer
First of all, the minus signs don't actually appear in $M$. You must have miscalculated somewhere.
The answer to your question is the $(C,B)$th entry of the matrix $M$. The expected number of visits to $B$ before hitting state $A$, starting at $C$, is 9/11.