An Improved Solution to the Probability Problem

My last blog gave a labored explanation of why given R red balls and W white balls in a bowl, if they are removed one at a time randomly until one color has been totally removed, what is the probability that White will be exhausted first.

Joshua Zucker gave much more elegant expalantion for the reason the probability of white being exhausted first is red/(red + white)

His solution, in my words.. forget everything except the last ball in the bowl... whatever color it is is Not the color that was exhausted. So All we have to do to know the probability that White is exhausted, is find the probability that the last ball drawn if we emptied the bowl would be red. But if we look at all the possible orders of drawing all the balls, 4/7 of the first balls drawn are red, 4/7 of the second balls drawn are red..and the same continues all the way to the end; 4/7 of the final balls drawn will be red, meaning that in 4/7 of the trials, the white balls were exhausted first.

Now I'm thinking about the case of three colors, red, white and blue. I haven't started, so if you have an easy explanation, lay it on me.... otherwise, more later.

-------------- edited afterward...
ask and you shall receive... Joshua does what he does best, thinking and explaining his thoughts on the fly... see the comment and learn ....

A Variation on a Harmonic Theme

One of the Blog sites I drop in on regularly is Sol Lederman's Wild About Math. He has a contest there about every two weeks, alternating with another site so that they produce a problem each week. The latest one is about the probability of hearing all five songs in a set if they are played randomly and you listen for eight times.. I know a way to do it..but the contest is not quite over, so I won't give that away..

But it did remind me of a related problem... Suppose you decided to set it out and wait for the band to play all five tunes. I just heard a nice talk at Gresham College by the current Gresham Lecturer in Geometry, and head of the Cambridge Dept of Math and Theoretical Physics, John Barrow about just this type of problem. The answer, somewhat nicely, is related to the harmonic sequence I wrote about before , 1/1 + 1/2 + 1/3 + ... etc...

Here is how it works... The average number of times it takes to succeed at something that has a probability of P, is 1/P... for example, the probability of rolling a one on a regular die is 1/6... if you set down repeatedly and counted how many times it would take until you rolled a one, on average it would take six trys... sometimes you might get it on the first roll, and sometimes you might have to roll 10 or 20 times...but on average, it would take six rolls...
Now lets look at the music problem... with five songs, you are going to hear one on the first try...so that is pretty easy... but what is the probablity that the next song is new?
Well, if you have only heard one song, then 4/5 of the songs will be new to you, so it will take 5/4 or an average of 1.25 songs until you hear a second song... so for two songs, on average it will take 1 + 1.25 = 2.25 songs to hear both of them...
The probability of a third new song is 3/5, so it should take another 5/3 songs to hear a new one.. so for three songs we would have to listen to 1 + 1.25 + 1.667 = 3.917 songs on average...
If we write these out another way, we notice a pattern... the first took 5/5, the second took 5/4, the third took 5/3.. so for all five songs it would take 5/5 + 5/4 + 5/3 + 5/2 + 5/1 which is 137 /12 or about 11.4 songs to hear them all... and factoring out a five that is 5 (1/1 + 1/2 + 1/3 + 1/4 + 1/5)... the harmonic sequence..

Ok, how does that help.. well for five songs, not much... but what if there are 100 songs in your MP3 player... or 1000 song on your computer ... and you wonder... Hmmm how long would it take on a random shuffle to hear ALL the songs on my MP3 Player... well, 100 (1/1 + 1/2+ ... + 1/100) and that might take a little time to add up ... except for the incredible Euler... 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 ln(n).. and Euler came up with a really good estimate of how wrong it would be. Today we often call the number gamma, or Euler's constant, but it is about .577... so if you want to know how long it will take to hear all 100 songs, just multiply 100 times (ln(100) + .577) .... I got about 518...
Ok, quick, let's check that with the answer we got for five songs.. 5 (ln (5) + .577) = 5 (1.609+.577) = 5(2.186) which is about 10.932....... compared to the actual 11.416.... NOT BAD for such a small number..

so for a thousand songs???? Well we leave that as a problem for the reader... good luck

Some Early Probability History Notes

So we make a fair bet, I roll one die, you roll the other, and who ever gets the highest scores a point. If we tie, we just redo the roll, and the first one to five points wins. Easy enough, but then, when the score is three to one my favor, you get an emergency phone call and have to leave. How should we distribute the stakes?

It was just such a problem that formed the foundation of early probability, and when it was solved, it sparked a rapid development of problems, and applications of probability.

I would tell you more, but I just read a neat blog by Keith Devlin that covered just such a development, so here, in part, are the words of a master:

"The Unfinished Game,
The problem of the unfinished game, also known as the problem of the points, was described in a book on arithmetic and geometry written by the Italian mathematician Luca Pacioli in 1494, [The text was Summa de arithmetica, geometrica, proportioni et proportionalita, and you can view it here PAT] though it is known to predate that mention. It asks how the pot should be fairly divided when a multi-round tournament has to be abandoned before it is finished. For instance, suppose two players are rolling a pair of dice and agree to playa best of five rounds tournament. Three rounds are played, leaving one player ahead 2 to 1, at which point they must abandon the game. How should they divide the pot?

Pacioli was unable to solve this problem. So too were a number of other mathematicians (and gamblers) who tried, including Girolamo Cardano, Niccolo Tartaglia, and Lorenzo Forstani. The consensus was that the problem could not be solved.

Then, early in 1654, a gambler by the name of Antoine Gombaud, more often referred to in modern history books by his French nobleman's title of the Chevalier de Mere, asked his friend the mathematician Blaise Pascal. Pascal produced a complicated argument that can be made to work, but was not happy with it, so at a friend's urging he wrote to Fermat about it. Fermat quickly found a simple solution.

There are two rounds left unplayed, argued Fermat. In each round, either player can win, so there are in all four different ways the game could continue to its five-round completion. The player who has won one round to the other's two must win both those final rounds in order to win the contest; in the other three possible endings, the player who is ahead after three rounds will win. Therefore, said Fermat, the player who is ahead when the game is abandoned should take 3/4 of the pot, with the other player taking 1/4.

To anyone who sees this solution today, it seems simple enough. (The solution assumes the tournament is thought of as a "best-of-five" rounds, as opposed to a "first-to-three". You need a slightly more complicated argument in the latter case, but the answer is the same, a 3 to 1 division of the pot.) But no one before Fermat saw it, including Cardano who did work out all of the basic rules we use today to combine probabilities. Moreover, when he did see Fermat's solution, Pascal could not accept it, and nor could various of his colleagues he showed it to. What was their problem?

Since the computation is trivial, indeed no different from the calculation of the odds in any game of chance (and actually much simpler than many), the only thing that could be holding everyone back was the fact that what Fermat was counting were "possible futures." Something that two thousand years of received wisdom said was not possible.

Once word got out about Fermat's breakthrough, however - presumably through the highly mobile network of gambling European noblemen - it did not take long for others to jump into the "future prediction" act. Within a single lifespan, modern future prediction and risk management were in place.

The speed of developments that followed the solution to the problem of the unfinished game is staggering.


1657. Christian Huyghens writes a 16-page paper that lays out pretty well all of modern probability theory, including the notion of expectation, which he introduces.[This one is LIBELLUS DE RATIOCINIIS IN LUDO ALEAE and can be found here

1662. John Graunt, an English haberdasher, publishes an analysis of the London mortality tables, and in so doing establishes the beginnings of modern statistical inference.

1669. Huyghens uses his new probability theory to re-compute Graunt's mortality tables with greater precision.

1709. Nikolas Bernoulli writes a book describing applications of the new methods in the law. One problem he shows how to solve is how long must elapse after an individual goes missing before the court can declare him dead and allow his estate to be divided among his heirs.

1713. Jakob Bernoulli writes a book showing how the new probability theory can be used to predict the future in the everyday world. This is the first time the word "probability" is used in the precise, mathematical sense we use it today. He also proves the law of large numbers, of which more in a moment.

1732. The first American insurance company begins in Charleston, S.C., restricted to fire insurance.

1732. Edward Lloyd starts the precursor of what in 1734 becomes Lloyd's List, and eventually gives birth to the insurance company Lloyds of London.
1733. Abraham de Moivre discovers the bell curve, the icon of modern data collection.


1738. Daniel Bernoulli introduces the concept of utility to try to get a better handle on human decision making under uncertainty.


1760s. The first life insurance companies begin.

"

A pretty concise History for one blog... If you have additional notes to offer, please do.

But That Would Almost NEVER Happen, Would It?

Click on images to see higher resoultion images

A young man in one of my classes, obviously trying to improve his A+ by sucking up to the teacher, mentioned that he had read my recent blog on the pigeon-hole principle. He went on to suggest that he really doubted the idea that 39 people could randomly seat themselves and ALL be in the wrong seat. "It just seems VERY unlikely." he suggested.

Rather than tell him the answer, I set him the task of simulating the activity with a deck of cards. Pull out any suit, say the spades, and really shuffle the remaining cards well. Now we need to decide on an order for the remaining suits, so let clubs be the numbers one to thirteen in order from Ace, two, up to King for thirteen. Then the ace of diamonds can be 14, up through the King of diamonds for 26. Finally the ace of hearts is 27 up to the king of hearts for 39. Now turn over the cards and as you do count, one, two, etc... and if you get a card that is where it should be, stop.. they didn't all sit in the wrong chairs. You need not go on forever, just ten or so trials should give you an idea of whether the event is really, really uncommon, or not so very uncommon.

I didn't tell him that I knew the probability, and that he should probably get three or four trials in a string of ten shuffles in which none of the cards landed in the right place. Such a mis-ordering of the cards was just the idea behind the first critical study of the idea we now call derangements by Leonhard Euler, the great Swiss mathematician. Euler was studying the probability of winning in the game of rencontre, now called "coincidences" in his paper "Calcul de la Probabilite dans le jeu de Rencontre", published around 1751. An English translation of the paper by Richard J. Pulskamp is available and the original document can be seen here.

So what did Euler discover? Well for larger values of N, say 39 or so, the probability of having a perfect mis-sorting of the items approaches 1/e, or about 36.8%, more than a third of the time. It is not an unusual event at all. For smaller numbers you can find the probability by using the idea shown here for six items..
. This can be rewritten more easily using the factorial notation as P= 1/2! - 1/3! + 1/4! - 1/5! + 1/6! which is only a tiny bit above 36.8%, already very close to the 1/e value given above for the limiting value. If the number of items is even, the series will be a little more than 1/e, and if it is odd (and the last term is subtracted) then the probability will be a little below 1/e, with the propbability approaching 1/e as a limit as n gets greater and greater.

I decided to simulate a lot more times than would be practical with a deck of cards, so I cranked up Fathom, a wonderful simulation software by the folks at Key Curriculum, and had it repeat the experiment of seating the 39 people at random 1000 times, and then count how many landed in the right place. The results are shown in the graph below.

It happened that no one landed in the right place 371 times.... Hmmmm, I guess Euler got it right.

Pick Two

A colleague from Colorado sent me an interesting probability problem the other day. I like it because it illustrates one of those serendipitous qualities of mathematics. Here is the problem. A Jar has a mixture of Red and White balls so that if you withdraw two, the probability of getting two alike, or two of different color are both equal to one-half. You may want to stop and try it before you read on.

Ok, so we let r = the number of red ones and W be the number of white ones, and the total is r+w. So how could we draw one of each color? Well, red first, and then white, or white first and then red. If we find the probability of each of these conditional events and add them up, that will have to equal 1/2. Ok, the probability of red on the first draw is r/(r+w), and on the second ball the probability is w/(r+w-1) since one of the red balls will be missing. The opposite order is exactly the same with the w and r reversed, so the probability of getting one of each color is 2rw/[(r+w)(r+w-1)]. Setting that equal to 1/2 we get

If we exapand (r+w)² and subtract the 4rw we get 0=r²-2rw +w²-r-w. NOTICE the symmetry, we could exchange r and w and get the same equation. We know right off that any solution (a,b) will have another soltuion (b,a).

One of the things that is often hard for students is to think of one variable as a constant and the other as a variable. I like to use the word "pronumeral", like a pronoun only instead of him or her we say "that number". It is like a variable that doesn't vary, we just don't know what it is in a particular case. So think of w as if it were fixed. We have that many white balls in the jar and we are wondering how many red can be put in to make the problem work... see it.. w is a "fixed" unknown, but r is going to "vary". That makes the equation a quadratic in r; Ar² +Br+c=0 where A=1, B= -2w-1, and C=w²-w.

We can solve this using the quadratic formula, but if this solution is going to be a rational number, and the number of balls in a jar must be rational, then the discriminant, the expression under the squre root radical in the quadratic forula, B²-4AC, must be a perfect square. B²= 4w²+4w+1 and 4AC= 4w²-4w; so B²-4AC= 8W+1. If there is a rational solution, it must be when 8W+1 is a perfect square. Wait, I know this one! That's a problem from number theory. The numbers that make 8W+1 a perfect square are called triangular numbers; 1, 3, 6, 10, 15. They are the sum of the first n counting numbers. But a neat thing happens if we plug 1 in for W, the solution for r is 3.... and if we use 3 for w, r=6. Each time we substitute one of the triangular numbers into the quadratic, the next comes out as a solution. So the probability of drawing two balls of the same color, (or of two that are not alike) will equal 1/2 whenever the number of balls of each color are consecutrive triangular numbers. A very geometric solution to a very algebraic question.

Thoughts While Avoiding Grading Papers

Trying to avoid actually grading semester exams, I was playing around with a problem from F. Mosteller's classic, "Fifty Challenging Problems in Probability." Problem two concerns a three-set tennis match in which the player, a youth named Elmer, will alternately play against his father and the club pro, given the club pro is a better player than the father. He will win a prize if he can win two consecutive matches of the three. The question is whether he is better of playing the sequence father-pro-father or pro-father-pro.

The counter-intuitive part is that his odds of winning are better if he plays the better play, the pro, more often. (This reminds me of Parrondo's paradox, which I will try to write about soon) Here is a simple explanation (I hope). If we let f represent the probability he wins against his father, and p the probability he beats the pro, then to get two consecutive wins, he must win the first two or the last two, so we need the probability win, win added to the probability of Lose, win, win.

For the sequence father-pro-father the probability of success is fp + (1-f)pf. We can distribute the 1-f to get fp + fp - fpf, and factoring fp out of each term we get fp(2-f).

If we do the same with the sequence pro-father-pro we just interchange the p and f to get pf(2-p). Now since we are given that p is smaller than f (he is LESS likely to beat the better player) we see that 2-p must be larger than 2-f, and so the pf(2-p) is the higher probability.

The advantage when actually calculated is very small. For example, Ifthe probability of beating his father is .4, and the probability of beating the pro is .2, his probability of winning in the father-pro-father sequence is about .128 . By switching the order to play pro-father-pro his probability of success increases to .144(which is twice what it would be if he only played a three set match against the pro).

What happens if we change these probabilities of success, but keeping the order so that the pro is better than the father? Letting p remain at .2 and raising his level against his father to .5 improves his chance of success to 18%. In fact, if we substitute the value .2 into the expression pf(2-p) we get .2f(1.8).... the probability of success is a linear equation, .36f. If we let his probability against his father go to one, you can see tha the has a 36% chance of winning if he goes Pro-father-pro. But if you look at the other sequence, fp(2-f), and again substitute in the .2 value against the pro, the equation is quadratic, .4 f - .2f². Visualizing the graph of this negative quadratic, we can see that he vertex will occur when f= 1, so that is the maximum, and when f=1 we get a probability of success of .2, exactly what his probability against the pro in a single game would be. This makes sense if you consider that if he ALWAYS beats his dad, the match really depends on the one game in the middle against the pro.

How would a fourth game alter the mix? does it matter in which order he plays? It would seem that with four games both orders might be equal, but lets look at the possible winning paths for each.

When the order is p-f-p-f two wins can happen with probabilities pf + (1-p)fp + (1-p)(1-f)pf. Now compare the probability when the order is reversed, fp + (1-f)pf + (1-f)(1-p)fp. Note that all the terms except the second are the same. Once more the fact that 1-p must be larger than 1-f (because f is greater than p) leads us to conclude the best order is to play the pro first.

The Rules of Three

In my youth, back when dinosaurs roamed the earth, there was “the rule of three”… singular, one, and even then the name was often described as “archaic”. More modern books tended to develop “properties of proportions” or similar terms for the problems of proportionalities. Now there seem to be an abundance of them; including one for witches, and one about businesses. There is not space enough to talk about all of them so I will mention three, of course.
The first rule of three is as old as math, and shows up at least as early as the Hindu mathematician Brahmagupta, and in Fibonacci’s famous Liber Abaci(1202). It was once so common that it was introduced into common language. Abraham Lincoln is quoted in his biography as stating that he learned to "read, write, and cipher to the rule of 3."
The most common and longest living form was the direct rule (although there was an inverse rule as well), in which case three numbers would be given and a fourth sought so that the ratio between the third and fourth would match the ratio between the first and second; a:b = c:d. Today students use the ideas in elementary school to complete fraction equivalences, “2/3 is the same as 10/?” Some of the ancient examples grew incredibly complicated.

I suppose the reason I chose to address three of the many “rules of three” is because of the rule of three from language and literature. Three just seems to be the right number for lots of things, there were Three Musketeers, Three Stooges, and Three Coins in the Fountain. It was Goldilocks and the Three Bears, and “bah bah black sheep” had “three bags full.” Comics in the newspaper usually have three panels and many jokes involve a three part ritual where the punch line is the third element, such as the t-shirt with “Great Cities of the World” on the top, and below, one after another, “Paris, Rome, Fargo”. The first two make the last funnier. In language the examples range from “Blood, sweat, and tears, to vidi, vidi, vici. If you don’t think there really is a mental tendency to have three terms, consider that in Churchill’s speech, he actually used four; “I say to the House as I said to ministers who have joined this government, I have nothing to offer but blood, toil, tears, and sweat. “
The final rule of three I would mention is from statistics, and is of more recent origin. It is also, I think, a really clever solution to what is a really difficult problem. Suppose something never happens; how can you assign a probability to it? It is not that it might not happen some day, just not so far. It is just such a problem the statistical rule of there was created to handle. Suppose you stopped at the same gum ball machine every day, but unlike the normal gumball machine, this one did not have a glass you could see into the gumballs inside. You buy a gum ball every day and get red ones, and green ones, but never a blue one. After a while you begin to wonder if they even put a blue one in the machine. So one day, after 20 days of getting all the other colors, over lunch you ask your local statistician (doesn’t everyone have lunch with a statistician?) how to figure out if there really is a blue one in there. He pauses, fork poised in mid-air, and informs you that you can be 95% sure (a common statistical benchmark) that the proportion of blue gum balls is no greater than 14.3%. He had mentally taken three, and divided by one more than the number of failed efforts, to get 3/21 or 1/7 as the upper limit of the possible fraction.
The idea is base on a simple extension of the binomial probability. If you knew that P % of the gum balls were blue, then you could calculate the probability that None showed up in 20 days. The probability would be (1-p)²⁰. Working back through this calculation many times you might notice that the number followed a pattern, a rule of thumb to calculate without tables and calculators, and that turns out to be 3/(n+1), the statistical rule of three. If you wanted greater certainty, you can use the rule of seven, which says that 7/(n+1) will give the 99% interval boundary. So in the case of your gumballs, you can be 99% sure the percentage of gumballs is less than 1/3.