Posted by: thumpasery | November 24, 2008

Discrete Math: Probability Problem

I like this following probability brainteaser because it incorporates elements of our coursework (including permutations and a little set theory) with the need for a little creative and/or deep thinking that was not taught to us:

In an infinite sequence of random integers between 0 and 9, which of the following sequences are you more likely to see first?

1,1,1,1,1 or 1,2,3,4,5

This is not a trick question!

Advertisements

Responses

1. Isn’t the likelihood of obtaining ‘1,1,1,1,1’ the same as ‘1,2,3,4,5’ assuming uniform distribution? since the odds of getting a 1 given random integers between 0 – 9 is 1/10. So the odds of getting 5 consecutive 1s would be 0.1^5. Same reasoning applies for ‘1,2,3,4,5’. Am I on the right track here?

Thanks!

2. I can’t fully answer since it would give it all away, but you’re asking the right questions.

What I will say is that the likelihoods are different, and involve conditional probability. I would suggest simulating it, by just going through example yourself.

3. Alright, here is the *solution*:

1,2,3,4,5 is more likely. I understand this problem in two ways.

1) Consider looking at a sequence of n integers in the infinite sequence. For n=1,2,3,4 there is obviously 0% chance of finding either sequence. For n=5 the chance of finding 1,2,3,4,5 is the same as finding 1,1,1,1,1. But, for n=6 there is a difference. Consider the sets of six digits containing either sequence. For 1,1,1,1,1 they are of the forms:
1,1,1,1,x
And x,1,1,1,1

Similarly for 1,2,3,4,5 we have 1,2,3,4,5,x and x,1,2,3,4,5 where x is in [0,9].

Now for each five digit sequence consider how many distinct six digit sequences contain it. For 1,2,3,4,5 there are 20 (of 10^6) six digit sequences which contain the desired sequence. It would appear to be the same for 1,1,1,1,1 but there’s a problem. For x=1, x,1,1,1,1,1 is the same as 1,1,1,1,1,x. Therefore only 19 (of 10^6) six digit sequences contain the desired sequence. That means you’ve got a better chance of finding 1,2,3,4,5 first. An interesting note: both sequences appear the same number of times. 1,1,1,1,1 just appears twice in the same sequence.

2) Both sequences rely on a beginning 1. Since the probability of obtaining a 1 is the same in both sequences, we consider then the probability of obtaining 1,1,1,1,1 vs. 1,2,3,4,5, conditioning on the first 1 being obtained in the series.

But after that first 1 is given, the probability of getting 1,1,1,1,1 is clearly smaller, since any number besides 1 would force the series to reset to the initial probability of obtaining 1,1,1,1,1 whereas in the second series, getting a 2 would be “ideal” but getting a 1 would not force the series to reset. Likewise, after getting 1,2 in the second series (vs. 1,1 in the first), there are still two possible numbers out of ten (1 and 3) that would not force the series to reset completely, as compared to 1.

Since, if there were only five numbers, the probabilities are clearly the same (as calculated by Gokul), conditioning this way sets up a pretty easy inequality.

Both are different ways of looking at the solution, but they both rely on the same underlying concept, conditional probability.