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.

enter image description hereA man is forced at time $0$ into a five-room maze shown as the diagram. At the end of each unit of time, it changes to a different room by choosing an exit at random. Let $X_n$ be the room number entered at time $n$. Suppose the man initial are in the room number $2$, what is the expected number of points in time (including time 0) it is in room number $2$?

share|improve this question
    
Is the probability of picking each room uniformly distributed (over all rooms that have available exits)? –  Christopher A. Wong Nov 20 '12 at 9:39
    
@ChristopherA.Wong ya as he randomly choose an exist –  Mathematics Nov 21 '12 at 2:40

1 Answer 1

up vote 1 down vote accepted

You can set it up as only three states: room 1, room 2, and other. Because once he goes out of both rooms 1,2 he cannot return. The times he is in room 2 can be $0,2,4,...$ [any even number.]

He starts out in room 2 which counts for 1. Then to get there again at time 2 the probability is $(1/2)(1/3)=1/6$. This keeps occurring so that the total expected time in room 2 is $$1 + (1/6) + (1/6)^2 + (1/6)^3 + ... = 6/5.$$

EDIT: I now think this approach is wrong for getting the expected value. As an absorbing markov chain, using states 1,2,3 where 1 is room 1, 2 is room 2, and 3 is "other", we have that 3 is the absorbing state. The transition matrix (rows and columns labelled 1,2,3 in that order) is a 3 by 3 matrix, first row $[0,1/3,2/3]$, second row $[1/2,0,1/2]$, and third row $[0,0,1]$. (The first two zeros in the third row correspond to the fact that from state 3 he cannot reenter either room 1 or room 2.)

Now the matrix $Q$ for the transitory states 1,2 is $[[0,1/3],[1/2,0]]$, i.e. the upper left 2 by 2 submatrix of the transition matrix. According to markov absorbing approach, one next finds the inverse $N=(I-Q)^{-1}$. I got this $N$ to be $[[6/5,2/5][3/5,6/5]].$

In general when $N$ is right multiplied by a column matrix of all 1's, it gives the expected times until absorption starting in the various states. In this case the result of this is the column vector $[8/5,9/5]^T$ (where T means transpose), and the 9/5 goes with state 2, so that (if my calculations above are right) the correct answer for the expected number of visits to room 2 (including the start in room 2) is 9/5, and not the 6/5 I obtained above using the too simple approach.

So it should be 9/5.

share|improve this answer
    
$1\over 6$ is the probability isn't it? Why you relate it to expected time –  Mathematics Nov 21 '12 at 2:39
    
He starts in room 2 so that's +1 for that to total count. Then the probability that he goes to room 2 at time 2 is 1/6 so we add +1*(1/6) to his total expected value. Then he gets to room 2 at time 4 with probability (1/6)*(1/6) so we add +1*(1/6)*(1/6) to his total expected value, and so on. That's how the number 1/6 comes in to the expected value. In general expected value is sum of (probability)*(value). –  coffeemath Nov 21 '12 at 9:13
    
Mathematics: I think my first answer may be wrong! See the part I added under "EDIT". –  coffeemath Nov 21 '12 at 10:11

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.