a little logical/probability/math problem for you (1 Viewer)

[andrew markworthy]

I thought of this while driving this morning and it's bugging me that I can't think through the answer properly. It's a while since we've had one of these logical/mathematical problems on After Hours so I thought some of you guys might be interested.

I have an MP3 player in my car that will either play the tracks sequentially or at random. If played sequentially, it obviously enough plays track 1, then track 2, etc, until you reach the last track. The random play plays tracks at random (duh ...) and can play the same track two or more times before all the tracks on the disc have been played.

Okay, here's the problem. Let's suppose that I have a disc with e.g. 100 tracks on it and I want to hear a particular song which I know is on the disc but I don't know where it is. Let's also suppose that once I start playing the disc I've just got to let it run (i.e. I can't use the track skip button). Will sequential or random play be more likely to play the song I want to hear first?

An additional question - does it matter how many tracks there are and whether some are much longer than others?

Obviously enough, the random play is more likely to succeed if the track is one of the last on the disc, but beyond that the problem gets a little sticky.

 

[Neil Joseph]

Seems to me like random or sequential will yield the same probablity as far as getting to the track without knowing where it is on the disk (from 1 to 100). If you know where it is on the disk then more detailed probablities can be calculated.

 

[george kaplan]

Yes to what Joseph said. To be more precise, if the 100 tracks take X minutes to play, then if your song begins in the first X/2 minutes, it will be more likely to play first sequentially. If it's in the latter half, you have a higher probability of hearing it first in a random selection without replacement. Since you have random selection with replacement, it's harder to tell. The length of the various tracks which might be repeated before your track come into play. The probability that your track is first won't change, but the expected time til your track plays will go up since you're sampling with replacement, and the precise details would depend on all those factors.

 

[Brian Perry]

I would say the sequential method would be faster only because the random method you mentioned can repeat tracks. If the random method played each song only once, I would say the times would be the same.

 

[Jimi C]

That button says random on it for a reason. There is no way to answer this question.

 

[Cees Alons]

Brian is right, and for the reason he mentioned.

This can also be phrased as follows: if you play sequentially, there's a 1 to 100 chance that your song is the first one. If it isn't, the chance raises to 1 to 99 that it's the next, then 1 to 98, and so on. Each next "choice" will have a better chance, finally leading to 1 to 1, if necessary.

If you play randomly as described, the chance will be 1 to 100, every the time, again and again. It's theoretically possible that it won't ever be selected.


Cees

 

[george kaplan]

Well, only if you play a finite number of times. If you play forever the probability of it never playing is zero. And of course the odds of any of 100 songs never coming up in a reasonably long string of events (e.g., in the thousands), soon becomes so close to zero as to be practically impossible. But yes, without playing infinitely, you can't rule out the chance that your song would never come up.

 

[Keith Mickunas]

Don't forget the issue of how random the random option is. When it comes to computers, there is no such thing as a random number. I've forgotten the specifics but as I recall you judge the quality of a random number generate by the length of it's sequence before it repeats the entire sequence again, and how many times it repeats the same number in a row, as well as the number of runs and the length of those runs of sequential numbers.

Sadly I can't remember me enough probability theory to tell you what the proper odds are. I think the odds 1 in 100! factorial to hear the song if the random never repeated, or something like that, and that might be the same for dealing with it sequentially, where as the odds for hearing it on random might be 1 in 100^100. But those both sound high, and like I said, it's been too long for me to remember properly.

But in short, I agree, sequential has the highest probability of hearing it sooner.

 

[Cees Alons]

True, in fact it will probably never repeat the same random "seed" number within a number of times equal to some large power of two. However, the hash-function that reduces the random number to an integer between 1 and 100 (inclusive) will yield repetitive results, unless the software prohibits this.

Of course, the chance we're discussing will be exactly equal to the one for a sequential method then (it will effectively be a sequential method that way, only in a hashed order).


Cees

 

[Brett_B]

Wouldn't this statement come into play when determining the odds (especially considering the fact of which playback option would yield a certain song being played first).

 

[Cees Alons]

Did you actually read the thread, Brett?


Cees

 

[DaveF]

Another perspective on this (were the player not allowed to repeat songs): Both cases in the stated problem are identical and so the liklihood of hearing your played would be identical.

In the first case, the song is randomly placed in a list which is played sequentially. The time to reach the song is then random.

The second case, the song is placed at the start of the list, the list shuffled, and then played in this random order.

In both cases a sequential list of songs is played, with the song of interest at some unknown, random position in the list. The scenarios are equivalent and so neither one is prone to play the song sooner or later.

Of course, since the player can repeat songs, it will most likely find the songs you dislike and play then incessantly, while avoiding the song of interest.

 

[andrew markworthy]

Thanks for the replies guys and I now think I can explain it conceptually (I could work out the forumla I guess, but life's too short).

Imagine that you have an opaque container in front of you and in it are balls about the size of pool balls. You can't see the balls inside the container and can only see what they look like when you pull them out of the container. You are told that all the balls are white except for one which is black. You are told to continue to pull out the balls until the black one appears, when you can stop. [The black ball represents the wanted track, the white balls the unwanted tracks]

Let's presume for the sake of argument that there are four balls (three white, one black). [The argument works perfectly well with other numbers, but four is about right for explaining the situation].

In the sequential condition, the container is like a really tight tube sock - it's impossible to rummage around, so you can only take the ball nearest the opening. You are thus forced to take the balls out in the reverse order they were inserted. Assuming that the balls were put in at random, there are four equally probable orders in which the balls can come out:

WWWB
WWBW
WBWW
BWWW

In the random non-refreshing condition, the container is like a normal sort of bag, so you are equally free to take out any ball, and when a ball is out of the bag, it isn't replaced. Thus, there are four possible sequences in which the balls can be taken out:

WWWB
WWBW
WBWW
BWWW

This is identical to the sequential condition - in other words, there is an equal probability of finding the black ball using the two methods. The odds in both cases are:

First pick: 1 in 4 chance of finding the black ball
Second pick: 1 in 3
Third pick: 1 in 2
Fourth pick: absolute certainty

In the random refreshing condition, when you take out a ball, it is replaced in the bag once you've looked at it. In other words, every time you put your hand in the bag, there are the same number of balls to choose between. Thus, on every occasion, the chances of finding the black ball are 1 in 4. The odds are thus considerably worse than the sequential or random non-refreshing condition.

The only time that the random refreshing condition stands a better chance of finding the black ball is when you know that the black ball is at or towards the end of the sequence. Suppose that the black ball is the last in the sequence of four balls. It will take three trials to discover this. In three trials of the random refreshng condition, there is a 3 in 4 chance (1/4+1/4+1/4) of getting the black ball. The odds get more in the random refreshing's favour the bigger the set size (e.g. if the black ball is the last in a line of 100, then there is a 99/100 chance of finding it in fewer trials by the random refreshing condition). However, this is only a probability - there is no guarantee using the random refreshing method that you will find the black ball, whilst the sequential method will always get a result. Plus, if the black ball is earlier in the sequence, the odds are greatly in favour of the sequential method. There is obviously a formula that represents the relative advantages of the two methods at different points in the draw, but as I said, life's too short to work it out (at least for my microbrain).

 

[ScottHH]

Andrew,

Working with your 4 ball random refreshing condition, your math is incorrect. You need to multiply, not add your probabilities. In three trials, what is the chance of NOT getting a black ball: It is .75 x .75 x .75, or 42.1875%

By definition, we now know that the chance of GETTING the black ball at least once in three trials is 1-.421875 or 57.8125%. But let's calculate it anyway:

Once we get the black ball we can stop. So we get a black ball in any of the three following scenarios:
B--
WB-
WWB

Here are the probabilities of these 3 scenarios:
B .25
WB .75*.25 = .1875
WWB .75*.75*.25 =.140625
Add them up and get .578125


Now let's go back to the original problem: 100 songs, you want to hear one. On average, using sequential play, your song will be the 50th you hear. So what is the chance you WILL NOT hear your song in 50 chances of the "random refreshing condition"? It is .99^50 = 60.5%. What are the chances you won't hear it in 100 trials: .99^100 =36.6%. I'd say use sequential play.

"An additional question - does it matter how many tracks" Yes, more tracks and random refreshing is worse. In reality by the time you have 25 tracks it's very close to the limit.

Here's the formula:
If there are N songs, the chance not hearing your song in the first half of play is (1-(1/N))^(N/2)

The chance of not hearing your song in N trials (meaning that even if your song is dead last sequential play will beat random refreshing) is (1-(1/N))^(N)

 

[andrew markworthy]

Surely not ... what you have cited is the probability of getting a particular sequence of events.

Let's take a more basic example. The odds of tossing heads on a coin are 1/2. Ergo, if you toss a coin twice, there is an evens (i.e. 1/1) chance of getting heads. Using the additive method, you get the right answer (1/2+1/2 = 1). Using your method, you would multiply the odds of not getting heads, which would give you 1/2x1/2 = 1/4 chance of getting heads on two tosses of the coin.

Now suppose we want to test the probability of a particular sequence of events. If we toss a coin twice, there are four possible outcomes:

HH
TT
HT
TH

The probability of tossing heads twice is 1/2 x 1/2 = 1/4. We can verify this by looking at the possible range of options and can see that 'HH' is one of four possible outcomes.

I think you're calculating the odds of a particular sequence rather than the odds of a specific event happening. However, I'm no expert on probability theory, so please correct me if I'm wrong.

 

[Cees Alons]

Andrew,

No, it's still possible to NOT get a head (the TT option in your example).

Scott is right, but you have to reverse twice. First multiply the chances of NOT get a head at all (because you stop when you do get one and thus, you won't throw the same length of series in those cases, complicating the computation) and - because now you have got the chance of not throwing a head at all in N throws - subtract it from 1 to find the only other outcome (getting at least 1 head).

So, in your example: each time there's a 1/2 chance of NOT throwing a head, so two tosses have a chance of 1/2 x 1/2 = 1/4 of NOT getting a head at all. Ergo, the chance to get at least one head in a maximum of two throws is 1 - 1/4 = 3/4. And indeed not 1.
In your example: HH, HT or TH, which is 3 of 4.

(Also note that the HH option doesn't count as two heads. )


Cees

 

[Neil Joseph]

I thought that if you tossed a coin, there was a chance, however remote, to get sides (neither heads nor tails)

 

[andrew markworthy]

Cees - ah right, now I see! So it's working along the lines of the 'same birthday' example (for those who don't know it - how many people do you need in a room for there to be a 50% chance or better that two people share the same birthday? The answer, amazingly enough, is about 22 people).

Thank goodness I only have to deal in statistics and not probability.


Yes indeed there is. Probably a slightly lower chance than a HTF Administrator has of not electrocuting himself by licking his fingers and putting them against a live wire. If you're game Neil, you start licking your fingers and I'll get out a coin.

 

[DaveF]

andrew - a sanity check also shows your original estimation of the refreshing/random case was suspect.

If, for the four-balls problem, the probabilities were additive, then five draws would give a 125% chance of picking the ball. That is, you were guaranteed to pull the black ball once and might get it a second time. But experience suggests this is not the case, and points us towards the subsequent explanations.

 

[Cees Alons]

It is possible to compute the overall chance by addition, but you need to add the proper numbers. Let's take andrew's example again.

The chance to immediately throw a head is 1/2 (I'm ignoring the so-called Neil's Possibility).
Only if you get tails, the other half of the chances, you will throw again and then (once more) have a chance of 1/2 that it's head again. So this chance is worth 1/2 x 1/2 = 1/4 of the total (half of the cases times the chance).

Total chance to throw at least one head in two tosses, and yes, both chances have to be added: 1/2 + 1/4 = 3/4 again!



Cees