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%).

Getting the Full Set

I recently wrote about some different forms of probability distributions, Binomial, Multinomial, Geometric and Poisson. Today I want to address a pretty type of problem that doesn't fit any of those.

Everybody who plays around much with recreational mathematics has encountered the famous "birthday problem." It is often stated similar to this: "How many randomly selected people must be assembled so that the probability that at least two of them have the same birthday is at least p (for some specific p, often 1/2)."

But today I want you to think about a slightly different variation. How many people (on average) would you have to gather in order to have at least one with a birthday on every day of the year" (like the birthday problem, we make some assumptions that are not exactly true... births occur with equal probability on every day of the year (they don't, see here. consider only 365 days a year, etc..)

That's probably a hard one to start, so let's break down to an easier problem. How many times should you have to flip a coin until you get at least one head and one tail?

The probability you get one of them on the first roll is 1. But how long should it take to get the "other" one. Well, each flip the probability it happens is p=1/2, and we know that the expected value of this geometric event is Ev= 1/p.. or 2 flips. So we figure that, on average, we will get both outcomes in three flips. To be suggestive, I will suggest that you see that as 2/2 + 2/1.

Ok, upping the ante a little. How many times would you have to roll a die to get all six possible outcomes? Again, break it into packets. How many times should you have to roll until you get one of the six outcomes? Good, you recognize that ONE of them has to happen on the first roll. Now to get one of the five others on the following rolls has a probability of 5/6, so it should take only 6/5 rolls (on average) to get a second outcome. By now you can see we will probably end up with 1+6/5+6/4+...+6/1. I point out here that that can be written as .
Ok, but that summation of 1/k as k goes from one to some number is a harmonic series. It grows very slowly, and no body wants to add up 365 fractions that get very small very quickly. Fortunately, Euler came to our rescue. What Euler did was come up with a really good approximation for 1/1 + 1/2 + 1/3 + ..... + 1/n for any n... It turns out that as n gets bigger and bigger, the sum gets closer and closer to n*ln(n).. and Euler came up with a really good estimate of how wrong it would be. As n gets really big the sum of is about n ln(n) + .577. So 365 outcomes is not much more difficult to calculate than six was. (365)ln(365)+.577 turns out to be about 2154 people. So if you go to a pretty big school, maybe there is a person enrolled who has a birthday on each day of the year.

So you need a challenge.... Suppose you don't have 2154 people on campus. What if you have say 1000. Now what is the probability that there is someone on campus with all 365 birth dates.

Be the first on YOUR campus to solve it, and send the solution here. It might be easier to start by making the problem smaller.

The "Nedial" Triangle

I wrote recently about the concept of a Nedian; an extension of the idea of medians created by Professor John Satterly of the University of Toronto. I have played around a little more with the concept and come up with a calculation for the area of what I call a nedial triangle, extending the idea of a medial triangle.



Most High School students are introduced to the Medians of a triangle, and it is quite easy to show using basic high school geometry that the triangle whose vertices are the three feet of the medians has an area equal to 1/4 the area of the original triangle. In fact, it is pretty easy to show that the original triangle can be dissected into four congruent copies of the medial triangle.



If instead we use the feet of the three nedians, we get a triangle I have called the nedial triangle. I have worked out that the area of such a triangle for an n-nedian (the cevian that cuts the opposite side 1/n th of the way along the edge) will have an area of
times the area of the original triangle ABC. Since the median is the 2-Nedian, this gives the correct ratio for the medial triangles.

The image below shows the 4-nedial triangle, which has an area of 7/16 the area of ABC.



The area of the three triangles at the vertices of the original triangle will each be
times the area of ABC.

The area of the nedial triangle will grow from a minimum of 1/4 the area of ABC increasing toward a limit of one as n approaches infinity. This can be confirmed by L'Hopital's rule or simple division of the terms. The fact that the limit is also one as n approaches one points out that when the base of the nedian is more than half way along the opposite side and the "n" in the nedian must be less than 2 but more than one we are measuring the area of what Satterly called the "backward nedians" which will create a nedial triangle of the same area. n=3/2 gives the exact area of n=3 (although the triangles are NOT congruent). In general for every k-nedial the area given by the nedial with index equal to ⁿ/_n-1 has the same area.

Achillles and the Tortoise, which came first... The Easy Way, or The Hard Way

The Math Forum introduces Zeno's Paradox this way, "The great Greek philosopher Zeno of Elea (born sometime between 495 and 480 B.C.) proposed four paradoxes in an effort to challenge the accepted notions of space and time that he encountered in various philosophical circles. His paradoxes confounded mathematicians for centuries, and it wasn't until Cantor's development (in the 1860's and 1870's) of the theory of infinite sets that the paradoxes could be fully resolved. "

One of the most famous is the paradox of Achilles and the Tortoise. Here is one explanation of the tale, from a web site called, "Platonic Realms".

Zeno of Elea (circa 450 b.c.) is credited with creating several famous paradoxes, but by far the best known is the paradox of the Tortoise and Achilles. (Achilles was the great Greek hero of Homer's The Iliad.) It has inspired many writers and thinkers through the ages, notably Lewis Carroll and Douglas Hofstadter, who also wrote dialogues involving the Tortoise and Achilles.
The original goes something like this:

The Tortoise challenged Achilles to a race, claiming that he would win as long as Achilles gave him a small head start. Achilles laughed at this, for of course he was a mighty warrior and swift of foot, whereas the Tortoise was heavy and slow.
“How big a head start do you need?” he asked the Tortoise with a smile.
“Ten meters,” the latter replied.
Achilles laughed louder than ever. “You will surely lose, my friend, in that case,” he told the Tortoise, “but let us race, if you wish it.”
“On the contrary,” said the Tortoise, “I will win, and I can prove it to you by a simple argument.”
“Go on then,” Achilles replied, with less confidence than he felt before. He knew he was the superior athlete, but he also knew the Tortoise had the sharper wits, and he had lost many a bewildering argument with him before this.
“Suppose,” began the Tortoise, “that you give me a 10-meter head start. Would you say that you could cover that 10 meters between us very quickly?”
“Very quickly,” Achilles affirmed.
“And in that time, how far should I have gone, do you think?”
“Perhaps a meter – no more,” said Achilles after a moment's thought.
“Very well,” replied the Tortoise, “so now there is a meter between us. And you would catch up that distance very quickly?”
“Very quickly indeed!”
“And yet, in that time I shall have gone a little way farther, so that now you must catch that distance up, yes?”

“Ye-es,” said Achilles slowly.
“And while you are doing so, I shall have gone a little way farther, so that you must then catch up the new distance,” the Tortoise continued smoothly.
Achilles said nothing.
“And so you see, in each moment you must be catching up the distance between us, and yet I – at the same time – will be adding a new distance, however small, for you to catch up again.”
“Indeed, it must be so,” said Achilles wearily.
“And so you can never catch up,” the Tortoise concluded sympathetically.
“You are right, as always,” said Achilles sadly – and conceded the race.

I imagine even in 450 BC it was common to have a faster person overtaking a slower person, so Zeno's real question was not about does Achilles really catch the tortoise, but more about the relationship of time and motion.

One way to solve it employs only simple algebra. The tortoise starts at position 10, and runs 1 meter per unit of time, t, so he will be at 10 + t meters for any t greater than zero. The speedy Achilles will start at 0 and advance 10 meters per unit of time, so he will be at 10 t meters. We seek the moment of capture when the two distances are equal, and the easy algebra gives t= 10/9 or 1 ¹/₉ units of time, so Achilles will have covered 11 ¹/₉ meters. The tortoise will have covered 1 ¹/₉ meters.

"Easy Peasy", as the British folk say. But there is another way to do it, a somewhat harder way, using a geometric series. As the tortoise said, by the time Archimedes moves the ten yard head start, the tortoise will move one yard.. and in fact, during each interval that Achilles moves to catch up with the tortoise, the tortoise will move 1/10 of the distance Achilles moves. In successive pursuits then, Achilles will move 10, 1, .1, .01..... meters. The sum of the geometric series is the same as above.

It appears that the first person to solve this using the infinite series was Gregory St. Vincent in 1647. Ok, I can accept and appreciate that. In fact his method was sort of a "limit" process. Here is an explanation of the importance of his method from a website at Fairfield University.

Gregory (St Vincent) was the first to apply geometric series to the "Achilles" problem of Zeno (in which the tortoise always wins the race with the swift Achilles since he has an unbeatable head start) and to look upon the paradox as a question in the summation of an infinite series. Moreover, Gregory was the first to state the exact time and place of overtaking the tortoise. He spoke of the limit as an obstacle against further advance, similar to a rigid wall. Apparently, he was not troubled by the fact that in his theory the variable does not reach its limit. His exposition of the "Achilles" paradox was favorably received by Leibniz and by other geometers over a century later.

OK, now read the bold (I added the emphases) again. Can that be true? Viete had come and gone with his novel use of letters as variables; was it still possible that no one had solved the problem algebraically? As improbable as that seems, I found the exact same quote (obviously the uncredited source of the above) in Cajori's, "A History of Mathematics" on page 182.


Comments?