Celebrate the year of the dog

A little over one year ago, this blog marked the beginning of the year of the rooster in this blog post. Now it’s time to celebrate the year of the dog.

2018 is the year of the dog

The Lunar New Year actually falls on February 16 this year. To be precise, the latest year of the dog will span from February 16, 2018 to February 4, 2019. We mark the New Year by highlighting a math problem that is related to the Chinese zodiac signs. In fact, this problem was also discussed in the blog post on the year of the rooster.

The Problem

The problem is this. There are 12 animal signs in Chinese zodiac – Rat, Ox, Tiger, Rabbit, Dragon, Snake, Horse, Goat, Monkey, Rooster, Dog and Pig. You ask people repeatedly their animal signs until all 12 signs have been represented. How many people do you have to ask in order to have encountered all 12 animal signs? We assume that the 12 animal signs are equally represented. This assumption makes the math more tractable.

The number of people you ask is a random quantity. Obviously the number of people you have to ask is at least 12. It is likely that you have to ask many more than 12 people. In the previous post, we discuss this problem in two different ways – through simulations and using a math formula based on the coupon collector problem. In this post we view this problem as an occupancy problem and solve it using the method of Markov chains.

The Occupancy Problem

Imagine there are 12 cells (e.g. boxes or urns). Balls are thrown into the cells one at a time at random (assuming that each ball always lands into one of the 12 cells). On average, how many balls do we need to throw so that each cell has at least one ball? In other words, how many balls do we need to throw so that there are no empty cell? This is one form of the occupancy problem. The occupancy problem being described here is a natural reformulation of the problem about asking people until all 12 animal signs are represented.

The problem can also be described as sampling with replacement. Put 12 balls labeled 1 through 12 in an urn. Draw balls at random one at a time with replacement. How many selections do we need to make so that each of the 12 numbers are drawn at least once?

Of course, there is nothing special about 12 cells. The number of cells in the occupancy problem can vary. Consider the problem of 6 cells. So balls are thrown until all 6 cells are occupied. Or an urn has 6 balls labeled 1 through 6. Then balls are drawn from the urn until all each of the 6 numbers has been chosen at least once. There is another way of looking at the 6-cell occupancy problem – rolling a die repeatedly until each face has appeared at least once.

Markov Chain Approach

There are more than one way to solve the occupancy problem (two ways are discussed in the previous posts).

The method to highlight here is to use Markov chains. A Markov chain is a series of random steps. Each random step is identified by a state. Each state is dependent only on the preceding state and not on the states prior to the preceding state. We use X_n to denote the state after the nth random step or at time n.

In the 12-cell occupancy problem, a state is the number of occupied cells after a ball is thrown. For example, X_0=0, which is the initial state (we assume that before throwing the first ball, the cells are empty). Then X_1=1 (after throwing one ball, one cell is occupied). After throwing the second ball, the number of occupied cells is random. For example, it could be that X_2=1 (if the second ball goes into the occupied cell holding the first ball) or it could be that X_2=2 (if the second ball goes into an empty cell). The first scenario has probability 1/12 and the second scenario has probability 11/12. Similarly, we can list out all the scenarios for X_3 (the number of occupied cells after throwing the third ball) and their probabilities. In fact, it will be much more efficient if we describe all these probabilities in a matrix.

\mathbf{P} =       \bordermatrix{ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12\cr        0 & 0 & 1 & 0  & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \cr        1 & 0 & 1/12 & 11/12  & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \ \cr        2 & 0 & 0 & 2/12  & 10/12 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \cr        3 & 0 & 0 & 0  & 3/12 & 9/12 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \cr        4 & 0 & 0 & 0  & 0 & 4/12 & 8/12 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \cr        5 & 0 & 0 & 0  & 0 & 0 & 5/12 & 7/12 & 0 & 0 & 0 & 0 & 0 & 0 \cr        6 & 0 & 0 & 0  & 0 & 0 & 0 & 6/12 & 6/12 & 0 & 0 & 0 & 0 & 0 \cr        7 & 0 & 0 & 0  & 0 & 0 & 0 & 0 & 7/12 & 5/12 & 0 & 0 & 0 & 0 \cr        8 & 0 & 0 & 0  & 0 & 0 & 0 & 0 & 0 & 8/12 & 4/12 & 0 & 0 & 0 \cr        9 & 0 & 0 & 0  & 0 & 0 & 0 & 0 & 0 & 0 & 9/12 & 3/12 & 0 & 0 \cr         10 & 0 & 0 & 0  & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 10/12 & 2/12 & 0 \cr        11 & 0 & 0 & 0  & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 11/12 & 1/12 \cr       12 & 0 & 0 & 0  & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \cr   } \qquad

The above matrix looks kind of huge. But there is an order behind it. The Markov chain of the 12-cell occupancy problem has 13 states (0, 1, 2, …, 12). In this case, a state refers to the number of occupied cells after a ball is thrown into the cells. So X_n is the number of occupied cells after the nth ball is thrown. For convenience, we can also think of the subscripts n as time. The type of Markov chains discussed here would be called discrete-time Markov chains.

The above matrix \mathbf{P} is called the transition probability matrix. It contains the probabilities of transitioning from one state into various states. Here’s how to read the matrix. Pick a row, say the row labeled 2. This refers to the situation of the process being at a point when 2 of the 12 cells are occupied. The next state can be 2, meaning that the next ball goes into one of the two occupied cells. Since there are two occupied cells, the probability is 2/12. The next state can be 3, meaning that the next ball goes into one of the empty cells. Since there are 10 cells not occupied, the probability is 10/12.

In general, this matrix tells us that if the process starts at state i, the process will remain at state i in the next time period with probability i /12 and the process will transition to i+1 with probability 1-i/12.

The state 12 is an interesting one. When all the cells are occupied, any additional balls thrown at them will still mean that the cells are occupied. Thus when the process reaches state 12, the process remains at 12 indefinitely. A state is called an absorbing state if the process does not leave that state once that state is entered. Thus state 12 is an absorbing state in 12-cell occupancy problem. The other states (0 to 11) are called transient states.

The probabilities in the matrix \mathbf{P} are called one-step transition probabilities because these probabilities tell us how the process transitions from a given step to the next step. These probabilities are notated by P_{ij}, signifying the probability that the state in the next period is j given that the process begins in state i. For example, P_{5,6}=7/12 and P_{10,11}=2/12. What about the two-step transition probabilities P_{ij}^2? The quantity P_{ij}^2 is the probability that the process will be in state j after two steps given that the process is currently in state i. The idea generalizes quite naturally. The quantity P_{ij}^k, a k-step transition probability, is the probability that the process will be in state j after k steps are taken given that the process is currently in state i.

To compute the k-step transition probabilities, all we need to do is to raise the matrix \mathbf{P} to the kth power. A matrix calculator will be helpful. Using this online matrix calculator, we raise \mathbf{P} to the 4th power, the following shows the non-zero elements in the first row.

    \displaystyle P_{0,1}^4=\frac{1}{20736}=0.00048

    \displaystyle P_{0,2}^4=\frac{165}{20736}=0.00796

    \displaystyle P_{0,3}^4=\frac{2750}{20736}=0.13262

    \displaystyle P_{0,4}^4=\frac{9900}{20736}=0.47743

    \displaystyle P_{0,5}^4=\frac{7920}{20736}=0.38194

After throwing 5 balls into 12 empty cells, the above probabilities tells us the likelihoods of the number of occupied cells. It is very unlikely to have 1 or 2 occupied cells. The most likely would be 4 or 5 occupied cells. To determine the likelihoods after throwing 6 balls into 12 empty cells, raise \mathbf{P} to 6 and so on.

For a detailed discussion on calculation of k-step transition probabilities, see this blog post.

Solving the Occupancy Problem

We now give an indication on how to solve the 12-cell occupancy problem (or the 12 animal signs problem). Recall that state 12 is an absorbing state. Now consider the matrix obtained by removing state 12 from \mathbf{P}. Call this new matrix Q. It is a 12 x 12 matrix. Let I be the 12 x 12 identity matrix. Compute the matrix I-Q. Then use an online matrix calculator to find the inverse matrix of I-Q. Let (I-Q)^{-1} be the inverse. The sum of the all the elements in the first row of (I-Q)^{-1} is the average number of steps that the Markov process takes to reach state 12. The following is the sum of the elements on the first row of (I-Q)^{-1}.

    \displaystyle 1+\frac{12}{11}+\frac{6}{5}+\frac{4}{3}+\frac{3}{2}+\frac{12}{7}+2+\frac{12}{5}+3+4+6+12=37.2385

On average, we need to throw 37.24 balls into the 12 cells to have no empty cells. With respect to the 12 animal signs, on average, it requires sampling 37.24 people to have encountered all 12 signs.

The matrix I-Q is called the fundamental matrix of the Markov chain represented by the matrix \mathbf{P}. The method is detailed in this blog post. That blog post also discusses the occupancy problem in some details.

The discussion here is a roundabout way and a long winded way to solve the coupon collector problem, which is discussed in this blog post from a year ago. However, the example discussed here is an excellent introduction to Markov chains. Further information can be found in the following blog posts.

\text{ }

\text{ }

Dan Ma math blog
Daniel Ma math blogs

Dan Ma math
Daniel Ma math

Dan Ma mathematics
Daniel Ma mathematics

\copyright 2018 – Dan Ma

Advertisements

The probabilities of poker hands

This post works with 5-card Poker hands drawn from a standard deck of 52 cards. The discussion is mostly mathematical, using the Poker hands to illustrate counting techniques and calculation of probabilities

Working with poker hands is an excellent way to illustrate the counting techniques covered previously in this blog – multiplication principle, permutation and combination (also covered here). There are 2,598,960 many possible 5-card Poker hands. Thus the probability of obtaining any one specific hand is 1 in 2,598,960 (roughly 1 in 2.6 million). The probability of obtaining a given type of hands (e.g. three of a kind) is the number of possible hands for that type over 2,598,960. Thus this is primarily a counting exercise.

___________________________________________________________________________

Preliminary Calculation

Usually the order in which the cards are dealt is not important (except in the case of stud poker). Thus the following three examples point to the same poker hand. The only difference is the order in which the cards are dealt.

These are the same hand. Order is not important.

The number of possible 5-card poker hands would then be the same as the number of 5-element subsets of 52 objects. The following is the total number of 5-card poker hands drawn from a standard deck of 52 cards.

    \displaystyle \binom{52}{5}=\frac{52!}{5! \ 47!}=2,598,960

The notation \binom{n}{r} is called the binomial coefficient and is pronounced “n choose r”, which is identical to the number of r-element subsets of a set with n objects. Other notations for \binom{n}{r} are _nC_r, C_{n,r} and C(n,r). Many calculators have a function for _nC_r. Of course the calculation can also be done by definition by first calculating factorials.

Thus the probability of obtaining a specific hand (say, 2, 6, 10, K, A, all diamond) would be 1 in 2,598,960. If 5 cards are randomly drawn, what is the probability of getting a 5-card hand consisting of all diamond cards? It is

    \displaystyle P(\text{all diamond})=\frac{1287}{2598960}=0.000495198=0.0495198 \%

This is definitely a very rare event (less than 0.05% chance of happening). The numerator 1,287 is the number of hands consisting of all diamond cards, which is obtained by the following calculation.

    \displaystyle \binom{13}{5} \times \binom{39}{0}=\frac{13!}{5! \ 8!} \times 1=1,287

The reasoning for the above calculation is that to draw a 5-card hand consisting of all diamond, we are drawing 5 cards from the 13 diamond cards and drawing zero cards from the other 39 cards. Since \binom{39}{0}=1 (there is only one way to draw nothing), \binom{13}{5}=1287 is the number of hands with all diamonds.

If 5 cards are randomly drawn, what is the probability of getting a 5-card hand consisting of cards in one suit? The probability of getting all 5 cards in another suit (say heart) would also be 1287/2598960. So we have the following derivation.

    \displaystyle \begin{aligned} P(\text{one suit})&=P(\text{all diamond})+P(\text{all heart})+P(\text{all club})+P(\text{all spade}) \\&=\frac{1287}{2598960}+\frac{1287}{2598960}+\frac{1287}{2598960}+\frac{1287}{2598960} \\&=\frac{5148}{2598960} \\&=0.001980792 \\&=0.198 \% \end{aligned}

Thus getting a hand with all cards in one suit is 4 times more likely than getting one with all diamond, but is still a rare event (with about a 0.2% chance of happening). Some of the higher ranked poker hands are in one suit but with additional strict requirements. They will be further discussed below.

Another example. What is the probability of obtaining a hand that has 3 diamonds and 2 hearts? The answer is 22308/2598960 = 0.008583433. The number of “3 diamond, 2 heart” hands is calculated as follows:

    \displaystyle \binom{13}{3} \times \binom{13}{2} \times \binom{26}{0}=\frac{13!}{3! \ 11!} \times \frac{13!}{2! \ 13!}=286 \times 78=22308

One theme that emerges is that the multiplication principle is behind the numerator of a poker hand probability. For example, we can think of the process to get a 5-card hand with 3 diamonds and 2 hearts in three steps. The first is to draw 3 cards from the 13 diamond cards, the second is to draw 2 cards from the 13 heart cards, and the third is to draw zero from the remaining 26 cards. The third step can be omitted since the number of ways of choosing zero is 1. In any case, the number of possible ways to carry out that 2-step (or 3-step) process is to multiply all the possibilities together.

___________________________________________________________________________

The Poker Hands

Here’s a ranking chart of the Poker hands.

The chart lists the rankings with an example for each ranking. The examples are a good reminder of the definitions. The highest ranking of them all is the royal flush, which consists of 5 consecutive cards in one suit with the highest card being Ace. There is only one such hand in each suit. Thus the chance for getting a royal flush is 4 in 2,598,960.

Royal flush is a specific example of a straight flush, which consists of 5 consecutive cards in one suit. There are 10 such hands in one suit. So there are 40 hands for straight flush in total. A flush is a hand with 5 cards in the same suit but not in consecutive order (or not in sequence). Thus the requirement for flush is considerably more relaxed than a straight flush. A straight is like a straight flush in that the 5 cards are in sequence but the 5 cards in a straight are not of the same suit. For a more in depth discussion on Poker hands, see the Wikipedia entry on Poker hands.

The counting for some of these hands is done in the next section. The definition of the hands can be inferred from the above chart. For the sake of completeness, the following table lists out the definition.


Definitions of Poker Hands

Poker Hand Definition
1 Royal Flush A, K, Q, J, 10, all in the same suit
2 Straight Flush Five consecutive cards,
all in the same suit
3 Four of a Kind Four cards of the same rank,
one card of another rank
4 Full House Three of a kind with a pair
5 Flush Five cards of the same suit,
not in consecutive order
6 Straight Five consecutive cards,
not of the same suit
7 Three of a Kind Three cards of the same rank,
2 cards of two other ranks
8 Two Pair Two cards of the same rank,
two cards of another rank,
one card of a third rank
9 One Pair Three cards of the same rank,
3 cards of three other ranks
10 High Card If no one has any of the above hands,
the player with the highest card wins

___________________________________________________________________________

Counting Poker Hands

Straight Flush
Counting from A-K-Q-J-10, K-Q-J-10-9, Q-J-10-9-8, …, 6-5-4-3-2 to 5-4-3-2-A, there are 10 hands that are in sequence in a given suit. So there are 40 straight flush hands all together.

Four of a Kind
There is only one way to have a four of a kind for a given rank. The fifth card can be any one of the remaining 48 cards. Thus there are 48 possibilities of a four of a kind in one rank. Thus there are 13 x 48 = 624 many four of a kind in total.

Full House
Let’s fix two ranks, say 2 and 8. How many ways can we have three of 2 and two of 8? We are choosing 3 cards out of the four 2’s and choosing 2 cards out of the four 8’s. That would be \binom{4}{3} \times \binom{4}{2} = 4 x 6 = 24. But the two ranks can be other ranks too. How many ways can we pick two ranks out of 13? That would be 13 x 12 = 156. So the total number of possibilities for Full House is

    \displaystyle 13 \times 12 \times \binom{4}{3} \times \binom{4}{2}= 13 \times 12 \times 4 \times 6 =3744

Note that the multiplication principle is at work here. When we pick two ranks, the number of ways is 13 x 12 = 156. Why did we not use \binom{13}{2} = 78?

Flush
There are \binom{13}{5} = 1,287 possible hands with all cards in the same suit. Recall that there are only 10 straight flush on a given suit. Thus of all the 5-card hands with all cards in a given suit, there are 1,287-10 = 1,277 hands that are not straight flush. Thus the total number of flush hands is 4 x 1277 = 5,108.

Straight
There are 10 five-consecutive sequences in 13 cards (as shown in the explanation for straight flush in this section). In each such sequence, there are 4 choices for each card (one for each suit). Thus the number of 5-card hands with 5 cards in sequence is 10 \times 4^5= 10240. Then we need to subtract the number of straight flushes (40) from this number. Thus the number of straight is 10240 – 10 = 10,200.

Three of a Kind
There are 13 ranks (from A, K, …, to 2). We choose one of them to have 3 cards in that rank and two other ranks to have one card in each of those ranks. The following derivation reflects all the choosing in this process.

    \displaystyle \binom{13}{1} \times \binom{4}{3} \times \binom{12}{2} \times \binom{4}{1} \times \binom{4}{1}=13 \times 4 \times 66 \times 4 \times 4 = 54912

Two Pair and One Pair
These two are left as exercises.

High Card
The count is the complement that makes up 2,598,960.

The following table gives the counts of all the poker hands. The probability is the fraction of the 2,598,960 hands that meet the requirement of the type of hands in question. Note that royal flush is not listed. This is because it is included in the count for straight flush. Royal flush is omitted so that he counts add up to 2,598,960.


Probabilities of Poker Hands

Poker Hand Count Probability
2 Straight Flush 40 0.0000154
3 Four of a Kind 624 0.0002401
4 Full House 3,744 0.0014406
5 Flush 5,108 0.0019654
6 Straight 10,200 0.0039246
7 Three of a Kind 54,912 0.0211285
8 Two Pair 123,552 0.0475390
9 One Pair 1,098,240 0.4225690
10 High Card 1,302,540 0.5011774
Total 2,598,960 1.0000000

___________________________________________________________________________
\copyright 2017 – Dan Ma

Celebrate the year of the rooster

year-of-rooster

According to the Chinese zodiac, the year 2017 is the year of the rooster. In fact, today (January 28, 2017) is the start lunar New Year, which is the first day of the year of the rooster. What better way to celebrate the year of the rooster than working a related math puzzle, or to perform a related random experiment!

At the office yesterday, conversation at the beginning of a meeting, before discussing the main topics, centered on the Chinese zodiac animal signs (the Chinese zodiac system is a 12-year cycle with a different animal representing each year). One coworker mentioned he is a tiger. Another coworker did not know his sign and Googled to find out that he is a rat! Another coworker is a rooster. It turns out that a pig is also represented. Imagine that you keep picking people at random and ascertain his/her animal sign. How many people do you have to ask in order to have met all 12 animal signs?

The number of people you have to ask is a random quantity. If you are very lucky, you may encounter all 12 signs by asking just 12 people (the minimum number of people you have to ask). The outcome of twelve people is not likely (it has only about 0.005% chance of happening). It is almost certain that you have to ask many more people. It turns out that the first few animals are easy to obtain (just like in the meeting with 4 different animal signs for 4 people). As you ask more people, the animal signs tend to repeat. So you have to keep asking more people. As you encounter more animal signs, it takes longer to get a new animal sign. For example, if you have encountered 11 animal signs already, you will have to ask on average 12 more people to find the last animal sign. So the overall average is not a number near 12. On average, you will have to ask about 37 people to get the entire set of 12 animals.

The random experiment that has been described is this. Put 12 slips of papers numbered 1 through 12 in a hat. Randomly draw a piece of paper and note the number and then put it back into the hat. Keep drawing until all 12 numbers have been chosen. Let X be the number of selections that are required to perform this random experiment. Of course, you can expand the sample space to include more slips of papers (i.e. with more numbers). But the context will not be picking animal signs.

There are two ways to get a handle on the random variable X as described above. One is through simulation and the other is through math.

Before discussing the simulation or the math, let’s point out that the problem discussed here is a classic problem in probability that goes by the name “the coupon collector problem”. The numbers 1 to 12 in a hat are like coupon (prizes) that are randomly given out when purchasing a product (e.g. a box of cereal). The problem discussed here is that the coupon collector desires to collect the entire set of coupons.
___________________________________________________________________________

Simulation

To get a sense of how long it will take, simulate random numbers from 1 through 12 until all numbers have appeared. The following is 5 iterations of the experiment.

    9, 2, 6, 8, 9, 10, 2, 9, 8, 1, 5, 11, 1, 1, 2, 10, 9, 8, 8, 9, 5, 11, 9, 3, 7, 9, 8, 8, 4, 3, 1, 4, 3, 12 (34 draws)

    7, 7, 1, 10, 11, 11, 10, 4, 5, 8, 8, 2, 6, 4, 6, 2, 12, 6, 6, 12, 9, 5, 8, 10, 1, 5, 10, 4, 9, 4, 1, 11, 11, 6, 2, 1, 6, 6, 3 (39 draws)

    9, 5, 2, 2, 1, 5, 6, 11, 7, 11, 4, 6, 1, 12, 3, 7, 8, 3, 3, 2, 2, 3, 5, 6, 2, 5, 1, 6, 8, 5, 4, 10 (32 draws)

    1, 5, 5, 4, 5, 12, 10, 1, 8, 1, 3, 9, 1, 3, 11, 9, 10, 3, 9, 11, 4, 4, 4, 7, 7, 3, 1, 11, 11, 4, 10, 6, 3, 2 (34 draws)

    6, 7, 6, 1, 12, 6, 1, 1, 7, 1, 11, 10, 3, 3, 9, 6, 9, 4, 2, 6, 11, 7, 7, 11, 2, 6, 2, 1, 7, 2, 5, 9, 6, 12, 6, 11, 1, 11, 11, 2, 5, 6, 7, 5, 2, 11, 2, 2, 6, 2, 12, 5, 5, 5, 12, 10, 3, 11, 1, 10, 10, 6, 9, 11, 10, 7, 11, 5, 1, 9, 11, 9, 8 (73 draws)

Each of the number is generated by using the =RANDBETWEEN(1, 12) in Excel. In each iteration, the numbers are generated until all 12 numbers have been generated.

There is considerable fluctuation in this 5 iterations of the experiment. With the 5th one being exceptionally long, it is possible that it takes a long time to find all 12 animal signs. The average of the first iteration is obviously 34. The average of the first two iteration is 36.5. The averages of the first 3, 4, and 5 iterations are 35, 34.75, and 42.4, respectively.The last average of 42.4 is quite different from the average of 37 indicated earlier.

What if we continue to run the experiment, say, for 10,000 times? What would the long run averages look like? The following graph shows the averages from first 100 runs of the experiment. It plots the average of the n iterations from n=1 to n=100.

    Figure 1 – Long run averages from 100 runs
    animal-signs-simulations-100b

Figure 1 shows that there is quite a bit of fluctuation in the averages in the first 25 runs or so. Eventually, the averages settle around 37 but still retain noticeable fluctuation. The following graph shows the averages from first 1000 runs of the experiment.

    Figure 2 – Long run averages from 1000 runs
    animal-signs-simulations-1000

The graph is Figure is smoother as it moves toward 1000, but still has noticeable fluctuation from 37 (in fact the graph is mostly below 37). The following graph shows the averages from first 10000 runs of the experiment.

    Figure 3 – Long run averages from 10000 runs
    animal-signs-simulations-10000

The graph in Figure 3 shows the average of the first n iterations with n goes from 1 to 10,000. The graph is for the most parts a horizontal line slightly above 37, especially after n=3000. In fact the average of all 10,000 iterations is 37.3381, which is close to the theoretical average of 37.2385.

The simulation is an illustration of the law of larger numbers. The essence of the law of large numbers is that the short run results of a random experiment are unpredictable while the long run results are stable and predictable and eventually settle around the theoretical average.

The first 5 runs of the experiment (as shown above) are certainly unpredictable. It may take 34 draws or may take 73 draws. The first 100 simulations also have plenty of ups and downs, even though graph in Figure 1 shows a movement toward 37. The first 1000 simulations display more stable results but are below average as the graph move toward 1000 (Figure 2). In simulating the experiment 10,000 times (Figure 3), the long run averages settle around the theoretical average of 37.2385.

So if you survey people their animal signs, the time it takes has a great deal of random fluctuations. It may take 34 asks or 73 asks (as shown in the first 5 simulations). If the experiment is done repeatedly, the results are predictable, i.e. the average is around 37.

The long run results of a gambling game are predictable too and will settle around the theoretical average. The theoretical average of a gambling game is usually referred to as the house edge. For example, for the game of roulette, the house edge is 5.26%. For each bet of $1, the gambler is expected to lose 5.26 cents. In playing a few games, the gambler may win big. In the long run, the house is expected to gain 5.26 cents per one dollar bet. Thus the law of large numbers can mean financial ruin for the gambler (or profits for the casino). For an illustration of the law of large numbers in the context of the game of Chuck-a-Luck, see here. For an illustration in the context of the roulette wheel, see here.

Another piece of useful information from the 10,000 simulated runs of the experiment is the frequency distribution.

Table 1
Frequency Distribution of the 10,000 Simulated Runs
\begin{array}{rrrrr}      \text{Interval} & \text{ } & \text{Frequency} & \text{ } & \text{Relative Frequency} \\      \text{ } & \text{ } \\      \text{10 to 19} & \text{ } & 375 & \text{ } & 3.75 \% \\      \text{20 to 29}  & \text{ } & 2817 & \text{ } & 28.17 \% \\      \text{30 to 39}  & \text{ } & 3267 & \text{ } &  \text{ } 32.67 \% \\      \text{40 to 49}  & \text{ } & 1931 & \text{ } & \text{ } 19.31 \% \\  \text{50 to 59}  & \text{ } & 901 & \text{ } & \text{ } 9.01 \% \\  \text{60 to 69}  & \text{ } & 379 & \text{ } & \text{ } 3.79 \% \\  \text{70 to 79}  & \text{ } & 190 & \text{ } & \text{ } 1.90 \% \\  \text{80 to 89}  & \text{ } & 88 & \text{ } & \text{ } 0.88 \% \\  \text{90 to 99}  & \text{ } & 30 & \text{ } & \text{ } 0.30 \% \\  \text{100 to 109}  & \text{ } & 13 & \text{ } & \text{ } 0.13 \% \\  \text{110 to 119}  & \text{ } & 3 & \text{ } & \text{ } 0.03 \% \\  \text{120 to 129}  & \text{ } & 3 & \text{ } & \text{ } 0.03 \% \\  \text{130 to 139}  & \text{ } & 1 & \text{ } & \text{ } 0.01 \% \\  \text{140 to 149}  & \text{ } & 2 & \text{ } & \text{ } 0.01 \% \\      \text{ }  & \text{ } & \text{ } & \text{ } & \text{ } \\      \text{Total }  & \text{ } & 10000 & \text{ } & 100.00 \%    \end{array}

Figures 1 to 3 tell us the long run behavior of the simulations (e.g. the long run average is 37). Table 1 gives the counts of the simulations that fall into each interval and the corresponding relative frequency (the percentage). Table 1 tells us how often or how likely a given possibility occurs. The total number of simulations that fall within the range 20 to 49 is 8015. So about 80% of the time, the experiment ends in 20 to 49 draws. Furthermore, 92.95% of the simulations fall into the interval 20 to 69. This really tells us what the likely results would be if we perform the experiment. The frequency distribution also tells us what is unlikely. There is only 3.75% chance that the experiment can be completed with less than 20 draws. In the simulations, there are two that are above 140 (they are 141 and 142). These extreme results can happen but are extremely rare. They only happened about 2 times per 10,000 simulations.

___________________________________________________________________________

The math angle

There is also a mathematical description of the random experiment of surveying people until all 12 animal signs are obtained. For example, there is a formula for calculating mean, and there is also a formula for calculating the variance. There is also a probability function, i.e. a formula for calculating probabilities (akin to Table 1). The formula for the mean is actually simple to describe.

Let X_n be the number of draws from the set \left\{1,2,3,\cdots,n \right\} with replacement such that each number in the set is picked at least once. The expectation of X_n is the following.

    \displaystyle E[X_n]=n \biggl[ \frac{1}{n}+\frac{1}{n-1}+ \cdots+ \frac{1}{3}+\frac{1}{2}+1    \biggr]

The 37.2385 theoretical average discussed above comes from this formula. The the case of n=12, the mean would be

    \displaystyle E[X_{12}]=12 \biggl[ \frac{1}{12}+\frac{1}{11}+ \cdots+ \frac{1}{3}+\frac{1}{2}+1    \biggr]=37.23852814

For more details of the math discussion, see this previous post. For a more in-depth discussion including the probability function, see this post in a companion blog on probability.

___________________________________________________________________________
\copyright \ 2017 \text{ by Dan Ma}

The coupon collector problem

The coupon collector problem is a classic problem in probability. It is usually described in this way: a person (called the coupon collector) is trying to collect all coupons (promotional gift items) when purchasing a certain type of products (e.g. boxes of breakfast cereal). Suppose that there are n different types of coupons. Suppose that when someone buys a unit of the product, he or she does not know what type of coupons that is inside the box. How many units of the product does the coupon collector have to buy in order to collect the entire set of coupons?

Note that the number of units to buy is a random quantity. To see it for yourself, roll a fair die until each of the six faces appears at least once. You can try this with your own die and record the numbers as you go. We rolled our own die and the following shows three such experiments.

    3, 4, 6, 2, 6, 1, 3, 2, 1, 4, 6, 2, 6, 1, 6, 1, 2, 3, 5

    6, 6, 4, 1, 3, 6, 6, 4, 1, 5, 4, 2

    6, 2, 1, 1, 5, 5, 1, 1, 1, 3, 6, 1, 3, 5, 4

The first experiment has 19 trials, the second one has 12 trials and the third one has 15 trials. If we run the random experiment another time, we would get another sequence. Also note that the first 5 of the faces (coupons) show up fairly quickly. It takes a few more trials just to get the last coupon.

Rolling a dice is simply a way to generate random numbers. Thus we can describe the coupon collector problem as a random sampling problem. Draw numbers repeatedly from the sample space S=\left\{1,2,3,\cdots n \right\} with replacement until each of the n numbers has been chosen at least once. Let X_n be the number of trials that are required to perform this experiment. As demonstrated above (or as confirmed by your rolling of a die), X_n is a random variable. The smallest value it can take on is n. Theoretically, the random variable X_n could be n or some other integer greater than n. The goal is to describe the probability distribution of the random variable X_n.

Some interesting things to know about this probability distribution are the expected value E[X_n] (the mean or the average number of trials that are needed to complete the experiment). Another one is the probability function (or probability mass function) so that we can determine how likely it is to complete the experiment in k trials. For a more detailed discussion, go to this previous post. In the remainder of the post, we discuss the expected value.

The expected value E[X_n] has a clear formula and is easily computed.

    \displaystyle E[X_n]=n \biggl[ 1 + \frac{1}{2}+\frac{1}{3}+ \cdots+\frac{1}{n-1}+\frac{1}{n} \biggr]

For the 6-coupon case (or the rolling of a die), it would take on average 15 trials to get all 6 faces.

    \displaystyle E[X_6]=6 \biggl[ 1 + \frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6} \biggr]=14.7 \approx 15

Of course, 15 is simply the average. The actual results may be more or less than 15 as the above illustrations show (or your own rolling of a die). To find out how likely it is to have a result around 15, it is necessary to have the probability function of X_6. See the previous post for more information on that.

Consider this example. Suppose that you want to throw candies at random to a group of 10 kids. Each candy is assigned to each child at random. You want to throw candies until each of the children has at least one candy. Of course some kids would receive a few candies. But the goal is that no one would come away empty handed. On average, you would need to throw about 30 candies.

    \displaystyle E[X_{10}]=10 \biggl[ 1 + \frac{1}{2}+\frac{1}{3}+ \cdots+\frac{1}{9}+\frac{1}{10} \biggr]=29.29 \approx 30

If there are 50 coupons, it would take on average 225 trials to get all 50 coupons. One interesting thing is that it is relatively easy to get the first few coupons. To get the last coupon, it would take a quite a few trials. In fact, it would take on average n trials to get the last coupon (if n is the number of coupon types).

Another point we would like to make is that the coupon collector problem requires an understanding of the geometric distribution. A random experiment that can modeled by a geometric distribution is the performance of a series of independent trials until some criterion is satisfied. The random variable X_n described here has some similarity with a geometric model (but not totally similar). The similarity: we keep drawing numbers with replacement until all numbers are drawn.

Let’s look at the third experiment 6, 2, 1, 1, 5, 5, 1, 1, 1, 3, 6, 1, 3, 5, 4 listed above. We draw the first number (happens to be 6). Next we wish to draw another number different from 6. Luckily it takes only one trail to get 2. Now we wish to draw a number different from 6 and 2. It also takes one trial (to get 1). Next, continue to draw until we get a number different from 6, 2 and 1. This time it takes two trials to get a 5. Then continue to draw until we get a number different from 6, 2, 1, and 5. It takes 5 trials to get a 3. Lastly it takes 5 more trials to get the last number 4. What this shows is that the random variable X_6 is a sum of 6 geometric random variables.

    X_6=C_1+C_2+C_3+C_4+C_5+C_6

Each of the C_i is a geometric random variable. The first one C_1 is kind of special. The value of C_1 is always 1 (it takes one trial to get the first number). The second variable C_2 is a geometric random variable (the number of trials to get a number different from the first chosen number. Then C_3 is the number of trials to get a number different from the first two chosen numbers and so on. If there are n coupons, then X_n is the sum of n geometric random variables.

    X_n=C_1+C_2+C_3+\cdots +C_{n-1}+C_n

The formula for the expected value E[X_n] is derived through this connection with the geometric distribution. See the previous post for a more in-depth discussion.

___________________________________________________________________________
\copyright \ 2017 \text{ by Dan Ma}

The Game of Chuck-a-Luck

Chuck-a-Luck is a game of chance that is often played at carnivals and sometimes used as a fundraiser for charity. The game is easy to understand and easy to play. The odds seem attractive. The carnival makes money consistently. It is a game of chance that seems to be popular for all sides. This post aims to shine a light on this game, from how it is played to how to evaluate its expected payout. When you gamble for a short duration, the results can be unpredictable. In playing just a few games, you may win big or stay even. What about the long run results? We will show that the house edge is about 8 cents per dollar wagered. That is, the expected payout is for the casino (or carnival) is 8 cents per $1 bet. That means for the player would on average lose 8 cents per $1 bet. We use the game of Chuck-a-Luck to open up a discussion on the law of large numbers.

The following is a Chuck-a-Luck set.

    chuck-a-luck-set
    A Chuck-a-Luck set

The set consists of three dice in a wire cage and a betting surface with spots for 1 through 6. Here’s how the game is played:

  • The player picks a number out of 1,2,3,4,5, and 6 and then places a stake on the spot corresponding to the number he/she chooses.
  • The three dice in the cage and then rolled.
  • If the player’s number appears on one, two or three of the dice, then the player receives one, two or three times the original stake, respectively, and the player can keep the original stake.
  • If the player’s number does not appear on any of the three dice, then the player loses the original stake.

Essentially the player or the bettor (the person who makes the bet on the chosen number) wins the amount of the bet for each occurrence of the chosen number. When the player wins, he or she also keeps the original stake. However, when the chosen number does not show up among the three dice, the player loses the original stake. Suppose $1 is placed on the number 2. Then if the three rolls are 2, 5 and 1, then the player wins $1, and keep the original stake of $1. If the the results of the three rolls are 2, 1 and 2, then the bettor wins $2, and keep the original stake of $1. If the results are 3, 1 and 4, then the player would lose the original stake $1. Of course, if the results are 2, 2 and 2, then the player wins $3 and keeps the original stake of $1.

Note that the original stake that is returned to you (when you win) is not considered part of the winning since it is your own money to start with. This is an important point to keep in mind when calculating the expected payout.

___________________________________________________________________________

A Counting Reasoning

The game of Chuck-a-Luck seems to be an attractive game. There are four distinct outcomes when three dice are rolled – zero, one, two and three occurrences of the chosen number. Yet the player wins in 3 of these outcomes. He/she loses in only one of the four outcomes. The game of Chuck-a-Luck is thus viewed favorably with at least even odds. The reasoning for even odds might goes like this: The probability of a two (if two is the chosen number) in a roll is 1/6. Since there are three dices, the probability of having at least one two is 1/6 + 1/6 + 1/6 = 3 (1/6) = 1/2, representing an even chance of winning.

To calculate the odds of winning Chuck-a-Luck, it will be helpful to find out the likelihood (or probability) of obtaining zero, one, two or three appearances of the chosen number in a roll of three dice. We can use an informal counting reasoning to do this. Again, we assume the chosen number is 2. The roll of one die has 6 outcomes. So rolling three dice has 6 x 6 x 6 = 216 possible outcomes. How many of these 216 outcomes are the losing outcomes for the player? In other words, how many of these 216 outcomes have no twos? Each roll has 5 outcomes with no two. Thus in three rolls, there are 5 x 5 x 5 = 125 outcomes with no twos.

Out of 216 bets, the player on average will lose 125 of them. So the probability of the player losing the game is 125/216 = 0.58 (about 58% chance of losing). That means when you play this game repeatedly, you win about 42% of the time (much worse than even odds).

Let’s find out how often the player will win one time, two times or three times of the original stake. Out of the 216 possible outcomes in rolling three dice, there are 125 outcomes in which the player are losing and the other 91 outcomes are ones in which the player are winning (216 = 125 + 91). Let’s break down these 91 winning outcomes.

In rolling three dice, how many of the 216 outcomes have exactly one 2? The patterns are 2-X-X, X-2-X and X-X-2. The X is a die that cannot be a 2 (and has 5 possibilities). The first pattern has 1 x 5 x 5 = 25 possibilities. Then there are 3 x 25 = 75 outcomes with exactly one of the chosen number.

Let’s count the outcomes that have exactly two of the chosen numbers. The patterns are 2-2-X, 2-X-2 and X-2-2. The first pattern has 1 x 1 x 5 = 5 possibilities. Then there are 3 x 5 = 15 outcomes with exactly two appearances of the chosen number. Finally, there is only one outcome with three of the chosen number, namely 2-2-2. These counts are summarized in the following table.

Table 1
Expected Frequency of Winning/Losing
\begin{array}{rrrrr}      \text{Outcome} & \text{ } & \text{Frequency} & \text{ } & \text{Percentage} \\      \text{ } & \text{ } \\      \text{No 2} & \text{ } & 125 & \text{ } & 57.9 \% \\      \text{One 2}  & \text{ } & 75 & \text{ } & 34.7 \% \\      \text{Two 2's}  & \text{ } & 15 & \text{ } &  \text{ } 6.9 \% \\      \text{Three 2's}  & \text{ } & 1 & \text{ } & \text{ } 0.5 \% \\      \text{ }  & \text{ } & \text{ } & \text{ } & \text{ } \\      \text{Total }  & \text{ } & 216 & \text{ } & 100 \%    \end{array}

The game is far from a fair game. The player on average loses about 57.9% of the time. Furthermore, the winning outcomes (happening 42.1% of the time) skew toward the outcomes for winning one time of the original stake. So the game is lopsidedly in favor of the house (the carnival or the casino). There is another angle that we haven’t explored yet, namely the expected payout. The above table only shows the likelihood of winning and losing. It does not take into account of the expected size of the winning for the four scenarios.

___________________________________________________________________________

Expected Payout

Table 1 above does not take into account of the size of the winning in each of the four scenarios. Let’s look at the following table.

Table 2
Expected Winning/Losing
\begin{array}{rrrrrrr}      \text{Outcome} & \text{ } & \text{Frequency} & \text{ } & \text{Winning per Bet} & \text{ } & \text{Expected Winning}\\      \text{ } & \text{ } \\      \text{No 2} & \text{ } & 125 & \text{ } & -\$1 & \text{ } & -\$125\\      \text{One 2}  & \text{ } & 75 & \text{ } & \$1 & \text{ } & \$75\\      \text{Two 2's}  & \text{ } & 15 & \text{ } & \$2 & \text{ } & \$30\\      \text{Three 2's}  & \text{ } & 1 & \text{ } & \$3  & \text{ } & \$3\\      \text{ }  & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ }\\      \text{Total }  & \text{ } & 216 & \text{ } & \text{ } & \text{ } & -\$17    \end{array}

The last column in Table 2 gives the expected winning for each scenario, which is obtained by multiplying the frequency and the winning per bet. For example, for the “No 2” scenario, the player is expected to lose $125 (out of 216 bets of $1). For the “two 2’s” scenario, the player is expected to win 15 x $2 = $30 (out of 216 bets). What is interesting is the sum of that column, which totals -$17. By putting up $216 ($1 for each bet), the player is expected to lose $17. The expected payout is -17 / 216 = -$0.079 (a negative payout).

___________________________________________________________________________

Simulations

The short run results are unpredictable. In playing a few games, the player may win most of the games and may even win big. What is the expected result if the player keeps playing? To get an idea, let’s simulate 100,000 plays of Chuck-a-Luck. We use the function Rand() in Microsoft Excel to generate random numbers between 0 and 1. The simulated values of the dice are generated based on the following rules.

Table 3
Rules for Simulations
\begin{array}{rrrrr}       \text{Random Number} & \text{ } & \text{Simulated Die Value} & \text{ } & \text{ } \\      \text{ } & \text{ } \\      \displaystyle 0<x \le \frac{1}{6} & \text{ } & 1 & \text{ } & \text{ } \\  \text{ } & \text{ } \\      \displaystyle \frac{1}{6}<x \le \frac{2}{6}  & \text{ } & 2 & \text{ } & \text{ } \\  \text{ } & \text{ } \\      \displaystyle \frac{2}{6}<x \le \frac{3}{6}  & \text{ } & 3 & \text{ } &  \text{ } \\  \text{ } & \text{ } \\      \displaystyle \frac{3}{6}<x \le \frac{4}{6}  & \text{ } & 4 & \text{ } & \text{ } \\  \text{ } & \text{ } \\      \displaystyle \frac{4}{6}<x \le \frac{5}{6}  & \text{ } & 5 & \text{ } & \text{ } \\  \text{ } & \text{ } \\      \displaystyle \frac{5}{6}<x < 1  & \text{ } & 6 & \text{ } & \text{ }    \end{array}

Three die values are simulated at a time. The process is repeated for 100,000 times. We cannot display all the simulated rolls of dice. The following table shows the first 20 simulated plays of Chuck-a-Luck.

Table 4
Simulated Chuck-a-Luck Games (Chosen Number = 5, $1 per Bet)
First 20 Plays
\begin{array}{rrrrrrrrr}     \text{Play} & \text{ } & \text{Die 1} & \text{ } & \text{Die 2} & \text{ } & \text{Die 3} & \text{ } & \text{Winning}\\      \text{ } & \text{ } \\     1 & \text{ } & 2 & \text{ } & 3 & \text{ } & 1 & \text{ } & -\$1 \\     2 & \text{ } & 1 & \text{ } & 2 & \text{ } & 5 & \text{ } & \$1 \\     3 & \text{ } & 3 & \text{ } & 6 & \text{ } & 1 & \text{ } & -\$1 \\     4 & \text{ } & 3 & \text{ } & 5 & \text{ } & 4 & \text{ } & \$1 \\     5 & \text{ } & 4 & \text{ } & 4 & \text{ } & 5 & \text{ } & \$1 \\     6 & \text{ } & 5 & \text{ } & 3 & \text{ } & 2 & \text{ } & \$1 \\     7 & \text{ } & 6 & \text{ } & 6 & \text{ } & 1 & \text{ } & -\$1 \\     8 & \text{ } & 4 & \text{ } & 6 & \text{ } & 5 & \text{ } & \$1 \\     9 & \text{ } & 6 & \text{ } & 4 & \text{ } & 2 & \text{ } & -\$1 \\     10 & \text{ } & 1 & \text{ } & 1 & \text{ } & 6 & \text{ } & -\$1 \\     11 & \text{ } & 4 & \text{ } & 3 & \text{ } & 5 & \text{ } & \$1 \\     12 & \text{ } & 5 & \text{ } & 6 & \text{ } & 3 & \text{ } & \$1 \\     13 & \text{ } & 4 & \text{ } & 6 & \text{ } & 5 & \text{ } & \$1 \\     14 & \text{ } & 3 & \text{ } & 4 & \text{ } & 1 & \text{ } & -\$1 \\     15 & \text{ } & 6 & \text{ } & 4 & \text{ } & 6 & \text{ } & -\$1 \\     16 & \text{ } & 2 & \text{ } & 4 & \text{ } & 3 & \text{ } & -\$1 \\     17 & \text{ } & 6 & \text{ } & 2 & \text{ } & 3 & \text{ } & -\$1 \\     18 & \text{ } & 5 & \text{ } & 5 & \text{ } & 4 & \text{ } & \$2 \\     19 & \text{ } & 1 & \text{ } & 5 & \text{ } & 5 & \text{ } & \$2 \\     20 & \text{ } & 5 & \text{ } & 4 & \text{ } & 6 & \text{ } & \$1    \end{array}

In the above 20 plays, the total winning adds up to $4. So the player is ahead. If he/she quits the game at this point, that would be a good night. The average winning in these 20 games is 4 / 20 = $0.20 (20 cents per game). According to the calculation based on Table 2, the expected payout is negative 8 cents per $1 bet. Does that mean Table 2 is wrong? The short run results of Chuck-a-Luck (or any other gambling game) is unpredictable. The player can win big or lose big or stay even in a small number of games. The following graph shows the average winning of the first 1000 simulated plays of the game. The graph plots the average of first game, the average of the first 2 games, the average of the first 3 games, and so on all the way to the average of the first 1000 games.

Figure 1
Long Run Averages in the First 1000 Games
chuck-a-luck-long-run-graph-1000-plays

The average winning is for the most part positive (staying above the zero) during the first 100 games. But after 200 games, the average is clearly in the negative territories. The end result of the first 1000 simulated games is a loss of $79, giving a payout of -$0.079. The following shows the long run averages in the 100,000 simulated games.

Figure 2
Long Run Averages in 100,000 Games
chuck-a-luck-long-run-graph-100000-plays

The graph is Figure 2 is for the most part a horizontal line below zero, except for the one spike at the beginning. The end result of the 100,000 simulated plays is a loss of $8057. Out of 100,000 bets of $1, the player has a loss of $8057. The average payout is -8057 / 100,000 = -$0.08057, which, though slightly higher, is in general agreement with the the expected payout of -$0.079.

___________________________________________________________________________

The Law of Large Numbers

The lesson is clear. The short run results are unpredictable. The first 20 games in Table 4 are actually profitable for the player. The first 100 simulated games have ups and downs but the averages are mostly above zero (Figure 1). The remainder of Figure 1 and the entire Figure 2 indicate that the long run average winning (actually losses in this case) is stable and predictable – the loss of about 8 cents per $1 bet. Any player who has sustained large losses and is trying to make up for the losses by playing more and more games should think twice.

The 100,000 simulated plays of Chuck-a-Luck demonstrated in Figure 1 and Figure 2 are just one instance of a simulation. If we perform another instance of simulations, the results will look different. But the long run results and averages will look stable and similar to the results shown above. That is, any long run results (simulated or actual playing) will have slightly different ups and downs from Figure 2 but will eventually settle at the average of -$0.079.

Thus the long run average results of playing Chuck-a-Luck are stable and predictable and will eventually settle around the loss of 0.08 (8 cents). This is the essence of the law of large numbers. In any random experiment, as more and more observations are obtained, the averages will approach the theoretical average. This applies to the game of Chuck-a-Luck or any other gambling games.

The game of Chuck-a-Luck is a good game. It can be played for entertainment or for giving to a charity. In either case, an individual player usually stops playing once the “budget” is depleted – the amount that is set aside for losing or for giving. Playing more and more games to recoup the losses after a losing streak will just lead to a deeper and deeper spiral of losses. Using the game as an “investment” vehicle is a sure recipe for financial ruin. Figure 2 should make that clear.

As indicated above, the house edge of 8 cents per dollar bet. There are other gambling games with better odds for player. For example, the house edge for the game of roulette is only 5.26 cents per dollar bet (see here for more information). This previous post has another take on the law of large numbers.

___________________________________________________________________________
\copyright \ 2016 \text{ by Dan Ma}