# Random Walk Expected Number of Visits

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!

-

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.
First, you are absolutely right about the minus signs. I somehow convinced myself that $$0 - \frac{1}{3} = \frac{1}{3}.$$ And to be clear, that (C, B)th entry of the matrix M accounts for the fact that our destination is vertex A, right? And that would be because we designated A as an absorbing state? – jrad Aug 18 '12 at 1:41
@JackRadcliffe Yes, in creating $Q$ and hence $M$ you have removed the destination state $A$. In general, of course, there can be more than one destination state. – Byron Schmuland Aug 18 '12 at 1:44
"Destination states" are defined as the set of states that complete the sentence "... before hitting..." If your question ends "... before hitting A", then the only destination state is A. If your question ends "... before hitting E", then the only destination state is E. If your question ends "... before hitting A or E", then the destination states form the set {A,E}. Each of these 3 problems has a different $Q$-matrix. – Byron Schmuland Aug 18 '12 at 1:57