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.

More Harmonic Thoughts

I got a note after my last post that reminded me how little Julian Havel seems to be known in the US. Denise, of Let's Play Math, related that her local library had NO books by him. Impossible... No, I don't mean that it is impossible they have no books by him (it should be)...but that is one of his really good books.



Havel is (or was) a headmaster at a British College (sort of like the last year of our HS in the US).

In his book, Impossible, he has a chapter on the Harmonic Series in which he mentions a couple of more interesting notes I might have added for students.

For example, it is quite easy to see that H₁= 1, and H₂= 3/2. H₆= 1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 = 2 9/20... and those three are the only ones in the entire infinite series that end in a terminating decimal. Havel states that, "it can be proved" but does not... anyone know an tractable proof for that to approach Pre-calc students?

Another quick point to mention is the extremely slow rate at which the function diverges.... Ralph Boas Jr was co-finder of the smallest n for which H_n> 100. It turns out it takes more than 15 10⁴² terms to reach 100. Which means it is adding less than .01 each step... and yet... as Borovik cautions us... It Diverges..

A Nice Presentation of the Harmonic Series

Here is a nice video here about the Harmonic series. I would love for all my Pre-calc and calc students to see this video just to see the really nice proof by contradiction that the series is infinite. The paradox itself is just a bonus, and the fact that the squares add up to a value involving pi is a beautiful story that ought not to be popped out as an aside... sometimes we need to take the time to dig a little deeper into what Euler has given us... but a nice presentation all the same. Enjoy, but remember the adomonition that Borovik gave to his students,

" Today I said to the calculus students, "I know, you're looking at this series and you don't see what I'm warning you about. you look at it and you think, 'I trust this series. I would take candy from this series. I would get in a car with this series.' But I'm going to warn you, this series is out to get you. Always remember: The harmonic series diverges. Never forget it.

For more about the harmonic series, here and here and one more here, but surely there are more...use the search function.

Different Question, Same Idea, Sort of

A couple of days ago I wrote about the probability of a 28 Year Snow and 100 year Rain. It reminded me of another problem that, seemingly completely different, is somewhat related.

Here is a version of the question... Suppose you were looking at a group of n (a large number of numbers) numbers presented one at a time. Your goal is to guess which is the largest number in the list. You get to look at one number, and say "That one." or pass, if you pass, you can never go back and the next number is presented.. How do you decide which number to pick. You could just guess one of the numbers, and when it comes along pick it.. the probability you would win is 1/n. Or you could guess that there will be approximately ln(n)+.58 numbers.. this is the limit for the harmonic series, $\sum_{k=1}^{n}\frac{1}{k}$= [1+¹/₂+¹/₃+¹/₄+...+¹/_n (for big n...and that doesn't mean huge...at n=20, the actual value is 3.597 and the approximation is 3.572) approaches ln(n) + .0.57721, which will estimate the number of record breaking events in N events, for example, record breaking floods in a 100 year period (look for about 5... ln(100)+.577 = 5.182).. and when that many record results occur, you could pick it... (this would have been my first choice)... unfortunately, the standard deviation of the number of records that occur is pretty wide, so you are not likely to win more than about 20% of the time... Still, in most cases that is better than 1/n.

But what if you decided to wait until a certain number, call it r, of events had passed, then pick the next number higher than any of the first r... But what r would you pick.

If there are three numbers, 1, 2, and 3, they can occur in six orders. If you decide to always pick the first, or second or third you would win 1/3 of the time.. Or you could wait and after the first, pick the next one that is higher... Well if 3 is first, you lose, but if the order is 1-3-2; 2-3-1; or 2-1-3 you would win, hey, that's a fifty percent chance of winning..

If there are four numbers, they can be in 24 different orders. Would it be best to let one number go, or two. If we pick the first number, we know the winning probability is only 1/4, and if we wait until the last number, it is again 1/4. But what if we let one go, then pick the next that exceeds that value... We would pick the right number in 11/24 of the orders.. If we let two go, then picked the next that exceeds those two, we would only win in 5/12 of the trials.

So how do you decide? How many numbers would you let go before you picked the next higher number. If there were ten numbers in all, for example, and you let r of them go by, the probability that the next one is the biggest (and hence you win) is 1/n. But you would also win if the next one was smaller than the max of the first r numbers [prob r/(r+1)] and the one after that WAS the largest in the set (prob 1/n again)... Or ...you could win if the next two after you stopped counting were not greater than the max of the first r numbers [probability r/(r+2)] and the following one (yep, prob 1/n) was the biggest value. Ok, you see a pattern here. So the probability of winning after waiting for any r-values is P(r) = ¹/_n[1 + ^r/_r+1 + ^r/_r+2 + ...+ ^r/_n-1] but if we factor out the r on top.. this is just ^r/_n [¹/_r+¹/_r+1...+ ¹/_n-1] and that last part is the harmonic series between ¹/_r and ¹/_n-1... If we make the assumption that r and n are pretty big then we can approximate the sum of the harmonic series out to 1/(n-1) as Ln(n-1)+ .577 and out to 1/r it would be Ln(r)+.577. Subtracting this last from the first, we see that it will be about Ln(n-1) - Ln(r) or, using the log properties you learned in Alg II, we can write that as the Ln(n-1/r)... so for any number of numbers n, if we let the first r go by and pick the next number greater than any of those, our probability of having that be a winning number is (^r/_n) Ln(^n-1/_r). All we have to do is find the maximum value of Ln(^n-1/_r) and we know how many r to let pass. For calculus students, n is a constant here, r is the variable, so we want find the maximum of (r/n)*Ln(n/r).... and for algebra students, graph it and find the max probability.

It turns out that the max happens when r=n/e... so for n= 100, we would wait for the first 1/e = 36.7 (ok, 37) numbers and then pick the next number that is bigger than any of those...and the probability you win.... 1/e or about 36.8%

And how is that related to the 100 year snow? Well, 1-.368 = .632... So the probability of picking the max value from a string of 100 numbers by this strategy is the same as the probability that you do NOT hava 100-year snow in the next hundred years... . Bundle up... the snow is more likely.... rule of the day for multiple choice.... Pick e.... ;-}