Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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? –  radcliffejh 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
    
So if it were the case that both A and E were destination states, the answer to the question: Suppose a walker starts in vertex C. What is the expected number of visits to B before the walker reaches A? would come from the same matrix as the question: Suppose a walker starts in vertex C. What is the expected number of visits to B before the walker reaches E? –  radcliffejh Aug 18 '12 at 1:50
    
"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
    
Ah okay, that makes sense. Thanks for your help! –  radcliffejh Aug 18 '12 at 1:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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