Sheldon Ross 10: Exercise 3.62

Sheldon Ross 10 Exercise 3.62_Everyone wins-01.jpg
Question: A, B, and C are evenly matched tennis players. Initially, A and B play a set, and the winner then plays C. This continues, with the winner always playing the waiting player, until one of the players has won two sets in a row. That player is then declared the overall winner. Find the probability that A is the overall winner.


Analytical Solution

To begin with, let us look at the problem flow. In the following tree, if there are two alphabets together, it means that those two players are playing that game. If you see AB, that means that A and B are playing that game.

  • AB (state 1)
    • A wins
      • AC
        • A wins End
        • C wins
          • BC
            • B wins →  AB (state 1)
            • C wins End
    • B wins
      • BC
        • B wins End
        • C wins
          • AC
            • A wins →  AB (state 1)
            • C wins End

In order to set calculate the probabilities, we follow the tree from above.

⇒ P(A) = 12 P( A|Bwins ) + 12 P( A|Awins )

⇒ P(A) = 12 12P(C) + 12 ( 12 + 12 P( A|Awins, loses ))

⇒ P(A) =14 P(C) + 12 ( 12 + 12 P( A|Awins, loses ))

⇒ P(A) =14 P(C) + 14 + 14 ( 0 + 12 P(C))

⇒ P(A) = 14 + 38 P(C)

 The above result also implies that P(B) = 14 + 38 P(C), this is due to the fact that A and B have similar elimination/success paths with both playing C upon winning the first game

We can obtain P(C) by looking at of the possible outcomes of the first game. Since the loser has to play with C. We can pick the game where A wins since we obtained a relation of A with C in the preceding calculation.

⇒ P(C) = 12 P( C|Awins ) + 12 ( 12 + 12 ( 0 + P(C))) = 14 + 18 P(C) = 27 

We are now left with three equations

  • P(C) 27 
  • P(A) = 14 + 38 P(C) = 514 
  • P(B) = 14 + 38 P(C) =  514 

Simulation Solution

The above has been simulated to get the results close to enough the predicted values. The code for this has been a little tricky because of the continuous reassignment of the players after each round. I used a temporary-intermediate value to fix it.


Code

This problem has been simulated entirely in Mathematica. Let me know if you have any questions with the code.

Module[{outcomes = {}, players = ToUpperCase[Alphabet[][[1 ;; 3]]],
  printTemporary, megaRuns = 1000},
  Table[
    Module[{outcome = {}, runs = 1000},
      printTemporary =
          PrintTemporary[
            Style["Simulating sequence: " <> ToString[r] <> " off " <>
                ToString@megaRuns, Red]];
      Table[Module[{counter = 0,
        gameTrack = <|"A" -> {}, "B" -> {}, "C" -> {}|>, waiting = "C",
        current = {"A", "B"}, roundLoser, roundWinner, winner},
        While[True,
          counter += 1;
          {roundLoser, roundWinner} = RandomSample[current, 2];
          current = {roundWinner, waiting};
          waiting = roundLoser;
          MapThread[(gameTrack[#1] =
              Append[gameTrack[#1], #2]) &, {{current[[1]], current[[2]],
            waiting}, {1, 0, 0}}];
          If[counter >= 2,
            If[Or @@ (Take[#, -2] == {1, 1} & /@ gameTrack),
              winner =
                  Piecewise[{#, Take[gameTrack[#], -2] == {1, 1}} & /@
                      Keys[gameTrack]];
              AppendTo[outcome, {counter, winner}];
              Break[]]
          ]
        ]], runs];
      AppendTo[outcomes, KeySort[Counts[#[[2]] & /@ outcome] / runs]];
      Pause[0.01];
      NotebookDelete@printTemporary;
    ], {r, 1, megaRuns}];

  outcomes =
      Association@
          Table[player -> (#[player] & /@ outcomes), {player, players}];
  DistributionChart[outcomes, "ChartElementFunction" -> #,
    PlotLabel -> Style[#, Bold, 16], ImageSize -> 788,
    AspectRatio -> 0.3,
    ChartLabels ->
        Placed[{# <> "\n" & /@ (ToString /@
            N /@ Mean /@ Values@outcomes),
          "\n" <> # & /@ Keys@outcomes}, {Above,
          Below}]] & /@ {"PointDensity", "SmoothDensity", "Quantile"} //
      Column // Framed
]

End of the post 🙂


.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.