Probability question

Factual Questions
21

I apologize for not taking the time to work this out, but one way to solve this problem is to use a Markov chain. The states are the number of successes you have had so far, and the matrix is pretty simple. The only entries will be along the diagonal, so P[sub]i,i[/sub] = i/s, and to the right, where P[sub]i,i+1[/sub] = q = 1 - i/s (as long as i < s+1).

E.g. for s = 5



(I used '.' to mean 0 in the matrix for easier reading.)

       0   1   2   3   4   5
  0    .   1   .   .   .   .
  1    .  1/5 4/5  .   .   .
  2    .   .  2/5 3/5  .   .
  3    .   .   .  3/5 2/5  .
  4    .   .   .   .  4/5 1/5 
  5    .   .   .   .   .   1

If you’re not familiar with Markov matrices, this is how to read it: The row represents the current state; the column represents the future state. The entry at a row and column is the probability of going from that row’s state to that column’s state on the next trial.

So, if we’ve already thrown 2 distinct numbers (2 ‘successes’ as it were), the probability on the next throw that we’ll go to 0 or 1 is of course 0 (can’t go down), it’s 2/5 that we stay at 2 (rolling the same number), and 3/5 that we get a new number (go to state 3). We can’t get more than 1 new number so the probability of getting 4 or 5 after 2 is 0.

Note that in the Markov matrix, all the values in a row add up to 1.

So what do we do with this to get an answer? All you need to do to get the results after any number of trials is raise the matrix to the number of trials, in other words multiply it by itself r times. (The sequence of matrices is what’s actually called the Markov chain.)

The values in the matrix will tell you the probability of going from any initial state (along the row) to a future state after r trials. So for what you’d want, you’d multiply the matrix by itself r times, then look at the upper right corner (row 0, col s+1), which is the probability of having s distinct numbers after r turns if you start from 0.

Now this is probably the easiest approach from a computational standpoint (assuming you’ve got some matrix math software), but there might be a way to derive a formula doing it algebraically. Unfortunately I don’t have time to do it right now.

22

FWIW (which isn’t much), an exact answer is given by this finite sum:

(s^r - C(r,1)(s-1)^r + C(r,2)(s-2)^r - C(r,3)(s-3)^r + …)/s^r

where C(r,i) = r!/i!(r-i)!, when i is between 0 and r and is 0 otherwise (which makes the sum finite). It is an application of the inclusion/exclusion principle. You are computing the odds that a function from a set of s elements to one of r elements covers every element of the latter. The number of functions is s^r and the number of ways of ending up in a given subset of n-1 elements is (s-1)^r, there are C(r,1) = r such subsets, but you are double counting those that end in a given subset of s-2 elements is (s-2)^r and they have to be subtracted,… To get more explanation, you need a book on combinatorics.

23

The Ryan is correct, the easiest way to do this problem is to use the principle of inclusion-exclusion. The same question (essentially) has come up before on the board, namely, in this thread, where it was asked how many people are required in a random group in order that it’s more likely than not that every birthday (ignoring leap days) is represented. This is exactly the same as the OP in this thread, where the die in question has 365 faces. My answer in that thread was:

This is the same as the formula The Ryan gave above:

sum(for i=0 to (s-1) of[ (-1)[sup]i/sup(s-i)[sup]r[/sup] )/s[sup]r[/sup].

On preview, I see Hari Seldon concurs as well, so I believe that settles it.

24

So, anyone willing to try to diagonalize the Markov matrix? Presumably it would be more complicated than my formula (and least that’s what my ego says). Also, one can approximate the binomial coefficients that appear in the formula with the normal distribution. Of course, that would result in a formula that one couldn’t solve exactly, but for large numbers it may be better in most circumstances.

25

Good, my hat looks too tough to chew properly (but I bought myself a beer just in case).

Happy as I am that the OP is answered I’d like to complain, Cabbage, how does your sig correspond to a mobius strip? Where’s the half twist in it? If anything it’s just a regular band, right?

26

Thanks very much guys, this problem is clearly harder than it looks at first sight. At least it confirms that my approximation, which simply assumes that the probabilities of having rolled each number are independent, works well enough for r > ~4s.

27

The Great Unwashed, yeah, it’s not a true Moebius sig, just a circular one. But “Moebius sig” sounds cooler than “circular sig”.

28

Wow, guess I came into this discussion VERY late (darn).
One time I wondered about rolling a 6 six-sided die and how many rolls it would take for the probability to be greater that .5 (or 50% if you will) that all 6 numbers would have appeared at least once. Like many of you have discovered, this innocent-looking problem is not very easy to solve.

I went through a lot of books (this was a pre-Internet era) and finally found that this is called an occupancy problem. Imagine that you have six boxes. A ball is then dropped with an equal likelihood that it will land in any of the six boxes. How long before the probability is greater than 50% that all boxes will be occupied? (Now you see where the term comes from). (Obviously this is another way of stating the 6-sided die problem).

I do remember 2 things 1) the answer involved using something called “Stirling’s Numbers of the Second Kind” and 2) the answer I got was 13 rolls of the die which seems to be in agreement with Ryan’s distribution table. Perhaps Ryan’s complex formula is the way to generate “Stirling’s Numbers of the Second Kind”.

Just out of curiosity Ryan, what is ‘p’ for 12 rolls and 13 rolls? I’m guessing it is slightly less than .5 for 12 rolls and slightly greater than .5 for 13 rolls.

29

For 12 rolls, p = 0.4378.
For 13 rolls, p = 0.5139.

You guess well. :slight_smile:

30

All right !!!
Actually, it was something I remembered from my “self-imposed” problem many years ago. I knew it had to be 13 to be better than a 50% chance. Glad to know I figured it out right, all those years ago.
Looks as if we all learned something from this thread.