A probability question for math people

[Star Treks]

I am not a math guy, but I could probably figure this out if I put enough time into it. Unfortunately it's late and I am sure asking people here will come up with a correct answer, more reliably than I could. I'm asking purely out of curiosity and thank you in advance for your help.

Let's assume a theoretical iPod with unlimited capacity, with a shuffle songs feature that truly randomly shuffled the songs beyond any possible detection of non-randomness.

Now let's assume one begins loading albums into this iPod with exactly 10 tracks per album; the number of tracks never varies - every album has exactly 10 tracks.

Long story short, what I'm trying to figure out is, is there a way to calculate the probability that if the entire contents of the iPod are played at random, at least once the shuffler will play two songs from the same album in a row based on the number of albums loaded onto this theoretical iPod and the number of tracks on each album, assuming all had the same number of tracks? Also assume every track must play once before it repeats.

For example, if there are only two albums, then there will be 20 songs; the chances of the first two shuffled tracks coming from the same album are 9 out of 19 or 47.37 percent (since Track 1 will come from either album A or B, and then there will be 19 tracks left, with 9 of them being from the same album and 10 of them being from the other album). But I'm not sure how to extend this sort of calculation to a playback of all 20 tracks; what are the chances that at least once the same album will appear twice in a row (I'm sure it's very high, like 99% plus, but I'm not sure how to calculate it).

I'm trying to figure out the likelihood of the same album appearing twice in a row with, say, 100 albums on the iPod, 1000, 5000, a trillion, etc. Is there a straightforward formula to figure this out?

One reasons logically that as the number of albums goes up, the chances of any two tracks played in a row coming from the same album go down - but, at the same time, playing through the entire iPod's contents, we will also have an increase in the number of individual chances of this event occurring (if you have 1,000 songs there are 999 chances of two songs in a row being from the same album, although any two aren't particularly likely to match, whereas if you have 20 songs are only 19 chances of this happening - but a very good chance for any two).

Again, thanks in advance for help.

 

[Venardhi]

Since one song is already playing, we can take it as a given, and won't have to factor that into things. (Otherwise just multiply the chance of any song/album playing by itself) The second song playing, if truly random, has the same chance of being from that album, or even being the same song of the software allows it, as of being any other song, so it is 1 over X. X being either the number of songs or number of albums.

100 albums? You have a 1/100(or 9/1000 if you don't want to include the first song) or 1% chance of having the next song be from the same album.

Am I missing something here? This seems deceptively simple. . .

Now, if you want to calculate based on each song having to play once before a song can repeat, you'll need to get help elsewhere.

 

[Star Treks]

Now, if you want to calculate based on each song having to play once before a song can repeat, you'll need to get help elsewhere.

Yeah that's exactly what I'm trying to figure out.

 

[ThunderAeroI]

that should also be easy. It is a population n sample.

your going to wind up with 1000!, otherwise a really large number when divided by 1, the chance of a song repeating is something like the chance of spontanious compustion or winning the lottery

 

[Star Treks]

Thunder, I don't think that's quite right. The chances are extremely high with only a few albums and even as the number goes up I don't think it approaches infinitessimal when every single song must be played through once. Obviously with any two the chances will be lower as the number of albums goes up but when playing through the entire iPod the chance stays pretty good for a long while.

 

[ThunderAeroI]

I dont think i understand your problem then. Give the following equation..

P = N! / (N-r)!

In your case N is the total number of songs, and r is the total number of songs in an alblum.

Your then looking at 1000! / (1000-10)! or 1000!/(90)!

In the end it is a really large number. I can't even find a website that will do 1000!

 

[Iasius]

In the end it is a really large number. I can't even find a website that will do 1000!

Using Stirling's approximation: 1000! = 4 * 10^2567

 

[Star Treks]

I dont think i understand your problem then. Give the following equation..

P = N! / (N-r)!

In your case N is the total number of songs, and r is the total number of songs in an alblum.

Your then looking at 1000! / (1000-10)! or 1000!/(90)!

In the end it is a really large number. I can't even find a website that will do 1000!

As I said I'm not a math guy, so I don't even completely understand your math here. Remember you're talking to a music and english major, and someone who hates math.

But I still don't think you understand the problem completely. Maybe it will be easier for you to think of this in more abstract terms, but I am not necessarily familiar with the lingo. I will do my best to put this in mathy terms:

We have X sets with Y items each. If items are picked at random, without repetition (that is, once an item is picked, it cannot be picked again), what are the chances of picking two items in a row from the same set, if every item must be picked?

 

[ThunderAeroI]

readhere http://www.answers.com/topic/probability

 

[Chaos Descending]

How can you be a music major and hate math????

 

[Star Treks]

How can you be a music major and hate math????

Because that's an untrue cliche about music and musicians. Music is art much more than it is math. I won't go extreme and say that math isn't an element of music, but it is a small one. It is as possible to love music and dislike math as it is to love cinema but dislike designing costumes; to love theater but dislike carpentry; to love eating but dislike throwing up.

 

[Captain Intrepid]

I dont think i understand your problem then. Give the following equation..

P = N! / (N-r)!

In your case N is the total number of songs, and r is the total number of songs in an alblum.

Your then looking at 1000! / (1000-10)! or 1000!/(90)!

In the end it is a really large number. I can't even find a website that will do 1000!

402,387,260,077,093,773,543,702,433,923,003,985,719,374,864, 210,714,632,543,799,910,429,938,512,398,629,020,592,044,208, 486,969,404,800,479,988,610,197,196,058,631,666,872,994,808, 558,901,323,829,669,944,590,997,424,504,087,073,759,918,823, 627,727,188,732,519,779,505,950,995,276,120,874,975,462,497, 043,601,418,278,094,646,496,291,056,393,887,437,886,487,337, 119,181,045,825,783,647,849,977,012,476,632,889,835,955,735, 432,513,185,323,958,463,075,557,409,114,262,417,474,349,347, 553,428,646,576,611,667,797,396,668,820,291,207,379,143,853, 719,588,249,808,126,867,838,374,559,731,746,136,085,379,534, 524,221,586,593,201,928,090,878,297,308,431,392,844,403,281, 231,558,611,036,976,801,357,304,216,168,747,609,675,871,348, 312,025,478,589,320,767,169,132,448,426,236,131,412,508,780, 208,000,261,683,151,027,341,827,977,704,784,635,868,170,164, 365,024,153,691,398,281,264,810,213,092,761,244,896,359,928, 705,114,964,975,419,909,342,221,566,832,572,080,821,333,186, 116,811,553,615,836,546,984,046,708,975,602,900,950,537,616, 475,847,728,421,889,679,646,244,945,160,765,353,408,198,901, 385,442,487,984,959,953,319,101,723,355,556,602,139,450,399, 736,280,750,137,837,615,307,127,761,926,849,034,352,625,200, 015,888,535,147,331,611,702,103,968,175,921,510,907,788,019, 393,178,114,194,545,257,223,865,541,461,062,892,187,960,223, 838,971,476,088,506,276,862,967,146,674,697,562,911,234,082, 439,208,160,153,780,889,893,964,518,263,243,671,616,762,179, 168,909,779,911,903,754,031,274,622,289,988,005,195,444,414, 282,012,187,361,745,992,642,956,581,746,628,302,955,570,299, 024,324,153,181,617,210,465,832,036,786,906,117,260,158,783, 520,751,516,284,225,540,265,170,483,304,226,143,974,286,933, 061,690,897,968,482,590,125,458,327,168,226,458,066,526,769, 958,652,682,272,807,075,781,391,858,178,889,652,208,164,348, 344,825,993,266,043,367,660,176,999,612,831,860,788,386,150, 279,465,955,131,156,552,036,093,988,180,612,138,558,600,301, 435,694,527,224,206,344,631,797,460,594,682,573,103,790,084, 024,432,438,465,657,245,014,402,821,885,252,470,935,190,620, 929,023,136,493,273,497,565,513,958,720,559,654,228,749,774, 011,413,346,962,715,422,845,862,377,387,538,230,483,865,688, 976,461,927,383,814,900,140,767,310,446,640,259,899,490,222, 221,765,904,339,901,886,018,566,526,485,061,799,702,356,193, 897,017,860,040,811,889,729,918,311,021,171,229,845,901,641, 921,068,884,387,121,855,646,124,960,798,722,908,519,296,819, 372,388,642,614,839,657,382,291,123,125,024,186,649,353,143, 970,137,428,531,926,649,875,337,218,940,694,281,434,118,520, 158,014,123,344,828,015,051,399,694,290,153,483,077,644,569, 099,073,152,433,278,288,269,864,602,789,864,321,139,083,506, 217,095,002,597,389,863,554,277,196,742,822,248,757,586,765, 752,344,220,207,573,630,569,498,825,087,968,928,162,753,848, 863,396,909,959,826,280,956,121,450,994,871,701,244,516,461, 260,379,029,309,120,889,086,942,028,510,640,182,154,399,457, 156,805,941,872,748,998,094,254,742,173,582,401,063,677,404, 595,741,785,160,829,230,135,358,081,840,096,996,372,524,230, 560,855,903,700,624,271,243,416,909,004,153,690,105,933,983, 835,777,939,410,970,027,753,472,000,000,000,000,000,000,000, 000,000,000,000,000,000,000,000,000,000,000,000,000,000,000, 000,000,000,000,000,000,000,000,000,000,000,000,000,000,000, 000,000,000,000,000,000,000,000,000,000,000,000,000,000,000, 000,000,000,000,000,000,000,000,000,000,000,000,000,000,000, 000,000,000,000,000,000,000,000,000,000,000,000,000,000,000, 000

 

[Jadzia]

Maths challenge time!


Q1.
On one summer afternoon, a neighbor has an ipod playing on desktop speakers, and you overhear some of the tunes and notice there are songs playing from various albums.

Over a period of time, 40 tracks are heard, 3 of which are recognized to be from the same artist, and belonging to the same album. A quick google confirms this fact, and you learn that this album has a total of 15 songs.

Assuming that the ipod is on random shuffle, estimate the number of songs in its memory.


Q2.
An internet radio station is left playing all day long, with playlist of music from the 1980s. Over a period of 1 day, 200 tracks are heard, and you notice at the end of the day that 6% of the tracks you heard today, you have already heard earlier today, on this same station.

Assuming the songs played are selected randomly from the archive, and with each selection, there is no preference for one song over the other, estimate the size of the radio station's song archive.

.

 

[Star Treks]

Well, don't look at me

 

[Jadzia]

Let's see this question Star Treks...

assume one begins loading albums into an iPod with exactly 10 tracks per album

calculate the probability that if the entire contents of the iPod are played at random, at least once the shuffler will play two songs from the same album in a row

Suppose the number of albums is N... So there are 10N songs.

The probability that one randomly selected song belongs to the same album as the previously played song is 1/N.

If we go through all songs, testing for this event, we repeat this test 10N times. (You said that we play the songs through once first, so song 1 does have a predecessor.)

Now you want to know the probability that any song belongs to the same album as its predecessor, over the full 10N songs.

Well first I'll tell you the expectation: = 10N x 1/N = 10 times we expect this event to happen, independent of the number of albums.

But you want a probability? To do this we first find the probability of it never happening:

= (1 - 1/N) for it not happening for one song,

= (1 - 1/N) ^ (10N) for it not happening for all 10N songs.

So for it to happen AT LEAST ONCE over the full playlist, as you asked:

probability = 1 - (1-1/N) ^ (10N)

or equivalently
= 1 - [ (N-1)/N ] ^ 10N

so some examples:
N = 1 album
probability = 1 - (1-1/N)^(10N) = 1-(0)^10 = 1 = certain.

N=2 albums
probability = 1 - (1/2)^(20) ~ 0.999999046 = almost certain.

N=1000
probability = 1 - (999/1000)^10000 = 0.9999548 = less likely but still almost certain.

what if N tends to an infinite number of albums?



Well notice the similarity in the formula for the definition of e.

e = (1+1/n)^n as n tends to infinity = 2.71828...

Let's make it look the same...

e = [ (n+1)/n ] ^ n
= [ n/(n+1) ] ^ -n
= [ (n-1)/n ] ^ (1-n)

[e . n/(n-1)]^10 = [(n-1)/n] ^ -10n

1 - [e . n/(n-1)]^-10 = 1 - [(n-1)/n] ^ 10n, which is it

so let n-> infinite number of albums

probability = 1 - [e . n/(n-1) ] ^ -10

n/(n-1) tends to 1.

probability = 1 - [e^-10] = exact answer

which is about 1 - 4.54e-05 = 0.99995460

so still very likely.

Again, thanks in advance for help.

no problem. I'll send you the invoice.

 

[Star Treks]

Jadzia, while I had to study like crazy to pass Statistics and remember next to nothing of it, your math looks very sound and I think your conclusion makes a lot of sense. I know it took some work but it confirmed my suspicions.

I listen to my iPod on shuffle all the time, but no matter how big my collection gets (from 500 songs to 2500 to now around 13000) I found that it was still frequently playing a couple of songs in a row from the same album.

I know the shuffler on the iPod isn't really authentically random, but I still thought this should happen less and less as I loaded more albums, but it really hasn't stopped happening, and your math strongly suggests that this is mathematically to be expected.

The only thing I'm not smart enough to be positive you took into account is the setting aside of a song once it has been played, until the whole iPod has been played. The shuffler shuffles every song into a random order (like a deck of cards), not just picking songs at random, and it seems to me this would decrease the chances of two in a row coming from the same album. But I'm not mathy enough to know if you accounted for this or not.

Either way, thanks again! Let me know if you need any help with music theory, that's about the only thing I have as deep a knowledge of as you seem to have of math.

 

[Jadzia]

The only thing I'm not smart enough to be positive you took into account is the setting aside of a song once it has been played, until the whole iPod has been played.

no i didn't take this into account. I did what is called "sampling with replacement", which keeps the probabilities constant each sample, and therefore easier.

I'll have a look at the "sampling without replacement" case for you too today if I have time, but I doubt the probabilities will be much different. It's reminiscent of drawing straws: the first person has many straws to choose from, so is unlikely to draw the short one. Those who draw later have less straws to choose from so are more likely to draw the short one, so is it better to draw early? Well if you draw late, the short straw might already have been drawn, so is it better to draw late? Which draw is the safest? Well they're all equal as the increasing factor exactly cancels the decreasing factor

I think another figure you might be interested in is how frequently these "double plays from one album" are expected to be, like once every x songs, etc. In the above it's easy = 1/ probability = N, so with N albums, you expect a double play, once in every N songs.

Either way, thanks again! Let me know if you need any help with music theory, that's about the only thing I have as deep a knowledge of as you seem to have of math.

hey, I am one of those people who enjoys music, maths, and their overlap.

I think of the renaissance times when the learned folk would go around saying "what do you know about the theory of harmonics, you can't even play the lute!"

 

[Jadzia]

The only thing I'm not smart enough to be positive you took into account is the setting aside of a song once it has been played, until the whole iPod has been played. The shuffler shuffles every song into a random order (like a deck of cards), not just picking songs at random, and it seems to me this would decrease the chances of two in a row coming from the same album. But I'm not mathy enough to know if you accounted for this or not.

Okies. I've just been thinking about this.

Suppose we have a randomly shuffled set of S songs, from N albums, with each album contributing 10 songs. Let this shuffled list be our ipod playlist.

So, S = 10N.

Let P(N) be the probability of the event in which (at least one instance in which) two tracks from the same album appear consecutively in the playlist. I'll refer to these consecutive pairs as a "double play".


Some cases are easy.
P(1) = 1 = certain. Because with only 1 album we can't avoid a double play.

For N=2, we have two albums A and B, with 20 tracks in the playlist. Here, to avoid a double play we must alternate between albums, although there is a small amount of choice. There are 2 ways of interlacing the two albums, viz:

ABABABABABABABABABAB
BABABABABABABABABABA

The total number of ways of shuffling 10A's and 10B's is 20-choose-10 = 184756

AAAAAAAAAABBBBBBBBBB
AAAAAAAAABABBBBBBBBB
AAAAAAAAABBABBBBBBBB
...etc


Meaning there are 184756 - 2 = 184754 ways of shuffling which do give double plays

So P(2) = 184754/184756 = 92377/92378


Now in order to find the general solution, I'm going to define Q(N) = 1 - P(N)

Q(N) = probability of there being no double plays in our randomly shuffled playlist with N albums.


How I'm going to proceed is to find this formula by induction. My favourite mathematics tool.


Supposing we have N-1 albums, shuffled in such a way that there are no double plays. The probability of a shuffle being like this is Q(N-1)

Now the good thing about this arrangement is that we can "filter in" or "insert" 1 more album of 10 songs into this shuffled playlist in such a way that we still have a playlist with no double plays. Understand?

The only requirement is that we don't filter in two songs from our new album into consecutive positions; we must keep them separated.

so let Q(N) = Q(N-1) x [f(N)/C(N)]

f(N) = the number of ways of filtering the new album into the playlist as described.
C(N) = the number of way of filtering the new album into the playlist any old how.

This quotient f/C describes the additional probability that the new album imposes on Q, the probability of maintaining a playlist with no double plays.

So to seed this induction, we need a base case. I have that Q(2) = 1 - P(2) = 1 / 92378, as found above.

C(N) is also easy = (10N)-choose-(10)

f(N) is the only difficult figure here.

Like above, consider album N are tracks labelled with "A", and tracks from all other albums are labelled with "B".

f(N) corresponds to the number of seqences with 10 A's and 10N-10 B's in which no two A's appear consecutively.

To do this, I'm going to use a little trick: Start with a playlist of length 10N-10, all "B"'s, and choose 10 of them and convert them into "A"'s. Then replace "A" with "AB".

This creates a playlist with 10 "A"'s and 10N-10 "B"'s and ensures that no two A's will appear consecutively. ie, this is an N album shuffle with no double plays.


But there are two cases here:

(Case I) "A" --> "AB" means we can't finish the playlist on an "A". So it only counts a subset of playlists where we don't finish on an "A".

So we also must add another selection:

(Case II) use a list of length 10N-10, all "B"'s, and choose 9 of them and convert them into "A"'s. Then replace "A" with "AB". Then add an "A" at the end.

This counts the subset of playlists in which we always finish on an "A", and by the nature of the construction, also has no double plays.

This will count all possible playlist shuffles with N albums with no double plays.


So what are the numbers?

Case I: = (10N-10) choose 10
Case II: = (10N-10) choose 9

So f(N) = { (10N-10) choose 10 } + { (10N-10) choose 9 }

which we can simplify using the binomial rule, to f(N) = (10N-9) choose 10


So putting this all together now gives the weak induction rule:

Q(N) = Q(N-1) x (10N-9)-choose-10 / (10N)-choose-10


expanding into factorials

= Q(N-1) x (10N-9)! / (10)! / (10N-19)! / (10N)! x (10)! x (10N-10)!

= Q(N-1) x [ (10N-9)! x (10N-10)! ] / [ (10N-19)! x (10N)! ]

= Q(N-1) x PRODUCT (i=0 to 9) { (10N-9-i) / (10N-i) }

Let us define:

K(N) = (10N)(10N-1)(10N-2)(10N-3)(10N-4)(10N-5)(10N-6)(10N-7)(10N-8)

and observe that Q(N) = Q(N-1) x K(N-1)/K(N)

index shifting,
Q(N-i) = Q(N-i-1) x K(N-i-1)/K(N-i)

gives the strong induction rule,
Q(N) = Q(N-i) x K(N-i) / K(N)


so letting i=N-2, resolves the closed form,

Q(N) = Q(2) x K(2) / K(N)

implementing the base case where:
Q(2) = 1/92378 = 10!x10!/20!
K(2) = 20x19x18x17x16x15x14x13x12 = 60949324800 = 20!/11!


Q(N) = (60949324800/92378) / K(N)
= (2/11)x10! / K(N)

we have the explicit formula you asked for:

P(N) = 1 - (60949324800/92378) / {(10N)(10N-1)(10N-2)(10N-3)(10N-4)(10N-5)(10N-6)(10N-7)(10N-8)}

= 1 - (2/11)x10! / {(10N)(10N-1)(10N-2)(10N-3)(10N-4)(10N-5)(10N-6)(10N-7)(10N-8)}



example of N = infinite number of albums:
K(N) --> infinity as N --> infinity ... therefore Q(N) --> 0 ... therefore P(N) --> 1
So with an infinite number of albums you are *certain* to get a double play from a random shuffle.


Also note that P(N) is a monotonic increasing function of N, so the more albums you have the less chance there is of not having a double play.

And the case of N=2 albums is a 1/92378 chance.


Now I just hope I got all that right !

 

[Star Treks]

Wow..... thanks.... My mind has exploded, but thanks!

 

[MilitaryCoo]

It's fairly obvious intuitively that the probability of no-adjacent-album plays is low, because for 2 albums there are only 2 sequences which don't have such a double play.