0

Two players A and B toss two fair coins independently. Whoever gets the smaller number of heads will pay that many dollars to the other player.

For example, if player A tosses two coins and gets 2 heads, but player B tosses two coins and gets only one head, then player B will give one dollar to A.

Also, if player A tosses the two coins and gets no heads, while player B tosses and gets 2 heads, in that case player A will give 2 dollars to player B.

If both players have the same amount of heads in a certain round, no money change hands.

In addition, if the one who losses the round does not have enough money to pay, then that player will give whatever he has left.

The game ends when one player gets all the money.

Write the transition matrix for the Markov chain for amount of money held by player A if both players start with $5.00 each.

user218698
  • 33
  • Any thoughts or first attempts? There are a few things which make this problem simpler. For one, if you know how much money one person has.. you know how much either has. Further, if you know player A has X dollars, what are the possible outcomes in the next turn, and what is the likehood of each outcome? – jameselmore Feb 23 '15 at 21:23
  • I am not sure how to find the probability for each player. – user218698 Feb 23 '15 at 21:23
  • For example, Player A has $5.00. Now he can gain $2.00 if he tosses two heads and at the same time player B tosses no heads. That makes P=0.5^4 – user218698 Feb 23 '15 at 21:24
  • Then so does Player B. $$_A = $10 - $_B$ – jameselmore Feb 23 '15 at 21:24
  • Then player A can gain $1.00 if there is one of the 4 situations: (A gets HH and B gets HT) or (A gets HH and B gets TH) or (A gets HT and B gets TT) or (A gets TH and B gets TT) – user218698 Feb 23 '15 at 21:26
  • Yeah, I would say only think of this in terms of player A. Just noting the fact that A is bounded by $$$0 and $$$10 – jameselmore Feb 23 '15 at 21:27
  • I believe I don't understand the transition matrix at all. How I look at it is that the matrix is what A gets after first round. Then if I need another round I need to square that matrix. But I know I am wrong as I cannot get player A to get $10 after one round. – user218698 Feb 23 '15 at 21:29
  • The transition matrix is fixed for all moves. Let me ask you the following and then I can format an answer. What happens when one person gets $10? Has the game terminated? – jameselmore Feb 23 '15 at 21:30
  • Yes, the game ends after one player wins with $10. – user218698 Feb 23 '15 at 21:31
  • These rules are ambiguous. Do they take turns per coin? Or per round? When do they decide how many coins to throw? Is that decided before the game starts, before the round, or before turn? Please give a more precise description of the game. – DanielV Feb 23 '15 at 22:15
  • there are only two coins for each player. Player A tosses two coinns and also player B tosses two coins in each round. The game ends after one player has $10 and the other one $0. – user218698 Feb 23 '15 at 22:20

1 Answers1

1

If we let $P_{i,j}$ be the likelihood of player starting with $i$ dollars, and ending with $j$ dollars after one move. Ignoring the edge cases for the moment, it should be clear that: $$P_{i,i+k} = P_{i,i-k}\ \forall k<i,\text{ further } P_{0,j} = P_{10,j} = 1\ \forall j$$

The second condition due to the fact that the game ends once player $A$ hits $\$10$ or $\$0$.

Let's for a moment assume that player has $2\leq i\leq8$ dollars. We know there to be 5 possible outcomes: Breakeven, win a dollar, lose a dollar, win two dollars, lose two dollars.

$$P_{i,i} = \text{Prob}((HH,HH),(TT,TT),(TH,TH),(TH,HT),(HT,TH),(HT,HT))$$ $$P_{i,i-1} = P_{i,i+1} = \text{Prob}((HH,HT),(HH,TH),(HT,TT),(TH,TT))$$ $$P_{i,i-2} = P_{i,i+2} = \text{Prob}((HH,TT))$$

Notice that each pair of double coinflips individually has likelihood of $2^{-4} = 16^{-1}$. Conveniently, if we add all events above they sum to $1$. Note that I'm double counting cases when they don't break even because there are two symmetric outcomes.

The issue arrises around the edges. If player A has $\$9$ for example, and rolls two more heads than player $B$ then he moves to node 10 and not the nonexistent 11th node.Because of this you need to include the likelihood of 2 Heads into the movement of node 9 to node 10.

Hope that's enough to get you started. If you find this somewhat confusing, imagine this game for the simpler case with 6 dollars and everyone starts with 3. Same structure, different scale and easier to play around with.

Also recall that the transition matrix does not change over time. Further, the transition matrix does not care at all what the initial conditions are. The fact that they ask for a transition matrix given the initial condition of $\$5$ is a red-herring designed to trick/distract

jameselmore
  • 5,207
  • Ok, if I understood correctly, for my transition matrix, if player A is in state 0 then the first row is 1,0,0,0,...0; and if player A is in state 1, then the second row of the matrix will be 0.25; 0.375; 0.25; 0.0625, 0,0,...0 – user218698 Feb 23 '15 at 21:52
  • 1
    Be careful on the second row! Remember that the column sums to $1$ and there may be more than one way for you to get to $$0$ – jameselmore Feb 24 '15 at 01:46