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 am working on a Linear Algebra problem. I am given the structure of a win/lose game that is as follows

In each turn, we are at one of the positions 1,2,3, or 4, or we have either won or lost. If we are at position $W$ or $L$, we stay there, because we have won or lost the game. If we’re at any of the positions 1 through 4, then during that turn we leave (with equal probability) along one of the lines coming out of that position.

The Game Diagram

In other words, if we’re at position 1, then there’s a 1/4 chance that we’ll end up at L the next turn, a 1/4 chance of ending up at 2, a 1/4 chance of ending up at 3, and a 1/4 chance of ending up at 4. On the other hand, if we’re at position 3, then there’s a 1/2 chance of ending up at position 1 and a 1/2 chance of ending up at position 4 on the next turn.

I am then instructed to find the $6 \times 6$ transition matrix that tells us how to get from turn of the game to another. I am to use the order of positions $1,2,3,4,W,L.$

So, I know that for a transition matrix, each entry $P_{ij}$ is the probability of moving from position $j$ to position $i$. Using this I get the following transition matrix,

$$ \begin{bmatrix} 0 & 1/4 & 1/2 & 1/4 & 0 & 0 \\ 1/4 & 0 & 0 & 1/4 & 0 & 0 \\ 1/4 & 0 & 0 & 1/4 & 0 &0 \\ 1/4 & 1/4 & 1/2 & 0 & 0 & 0\\ 0 & 1/4 & 0 & 1/4 & 1 & 0\\ 1/4 & 1/4 & 0 & 0 & 0 & 1 \end{bmatrix}. $$

Now, for example, the entry in row one, column 2, gives the probability of moving from 2 to 1, which is $1/4$. For the next parts of the question:

(b) For each of the squares 1,2,3, and 4, work out the probability of winning if you start on that square.

(c) Which starting square has the best chance of winning?

So, do I need to find $A^k$, where $A$ is the transition matrix, for $k \to \infty$? Then plug in different values for the input matrix?

share|improve this question

2 Answers 2

up vote 0 down vote accepted

EDIT: For $j=1,2,3,4$, let $x_j$ be the probability of winning if you start on square $j$. Then you get the equations, $$\eqalign{x_1&=(1/4)(x_2+x_3+x_4)\cr x_2&=(1/4)(1+x_1+x_4)\cr x_3&=(1/2)(x_1+x_4)\cr x_4&=(1/4)(1+x_1+x_2+x_3)\cr}$$ Now solve.

share|improve this answer
    
Won't the steady state vector simply give me the proportion of wins and loses? That is, tell me what the chance of winning and losing is given any starting position? Though the chances of winning must be different depending on what the starting position is. –  clarence_atwater Feb 25 '13 at 12:36
    
You're right. I didn't read the question carefully. I have replaced my previous answer with one that I think is better. –  Gerry Myerson Feb 25 '13 at 22:31

One thing I learnt about transition matrices is that every element in a row should add up to $1$. In your case, the 5th & 6th rows do not add up to $1$. You mentioned in your question that if you are in the state of "WIN" or "LOSE", there is no chance to move to other states.

Secondly, since you said there is an equal chance to transit from 1 state to the other in the positions of 1 - 4, the elements in the other rows should be equal. The resultant is

$$ \begin{bmatrix} 0 & \frac 14 & \frac14 & \frac 14 & 0 & \frac14 \\ \frac 14 & 0 & 0 & \frac 14 & \frac14 & \frac14 \\ \frac 12 & 0 & 0 & \frac 12 & 0 &0 \\ \frac 14 & \frac 14 & \frac14 & 0 & \frac 14 & 0\\ 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix} $$

share|improve this answer
    
Thank you for your answer. I had believed that each column should add up to 1? The transition matrix I found also matched the answer given (they include the eigenvectors, for us to check our answer). –  clarence_atwater Feb 25 '13 at 10:47
    
These are common errors. You might want to edit this matrix before moving to tackling your answer. –  bryansis2010 Feb 25 '13 at 10:49
    
In my textbook (Linear Algebra - A Modern Introduction, by David Poole) the transition matrices have their columns summing to 1. Further, we are instructed to think of the columns being labeled with the present states, and the rows as the "next" states. Is this a matter of convention? –  clarence_atwater Feb 25 '13 at 10:56
    
My experience is that mathematicians generally have the columns add up to one, and write $Av$ with matrix on the left, column vector on the right; economists generally have the rows add up to one, and write $vA$ with row vector on the left, matrix on the right. So, yes, it's a matter of convention. –  Gerry Myerson Feb 25 '13 at 12:08
    
I would say you can simply transpose this matrix to make the columns add up to 1...this was just what my university taught me... –  bryansis2010 Feb 25 '13 at 13:23

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.