Back of the Envelope Answers to a Hard Problem

In a comment "td" asked if I was going to answer the last question I asked in my blog on a variation of the birthday problem. The question asked the probability that a random selection of 1000 people would include a person with every birth date for all 365 calendar days of a non-leap year.

I had not done the problem, but figured from its nature that it was of a size to be difficult to calculate, but theoretically not too difficult.

I thought of three ways to try and attack it. I was pretty sure it could be done exactly with Markov matrices (more later) if software was available to raise a square matrix of order 365 to the 1000th power. I will illustrate how this might be done with a much smaller problem.

I thought it could probably be approximated really well by using a combination of simulation and statistics... I will do that with also with a smaller problem.

And I thought you could convince any reasonable reader with a bit of basic logic that it was a very, very, low probability... I'll do that now.

I reasoned that the probability of finding all B-days would be small if the probability of failing for any particular day was only relatively small, so I set out to try and find the probability that any given date (they will all be the same) did not appear in the list of Birthdays of the sample. This part of the problem is actually binomial. The birth dates of the random sample are independent of each other, and with a large population to draw from, the probabilities of getting any date on any person selected will be essentially the same. For a particular date, we can say that the probability that a person selected would NOT have that date of birth is 364/365. So the probability of 1000 people being selected who all did NOT have that date is (364/365)¹⁰⁰⁰. My Ti-84 calculator barely blinked to compute .06434 for the probability. Since the probability of each success is a really small, 1/365, we could also use the Poisson with a mean of 1000/365 and find the probability of zero successes. That comes out to .0645 on my calculator.

Once we know the prob of any date not showing up is about .06, we might assume that for 365 dates, even with their lack of independence, the probability of getting all dates in a sample of 1000 would be pretty low.

To see how low, I thought I would try to simulate a few trials and see how often I was successful. I wrote a short program for the TI-84, but it took a long time to run (probably bad program more than bad device) so I switched over and wrote used a spreadsheet run off 1000 random integers between 1 and 365. Then I had it how how many times each of the numbers appeared in the list. Finally I just multiplied these counts all together. If it came out one, then there was at least one birthday missing. It took a little longer to lay out, but it would run a test in a few seconds. Then I got a little more clever and just copied the whole thing across for 100 columns. Now I could run 100 trials at a time..(this time the computer blinked).

I ran that five times, for a total of 500 simulations, and never got a full set of birthdays. That made me wonder if it was working correctly, so I extended the list to 2000 random integers. Now I started to get some hits. It was working after all.

One of the beautiful things about statistics is that you can approximate the probability of something happening that has never happened if it has never happened with enough opportunities to happen. In this case we were 0 for 500. Statistically that doesn't mean the probability is zero. But there is a clever rule of thumb that says if it has not happened in n trials, the probability of happening on any trials is less than 3/n with about a 95% confidence.(How we do that in another blog later.) So I'm figuring that the probability of a full set of birth dates in a group of 1000 is about 3/500 or less.

I wanted to do an exact calculation using Markov Matrices, but none of the software I had access to would handle raising a really big matrix to such a high power. Still, it is a beautiful way to handle (smaller) problems like this so I thought I would illustrate the process for students with a mini version of the problem.

Suppose instead we had picked seven students from a large high school and wanted to know the probability that we would get one from each of the freshman, sophmore, jr and senior classes. The birthday problem for 10000,365 scaled down to 7,4.

We will treat the process as if people were selected one at a time. After the first person is selected, since they will obviously have some birth date, we will say we are in state 1. As each new person is added to the mix, we will move to the next higher state if they have a different birthday to everyone already present, and remain in the previousl state if they match one of the other dates. We can illustrate this with a "State Diagram", a graph of the probability of moving from one state to another as each person is introduced into the mix.



In state one, all the people up to that point have had a single birth date. The probability the next person has a different birthday and moves us to state two is 3/4, and the probability that they have the same birthday as everyone else so far is 1/4. The red lines show the probability of moving from one state to the next, while the blue lines show the probability of staying where they are.

To find the probability we are in any state after n selections we must add the probability we just moved there from a lower state with the probability we were already in that state after n-1 selections. To accomplish this multiplication process we embed the probabilities in a transition matrix. Each row and column gives the probability that you move from the row-state to the column state. For example, row 2 column 3 gives the probability that you move from state two to state three on any selection.
The zeros indicate impossible transitions, like moving from state one to state four on the next person. The one in row 4 column 4 says that once you have all four birthdays, you stay there. This is called an absorbing state.

Now the pretty part. This matrix tells us the probability of being in any state after two poeople (because we started after the first person put us in state one).
The probability we are still in state one is 1/4, and the probability we are in state two is 3/4. Now to find the probability after a third person is selected, we simply multipy our present matrix state by this matrix... we square our transition matrix. Now we have the probability of being in each state in the first line. Notice that this is after three people... two have been added to the original person who put us in state one.
You can check these manually. To be still in state one, we must have had both the 2nd and third person have the same birth date as the initial person, a probability of (1/4)(1/4)=1/16. To be in state three, the second must have differed from the first and the third must have differed from both the others. The probailities in order are 3/4 and 1/2 so there is a 3/8 probability of this outcome after three people. The probablitly of state two is now what is left to total one.
So after seven people, six beyond our initial person, we want to raise the matrix to the sixth power. The top row gives us the probability of being in any of the states after seven people. .

For seven people, the probability we have found all four birthdays is about 52%.

Which means I can solve the problem with 365 birthdays and 1000 people exactly, I just need someone to loan me the money to rent a big Cray Computer for a few seconds.... "anyone, anyone......Bueller?"

*** FOOTNOTE: I got a comment from Jon Ingram that says (in much nicer words) that my inability to find the 1000th power of a 365x365 matrix was a matter more of my ignorance than restrictions in computing power that is readily available. Math teachers should be aware of the power that is out there to do this kind of stuff, much of it either very modestly priced, or free. Here is Jon's comment, with my appreciation... I'm old, but I'm not done learning...

You don't need a Cray! It took my computer (using Python with the Numpy extension) about 10 seconds to calculate the 1000-person, 365-days matrix. It looks like you shouldn't be surprised not to find all the birthdays, as the probability of getting to that state is around 1.7e-12. The most likely outcome is 342 distinct birthdays (probability around 9.4%).

The 28 Year Snow and The 100 Year Flood

Europe just went through one of its worst winters in years, and according to the press, the largest snowfall in England for 28 years (and apparently similar effects in the US.. that darn El Nino). The last this big in Europe was 1982. That doesn't actually make it a 28 year Snow, in the sense of a 100 year flood. Most people don't realize that the probability of having a "100 year flood" in any 100 years is only about 63% (go on, say "Huh?").. Officially, a 100 year flood is a flood that has a 1/100 chance of happening in any given year (I think, technically, they say the probability of a flood that great or greater). You can use a little easy probability to see why it would only have a 63% probability of occurring in the next 100 years (even if it hasn't occurred in 200 years, or if it happened yesterday.. the assumption is that the great floods are essentially independent events). So the probability of having (at least one) "100 year flood" in the next 100 years is just 1- (the probability that we don't have one)..which is easier to compute. The probability of NOT having a 100 year flood this year is .99 or 1- the probability that we do.. The probability we don't have one in the next 100 years is just (.99)¹⁰⁰ which my trusty calculator tells me is about .366. So it there is a .366 chance of NO great flood, then there is a .634 chance of having at least one.
"You mean there might be MORE than one?" I hear you ask. Well yes, now we just apply the binomial distribution to find, for example, the probability of great floods in two of the next 100 years (and not in 98 others) and accounting for all the possible orders, we get $\dbinom{100}{2}(.01)^2(.99)^9^8$ or about 18.5%; and if you extend that to exactly three great floods, the probability comes out to about 6%... so there is something like a 36% chance of NOT having a great flood, and about a 40% chance of just one. (It takes about 230 years to be 90% sure of having a 100 year flood; and almost 300 years to be 95% sure).

Now if we said, Wait, a "100 year flood" should have a probability of almost one of happening (would you settle for the proverbial 95% standard from statistics?) then we could work backwards and compute the probability of such a flood this year (or any random year). Since the probability of not having one in 100 years is 1-.95, all we have to do is solve the problem (1-p)¹⁰⁰ = .05 and we get the annual probability of such a flood. Surprisingly, that puts the probability up to about 3% (.0295..)

So if we assume that this winter was the traditional "28 year snow" by the normal definition (ie, one that has a 1/28 chance of occurring) then the probability that it happens again next winter is 3.57% ( a little greater than our "certain 100 year flood". So how likely is THAT to happen in the next 28 years...... (you are soooo gonna love this) .... about 63%, to be slightly more precise, about 63.87%...

Hmmm (wheels turning in your mind)... that's almost the same answer..... "COINCIDENCE? " I ask my students; and they know the proper reply..." I THINK NOT!". So what is happening here. If the probability of an n-year flood is 1/n, then the probability of one occurring in the next n years is given by Prob(flood)=1-$[\frac{n-1}{n}]^n$.. and if we plot this we see that it very quickly becomes asymptotic to about .63... or 1-(¹/_e); which is perfectly understandable since the limit as n goes to infinity of $[\frac{n-1}{n}]^n$ is e^-1; or about .36.

Which means, for anything more than a ten year event or so, the probability that it happens in the next N years is always about the same...about 63%... Many questions, one answer.... ahhhh ... gotta love it.

A Limit Approach to a Classic Geometric Probability Problem

One of the common problems from probability texts is : "A stick is broken into three parts. What is the chance that the sum of the lengths of eveiy two is greater than the length of the third that is that the three parts will form a triangle?"

The traditional method for an area approach for pre-calculus students is to begin by assuming the stick is of unit length, and the breaks occur at distances of x, and x+y from one end, giving three pieces of length x, y, and 1-x-y. Then a graph of all possible outcomes can be found by graphing the lenghts x and y on the coordinate plane. The regiong bound by x>0, y>0 and x+y<1 defines a triangle containing all possible solutions. To find the subset which will fit together to form a triangle, we think about the basic triangle inequality from plane geometry; "any two sides must be greater than the third side." That restriction means x <1/2, (otherwise, the other two sides will be less than x) and similarly y<1/2. Finally, since the remaining part, 1-x-y must also be less than 1/2, x+y > 1/2. By adding these three lines to our graph, we see that solutions which make a triangle form must fall into the smaller triangle, which is 1/4 of the total sample space of outcomes.


I was reminded of this problem by an article in the Mathematical Spectrum, Vol 2, #2. by L. Rade. He begins with a finite version of the problem. A stick of length five units is cut into five equal spaces with six endpoints at A₀ to A₅.

Two of the four interior points are selected at random and the stick is broken at those two points. What is the probability that the broken pieces form a triangle?


He shows that there are $\dbinom{4}{2}$ , or 6 ways to break the stick, and only three of those will form a triangle. He then uses the lengths of the first two sticks (from the left) to plot a point on the xy plane to show the sample space of all solutions, and then a subset of those that form a triangle.
Then he proceeds to show that for five, six, seven, and eight points equally spaced on the stick, the probabilities of getting a triangle are 1/2, 1/10, 2/5, and 1/7 respectively. Finally he generalizes the previous graph to n points


and shows that the total number of points in the sample space is the triangular number for n-2, $\sum_{i=1}^{n-2}i = \frac{n^2-1}{8}$ .
Then he shows that the number of points in the sample space is given by a different formula if n is even or odd, and produces the probability of forming a triangle as [and guess who is doing piece-wise functions right now in pre=calc]
Finally, we derive the answer for an infinite number of possible points by letting n go to infinity and examine the graph of P(n)
I think this might be a very effective way to present this problem, and probably end up with a little less of the glassy eyed stare when you finish; and it might also provide a good model for them to attack geomtric probability problems in the future.

A history note:
Dr. David Singmaster's web page on the chronology of recreational mathematics gives "1873 Lemoine considers Probability that Three Lengths Form a Triangle." However, I have found the problem presented in the 1865 "A treatise on infinitesimal calculus" by Bartholomew Price. . I have asked Dr. Singmaster to comment, and if he has additional detail, I will include it here in a future edit.
and a followup question Given that the broken stick forms a rectangle, what is the probability that the triangle is acute? I just noticed after I had typed all this, that the followup question was sent to the Mathematical Spectrum by the same Dr. David Singmaster I have referred to above.

And a followup history note: J. J. Sylvester was the first to pose this question in 1865, according to David Singmaster's chronology.


just ... fiddling around.. , this is me trying to write piecewise functions in LaTeX
\$f(x)=\begin{cases}
\frac{n-4}{4(n-1}&\text{for n even } \\
\frac{n+1}{4(n-2)}&\text{for n odd} \end{cases} \$