Puzzling Probability Part 3

This is part 3 of a series in which I am exploring some interesting probability puzzles.

As someone who loves to walk, probability puzzles that involve considering different routes to the same destination are interesting to me. However, this puzzle requires a warm up. Consider the following:

How many ways are there to walk from A to B (assuming no back tracking)?

path-1

At first, I tried to draw all the possible paths:

path-1-5

Then I realized that it was going to take far too long and I could never be sure that I didn’t miss a path. I needed another approach. Instead of trying to figure out how many ways there were to get from A to B, I asked a simpler question: How many ways to get from A to C?

path-1-75

Clearly, we can only get to C in only 1 way. We place a number 1 at the intersection. Similarly, we only have 1 way to get to each intersection point along the top and along the left side. Next, we need to determine how many ways to get to point D.

path-3

Since there is 1 way to get to the point above D and 1 way to get to the point left of D, we add these and obtain 2 ways to get to D. Continuing like this with each intersection point on the grid, we have:

path-4

Thus, there are 20 different ways to walk from A to B.

Now we can answer the actual question. What is the probability that a random walk from A to B (assuming no back tracking) passes through the middle of the grid below?

path-5

Using the above method, we find that there are 70 ways of walking from A to B. To count the number of ways through the middle, we simply redraw the gird to force us through the middle as follows:

path-6

Again, using the above method, we find that there are 36 ways of walking through middle.

Hence, the probability is 36/70. If you try this exercise for a 6 by 6 grid, you will find that the probability is 4900/12870.

This was counter intuitive to me. In a very large gird, if you were to randomly walk from one end to the other, it seemed to me very unlikely you would pass exactly through the center. The above solution shows that even for a 6 by 6 grid, the probability of walking through the exact center is 38%. As an extension, what do you think happens to this probably as the grid grows larger? Does it approach a specific value? Or does the probability eventually tend to zero?

Leave a comment

Filed under Uncategorized

Puzzling Probability Part 2

This is part 2 of a series, in which I am exploring some interesting probability puzzles.

Imagine a typical dice game. You roll 2 dice and compute their sum. For example, the first die is a 4 and the second die is a 3. The sum is 4 + 3 = 7. From our everyday experience with rolling dice, we know that 7 comes up most often, and numbers like 3 or 11 are rarer.

Now imagine a pair of strange dice, with the following numbers:

Die 1: 1, 3, 4, 5, 6, 8

Die 2: 1, 2, 2, 3, 3, 4

Is rolling these two dice is the same as rolling 2 standard dice? Or better yet, how could we determine if the strange dice are equivalent to standard dice?

The first idea I had was to add up all the numbers on both dice:

(1 + 3 + 4 + 5 + 6 + 8) + (1 + 2 + 2 + 3 + 3 + 4) = 42

If you add up all the numbers on two standard dice, you also get a sum of 42. At first, I thought this might be enough to confirm that the strange dice were equivalent. However, consider the following two dice:

Die 3: 6, 6, 6, 6, 6, 6

Die 4: 1, 1, 1, 1, 1, 1

The sum of the all the numbers on the above two dice is clearly 42. But the only number that comes up when rolling both is 7. For an alternate pair of dice to be equivalent to the standard dice, there should be a way of rolling a 2, or a 12, or the other numbers typically rolled from standard dice.

Creating a table is very helpful for eliciting the answer in this particular situation. Here are all the possible sums for two standard dice:

dice-1

The numbers along the outside are the standard dice numbers and the numbers on the inside of the grid are the sums. If we count up the occurrences of each sum, we have the following:

dice-2

Now, we can repeat the same process with the strange dice:

dice-3

dice-4

How interesting! The strange dice have the same sums with the same frequency as the standard dice. However, I doubt I could get away with using these dice at a casino, even if they are mathematically equivalent.

Leave a comment

Filed under Uncategorized

Puzzling Probability Part 1

In this series, I am going to explore some interesting probability puzzles. First, I want to consider a question about selecting balls from an urn.

“An urn contains four colored balls: two orange and two blue. Two balls are selected at random without replacement, and you are told that at least one of them is orange. What is the probability that the other ball is also orange?”

What an interesting problem. Take a guess at what the answer might be.

At first, I was partial to the idea that the probability would be 1/3. After you have been told the first ball is orange, there is a 1 orange ball left out of the total of 3 remaining balls.

Then, I thought the answer must be 1/6. The probability of drawing an orange on the first selection is 2/4 and the probability of drawing an orange on the second selection is 1/3. Using multiplication, we get 1/6.

Unfortunately, neither of these approaches is correct. In fact, the answer is 1/5. Why 1/5 you might ask? Let’s diagram out the situation.

I labelled the balls: O1, O2, B1, B2. We are told that of the 2 balls selected, 1 of the balls is orange. Thus, we must have one of the following situations:

O1, O2

O1, B1

O1, B2

O2, B1

O2, B2

As you can see, there are only 5 possible selections where at least 1 of the balls selected is orange. Further, only 1 of these possibilities has 2 orange balls. Thus, the probability that the other ball is also orange is 1/5.

This was very shocking to me. I did not expect such a strange answer from a seemingly simple problem.

Leave a comment

Filed under Uncategorized

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:

pic 1

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.”

pic 2

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.

2 Comments

Filed under Uncategorized

Noodles Part 1

A dish contains 100 strands of cooked spaghetti. See the picture below:Capture

Two ends of spaghetti are chosen at random and tied together. For example:

Capture2

If this process continues until there are no more loose ends, what is the probability that all strands will form one big loop? In other words, what are the chances that this big mess is actually just a circle?

Capture36

Seriously, take a guess. When I first read a version of this problem,1 I thought the answer must surely be less than 1%. Watch this:

Now you may think that I took a particularly well behaved group of noodles for the above animation. However, mathematically speaking, the probability of getting a single big loop is 9%, much higher that you probably guessed.

I want to walk you through some of the interesting twists and turns that it took for me to get the answer. First, I had to find a formula for calculating the above probability. My first method was to try less noodles. With 2 noodles, it seemed like I could figure out all the possibilities.

Capture 5

For the first noodle, I started with the left end. I could tie it to itself:Capture6

Then I would have to tie the other noodle to itself and I would not have a big loop:

Capture7

Another option would be to tie the left end to the end below it:

Capture8

Then I would tie the remaining 2 ends together to make a loop!

Capture9

My last option would be to tie the top left end to the right bottom end:

Capture10

Then I would have to tie the remaining 2 ends together:

Capture11

Do some untwisting, and make a loop!

Capture115

To recap, with 2 noodles, we have a 2/3 probability of getting a one big loop. How about 3 noodles?

Capture12

Instead of going through all the probabilities, we can use a trick. If I tie the top left end of the noodle to the right end of the same noodle, I create an isolated loop like before. That is not good. So instead, consider tying the top left end to any other noodle end:

Capture13

By doing this, we create one long noodle, which we can move around to form:

Capture14

Voila! We are back to the 2-noodle case. Since there are 4 places I could tie the top left end (green), and 1 place I cannot (red, since it would make an isolated loop) I have a 4/5 chance.

Capture15

We multiply this by the 2-noodle case to get

\frac{2}{3} \times \frac{4}{5}

You can continue this logic and find the probability for 5 noodles is:

\frac{2}{3} \times \frac{4}{5} \times \frac{6}{7} \times \frac{8}{9}

Now I noticed a pattern. Combine the top and bottom numbers:

\frac{2 \times 4 \times 6 \times 8}{3 \times 5 \times 7 \times 9}

We are actually just multiplying even numbers and dividing them by odd numbers! I was so excited! I went into excel, punched in the formula, and was thoroughly disappointed.

Capture4

Apparently, multiplying 100 numbers got excessively big for my computer to handle. I needed a new approach. The noodle probability formula can be written as follows:

f(n) = \cfrac{2 \cdot 4 \cdot 6 \cdot 8 \dots (2n-2)}{ 3 \cdot 5 \cdot 7 \cdot 9 \dots (2n-1)}

Using double factorial notation, we can rewrite it as:

f(n) = \cfrac{(2n-2)!!}{(2n-1)!!}

Using basic double factorial identities2, we can convert the double factorials into regular factorials:

f(n) = \cfrac{2^n n!}{2n} \times \cfrac{2^n n!}{(2n)!}

And use some algebra to simplify:

f(n) = \cfrac{2^{2n} n! n!}{2n (2n)!}

Enter, the Stirling Approximation!3

n! \approx \sqrt{2n\pi} \left( \cfrac{n^n}{e^n} \right)

f(n) \approx \cfrac{2^{2n}}{2n} \times \cfrac{\sqrt{2n\pi} \left( \frac{n^n}{e^n} \right) \times \sqrt{2n\pi} \left( \frac{n^n}{e^n} \right)}{\sqrt{4n\pi} \left( \cfrac{(2n)^{2n}}{e^{2n}} \right)}

We can cancel a bunch of terms to get:

f(n) \approx \cfrac{\sqrt{\pi n}}{2n} = \sqrt{\cfrac{\pi }{4n}}

Finally, a formula my computer can handle! This formula will work for any number of noodles. Maybe you were wondering what number of noodles you would need for the probability to be below 1%. The formula states that we would need 7854 noodles! Personally, if you would have told me that before analyzing the problem, I would have thought you were out to lunch 😛

1The Mathematics Teacher, Volume 109, Number 3, October 2015, page 201.

2https://en.wikipedia.org/wiki/Double_factorial

3https://en.wikipedia.org/wiki/Stirling’s_approximation

 

Leave a comment

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:

pic 1

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