How many rolls 'till n values in a row.

December 19, 2007 3:01 PM

Given a fair die with s sides, what is the expected number of rolls r before I get o outcomes with the same value v in a row? [Note this is emphatically NOT a homework problem; I just really want to know, feel like I should be able to figure it out, can't, and it is driving me nuts.]

For clarity a sample case would be, how many times do I need to roll a 6 sided die before I get 5 1s in a row. Please help.

posted by lucasks to science & nature (30 answers total)

Do you mean "before the probability that I have had o outcomes with the same value v in a row is greater than 50%? Or some other value of expected? You need to answer that before you can solve the problem.
posted by iknowizbirfmark at 3:07 PM on December 19, 2007

yes, 50% (though a generic solution would be awesome).
posted by lucasks at 3:09 PM on December 19, 2007

Probably not pure, but here's a way to think about it...

First, what the is probability of getting N die all the same. This is almost a binomial problem. You're looking for the probability of r "hits" in r rolls with the probability 1/s for each roll. That is, 3 hits in 3 rolls with probability 1/6 for normal dice. The probability of this is 0.00463. But, there are s ways to do this (3 ones, 3 twos, etc), so you need to multiply by s, for 0.02778. Call this probability x. If you try to work out the combinatorics directly, you'll probably get a slightly different answer, but that will be close.

If you think in terms of having a series of discrete trials of r rolls each, then it's just another binomial problem except you're not solving for the probability. You want to know what is the number of trials that will give you a probability of at least one hit of 0.5 or more. You should be able to do this easily enough by trial and error. In the case of 3 of a kind and normal dice, the resulting answer is 25 sets of 3 rolls.

Of course, it's not a series of discrete sets of rolls, and you might have 3 of a kind from the last two of one "set" and the first of the next. But the answer should be the right ballpark.
posted by ROU_Xenophobe at 3:25 PM on December 19, 2007

iknowizbirfmark: Expected value means if you did this experiment an infinite number of times, what would the average result be. This is not the same as when does the probability reach 50%.

For instance, the expected number of coin tosses before you get a head is 2. (1/2 of the time it will take just one toss, 1/4 of the time it will take two tosses, 1/8 of the time, 3, and so on, really looks like it approaches 2) But on your first toss, you have a 50% chance of getting a head.
posted by aubilenon at 3:29 PM on December 19, 2007 [1 favorite]

Given r rolls of an s-sided die, the probability of any particular sequence is 1/(s^r). There are s such sequences that satisfy your criterion, so the probability of getting such a sequence "in one go" would be s/(s^r) or 1/(s^(r-1)).

But you asked how many rolls would be necessary before such a sequence occurred with probability .5 or better. As a first approximation, you could ask how many sets of r rolls would be necessary before one fit your criterion. I think that's a simple matter of solving the equation .5 = xs/(s^r).

For a 6-sided die and 3 rolls, the result is x = 18.

For a numeric answer, I will be back shortly with the results of a computer program that simulates your problem.
posted by jedicus at 3:48 PM on December 19, 2007

One way of lookoing at it is that for a die with s sides and n identical outcomes, there will only be s different results for each n. So with a standard 6-sided die, in any combination of three rolls there will be 6 triples rolled out of s^n possible results.

So the chance c that any given sequence will be a run will be c=s/(s^n).

So determine c, then figure out how many iterations of c gives you a 50/50 shot at meeting the criterion. I don't remember the formula to determine the number of iterations (r) to make the odds 50/50, however....

But that's for any run. For a specific run, multiply r by s.

I think this is right. The mathemagicians around here will know for sure.
posted by ten pounds of inedita at 3:49 PM on December 19, 2007

Think of it this way:

I have an n-sided die. I want to get r rolls with v. If I already have r-1 rolls of v in a row, I should have a 1/n chance of this happening, meaning I need to do it n times for it to happen once. So this means that E_n(r) = (E_n(r-1)+1)*n, with E_n(0) = 0.

Solving the recurrence gives E_n(r) = n^r + n^r-1 + ... + n¹.
posted by goingonit at 3:49 PM on December 19, 2007

P(s,r,o,v)=(r-o+1)((1/s)^o)

so for your example:
0.5 0.5<> r>3892
posted by Durin's Bane at 3:56 PM on December 19, 2007

what the...?

That last line should be

0.5 is less than (r-5+1)((1/6)^5)

r is greater than 3892
posted by Durin's Bane at 4:01 PM on December 19, 2007

The probability that you will have three in a row of a particular value is p=1/s³ for any particular three rolls. For every roll of the die at or after o outcomes, there is p probability, so the number of rolls to achieve a particular probability q of the result r = (o - 1) + q/p. That won't work for any case where p>q, i.e. when where the probability threshold you set is below the probability of achieving the result on the first try. That seems quite simple, so maybe I'm misunderstanding the question.
posted by ssg at 4:01 PM on December 19, 2007

Oops, that should obviously be p=1/s^o
posted by ssg at 4:03 PM on December 19, 2007

Durin's Bane -- that formula doesn't make sense, since when r is large enough, P exceeds 1.
posted by goingonit at 4:06 PM on December 19, 2007

Okay okay. So the number of rolls it takes you to get any specific number on an N sided die is N. This makes intuitive sense, but I calculated the odds for the first 30 rolls and it checks out (the formula is: sum(t = 1->∞, t * 1/N * ((N-1)/N) ^ (t-1))) I'm not good enough with series to prove this will always converge on N, but it sure seems to for the few values I tried it with.

I'll come back to this. Let's define f(N, r) as how the expected number of rolls of an N sided die before you get any number r times in a row.

f(N, 1) = 1 (you will always get 1 number in a row on your first roll)

f(N, 2) = N+1
This is that first part, but instead of looking for a certain number you're looking for the previous number. It's impossible for the first roll, but for each other roll there's a 1/N chance you get the same number as before.

Okay each time you get x in a row, there's a 1/N chance you're also going to get x+1 in a row one roll later. But you can't just reroll, you have to reroll an average of f(N, x) times before you get another chance.

So F(N, r) = F(N, r-1) * N + 1

Oh crap! I just realized you were talking about a specific number repeatedly, not just any number repeatedly! No problem, though. We've already show that f'(N,1) = N, the inductive step stays the same!

So if you want to roll repeated ones here's a table :

Number in a row   |   required patience (in rolls)1                 |             62                 |            373                 |           2234                 |          13395                 |          80356                 |         48211

That's also the expected number of rolls before you come up with 123456 all in a row, or any arbitrary sequence that does not contain its own first digit anywhere but the beginning.

This is growing slightly faster than N^r
posted by aubilenon at 4:07 PM on December 19, 2007

Sorry that might be confusing. That table is the expected number of rolls for a specific result that many of times in a row. Not just any 4-of-a-kind
posted by aubilenon at 4:09 PM on December 19, 2007

aubilenion -- you're one is in the wrong place, because each time you get x in a row you need to roll one more to see if you'll get x+1 in a row. (I just did a monte carlo simulation because I wasn't sure of my reasoning, and found that the expected number of times you have to roll to get 2 in a row with a 6-sided die is 42).
posted by goingonit at 4:09 PM on December 19, 2007

sorry your one
posted by goingonit at 4:10 PM on December 19, 2007

Nevermind, then. I think I'm out of my league here.
posted by Durin's Bane at 4:15 PM on December 19, 2007

Oh shit, my reasoning is sound except the bit where I say the inductive step is the same. Thanks for catching me on that. I did my own simulation and sure enough, the adjusted formula holds (258 is the next value)

If you're looking for a specific value repeated, the number after a sequence of that value will not be of that value. When you're just looking for any old value to be repeated, one repeated sequence can immediately follow another.

So the correct answer for a specific value is:
So F(N, r) = F(N, r-1) * N + N


while the answer for ANY value r times in a row is
G(N,r) = G(N, r-1) * N + 1

Hah, for the base case, we can say: F(N, 0) = G(N, 0) = 0 (it takes no rolls to get 0 in a row)

So I'm not going to redo the table but for a 6 sided die, and {1-6} 1's in a row, the expected numbers of rolls required are: {6, 42, 258, 1554, 9330, 55986}
posted by aubilenon at 4:37 PM on December 19, 2007

Assuming my program is correct (and I feel better about it than my math), I get the following values for a 6-sided die averaged over 500 runs. Note, these are the values for any match, which is why they are slightly lower than aubilenon's.

(Number in a Row -> Average Number of Rolls)

1 -> 1
2 -> 7.092
3 -> 42.174
4 -> 250.48
5 -> 1509.946

About there I ran out of patience. Anyway, the data seem to line up pretty well with aubilenon's closed-form solution.
posted by jedicus at 4:41 PM on December 19, 2007

jedicus: Make sure you're using a good random number generator; and definitely make sure you're not using the lower bits of rand(). (ie., "rand() % 6" would be bad bad bad)
posted by blenderfish at 4:45 PM on December 19, 2007

blenderfish: rand() % 6 gave me the expected result that my (updated) calculations predicted, when I did it.
posted by aubilenon at 4:48 PM on December 19, 2007

Actually, that was over a 1000 runs. Also, the result for length 6 was 9025.9666

blenderfish: I assume that by now C#'s RNG is decent. I used Random.GetNext(1, sides + 1). Of course, I don't know what it's doing under the hood but I presume the function is sane.
posted by jedicus at 4:49 PM on December 19, 2007

Here's the Math World article for what you're interested in. Your dice toss is essentially a Bernoulli trial. In the Math World formula (2), however, I'm not sure what value "c" takes.
posted by sbutler at 5:17 PM on December 19, 2007

Sorry to change notation, but I'm using "n" to denote the number of sides of the die, and "r" the desired constant-run-length that you want to achieve. You won't necessarily like this, but someone else can simplify it to get a formula in terms of n and r alone, or I can do it in the morning after I double check it and find I've made a mistake anyway.

Let φ(x) = nx^r / (1 - (n-1)(x+x^2+...+x^(r-1)))

Let &lambda(x) = x&phi'(x)

Your expected wait to get a run of length r is &lambda(1/n).

Example: How many rolls of an n=6-sided die does it take, on average, to get a run of 4? Write out φ(x) as described above, differentiate and multiply by x, then plug in 1/6 for x. Answer: 259 rolls.
posted by Wolfdog at 6:44 PM on December 19, 2007

Preview. Bless its little heart.

Let λ(x) = xφ'(x).

And compute λ(1/n).

This is the expected wait before SOME run of length r shows up, without any preference for what the repeated one is. If you insist on having a run of 1's (or whichever your favorite is) you should be able to just multiply this result by n.
posted by Wolfdog at 6:49 PM on December 19, 2007

I believe that simplifies to (n^r - 1) / (n-1), actually. Now someone can come along and explain why that formula is totally obvious in hindsight.
posted by Wolfdog at 7:03 PM on December 19, 2007 [1 favorite]

Here's a nice thread on this problem, in the case where you ask: what is the expected number of flips of a coin before the first run of r heads is seen? The answer is 2^(r+1) - 2. Wolfdog's answer on the nose!
posted by escabeche at 7:41 PM on December 19, 2007

escabeche: that's not wolfdog's answer.

for n = 2, r = 6, wolfdog predicts 63, where your formula predicts 126.
posted by aubilenon at 1:28 AM on December 20, 2007

It is my answer on the cold wet nose, because (according to me), the time until a run of r (either heads or tails) is 2^r - 1. As I said, then, if you want the time until a run of r heads specifically, you have to multiply that by n=2.
posted by Wolfdog at 4:41 AM on December 20, 2007

Delightfully, not only is (n^r - 1)/(n-1) always an integer (which is a little unusual for an expected value problem like this), it can be rewritten as 1 + n + n^2 + ... + n^(r-1). And that means its representation in base n is precisely a run of r 1's. The question is "How long do I wait until a run of length r occurs?", and the answer is a run of length r! Again, I say, delightful.
posted by Wolfdog at 7:00 AM on December 20, 2007