mp3 player probability question

[TheBoyPaj]

Here's one which popped into my head the other day, and I'm not sure how to solve it.

You have an mp3 player with an album containing ten tracks. You have put it on "random play".

What is the probability that two or more tracks on that album will play out in their original order? They could be at any point in the ten-track sequence.

for example: 6-3-9-8-1-4-5-10-2-7

 

[mgidm86]

I don't know, but that avatar is the scariest I've ever seen.

 

[Cuddles]

Is this assuming it plays all tracks with no repeats? All the ones I've seen will quite happily play some songs several times while not playing others for ages.

I would try to work this out, but statistics don't like me so I try to avoid them. I would think it's actually very likely that at least two tracks will play in order.

 

[fribble]

Assuming you are not allowing repeats, I reckon you can do this by the Inclusion-Exclusion principle as follows:

Let A be the event "the sequence 1,2 appears in your playlist"
Let B be the event "the sequence 2,3 appears in your playlist"
...
Let I be the event "the sequence 9,10 appears in your playlist"

The Inclusion-Exclusion principle says:

p(A U B U ... U I) =
p(A) + p(B) + p(C) + ... + p(I)
- p(A ∩ B) - p(A ∩ C) - ... - p(H ∩ I)
+ p(A ∩ B ∩ C) + p(A ∩ B ∩ D) + ... + p(G ∩ H ∩ I)
- ...
+ ...
...
+ p(A ∩ B ∩ C ∩ D ∩ E ∩ F ∩ G ∩ H ∩ I)

[where p(A∩B) is the probability of A AND B occuring, and p(AUB) is the probability of A OR B OR both occuring]

What you're after is the left-hand side, the probability that at least one of the events A to I occurs. So if we can evaluate the left-hand side, we're done.

P(A) = 9x8!/10! (since there are 8! ways to arrange 3,4,5,6,7,8,9,10, and having arranged them there are 9 gaps to slot 1,2 into. So 9! ways out of 10! have 1,2 in them)
Fairly obviously, P(A) = P(B) = ... = P(I) = 9x8!/10! = 1/10

P(A∩B) = 8x7!/10! (since A∩B is the event "1,2,3 occurs in the playlist", then use a similar argument to above.) Fairly obviously, P(A∩B) = P(B∩C) = P(C∩D) = ..., so all these terms with two consecutive letters are 8!/10!.
However, this leaves terms like P(A∩C) where the letters are not consecutive. But it turns out that these are all equal to 8!/10! as well. (example: p(A∩C) = 8x7x6!/10!, since there are 6! ways to permute 5,6,7,8,9,10, then 7 slots to fit 1,2 into, then 8 slots to fit 3,4 into).

You can use a whole host of similar arguments to prove that P(? ∩ ? ∩ ?) = 7!/10!, P(? ∩ ? ∩ ? ∩ ?) = 6!/10!, etc.

So p(A U B U ... U I) = [(9C1)x9! - (9C2)x8! + (9C3)x7! - ... + (9C9)x1!]/10! Which is disgusting. I make it about 0.595.

 

[Grundar]

Welcome fribble. Looks correct to me but I did some dirty checking (write up all possibilities and count) and for 2,3,4 and 5 songs the probability is 0.5 and there seems to be no reason the pattern shouldn't continue. The only suspicious piece in there seems to be at the end were you have ...(9C2)x8!... there are more than 9 (A ∩ B) there is (8+7+6+5+4+3+2+1) of them. and that goes for the rest of the terms too.

/Hans

Edit for spelling.

 

[fribble]

Thanks for the welcome!

While I agree that the probability with 2 or 3 songs is indeed 0.5, I disagree with you on your probabilities with 4 and 5 songs- I get 13/24 and 67/120 respectively.

As for (9C2)x8! - 9C2 is the same as 8+7+6+5+4+3+2+1 is it not?

9C2 = 9!/7!2! = (8x9)/2.

I would have used the more common binomial coefficient notation instead of nCr but I don't know how to do that.

 

[Grundar]

You are correct i missed one on 4 and that spread into the check on 5. And I'm sorry I didn't recognized that notation for the binomial coefficient. I stand corrected.

/Hans

 

[illuminatedwax]

Thanks for the welcome!

While I agree that the probability with 2 or 3 songs is indeed 0.5, I disagree with you on your probabilities with 4 and 5 songs- I get 13/24 and 67/120 respectively.

As for (9C2)x8! - 9C2 is the same as 8+7+6+5+4+3+2+1 is it not?

9C2 = 9!/7!2! = (8x9)/2.

I would have used the more common binomial coefficient notation instead of nCr but I don't know how to do that.

[ latex ]$ \binom{9}{2} $[ / latex ]
[latex]$\binom{9}{2}$[/latex]

 

[GreedyAlgorithm]

Hooray for brute-force, lookup, and shoulders of giants... OEIS is an amazing resource.

The probability you get at least 2 songs in the original order if your playlist has n+1 songs is
[latex]$1-\frac{\lfloor e^{-1}n! (n+2) +\frac{1}{2}\rfloor}{(n+1)!}$[/latex]
So for 10 songs, n=9, and we get a probability of 1-1468457/3628800 = 0.5953ish.

Edited for sign error and off by one error.

 

[TheBoyPaj]

Hooray for brute-force, lookup, and shoulders of giants... OEIS is an amazing resource.

The probability you get at least 2 songs in the original order if your playlist has n-1 songs is
[latex]$1-\frac{\lfloor e^{-1}n! (n+2) +\frac{1}{2}\rfloor}{n!}$[/latex]
So for 10 songs, n=9, and we get a probability of 1-1468457/3628800 = 0.5953ish.

I'm just a maths dunce, but if 10 = n-1 then isn't n = 11, not nine?

 

[GreedyAlgorithm]

I'm just a maths dunce, but if 10 = n-1 then isn't n = 11, not nine?

Absolutely correct. Turns out it's n+1.

Retconned!

 

[TheBoyPaj]

Assuming you are not allowing repeats, I reckon you can do this by the Inclusion-Exclusion principle as follows:
...

Which is disgusting. I make it about 0.595.

That fried my brain but I understood some of it. Thanks Fribble.