Your cart is empty
Probabilistic games on graphs
(extra-curricular topic)
(extra-curricular topic)
The theory of probability calculations originated in the examination of games of chance. The following example demonstrates this.
Example 1
How shall two equally qualified players divide the pot of the game in case the game is interrupted, if we know the number of points needed for both of them to win the game?
Let us solve the problem for the special case when Ann needs \latex{ 2 } points and Bruce needs \latex{ 3 } points to win. (Let us consider the game so that it consists of rounds and who wins the round gets one point.)
Let us play the missing rounds of the game by flipping a coin, and let us estimate the ratio of the division (one flip is one round; Ann wins if it lands on heads, Bruce wins if it lands on tails).
Let us solve the problem for the special case when Ann needs \latex{ 2 } points and Bruce needs \latex{ 3 } points to win. (Let us consider the game so that it consists of rounds and who wins the round gets one point.)
Let us play the missing rounds of the game by flipping a coin, and let us estimate the ratio of the division (one flip is one round; Ann wins if it lands on heads, Bruce wins if it lands on tails).
The solution of Fermat
Let us examine what could have happened if the game had not been interrupted. If they play \latex{ 3 } more rounds, then the game is not finished only in the case when Ann gets \latex{ 1 } point and Bruce gets \latex{ 2 } points. However after this whoever wins the fourth round, that person wins the game. So the game would have finished in at most \latex{ 4 } rounds. Let us investigate the possible results of the \latex{ 4 } rounds.
The \latex{ 4 } rounds can be won by \latex{ 2 } people, giving \latex{2^{4}=16} possibilities:
The \latex{ 4 } rounds can be won by \latex{ 2 } people, giving \latex{2^{4}=16} possibilities:
possible results
\latex{ A } won
(number of rounds)
(number of rounds)
\latex{ B } won
(number of rounds)
(number of rounds)
number of possibilities
AAAA
\latex{ 4 }
\latex{ 0 }
\latex{1=\left(\begin{matrix} 4\\ 0 \end{matrix} \right)}
AAAB
AABA
ABAA
BAAA
AABA
ABAA
BAAA
\latex{ 3 }
\latex{ 1 }
\latex{4=\left(\begin{matrix} 4 \\ 1 \end{matrix} \right)}
AABB
ABAB
ABBA
BAAB
BABA
BBAA
ABAB
ABBA
BAAB
BABA
BBAA
BBBA
BBAB
BABB
ABBB
BBAB
BABB
ABBB
\latex{ 2 }
\latex{ 2 }
\latex{6=\left(\begin{matrix} 4 \\ 2 \end{matrix} \right)}
\latex{ 1 }
\latex{ 3 }
\latex{4=\left(\begin{matrix} 4 \\ 3 \end{matrix} \right)}
BBBB
\latex{ 0 }
\latex{ 4 }
\latex{1=\left(\begin{matrix} 4 \\ 4 \end{matrix} \right)}
Ann got at least \latex{ 2 } points in \latex{1+4+6=11} cases.
Bruce got at least \latex{ 3 } points in \latex{4+1=5} cases.
So the pot should be divided between Ann and Bruce in the ratio of \latex{ 11:5 } in the case the game is interrupted.
Pascal got to the same result, but he calculated the number of possibilities from Pascal's triangle. So the previous result can be seen in Figure 9. Pascal got to the same result, but he calculated the number of possibilities from Pascal's triangle. So the previous result can be seen in Figure 9.
Bruce got at least \latex{ 3 } points in \latex{4+1=5} cases.
So the pot should be divided between Ann and Bruce in the ratio of \latex{ 11:5 } in the case the game is interrupted.
Pascal got to the same result, but he calculated the number of possibilities from Pascal's triangle. So the previous result can be seen in Figure 9. Pascal got to the same result, but he calculated the number of possibilities from Pascal's triangle. So the previous result can be seen in Figure 9.
The continuation of the game can also be traced on a graph. We are going to investigate what would be the probability for Ann and for Bruce to win the continuation of the game.
There are two possibilities in every round: either Ann wins, or Bruce wins. So there are two branches from every point; let us write the name of the person who won to the end-point of these branches.
On the edges let us write the probability of getting from the starting point of this edge to its end-point. In this problem the two players are equally good, thus they both win a round with a probability of \latex{\frac{1}{2}}.
We represented the game with the graph only until one of the players won the game; we wrote the name of the winner to the leaves of the graph. And the probability with which the person wins is obtained by multiplying the probabilities written on the edges starting from the root of the tree along the branches and to the leaves of the tree. (Figure 10)
at least \latex{ 2 } points
for \latex{ A }
for \latex{ A }
at least \latex{ 3 } points
for \latex{ B }
for \latex{ B }
\latex{ 2 }
\latex{ 1 }
\latex{ 1 }
\latex{ 1 }
\latex{ 1 }
\latex{ 1 }
\latex{ 6 }
\latex{ 3 }
\latex{ 3 }
\latex{ 1 }
\latex{ 1 }
\latex{ 4 }
\latex{ 4 }
\latex{ 1 }
\latex{ 1 }
Figure 9
Ann
Ann
Ann
Bruce
Ann
Ann
Bruce
Ann
Bruce
Bruce
\latex{ B }
\latex{ A }
\latex{ B }
\latex{ B }
\latex{ A }
\latex{ B }
\latex{ B }
\latex{ A }
\latex{\left(\frac{1}{2} \right)^{3}}
\latex{\left(\frac{1}{2} \right)^{4}}
\latex{\left(\frac{1}{2} \right)^{4}}
\latex{\left(\frac{1}{2} \right)^{4}}
\latex{\left(\frac{1}{2} \right)^{4}}
\latex{\left(\frac{1}{2} \right)^{3}}
\latex{\left(\frac{1}{2} \right)^{3}}
\latex{\left(\frac{1}{2} \right)^{4}}
\latex{\left(\frac{1}{2} \right)^{4}}
\latex{\left(\frac{1}{2} \right)^{2}}
\latex{ \frac{1}{2} }
\latex{ \frac{1}{2} }
\latex{ \frac{1}{2} }
\latex{ \frac{1}{2} }
\latex{ \frac{1}{2} }
\latex{ \frac{1}{2} }
\latex{ \frac{1}{2} }
\latex{ \frac{1}{2} }
\latex{ \frac{1}{2} }
\latex{ \frac{1}{2} }
\latex{ \frac{1}{2} }
\latex{ \frac{1}{2} }
\latex{ \frac{1}{2} }
\latex{ \frac{1}{2} }
\latex{ \frac{1}{2} }
\latex{ \frac{1}{2} }
\latex{ \frac{1}{2} }
Figure 10
By counting the chance of winning for Ann:
\latex{\left(\frac{1}{2} \right)^{2}+\left(\frac{1}{2} \right)^{3}\times 2+\left(\frac{1}{2} \right)^{4}\times 3=\frac{1}{4}+\frac{2}{8}+\frac{3}{16}=\frac{11}{16}.}
The chance of winning for Bruce is:
\latex{\left(\frac{1}{2} \right)^{3}+\left(\frac{1}{2} \right)^{4}\times 3= \frac{5}{16}.}
So Ann and Bruce should divide the pot in the ratio of \latex{ 11: 5 } in case the game is interrupted
Example 2
A sailor called Jack in a silly way offended his two peers, Bill and Bob, who invited him to a duel. Jack, thanks to his persuasiveness, arranged that not both of them will shoot at him, but anyone can shoot at anyone else. Who gets injured will stand out. Jack, Bill and Bob stand at the three vertices of an equilateral triangle; they draw who shoots first, then the shooting order is clockwise for those who still take part in the duel.
Let us establish who has the highest chance to get out unscathed, if Jack hits the target with a probability of \latex{ 50 }%, Bob hits it with a probability of \latex{ 80 }% and Bill hits it with a probability of \latex{ 100 }%.
Let us establish who has the highest chance to get out unscathed, if Jack hits the target with a probability of \latex{ 50 }%, Bob hits it with a probability of \latex{ 80 }% and Bill hits it with a probability of \latex{ 100 }%.
Solution
Let us first think over the possible tactics of the participants.
Bob will surely shoot at Bill, and Bill will shoot at Bob, because he is more dangerous, no matter that he is cross with Jack. If Jack shoots one of them, then it will be the other one's turn, and he will hit Jack with a high probability, thus it is not worth for Jack shooting down any of them, until the other one falls out. So as long as Bill and Bob are in the game, Jack shoots in the air (we assume that he “hits” the air).
Bob will surely shoot at Bill, and Bill will shoot at Bob, because he is more dangerous, no matter that he is cross with Jack. If Jack shoots one of them, then it will be the other one's turn, and he will hit Jack with a high probability, thus it is not worth for Jack shooting down any of them, until the other one falls out. So as long as Bill and Bob are in the game, Jack shoots in the air (we assume that he “hits” the air).
As they draw their places at the vertices of the triangle and also the participant who starts the duel, based on the previous Bob and Bill starts the duel with the same probability of \latex{ 50-50 }%.
Now let us have a look at Figure 11.
Now let us have a look at Figure 11.
\latex{ 50 }%
Bill stars
Bill shoots down Bob
\latex{ 100 }%
\latex{ 50 }%
Jack shoots down Bill:
Jack wins, \latex{ 25 }%
Jack wins, \latex{ 25 }%
\latex{ 50 }%
Jack misses
\latex{ 100 }%
Bill shoots down Jack:
Bill wins, \latex{ 25 }%
Bill wins, \latex{ 25 }%
\latex{ 50 }%
\latex{ 20 }%
Bob misses
\latex{ 100 }%
Bill shoots down Bob
\latex{ 50 }%
Jack shoots down Bill:
Jack wins, \latex{ 5 }%
Jack wins, \latex{ 5 }%
\latex{ 50 }%
Jack misses
\latex{ 100 }%
Bill shoots down Jack:
Bill wins, \latex{ 5 }%
Bill wins, \latex{ 5 }%
Bob starts
\latex{ 80 }%
\latex{ 50 }%
Jack shoots down Bob:
Jack wins, \latex{ 20 }%
Jack wins, \latex{ 20 }%
Bob shoots down Bill
\latex{ 50 }%
\latex{ 20 }%
Bob misses
\latex{ 50 }%
Jack shoots down Bob:
Jack wins, \latex{ 2 }%
Jack wins, \latex{ 2 }%
Jack misses
\latex{ 80 }%
Bob shoots down Jack:
Bob wins, \latex{ 16 }%
Bob wins, \latex{ 16 }%
\latex{ 50 }%
Jack misses
\latex{ 20 }%
Bob misses
\latex{ 80 }%
Bob shoots down Jack:
Bob wins, \latex{ 1.6 }%
Bob wins, \latex{ 1.6 }%
Figure 11
We created the tree graph as seen in the previous example. We wrote the name of the winner of the duel and the probability of it on the leaves. We calculate the order of the chance of winning of the participants by disregarding the chances lower than \latex{1\%}:
Jack: \latex{25\%+5\%+20\%+2\%=52\%}
Bill: \latex{25\%+5\%=30\%}
Bob: \latex{16\%1.6\%=17.6\%}
Bill: \latex{25\%+5\%=30\%}
Bob: \latex{16\%1.6\%=17.6\%}
So with a good tactic the weakest shooter has the highest chance to win the duel corresponding to the rules given.
It can happen that the duel does not finish. The probability that the duel does not finish in \latex{2n+2} steps is: \latex{0,4\times (0,1 )^{n}} which becomes very small when \latex{ n } is large.
It can happen that the duel does not finish. The probability that the duel does not finish in \latex{2n+2} steps is: \latex{0,4\times (0,1 )^{n}} which becomes very small when \latex{ n } is large.
Example 3
The simplest two player game is when a coin is flipped, and Ann wins if it lands on heads, and Bruce wins if it lands on tails. It can be generalised for example in the following way for four players (Ann, Bruce, Chris and me): everyone flips a coin, and if \latex{ 1 } lands on heads and \latex{ 3 } lands on tails, then the winner is with the heads, if \latex{ 1 } lands on tails and \latex{ 3 } lands on heads, then the winner is with the tails, otherwise they flip the coins again.
- What is the probability that I win in the first step?
- What is the probability that the game finishes in the first step?
- What is the probability that the game does not finish in \latex{ 100 } steps?
- If the four of us, Ann, Bruce, Chris and me play this game, then what is the probability that I win?
Before solving the example let us first try to play the game with four players several times, and let us collect experience in connection with the questions. After the solution let us examine how much did the experience match the theoretical results.
Solution (a)
The coins land on either side with equal probability, thus the classical probability model can be applied.
We flip four coins in one step, which can land on heads or tails in a total of \latex{2^{4}} different ways.
I win if my coin lands on heads and the coins of the others land on tails, it can happen in \latex{ 1 } different way, or if my coin lands on tails and the coins of the others land on heads, it is \latex{ 1 } possibility. Thus I can win in \latex{ 2 } different ways, so my chance of winning in the first step is:
We flip four coins in one step, which can land on heads or tails in a total of \latex{2^{4}} different ways.
I win if my coin lands on heads and the coins of the others land on tails, it can happen in \latex{ 1 } different way, or if my coin lands on tails and the coins of the others land on heads, it is \latex{ 1 } possibility. Thus I can win in \latex{ 2 } different ways, so my chance of winning in the first step is:
\latex{\frac{2}{2^{4} }=\frac{1}{2^{3} }=\frac{1}{8}.}
Solution (b)
The number of all cases according to the previous is: \latex{2^{4}}.
The player, whose coin lands on heads while the other coins land on tails, can be chosen in \latex{ 4 } different ways, and in the same way the player, whose coin lands on tails while the other coins land on heads, can be chosen in \latex{ 4 } different ways. Thus the number of the favourable cases is \latex{2\times 4.}
So the probability that the game finishes in the first step is:
The player, whose coin lands on heads while the other coins land on tails, can be chosen in \latex{ 4 } different ways, and in the same way the player, whose coin lands on tails while the other coins land on heads, can be chosen in \latex{ 4 } different ways. Thus the number of the favourable cases is \latex{2\times 4.}
So the probability that the game finishes in the first step is:
\latex{\frac{2\times 4}{2^{4} }=\frac{1}{2}.}
Solution (c)
Based on the answer given to the previous question the probability that the game finishes with the next flip is also \latex{\frac{1}{2}} irrespectively of the number of previous steps.
The probability that the game does not finish in one step is:
The probability that the game does not finish in one step is:
\latex{1-\frac{1}{2}=\frac{1}{2}.}
So the probability that the game does not finish in \latex{ 100 } steps is:
\latex{\left(\frac{1}{2} \right)^{100}=\frac{1}{2^{100} }=\frac{1}{(2^{10} )^{10} }\approx \frac{1}{(10^{3} )^{10} }=\frac{1}{10^{30} }.}
In theory the game can continue ever so long, but the probability that it does not finish in many steps is very small.
Solution (d)
We are going to show several methods for the solution of the problem.
Method I
Based on the symmetry principle my chance of winning is the same as that of my friends, so it is \latex{\frac{1}{4}}.
Method II
We represent the course of the game with a graph. (Figure 12)
\latex{\frac{1}{8}}
\latex{\frac{1}{8}}
\latex{\frac{1}{8}}
\latex{\frac{1}{8}}
\latex{\frac{1}{8}}
\latex{\frac{1}{8}}
\latex{\frac{1}{8}}
\latex{\frac{1}{8}}
\latex{ 1 }st flip
\latex{\frac{1}{2}}
\latex{ 2 }nd flip
\latex{\frac{1}{2}}
\latex{ 3 }rd flip
\latex{ A }
\latex{ B }
\latex{ C }
\latex{ Me }
\latex{ A }
\latex{ B }
\latex{ C }
\latex{ Me }
Figure 12
Let x denote my chance of winning that is unknown at the moment. The probability that I win in the first step is:
\latex{\frac{2}{2^{4} }=\frac{1}{2^{3} }=\frac{1}{8}.}
The probability that the game continues is: \latex{\frac{1}{2}.} The situation is the same in the continuation as at the beginning, since the coins do not have a “memory”. Therefore
\latex{x=\frac{1}{8}+\frac{1}{2}x\Rightarrow \frac{x}{2}=\frac{1}{8}\Rightarrow x=\frac{1}{4},}
\latex{x=\frac{1}{8}+\frac{1}{2}x\Rightarrow \frac{x}{2}=\frac{1}{8}\Rightarrow x=\frac{1}{4},}
so my chance of winning is \latex{\frac{1}{4}.}
Method III
By considering the graph let us calculate the probability that I win in each of the steps. Let us colour the proportion of a \latex{1\times 1} square corresponding to the probabilities by using different colours for the chances of winning for the four players:
Step 1: \latex{\frac{1}{8};} Step 2: \latex{\frac{1}{2}\times \frac{1}{8};} Step 3: \latex{\left(\frac{1}{2} \right)^{2}\times \frac{1}{8};} Step 4: \latex{\left(\frac{1}{2} \right)^{3}\times \frac{1}{8}}
and so on.
If the game continues, it can be seen that we colour the square with four colours, equal areas with every colour. The quarter of the square means my chances of winning, so the sum of my chances of winning is \latex{\frac{1}{4}.} (Figure 13)
If the game continues, it can be seen that we colour the square with four colours, equal areas with every colour. The quarter of the square means my chances of winning, so the sum of my chances of winning is \latex{\frac{1}{4}.} (Figure 13)
Ann
Bruce
Chris
Me
\latex{\frac{1}{8}}
\latex{\frac{1}{16}}
\latex{\frac{1}{64}}
...
Exercises
{{exercise_number}}. Before passing on from every point on the game boards below we roll a regular die. If we roll at most \latex{ 2 }, then we turn right, if we roll at least \latex{ 3 }, then we turn left. What is the probability that we get to each of the exits?
\latex{ A }
\latex{ B }
\latex{ C }
\latex{ D }
\latex{ E }
\latex{ F }
\latex{ G }
\latex{ H }
\latex{ A }
\latex{ B }
\latex{ C }
\latex{ D }
\latex{ E }
\latex{ a })
\latex{ b })
{{exercise_number}}. Ann and Chris play a game in which both players win one point with equal probability. Now Ann has \latex{ 4 } points, Chris has \latex{ 3 } points. If the winner of the game is the person who collects \latex{ 5 } points as first, then what is the probability that Ann wins?
{{exercise_number}}. If we change in the previous game only that Ann wins one point with a probability of \latex{ p }, then what is the probability that Ann wins the game? What shall \latex{ p } be equal to so that Chris has a higher chance of winning the game?
{{exercise_number}}. We draw \latex{ 3 } cards from the Hungarian pack of \latex{ 32 } cards in succession without replacement, and we observe whether the card drawn is Hearts or not.
- The probabilities are denoted by letters in many places in the diagram shown in the figure. Give the numbers that can replace the letters.
- Based on the diagram calculate the probability that all three cards drawn are Hearts
- What is the probability that there are at least two Hearts among the cards drawn?
\latex{\frac{6}{30}}
hearts
\latex{\frac{8}{32}}
no hearts
\latex{\frac{23}{31}}
\latex{\frac{8}{30}}
card 1
card 2
card 3
\latex{ C }
\latex{ D }
\latex{ E }
\latex{ F }
\latex{ G }
\latex{ H }
\latex{ I }
\latex{ B }
\latex{ A }
{{exercise_number}}. Pete has an exam, but he managed to learn only \latex{ 16 } questions out of the \latex{ 20 }. He is the first examinee and he has to draw three questions in succession. He needs to know at least two questions out of these in order to pass the exam.
- Represent the draw of questions with a graph.
- Calculate the probability that Pete passes the exam.
- How much higher would the chance be that he passes the exam if he had managed to learn one more question?
{{exercise_number}}. There are \latex{ 2 } girls and \latex{ 4 } boys in a mixed amateur volleyball team. A girl can serve an ace with a probability of \latex{\frac{1}{18},} a boy can do it with a probability of \latex{\frac{1}{5}.} If they decide who serves first by rolling a die, then what is the probability that the first serve will be an ace? Represent the possibilities on a diagram.
{{exercise_number}}. On a cold winter day Steve goes to school without a cap, thus there is a chance of \latex{ 80 }% that he catches a cold. If he catches a cold, then he will catch the flu with a chance of \latex{ 75 }%, if he does not catch a cold, then this chance is \latex{ 25 }%. What is the chance that he will not catch the flu? (The cold and the flu are two distinct illnesses.)
{{exercise_number}}. Andrew, Bruce and Chris play a game. They flip coins each. If the coin of one of them lands on heads and the other coins land on tails, then the winner is whoever flipped heads. Similarly, if someone’s coin lands on tails and the other coins land on heads, then the winner is whoever flipped tails.
- Play the game.
- Give the probability that the game does not finish in \latex{ 20 } steps.
- What is the probability that Andrew wins?
- Andrew's coin is not fair, i.e. it does not land on either side with equal probability: it lands on heads with a probability of \latex{\frac{1}{3}}, it lands on tails with a probability of \latex{\frac{2}{3}.}
In this case what is the probability that Andrew wins?