MAT109 · Erich Prisner · Franklin College · 2007-2009

Theory Chapter 4:
Probability

Note to the Teacher: ....................

Very often games contain some random features. In poker and other card games, the first move is not done by the players but by the dealer who deals the cards randomly. Outcomes do not only depend on the players' moves, but also on some random elements. Later we will also see that even some completely deterministic games, like ROCK-SCISSORS-PAPER, are best played using some random device. For this reason, the theory of probability has to be discussed.

1. Terminology

A lot of mathematical reasoning is concerned with trying to predict outcomes of certain situations. If I create a sphere of radius 20cm, how large will the surface area be? If I put together 20ml of a 20% acid solution and 30ml of a 50% acid solution, what kind of solution do I get? What will the speed of a falling apple be after 0.1 seconds? If the roulette ball has an initial speed of 3 meter per seconds, and a given initial direction, and the roulette wheel is spinning at a certain speed, where will the ball end? If the interest rate increases by 0.05, and productivity increases by 3%, how will it affect unemployment rate? Unfortunately, in many situations, models from the sciences, social sciences, or economics are not strong enough to predict these outcomes. Or, the models may be accurate, but the data available is just not sufficient, which is the case in the roulette example. In those cases, the outcomes seem random or unpredictable to us.

This is where Probability Theory enters. There is usually a better prediction than "I don't know what the outcome will be, it is random anyway." Although you cannot predict the outcome in these cases, you may be able to describe the likelihood of the different possible outcomes. And this may tell you "what you may expect". Of course, expectations are not always what you get, but we will see that in the long run they will.

Probability Theory uses some terminology which we have to get used to. For instance, the situations whose possible outcomes are to be predicted are called experiments. Ideally, like scientific experiments, these experiments are not singular and isolated, but can rather be repeated over and over in a controlled way since their settings and conditions are very clearly defined. Examples are rolling a die, throwing a coin, or selecting a card from a shuffled 52-card deck. But the weather tomorrow, or the outcome of elections, could also be called experiments, although they are less controllable. We concentrate on one feature of the experiment, like which number the die shows, or what card is chosen, thereby neglecting other possible features (as, for instance, how long the die rolls). Therefore when describing an experiment you should always describe the procedure and what you are looking at.

Very often only finitely many outcomes are possible in these experiments---these outcomes are called the simple events. Events themselves are groups of simple events. For instance, each one of the 52 possible cards is a simple event of the experiment of drawing a card from a shuffled deck of cards. Examples of events are drawing an ace (combining four simple events) or drawing a diamond (combining 13 simple events), but an event does not have to be expressible as elegantly as in these two examples. Sometimes events can only be described by listing all the simple events they consist of. For instance, drawing either a club King, or a heart 8, or a diamond 3, is also an event.

The task of Probability Theory is to assign a value p(A) to each event A. This value p(A) is called the probability that the outcome of the experiment belongs to A. These numbers are between 0 and 1, where 0 means "impossible" and 1 means "absolutely certain", but everything between these two extremes is possible.

There are different ways to obtain these probabilities. One way is to perform the experiment often and measure how often the event occurs. If you perform the experiment n times, and if in k of the cases event A occurs, then the empirical probability p(A) of that event is defined to be the relative frequency k/n of the event. An obvious disadvantage is that we have to perform the experiment repeatedly, and also that the probabilities we get vary slightly.

However, in so-called "a priori" models we want to avoid having to perform the experiment at all. Rather we are interested in obtaining values of theoretical probabilities p(A) using mathematical reasoning (theory). These values should predict the relative frequency (empirical probability) as described above in the following sense:

Law of Large Numbers: If an experiment is repeated more and more times, the empirical probability (relative frequency) of an event will converge, i.e. eventually come closer and closer, to its theoretical probability. If not, the a priori model is not a good reflection of reality.

Assume that the theoretical probability for the event "head" in the experiment "flipping a coin" is 1/2. Assume that frequencies of "head" after 100, 1000, and 10000 throws are 49, 550, and 5200. Then the corresponding relative frequencies are 49/100=0.49, 550/1000=0.55, and 5200/10000=0.52. The "closer and closer" part stated above does not say that these relative frequencies cannot temporarily move away from 0.5, like in the example from the close 0.49 to the a little disappointing 0.55. What it says is that eventually the relative frequency will come closer to 0.5 than it was before almost surely. We can also formulate it like this. A deviation of, say 0.03, a value below 0.47 or above 0.53, is always possible, but the probability for such a fixed deviation decreases as the number of trials increases. Actually the probability for such a fixed deviation in the relative frequency approaches 0. But note also that the absolute deviation can always exceed a fixed value. In the example above, the absolute deviation between the number of heads and the predicted number of heads is -1, 50, 200, and these numbers may increase as the number of trials increases.

Let me mention a common misconception of the Law of Large Numbers. You throw a coin and get a sequence of "Head", "Tail", "Tail", "Head", "Tail", "Head", "Tail", "Tail", "Tail", "Tail", "Tail". How likely is "Head" next? "Many people would say it is higher than 50%, since it is "due". Others may question the fairness of the coin and rather predict another "Tail". However, if we know that we have a fair coin, that the theoretical probability of 50% is the right one, then the probability for "Head" is still exactly 50% for all future rounds. Probability Theory and the Law of Large Numbers are not "fair" in the way of actively fighting against an existing deviation. Rather this deviation may absolutely persist, or very likely even increase, but then the relative deviation will still go to 0.

Historical Remark: Although there has been some work on probabilities by Girolamo Cardano in the 16th Century, this work was not noticed much, and Probability Theory did really start in 1654 in an exchange of letters between Blaise Pascal and Pierre de Fermat, as described on this page. Christian Huygens published the first book on this new theory of probability in 1657. The Law of Large Numbers was forumlated and proved by Jakob Bernoulli in 1713. 100 years later, Pierre de Laplace introduced a lot of new tools, and applied Probability Theory to areas outside of games of chance. Later the area of statistics emerged from Probability Theory.

2. Computing probabilities

2.1 Equally likely simple events

Note that the probabilities of all simple events always add up to 1, since the event containing all simple events will occur surely. Therefore it is simple to find these probabilities when it is known that all outcomes are equally likely (like for a fair die). If there are n possible outcomes, n simple events, then each probability equals 1/n.

Note that the probability p(A) of any event A equals the sum of the probabilities of the simple events contained in it. If all simple events have the same probability then p(A) equals the number of simple events in A divided by the total number of simple events.

Example 1: How likely is it to throw two fives with two dice of different color?
We consider the case of rolling two dice, a red one and a blue one. The simple events are the 36 pairs of numbers (1,1), (1,2), ... (6,5), (6,6), where the first entry indicates what the red die shows and the second entry what the blue die shows. A red "3" and a blue "5", abbreviated as (3,5), and a red "5" and a blue "3", denoted by (5,3), are two different outcomes. All these simple events are equally likely, therefore each one has a probability of 1/36. Thus p((5,5))=1/36.

2.2 Simple events not equally likely

More difficult is the situation when the outcomes are not equally likely, like for a biased die. Sometimes one has to use the empirical probability p(A), which is defined as the relative frequency, the number of observed outcomes of A divided by the total number of experiments. But sometimes it is also possible to look at the situation differently, to define these simple events differently, thereby arriving at equally likey simple events again. Take the following three examples:

Example 2: A container contains 5 red marbles, 4 blue marbles, and 3 green marbles. Closing your eyes, you remove one randomly. What is the probability of picking a red marble?
If we define "red", "blue", and "green" as simple events, then these simple events are not equally likely. It is also not too difficult to assign probabilities to them, but maybe it is best to formulate the problem differently. Instead of having three simple events, we could label the different marbles and work with 12 different equally likely simple events: "red1", "red2", ... "green2", "green3". The event "red" consists of the five simple events "red1", ... "red5", therefore p(red)=5/12.

Example 3: How likely is it to throw two fives with two dice?
We could look at all pairs of numbers as simple events, If both dice are indistinguishable, there is only one outcome showing "1" and "2", the same as showing "2" and "1". Then there are 21 possible outcomes. However they are not equally likely. Therefore it is simpler to color one die. Then we arrive at the situation discussed above with 36 equally likely outcomes of probability 1/36 each. Therefore p(5 and 5) = 1/36, but p(1 and 2) = 2/36, since two simple events in the colored version would correspond to the simple event of one die showing a "1" and the other showing a "2".

Example 4: How likely is it to get a sum of four with two dice?
It would be possible to formulate the simple events to be the sums of the numbers shown by the two dice. However, this model would have the big disadvantage that the probabilities of the simple events would not be identical (which may not even be obvious to you---think about how likely a sum of 2 is compared with a sum of 7). Therefore a better model uses the 36 pairs of numbers as simple events. Then our event A in question of a sum of four consists of three simple events, namely (1,3), (2,2), and (3,1)---note again that (1,3) and (3,1) are different simple events. Therefore p(A)=3/36.

3. Expected Value
Example: You have the opportunity to throw a coin. If it shows head, you get 100 Dollars. If it shows tail, you get 50 Dollars. If it ends standing on its edge, you have to pay 20 Cents. Would you decline the offer to play since you may lose 20 Cents? Would there change anything in your willingness to play if you would have to pay instead 10,000,000 Dollars if the coin ends standing on its edge?

Very often a numerical value is attached to each outcome of an experiment. Such a value is usually called a random variable, abbreviated by a letter, say X. In our context of games the payoff of a player is such a value. If the simple events (possible outcomes) of an experiment are A1, A2,... An and the payoffs, the amounts attached to these simple events are X1, X2,... Xn, respectively, then how high a payoff would you expect? Probably the average of all these values, provided all outcomes are equally likely, i.e. if p(A1) = p(A2) = ... = p(An) = 1/n. Note that the average in this case equals the sum of the products p(Ai)·Xi of probabilities and amounts attached. If the outcomes are not equally likely, the expectation would be tilted towards the payoffs attached to the more likely outcomes. Instead of an average, we take a weighted average, where the probabilities of the outcomes serve as the weights. Therefore, the expected value for the random variable X is defined by

E(X) = p(A1)·X1 + p(A2)·X2 + ... + p(An)·Xn.

The same as the probability of an outcome approaches the relative frequency of that outcome if one repeats the experiment often, the average of a random variable approaches its expected value when repeating the experiment often.

Example 5: Three amounts of money, $10, $100, and $1000 are in three closed identical looking envelopes. After shuffling these envelopes, one of them is given to you. How much do you expect?
Interestingly your expectation is higher than the middle value, $100. Since all three envelopes are equally likely with probability 1/3, the expected value for the money is (1/3)·10 + (1/3)·100 + (1/3)·1000 = (1/3)·1110 = 370. We "expect" a value that doesn't even occur among the values inside the envelopes. But if we play the game 1000 times, we will have won about $370 on average each time.

Therefore the expected value of a random value is not the value that occurs most frequently or most likely. This value is usually called "mode" but not used in our context.

Example 6: You have to draw a card from a deck of 52 cards. You win $10 if you have chosen an ace, and $3 for a king. What is the expected value?
We have 52 simple events. To four of them (the aces), $10 is attached, to four of them (the kings) $3 is attached, to the remaining 44 of them $0 is attached. Each of the 52 simple events have the same probability of 1/52. Then the expected value E = 48·(1/52)·0 + 4·(1/52)·3 + 4·(1/52)·10 = 52/52 = 1.
Example 7: In a European roulette, all numbers between 0 and 36 are equally likely. If you bet on "Even", you obtain $1 if the result is one of the 18 even numbers larger than 0 (!), otherwise, if the result is odd or 0, you have to pay $1. What is the expected value?
All 37 simple events are equally likely of probability 1/37. 18 of them have the value "1" attached, 19 have "-1" attached. Then the expected value is E = 18·(1/37)·1 + 19(·(1/37)·(-1) = -1/37.

Example 8: We roll two dice and consider the sum of the two dice as the random variable. What is the expected value?
We have seen already that the most convenient way to model this is by assuming the dice have different colors, and we therefore have 36 different possible outcomes. One simple event has 2 as the sum of the dice, two have sum 3, three have sum 4, and so on until sum 7 which occurs six times. From then on, the frequency for the sum decreases again. We have 5 cases of a sum of 8, 4 cases of a sum of 9, and so on, until the one simple event of a sum of 12. These values can can be tested empirically here. Now the expected value for our random variable is 1·(1/36)·2 + 2·(1/36)·3 + 3·(1/36)·4 + 4·(1/36)·5 + 5·(1/36)·6 + 6·(1/36)·7 + 5·(1/36)·8 + 4·(1/36)·9 + 3·(1/36)·10 + 2·(1/36)·11 + 1·(1/36)·12 = 7.

Note that expected values can only be computed for numerical values. If you draw a marble from a container containing six blue ones and six yellow ones, the expected outcome is not a green marble. Actually there is no such thing as "expected outcome", just expected value of the payoff, the numerical random variable.

Modeling 4: Measurement Scales

Assume there are three possible outcomes: "bad", "good", and "very good", and let's assume we translate these outcomes into payoffs of 0, 1, and 2. Then would you prefer a 60% chance of a very good outcome and a 40% chance of a bad outcome over a good outcome? Well, the arithmetic is easy: 60%·2+40%·0 = 1.2 > 1, so you would. However one could question whether the assignment of the numbers 0, 1, and 2 to the three outcomes is really appropriate. Maybe the difference between "very good" and "good" is small, but the difference between "good" and "bad" is large? In that case, risking a bad outcome in 40% of the cases would seem rather reckless.

There are four types of measurement scales. A nominal scale is the weakest one. Some features of the outcome, like "red", "green", "blue", for example, have no natural order in it. This type of measurement scale cannot be used for payoffs/random variables, since they must be expressed in numbers, and in order to do so, the possible outcomes must have a natural ordering. Features of outcomes are ordinal if there is such a natural ordering. An example is given above with "bad", "good", and "very good". Such features can be used for payoffs in games, however, in order to use them for expected values, the differences between the payoffs must also be comparable. This third level is called an interval scale. In the previous example, the outcomes are interval if we can tell whether "good" is closer to "bad" or to "very good", and to what extend. Then of course encoding by 0,1,2 may not be appropriate, maybe rather 0,2,3 is more appropriate. The final fourth level is a ratio scale, having a natural zero, but for our purposes, in expected values and games, we will never require ratio scales.

Summarizing, we always need at least ordinal scales for our payoffs, and if randomness or mixed strategies (explained later) come into play, we even need interval scales.

4. Multistep Experiments

4.1 Probability Trees

Some experiments consist of two or more sub-experiments which are performed sequentially. Such an experiment is called multistep experiment. In the simplest case, we first have an experiment with possible outcomes A and B. If the outcome is A, a second experiment is performed with possible outcomes C and D. If the outcome of the first experiment is B, a second experiment with possible outcomes E and F is performed. The graph to the right visualizes the situation, and it is called a probability tree. Starting with the leftmost vertex, one of the two vertices in the middle is reached after the first experiment, and then one of the four vertices to the right can be reached. The probabilities for the outcomes are written below the corresponding line leading to that outcome. Of course the similarity to extensive forms or game trees in sequential games is obvious. What was called position there is now called situation---the combination of all what is known so far.

Now how likely is outcome A in the first round and outcome C in the second round? The probability for that combined event is the product of the probabilities on the arcs, p(A)·p(C).

4.2 Conditional Probabilities

Very often in multistep experiments, the possible outcomes of the second-round experiments are the same, but the probabilities for these outcomes differ depending on the situation, on the outcome of the first-round experiment. An example is shown to the right. Since more than one arc in the tree has C as outcome, but the probabilities are maybe different, we need a more involved notation. Let p(C|A) denote a conditional probability, the probability for outcome C provided we are in situation A. Thus p(C|A) and p(C|B) may not be identical. Totally, for the combined experiment, four different outcomes are possible: A and C (A&C), A and D (A&D), B and C (B&C), and B and D (B&D). How likely is each? It turns out that the total probability for each of the combined outcomes, of the four vertices to the right, are the products of the probabilities of the path leading to this vertex when starting at the leftmost vertex. Therefore

Example 9: AIDS tests, even when good and useful, are not perfect. Assume your hospital uses one that gives gives a positive result in 97.7% of the cases if the person has the AIDS virus, and a negative result in 92,6% of the cases where the person is not infected. Further assume that 0.5% in the population in your city carries the AIDS virus.

If someone from your city tells you that he or she has been tested positive with this test, what is the probability that he or she really carries the virus? [A. Rossman, B. Chance 2004]

We model this as a two-step experiment. In the first round, the outcomes are "AIDS infected" ("A") with probability 0.5% and "not AIDS infected" ("H" for healthy) with probability 99.5%. Then, in the second step, the test is positive ("P") or negative ("N") with probabilities depending on the outcome of the first step. The first and third outcome of the two-step experiment combined are the outcome of a positive test. The first outcome of the two-step experiment means the person has AIDS and is tested positive. The probability for that equals p(A)·p(P|A) = 0.5%·97.7% = 0.4985% The third outcome means the person is not AIDS infected but still has been tested positive. The probability for that outcome equals p(H)·p(P|H) = 99.5%·7.4% = 7.363% Then the probability that the person tested positive is AIDS infected equals 0.4985%/(0.4985%+7.363%) = 6.34%, so there is not real reason for panic yet.
Example 10: A deck of 52 cards is available. The first experiment consists of drawing a card. The possible outcomes are "red" or "black". Thus A is the outcome of having a red card drawn in the first drawing, and B is the outcome of this card being black. Then another card is drawn from the remaining 51 cards. C is the event that this second card is red, and D that this second card is black.
Obviously p(A)=p(B)=26/52. However p(C|A), the probability for a second red card if one red card has already been drawn, equals p(C|A)=25/51, but p(D|A)=26/51, p(C|B)=26/51, and p(D|B)=25/51. Therefore the combined event of two red cards A&C has the probability p(A&C) = p(A)·p(C|A) = 26/52·25/51. The same for the combined event B&D of two black cards; p(B&D) = p(B)·p(D|B) = 26/52·25/51. The event A&D means we draw a red card in the first round and a black card in the second round; its probability equals p(A&D) = p(A)·p(D|A) = 26/52·26/51. The same probability we get for the event B&C for a black card in the first round and a red card in the second round. Therefore the probability for two different cards in both rounds equals p(A&D)+p(B&C) = 26/52·26/51+ 26/52·26/51 = 26/51, slightly higher than 1/2.

4.3 Probability Digraphs

Let's say we draw three cards from a stack. A, C, respectively E mean a red card in the first, second, respectively third drawing, and B, D, respectively F mean a black card in the first, second, respectively third drawing. The probability tree is shown to the right.

Now at the end we may not care about the ordering but rather only on how many black and red cards are drawn altogether. Therefore we don't distinguish between A&C&F and A&D&E and B&C&E---in each of these three cases we have two red cards and one black one. Also after the second drawing we don't have to distinguish between the situation A&D of a red card in the first drawing and a black one in the second, and B&C of a black card in the first drawing and a red one in the second. In both cases we have one red and one black card in the hand, and 25 red cards and 25 black cards remaining in the stack. So the prospects for the future, for the third drawing are also identical. This is expressed by the fact that both subtrees of the probability tree starting at A&D respectively B&C are identical. In these cases we are allowed to identify these states (and also the subtrees starting at these vertices). What we get by doing so is called a probability digraph.

Now in such a digraph, the probability for a combined event like A&C&F would be obtained like this. You look at all paths starting at the leftmost (start) vertex, always moving to the right, and arriving at the vertex in question. For each of these paths you multiply the probabilities along all edges. And then you add all these products. In the example above, there are three such paths, A,C,F, A,D,E, and B,C,E. leading to the outcome of two red and one black card. Therefore the probability for this outcome is P(A&C&F=A&D&E=B&C&E) = p(A)·p(C|A)·p(F|A&C) + p(A)·p(D|A)·p(E|A&D) + p(B)·p(C|B)·p(E|B&C).

If you draw three cards from a stack of 52 cards, the probability of getting 2 red cards and 1 black one equals (1/2)·(25/51)·(26/50) + (1/2)·(26/51)·(25/50) + (1/2)·(26/51)·(25/50).

Please see the following for another application of this method, and also for remarks on the history of probability theory.

5. Randomness in Simultaneous Games

Let's now return to games. Very often, the payoffs in a simultaneous game do not only depend on the choices of the players, but also have a random component. Consider the following example:

Example 11: Variant of TWO BARS: Two bars charge $2, $4, or $5 for a beer. Marginal cost can be neglected. As before, every month 4000 beers are drunk by natives, who go to the bar with lower prices. Tourists just choose one of the two bars randomly. Depending on whether a planned hotel will be build or not, (both outcomes are equally likely) 7000 or 4000 beers are drunk by tourists. What prices would the bars select?

Later we will see that sequential games involving randomness are modeled by defining a random player, called "Nature". For simultaneous games this is not necessary. All we have to do is to replace the payoffs by expected payoffs.

In our example, assume both set a price of $2. Then both will sell 2000 beers to natives. With 50% probability both will sell 3500 additional beers to tourists, each making therefore 2·(2000+3500)= 11000 dollars, and with 50% probability both will sell only 2000 additional beers to the tourists, each making 2·(2000+2000)= 8000 dollars. The expected value for each is (1/2)·11000+(1/2)·8000= 9500 dollars. The same analysis could be done for the other eight entries. Of course, in this simple example we could also use the deterministic model (and the same Excel sheet) with an expected number of (1/2)·7000+(1/2)·4000=5500 tourists.
The modified bimatrix is
  2    4    5  
  2    9500, 9500    13500, 11000    13500,13750  
  4    11000, 13500    19000, 19000    27000, 13750  
  5    13750, 13500    13750, 27000    23750, 23750  

Example 12: A 3-spinner is a random device that shows one of three possible numbers with equal probability. Each of two player bring two 3-spinner (7,5,4) and (1,8,6) to the game, and has to select one simultaneously. The chosen spinner play against another. The player whose 3-spinner shows the larger number wins. Which 3-spinner would you select?
There are 9 outcomes possible, 7-1, 7-8, 7-6, 5-1, 5-8, 5-6, 4-1, 4-8, 4-6, and all of them are equally likely. In outcome 1, 3, 4, 7, the left player wins, in the other 5 outcomes, the right player wins. Therefore the (1,8,6) spinner is better than the other one, and both will select the better one.

Spinning Applet: Select three values for the left spinner and three values for the right spinner (change the values). Then spin, to see which one is better.
Left Spinner:     Right Spinner:
  Selected Values: :       Cumulative Result:

Example 13: Assume each player brings three 3-spinner to the game: (3, -1, -2), (2, 2, -4), and (-1, -1, 2). Each player selects one of these three 3-spinners simultaneously, and they spin. The player whose spinner shows the higher number wins one dollar from the other. Which spinner should be selected?
This is a zero-sum game, so it suffices to display the expected payoff for the row player Ann.
  (3, -1, -2)    (2, 2, -4)    (-1, -1, 2)  
  (3, -1, -2)    0    1/9    -1/9  
  (2, 2, -4)    -1/9)    0    1/9  
  (-1, -1, 2)    1/9    -1/9    0  
It may be a little surprising to see that there are no Nash equilibria. There is no "best" spinner.

6. Counting without Counting

The probability of an event equals the sum of the probabilities of the simple events "contained" in that event. Therefore, if we know all probabilities of the simple events, computing these probabilities is rather simple. This is in particular true in the many cases where all simple events have equal probabilities. Still, in some cases manually counting all these simple events seems to be a little too tedious. Formulas for this case are the content of the part of Mathematics called "Combinatorics", but we don't have to time to go into this interesting subject.

References

Exercises and Projects