0
$\begingroup$

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$?

  • 0
    @ChristopherA.Wong ya as he randomly choose an exist2012-11-21

1 Answers 1

1

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.

  • 0
    Mathematics: I think my first answer may be wrong! See the part I added under "EDIT".2012-11-21