1
$\begingroup$

Consider the following problem, from Tijms's Understanding Probability:

Three equally matched opponents decide to have a ping-pong tournament. Two people play against each other in each game. Drawing lots, it is determined who are playing the first game. The winner of a game stays on and plays against the person not active in that game. The games continue until somebody has won two games in a row. What is the probability that the person not active in the first game is the ultimate winner?

Let's call the three players A, B, and C.

To solve this problem using a Markov chain, I introduce the following states:

  • state 0: there is going to be a match between A and B, and nobody has won the previous match because there have been no previous matches. I will denote this state with the shortcut $(AB, 0)$ (this is the initial state);
  • state 1: there is going to be a match between A and B, and A won the previous match. Shortcut: $(AB,A)$;
  • state 2: there is going to be a match between A and B, and B won the previous match. Shortcut: $(AB,B)$;
  • state 3: there is going to be a match between A and C, and A won the previous match. Shortcut: $(AC,A)$;
  • state 4: there is going to be a match between A and C, and C won the previous match. Shortcut: $(AC,C)$;
  • state 5: there is going to be a match between B and C, and B won the previous match: $(BC,B)$;
  • state 6: there is going to be a match between B and C, and C won the previous match: $(BC,C)$;
  • state 7: A has won two matches in a row;
  • state 8: B has won two matches in a row;
  • state 9: C has won two matches in a row.

The last three states should be absorbing states.

By considering all the possible games, one can easily write down the nonzero entries of the transition probability matrix: $$ \begin{gathered} p_{03} & p_{05} & p_{17} & p_{15} & p_{23} & p_{28} & p_{37} & p_{36} & p_{41} & p_{49} & p_{58} & p_{54} & p_{62} & p_{69}, \end{gathered} $$ which are all equal to $\frac12$.

Already after 20 matrix multiplication, we have the following quite stable probabilities: $$ p^{(20)}_{07} = p^{(20)}_{08} = 0.3571, \qquad p^{(20)}_{09} = 0.2857, $$ so the probability that the person not active in the first game wins is 0.2857.

Does the result seem right? Intuitively, I would expect that the player not involved in the first game has lower probability of winning, because if it loses there won't be any more matches.

I noticed that building the probability transition matrix is quite tedious, is there a more systematic way to doing this?

$\endgroup$
0
$\begingroup$

have you come across hitting probabilities? If not see theorem 1.3.2 in these notes: http://www.statslab.cam.ac.uk/~james/Markov/s13.pdf

These let you set up equations relating the hitting probabilities starting from each state, which can be solved. Remember to exploit symmetry to save computation.

$\endgroup$
  • $\begingroup$ Thanks, I will read the notes and retry the computation with hitting probabilities. $\endgroup$ – J. D. Jun 6 '19 at 9:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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