## Tuesday, 27 January 2009

### 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