# Tag Archives: probability

## Card Probability

Suppose that a deck of 52 cards has been shuffled and placed face down. You draw 1 card but do not look at it. You place it face down and off to the side. What is the probability that you drew the Ace of Hearts?

Since there is 1 Ace of Hearts in the deck and 52 cards total, the probability is 1/52.

Now you prepare to draw a second card. What is the probably that the new card is an Ace of Hearts? Is it more likely than before? Less likely? The same? Impossible to know?

To determine the answer, we need to use a probability tree. Here are all the different options that could occur:

If we first drew the Ace of Hearts and placed it face down, there is no chance of drawing the Ace of Hearts for our second card. However, if we didn’t draw the Ace of Hearts, then our second card could or could not be the Ace of hearts.

To compute probabilities, we multiply. We want to determine the probability of drawing an Ace of Hearts on the second card. Hence, we multiply the probability of “Not Ace” by the probability of “Ace.”

The above fraction reduces to 1/52. This is the same probability as before! We could apply this logic to drawing a third card (assuming we didn’t peak at the second card). We would find that the probability of drawing the Ace of Hearts is still only 1 in 52. No matter how many cards you remove, the probability doesn’t change. Why is this?

One way of understanding this enigma is to consider the information you have. At the beginning, you know that there are 52 cards and 1 specific card you are looking for. Once you start drawing cards, although you keep removing the cards from the deck, you don’t know which cards you are removing. You could be removing the Ace of Hearts, or you could be removing random cards. You don’t gain any new information with each card you remove. So each time you have the same probability as in the beginning.

Or consider another scenario. Suppose I draw a card from the bottom of a full deck. What is the probability that it is an Ace of Hearts? Since the deck is shuffled, the probability should be 1/52. But to get to this card, I could have physically removed all 51 cards above it (without looking at them), placed them in a pile, and then selected the bottom card. Having a pile of unknown cards does not change the probability of the remaining card being an Ace of Hearts.

Filed under Uncategorized

## Matching Tests Proof

Warning, this post uses some fierce math to prove why the pattern continues in the last post. If you want to know why the pattern continues, then welcome to the explanation.

In the last post we counted how many ways to hand student back their tests so that no student had his or her own test. This type of matching has a special name, a derangement. For a group of n students we denote the derangement as

!n

To determine this quantity we need a formula. From before, we know that !3 = 2 and !4 = 9. Now consider the general case. How many ways are there of handing back a test to the first student? We certainly can’t give him his own test. However, we could give him any of the other n – 1 tests. Let’s say we give him test i.

We could hand out the next test to anyone. Let’s consider handing it out to student i (the student with test i). We have two options. First, student i gets student 1’s test. Here is a picture:

Once these 2 students have been assigned their tests, we have n – 2 students who still need tests. However, assigned them tests is analogous to our original problem, and we can denote this as !(n – 2).

Second, student i does not get student 1’s test. Thus, student i has 1 forbidden test. All the other students also have 1 forbidden test (namely their own test). Again, this is analogous to our original problem with n – 1 students (since we have not given student i a test yet). We can denote this as !(n – 1).

To summarize, to hand out n tests, we have the following recursive formula:

$!n = (n-1)(!(n-1) + !(n-2))$

We can use this formula to calculate derangements as high as we like, provided we proceed in order.

!5 = 4(!4 + !3) = 4(9 + 2) = 44

!6 = 5(!5 + !4) = 5(44 + 9) = 265

These are exactly the numerators we found when computing the fractions in the previous post!

To determine what would happen in a large class, we need a closed form for derangements. To simplify the notation for the next section, we will denote !n as D(n).

Observe the following pattern:

 D(n) D(n)-nD(n-1) D(4) = 9 9 – 4*2 = 1 D(5) = 44 44 – 5*9 = -1 D(6) = 265 265 – 6*44 = 1 D(7) = 1854 1854 – 7*265 = -1

We can prove the above pattern continues using induction. The base case has been dealt with above. Our inductive hypothesis is:

$D(n) - nD(n-1) = (-1)^n$

Consider n+1:

$D(n+1) - (n+1)D(n) = n(D(n)+D(n-1)) - (n+1)D(n)$ using the recurrence relation

$= nD(n) + nD(n-1) - nD(n) - D(n)$

$= nD(n-1) - D(n)$

$= -(D(n) - nD(n-1))$

$= -(-1)^n$ by the inductive hypothesis

$= (-1)^{n+1}$

Using this information, we have a new recurrence relation for D(n):

$D(n) = nD(n-1) + (-1)^n$

Unfortunately, this is still not a closed form solution. However, we will use induction again to get us the rest of the way. The following is the closed form solution for D(n):

$D(n)=n!\sum_{k=0}^n\frac{(-1)^k}{k!} = n! \left( \frac{1}{0!} -\frac{1}{1!} +\frac{1}{2!} - \frac{1}{3!} + \dots + \frac{(-1)^n}{n!} \right)$

Checking the OEIS, we find that D(0) = 1 and D(1) = 0. Using the formula for D(3), we can see that the base case will hold:

$D(3) = 3! \left( \frac{1}{0!} -\frac{1}{1!} +\frac{1}{2!} - \frac{1}{3!} \right)$

$= 6 \left( 1 -1 + \frac{1}{2} - \frac{1}{6} \right)$

$= 6 \left(\frac{3}{6} - \frac{1}{6} \right)$

$= 6 \left(\frac{2}{6} \right)$

$D(3) = 2$ as expected.

Suppose the formula is true for D(n). Consider D(n+1):

$D(n+1)= (n+1)D(n) + (-1)^{n+1}$ from the new recursive formula

$= (n+1)n!\sum_{k=0}^n\frac{(-1)^k}{k!} + (-1)^{n+1}$ using the inductive hypothesis

$= (n+1)!\sum_{k=0}^n\frac{(-1)^k}{k!} + (-1)^{n+1}$ definition of factorial

$= (n+1)!\sum_{k=0}^n\frac{(-1)^k}{k!} + (-1)^{n+1} \frac{(n+1)!}{(n+1)!}$

$= (n+1)! \left[ \sum_{k=0}^n\frac{(-1)^k}{k!} + \frac{(-1)^{n+1}}{(n+1)!} \right]$

$= (n+1)! \sum_{k=0}^{n+1}\frac{(-1)^k}{k!}$

Thus, the formula is true for any n. This formula is closed, but complicated. The last step in the process is to relate derangements to our original problem. Since we were looking for a probability, we were really interested in $\frac{D(n)}{n!}$. Using the Taylor series approximation for e-1 we get the following:

$\frac{D(n)}{n!} = n! \left( \frac{1}{0!} -\frac{1}{1!} +\frac{1}{2!} - \frac{1}{3!} + \dots + \frac{(-1)^n}{n!} \right) \frac{1}{n!}$

$= \left( \frac{1}{0!} -\frac{1}{1!} +\frac{1}{2!} - \frac{1}{3!} + \dots + \frac{(-1)^n}{n!} \right)$

$\approx e^{-1}$

Finally! We have our answer! Since the number of students determines how many terms of the sequence for e we use, the approximation is valid for even small classes of only 10 or 15 students. The probability of handing out tests properly is approximately $e^{-1} = \frac{1}{e} = \frac{1}{2.71828} \approx 37\%$

1 Comment

Filed under Uncategorized

## Matching Tests

An interesting coincidence happened today in class. My co-teacher was handing the students back their tests. She wanted each student to mark another’s test. However, she accidentally handed a student back her own test. She casually said to me “weird, what are the chances of that?” Her question implied that this was a rare event. The answer is quite the opposite.

My co-teacher had a 63%, or $\frac{e-1}{e}$ to be precise, chance of handing a student back his or her own test. If you are wondering, e stands for a special number:

e = 2.71828…

This percentage is not good. It means that, if you randomly distribute tests to students to mark, about two thirds of the time at least 1 student will end up with his or her own test!

How in the world did I come up with that answer? Let me back up a bit. Suppose we had 3 students and we wanted to give them back their tests to mark so that no student had his or her own test. What options do we have? One option is:

Student A: test B

Student B: test C

Student C: test A

Another option is:

Student A: test C

Student B: test A

Student C: test B

Hence, we have 2 options where we will hand back the tests with no matches. How many options do we have in total?

3! = 3*2*1 = 6

Thus, there is a 2/6 = 33.3% chance that everyone has a different test. In other words, there is a 66.6% chance that at least one student receives his or her own test to mark (which would not be good for academic standards).

What if we had 4 students? You can do the math, and you will find that there are 9 options where the students have different tests. For example:

Student A: test B

Student B: test C

Student C: test D

Student D: test A

Again, basic counting principles dictate that there will be 4! = 24 different possible combinations. Hence, there is a 9/24 = 38% chance each student will have a proper test to mark. We could continue on like this; painstakingly grinding out the probabilities for each situation until we reached a class size of 25. However, there is a pattern we can exploit. Consider the following table:

 Number of Students Fraction of proper distributions 3 2/6 = 33% 4 9/24 = 38% 5 44/120 = 37% 6 265/720 = 37% 7 1854/5040 = 37% 8 14833/40320 = 37%

Do you see the pattern? Once the class size gets to 5, the percentage becomes stable. Based on the above data, we could predict that a class of 25 students will have roughly the same percentage, 37%. Indeed, one can prove mathematically that this percentage will be true for any size class, large or small.1 Thus, my advice to teachers is as follows. Be careful distributing tests to students to mark. You are playing a game with a 37% chance of winning. And any gambler knows, those are not good odds.

1See next blog post.

1 Comment

Filed under Uncategorized

## Probability Sums

The other day as I was perusing the MTBoS, I found an interesting problem.

“5 distinct numbers are chosen at random from {1,2,3,4,5,6,7,8,9}.

P(k) = probability their sum = k.

What are some of the ways you can find this in general?

What sum is/are the least likely?

Which sum is/are most likely?”

http://matharguments180.blogspot.ca/2014/10/269-probability-sums.html

At first, I started trying to make different numbers with different sums. For example: choose 2,3,5,6,7 and you get 2+3+5+6+7 = 23.

Then I realized there would be many possible sums. 126 in fact.1

I didn’t really feel like working with all 126 of those different sums so I wrote a quick script in Python to do it for me. Here are the results:

You can clearly see that 25 is the most likely sum with 12 ways of making 25. For fun, here are all 12 ways of making 25:

 [1, 2, 5, 8, 9] [1, 2, 6, 7, 9] [1, 3, 4, 8, 9] [1, 3, 5, 7, 9] [1, 3, 6, 7, 8] [1, 4, 5, 6, 9] [1, 4, 5, 7, 8] [2, 3, 4, 7, 9] [2, 3, 5, 6, 9] [2, 3, 5, 7, 8] [2, 4, 5, 6, 8] [3, 4, 5, 6, 7]

Also, 15, 16, 34, and 35 are the least likely sums. Since the table is symmetric about 25, this also means that, on average, your sum will be 25. Problem solved.

1You have to select 5 numbers from the set of 9 total. This corresponds to the mathematical idea of “choose.” We have 9 choose 5 = 126 possible options

Filed under Uncategorized

## Silent Auction

I was at a friend’s party the other day and it got me thinking about silent auctions. For those of you who don’t know, a silent auction is kind of like a draw. There are different prizes and each prize has a bag next to it. You buy tickets and put your tickets in the bags next to the prizes you hope to win. At the end of the night, one ticket is drawn from each bag to decide the winner.

The question I had was this: suppose I want to win a prize. Should I put all my tickets in one bag, or should I distribute my tickets among all of the bags?

To attack this problem I am going to simplify the situation. I want to address the probabilities involved in the two strategies. Now I can already hear some of you saying “but that’s not real life.” I know it’s not real life. However, to understand real life, we are often required to investigate a simpler version of the problem first. Then we can build back in the complexity of real life later.

At my idealized silent auction, each prize is of equal value and desirability. Suppose there are only two prizes, a red gift card and a blue gift card. Further, suppose each bag has 10 tickets in it already and you are the last person putting in tickets. Let’s start by buying 2 tickets.

In strategy one, you put both of your tickets into the bag for the red gift card. Now that bag has 12 tickets in it and 2 of them are your tickets. Hence, basic probability tells us that your chance of winning is 2/12 or 16.7%.

In strategy two, you put one ticket in each bag. Now the red gift card bag has 11 tickets in it and 1 of them is your ticket. Hence, your chance of winning the red gift card is 1/11 or 9.1%. The blue gift card bag has 11 tickets in it and 1 of them is your ticket. Hence, your chance of winning the blue gift card is 1/11 or 9.1%. We then add up these probabilities*, and our chance of winning one of the gift cards is 17.4%.

Clearly 17.4% > 16.7%. Hence, our second strategy seems better. What if we had more tickets of our own, say 10.

In strategy one, you put all of your tickets into the bag for the red gift card. Now that bag has 20 tickets in it and 10 of them are your tickets. So 10/20 or 50.0% chance of winning.

In strategy two, you put 5 tickets in each bag. Now the red gift card bag has 15 tickets in it and 5 of them are your tickets. So 5/15 or 33.3% chance of winning. The blue gift card bag has 15 tickets in it and 5 of them are your tickets. So 5/15 or 33.3% chance of winning. We add up these probabilities**, and our chance of winning one of the gift cards is 55.5%.

Strategy two seems to be gaining significant ground. What if there were 3 prizes? I guarantee you that strategy two is better. I’ll leave this situation as an exercise for the reader to verify.

Here is my intuitive explanation as to why strategy two is better. The problem with dumping all of your tickets into a single bag is that it dramatically increases the number of tickets in the bag. All of your tickets have to fight against each other to try to win the same prize. When all of your tickets are spread out in different bags, they don’t have to compete with one another and you gain a higher probability of victory.

There you have it. If you want to optimize your chances of winning a prize at a silent auction, distribute your tickets evenly among all the prizes. And when you win yourself that big 60’ TV, remember to thank math.

*To add up these probabilities we need to use a bit of sophisticated math. We don’t just add up the percentages of each event occurring.

Think of finding this probability as finding the area of two overlapping circles. We can take the area of event A and add it to the area of event B. But that means that we double counted the area where the two circles overlap. Therefore, we have to subtract off this area,

Below is a diagram of how the “addition” works.

We use the following formula:

Probability (A or B) = Probability (A) + Probability (B) – Probability (A and B)

17.4% = 9.1% + 9.1% – 0.8% (0.8% is the probability of winning both prizes, 1/11 * 1/11 = 1/121)