0
$\begingroup$

Question:

A, B, and C students will participate in a badminton competition, and the agreed format is as follows:

Those who have accumulated two losses are eliminated;

Draw lots before the competition to determine the first two contestants, with the other person taking turns;

The winner of each game will play the next game with the vacant player, and the loser will be left in the next game until one player is eliminated;

After one person is eliminated, the remaining two people continue to compete until one person is eliminated and the other person ultimately wins, ending the competition

After drawing lots, Party A and Party B will compete first, while Party C will take turns.

Let's assume that the probability of both sides winning in each game is 1/2

(1) Calculate the probability of winning four consecutive games in A;

(2) Find the probability of needing to play the fifth game;

(3) Find the probability of C winning in the end

The process of manual calculation is as follows:

The probability of winning four consecutive games in solution

(1) is 1/16

(2) According to the competition system, at least four matches are required, and at most five matches are required After four matches, there are three situations: The probability of A winning four consecutive games is 1/16; The probability of B winning four consecutive games is 1/16; The probability of C winning three consecutive games after playing is 1/8 So the probability of needing to play the fifth game is 1-1/16-1/16-1/8=3/4

(3) There are two situations in which C ultimately wins: The probability of C winning after four matches is 1/8; At the end of five matches and C ultimately wins, there are three scenarios for C's win, loss, and rotation results starting from the second game: win or lose, win or lose empty, and win or lose empty, with probabilities of 1/16, 1/8, and 1/8, respectively Therefore, the probability of C winning in the end is 1/8+1/16+1/8+1/8=7/16

Current issue:

How to draw a probability distribution tree diagram for this problem and calculate their respective probabilities?

My personal attempt is as follows:

tree = KaryTree[2^5, DirectedEdges -> True]
levels = {"A", "B", "C"};
labels = {"AB"}~Join~
   Flatten[Table[
     Table[{#, "NOT " <> #} &@levels[[k]], 2^(k - 1)], {k, 3}]];
Vrelabel = Thread[Range[15] -> labels];
manualEDGE = 1/2;
Erelabel = Thread[EdgeList[tree] -> manualEDGE];
SetProperty[tree, {VertexLabels -> Vrelabel, EdgeLabels -> Erelabel, 
  PlotTheme -> "Marketing"}]

enter image description here

Not expected effect

enter image description here

The manually drawn tree view is shown above:As shown in the above figure, the two letters of each node represent the names of the opponents on both sides of the competition. For example, AB means that both parties in this competition are A and B. The letters and numbers on each branch line indicate that a participant's result in this competition is a loss, and the numbers represent the cumulative number of losses. For example, A1, the loser after this competition is A, with a cumulative loss of one. C2 indicates that the loser in this competition is C, who has lost 2 times and is eliminated.

@ubpdqn

Thank you very much for your reply. I can feel from it that you have put in a lot of effort!

$\endgroup$

1 Answer 1

2
$\begingroup$

Correected This is after correction of error in graph. If there are other errors I would be happy to delete.

I note the update by OP. I encourage OP to code their own graph. The vertices (states) will not be the same but same process is being labeled in different ways.

I post this, acknowledging that it is at risk of using Mathematica/Wolfram Language as a pen/typewriter.

I may have made error(s). If so I apologize.

My motivation for this post was to illustrate a possible approach to visualization and the graphs would look different by different state labels.

In the following the states of game play are (Win A, Loss A,Win B, Loss B, Win C, Loss C):

gr={"000000" \[DirectedEdge] "100100", "000000" \[DirectedEdge] "011000",
  "100100" \[DirectedEdge] "200101", 
 "100100" \[DirectedEdge] "110110", "011000" \[DirectedEdge] "012001",
  "011000" \[DirectedEdge] "011110", 
 "200101" \[DirectedEdge] "300201", "200101" \[DirectedEdge] "211101",
  "110110" \[DirectedEdge] "111111", 
 "110110" \[DirectedEdge] "110220", "012001" \[DirectedEdge] "112101",
  "012001" \[DirectedEdge] "023001", 
 "011110" \[DirectedEdge] "111111", "011110" \[DirectedEdge] "021120",
  "300201" \[DirectedEdge] "400202", 
 "300201" \[DirectedEdge] "310211", "211101" \[DirectedEdge] "212102",
  "211101" \[DirectedEdge] "211211", 
 "111111" \[DirectedEdge] "211211", "111111" \[DirectedEdge] "122111",
  "110220" \[DirectedEdge] "210221", 
 "110220" \[DirectedEdge] "120230", "112101" \[DirectedEdge] "212102",
  "112101" \[DirectedEdge] "122111", 
 "023001" \[DirectedEdge] "024002", "023001" \[DirectedEdge] "023111",
  "310211" \[DirectedEdge] "410212", 
 "310211" \[DirectedEdge] "320221", "211211" \[DirectedEdge] "311212",
  "211211" \[DirectedEdge] "221221", 
 "122111" \[DirectedEdge] "123112", "122111" \[DirectedEdge] "122221",
  "021120" \[DirectedEdge] "022121", 
 "021120" \[DirectedEdge] "021230", "022121" \[DirectedEdge] "023122",
  "022121" \[DirectedEdge] "022231", 
 "023111" \[DirectedEdge] "024112", "023111" \[DirectedEdge] "023221",
  "212102" \[DirectedEdge] "312202", 
 "212102" \[DirectedEdge] "223102", "210221" \[DirectedEdge] "310222",
  "210221" \[DirectedEdge] "220231"}

Making graph (and modifying a style function from documentation):

panelLabel[lbl_] := 
 Framed[lbl, FrameMargins -> 1, Background -> Lighter[Yellow, 0.7]]
gcm = Graph[gr];

Identifying winners and creating absorbing states:

lf = Pick[VertexList[gcm], VertexOutDegree[gcm], 0];
f[x_] := 
 Module[{w = ToExpression[Characters[x]]}, 
  x \[DirectedEdge] (Position[w[[{2, 4, 6}]], _?(# < 2 &)][[1, 
       1]] /. {1 -> "A", 2 -> "B", 3 -> "C"})]
winners = f /@ lf

Creating visualization

gfull = Join[gr, winners];
gfulli = Graph[gfull];
el1 = # -> 
     Placed[Framed[0.5, Background -> White, RoundingRadius -> 25], 
      Center] & /@ gr;
el2 = Placed[Framed[1, Background -> White, RoundingRadius -> 30], 
     Center] & /@ winners;
Graph[gfull, VertexSize -> 0, 
 VertexLabels -> Placed[Automatic, Center, panelLabel], 
 EdgeLabels -> Join[el1, el2]]

enter image description here

Hightling wins for C, A and B:

cwin = FindPath[gfulli, "000000", "C", Infinity, All];
awin = FindPath[gfulli, "000000", "A", Infinity, All];
bwin = FindPath[gfulli, "000000", "B", Infinity, All];
HighlightGraph[gfulli, DirectedEdge @@@ Partition[#, 2, 1] & /@ cwin]
HighlightGraph[gfulli, DirectedEdge @@@ Partition[#, 2, 1] & /@ awin]
HighlightGraph[gfulli, DirectedEdge @@@ Partition[#, 2, 1] & /@ bwin]

enter image description here

enter image description here

enter image description here

You can calculate probabilities:

  1. Probability C will win:

     Total[1/2^(Length[#] - 2) & /@ cwin]
    

yields 7/16

  1. Probability A wins:

     Total[1/2^(Length[#] - 2) & /@ awin]
    

yields 9/32

  1. Probability B Wins(and as expected by symmetry)

     Total[1/2^(Length[#] - 2) & /@ bwin]
    

yields 9/32

  1. Fraction requiring 5 games: This is done as in OP. The 5 below are 4 games states

     c4 = 1/16 Length[FindPath[gfulli, "000000", "C", {5}, All]];
     a4 = 1/16 Length[FindPath[gfulli, "000000", "A", {5}, All]];
     b4 = 1/16 Length[FindPath[gfulli, "000000", "B", {5}, All]];
     1 - (a4 + b4 + c4) 
    

yields 3/4

  1. There are 28 paths. This is consistent with OP's graph despite less vertices in my representation.

     Total[Length /@ {awin, bwin, cwin}]
    

yields 28.

Note: DiscreteMarkovProcess could be used. See first example in "Generalizations and Extensions".

$\endgroup$
10
  • 1
    $\begingroup$ see my remarks. 000000 means no games played. 100100 means A won 1 loss 0, B won 0 lost 1, C 0 win 0 loss and so on. $\endgroup$
    – ubpdqn
    Jul 10, 2023 at 0:03
  • 1
    $\begingroup$ I used Mathematica after working out tree but I hope having an answer will motivate you or other users to programmatically generate tree from game rules. I am just illustrating how to use some graph functions. I hope other users will have better answers. $\endgroup$
    – ubpdqn
    Jul 10, 2023 at 0:08
  • 1
    $\begingroup$ There are 28 paths but in the way I constructed some paths converge to same state. Just code your own tree since you have drawn. I am sure other users will have better insights. I am in middle of full day of work. Sorry. $\endgroup$
    – ubpdqn
    Jul 10, 2023 at 1:51
  • 1
    $\begingroup$ There is a major error in my graph. I will correct when I get a chance. I will delete till then. $\endgroup$
    – ubpdqn
    Jul 10, 2023 at 1:55
  • 1
    $\begingroup$ There may be better answers and I may have made error but I think I have corrected major error. Playing with Mathematica will give you lots of insight and you’ll probably have a better way of achieving what you want. Good luck:) Other users may have programmatic ways to simulate games. If so and better suitsaccepts theirs . I’ll move on for now. $\endgroup$
    – ubpdqn
    Jul 10, 2023 at 8:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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