Numbering Blank Dice

[Latrinsorm]

I wondered about the following situation: if you had a die with X sides, how many rolls would it take you (on average) for all X sides to come up at least once? We can consider a 4-sided die with blank sides. The first side that comes up is labeled 1:

1 roll: 1/1 chance of 1 side numbered.

Now, we have a 3/4 chance to get a new side to number and a 1/4 chance to get the same side, so:

2 rolls: 1/4 1 side, 3/4 2 sides.

The 1 side state has the same chances as before, and the 2 sides state has a 1/2 chance of getting a new or old side, so:

3 rolls: [1/16 1 side, 3/16 2 sides], [3/8 2 sides, 3/8 3 sides]
3 rolls: 1/16 1 side, 9/16 2 sides, 3/8 3 sides

The 3 sides state has 1/4 chance of getting the last side and 3/4 chance of getting an old side:

4 rolls: [1/64 1 side, 3/64 2 sides], [9/32 2 sides, 9/32 3 sides], [9/32 3 sides, 3/32 4 sides]
4 rolls: 1/64 1 side, 21/64 2 sides, 9/16 3 sides, 3/32 4 sides

Naturally, the only way to get to 4 sides on any subsequent roll is from the 3 sides state, so if we can find an expression for the total 3 sides state for any n rolls we can multiply by 1/4 and obtain an expression for the incremental 4 sides state. We can then sum the products of the incremental 4 sides states with the number of rolls from n = 1 to infinity to find the average number of rolls to have all sides come up at least once. It is not necessary to actually go to infinity, luckily, because the incremental 4 sides state goes to zero (much) faster than n goes to infinity.

It turns out that the expressions are pretty easy if you start with the easiest:

1 side: 1 / [4 ^ (n-1)]
2 sides: (2 ^ (n-1) - 1) * 3 / [4 ^ (n-1)]
3 sides: (3 * (3 ^ (n-1) - 2 ^ n + 1)) / [4 ^ (n-1)]

All of which go to zero, as they should, so our sum is simply:

sum (n = 1, ..., infinity) {3 * (n + 1) * (3 ^ (n-1) - 2 ^ n + 1)) / [4 ^ (n-1)]}

Beats the hell out of me how to do that analytically, so I did it in a spreadsheet: 8 + 1/3. I also did it for n from 1 to 20:




1 1.00
2 3.00
3 5.50
4 8.33
5 11.42
6 14.70
7 18.15
8 21.74
9 25.46
10 29.29
11 33.22
12 37.24
13 41.34
14 45.52
15 49.77
16 54.08
17 58.45
18 62.86
19 67.31
20 71.79


But a much more interesting way of looking at it is like this:



1 1 1
2 1 3
3 2 11
4 6 50
5 24 274
6 120 1764
7 720 13068
8 5040 109584
9 40320 1026575.994
10 362880 10628639.34


Where the second column is (n-1)! and the third column is the numerator if the second column is used as the denominator. (My feeling is that the last two numbers in the third column being non-integral is due to rounding errors with the software.)

How cool is that??? We have a factorial in the denominator of a function that looks like a lazy polynomial. The best fit I can obtain is with fourth order, so:

Average Rolls = function(n) / (n-1)! ≈ f(n) / n! ≈ kn^4
(Where k is a numerical constant.)

ln [f(n) / n!] = ln [kn^4]
ln (f(n)) - ln (n!) = ln (k) + 4*ln(n)
ln (f(n)) - n * ln (n) + n ≈ ln (k) + 4*ln(n)
ln (f(n)) = ln (k) + (4 + n) * ln (n) - n

Exponentiating both sides:

f(n) = k * exp [(4 - n) * ln(n)] / exp (n)
f(n) = k * n ^ (4 + n) / exp (n)

Which matches pretty well (so far) at the top end with what I found empirically! I was really interested to see if there would be a limit, but it would appear that the average rolls needed to fully number a blank die plods resolutely to infinity as sides increase.

[Tisket]

Fucking math geek.

[LMingrone]

Go to any casino if you think they haven't already figured this out, bet money on your math. You'll either get rich or get kicked out.

Don't even go to a casino. There are plenty of places online that are ready to take your money.

Edit: I'll let you look it up on your own because I'm a jerk like that. But, there is a one line, short equation that explains everything you're trying to explain.

[Latrinsorm]

Fucking math geek.You make me so damp... down there.
Go to any casino if you think they haven't already figured this out, bet money on your math. You'll either get rich or get kicked out.

Don't even go to a casino. There are plenty of places online that are ready to take your money.

Edit: I'll let you look it up on your own because I'm a jerk like that. But, there is a one line, short equation that explains everything you're trying to explain.I'm not sure what you thought you read, but there aren't any gambling applications for this. There probably aren't any real world applications for this whatsoever. It's just (a cool) math (story). :)

[Delias]

I've already decided that dice are out to get me, and all the math in the world won't make it otherwise. I plan on rolling 1 less than the number I need, forever.

[phantasm]

At what number of sides does it become impossible to calculate?

[Bobmuhthol]

You are combining independent geometric distributions. I just woke up and I don't want to think about this, but you're basically saying "I want to keep going until my first success and my success probability changes after each success." It takes 1 try every time for the first side, on average 4/3 attempts for the second (p = 3/4), on average 2 attempts for the third (p = 1/2), and on average 4 attempts for the fourth (p = 1/4). So, on average, it takes 8 1/3 rolls to cover a 4-sided die, since an expected value of a sum is simply the sum of the expected values when the events are independent.

Why you need to formalize it in an equation is beyond me.



At what number of sides does it become impossible to calculate?

Never. It's always a sequence with as many terms as there are sides, so you'd have to have infinitely many sides.

[Bobmuhthol]

And no, there is no limit. It definitely diverges to infinity because it is impossible for the average number of necessary rolls to ever stay the same or decrease as n increases.

[Bobmuhthol]

If n represents the number of sides on the die, then the expression for how many rolls it takes, on average, to fill that die is:

sum(n/n + n/(n-1) + n/(n-2) + n/(n-3) + ... + n/(n-(n-2)) + n/(n-(n-1)) + n/1)

I always hated making equations to fit sequences but you might be able to do something with that. The continuous function doesn't really make sense to me for a few reasons, particularly because this is a purely discrete scenario.


Alternatively, factor the n:

n * sum(1/n + 1/(n-1) + 1/(n-2) + 1/(n-3) + ... + 1/(n-(n-2)) + 1/(n-(n-1)) + 1/1)


And with negative exponents:

n * sum(n^-1 + (n-1)^-1 + (n-2)^-1 + (n-3)^-1 + ... + (n-(n-2))^-1 + (n-(n-1))^-1 + 1^-1)


And thus, use sigma notation, i=1, toward n, n * i^-1.

That was easier than I expected.

[Asha]

I feel like I've wasted my life, partying and banging chicks.

[Bobmuhthol]

I haven't touched a programming language for long enough that I can't get a VBA do-loop to work correctly for me. If I still had QBasic I would be able to write it in a few seconds.

[Paradii]

I feel like I've wasted my life, partying and banging chicks.

Yeah, you do realize this is a online forum for a text based game that reach it's hay day in the AOL/Prodigy era. You are not fooling anyone.

[Bobmuhthol]

Okay, got it. Latrinsorm, your approximations are just slightly off starting with n=16, presumably due to rounding.


01 1.000
02 3.000
03 5.500
04 8.333
05 11.417
06 14.700
07 18.150
08 21.743
09 25.461
10 29.290
11 33.219
12 37.239
13 41.342
14 45.522
15 49.773
16 54.092
17 58.472
18 62.912
19 67.407
20 71.955
21 76.553
22 81.198
23 85.889
24 90.623
25 95.399
26 100.215
27 105.069
28 109.961
29 114.888
30 119.850
31 124.845
32 129.872
33 134.930
34 140.019
35 145.137
36 150.284
37 155.459
38 160.660
39 165.888
40 171.142
41 176.420
42 181.723
43 187.050
44 192.400
45 197.773
46 203.168
47 208.584
48 214.022
49 219.481
50 224.960


The step between two consecutive n values is increasing at a decreasing rate (it's about 7.8 at n=500) and the step between two consecutive steps is 1/(n-1). That is, there is a step of 2 between n=1 and n=2, and a step of 2.5 between n=2 and n=3. The difference in those steps, which first appears at n=3, is 1/2. For n=11, it's 1/10, and the same pattern follows for all n.

I also couldn't get the tabs to stick in IE so you probably won't be able to copy/paste the list in Excel :(

[Ryvicke]

http://img.photobucket.com/albums/v225/nobody_boy/KittenMittens.gif

[Bobmuhthol]

And the first 50 terms of your third column:


1
3
11
50
274
1764
13068
109584
1026576
10628640
120543840
1486442880
19802759040
283465647360
4339163001600
70734282393600
1223405590579200
22376988058521600
431565146817638000
8752948036761600000
186244810780170000000
4148476779335450000000
96538966652493100000000
2342787216398720000000000
59190128811701200000000000
1554454559147560000000000000
42373564558110800000000000000
1197348677077520000000000000000
35027999979859800000000000000000
1059681761389530000000000000000000
33115387462887700000000000000000000
1067915237466590000000000000000000000
35504333673331000000000000000000000000
1215830662512070000000000000000000000000
42849305986961900000000000000000000000000
1552908163497020000000000000000000000000000
57829595376179500000000000000000000000000000
2211288377386050000000000000000000000000000000
86763269335522400000000000000000000000000000000
3490928655502090000000000000000000000000000000000
14394399015883400000000000000000000000000000000000 0
60791001132841800000000000000000000000000000000000 00
26280631098897300000000000000000000000000000000000 0000
11623892946578200000000000000000000000000000000000 000000
52573345417080600000000000000000000000000000000000 0000000
24303361112722600000000000000000000000000000000000 000000000
11477605944577700000000000000000000000000000000000 00000000000
55351131775484300000000000000000000000000000000000 000000000000
27246193725912600000000000000000000000000000000000 00000000000000
13683925049359800000000000000000000000000000000000 0000000000000000

[Latrinsorm]

Why you need to formalize it in an equation is beyond me.Really? I think I would think it's pretty SOP for me judging from some of my other posts.

I like the sum you did, although you have a redundant term in n/(n-(n-1)) and n/1. It's already cleaned up some of the numerical errors I was running into: 9 goes exactly to 1026576 over 8!, 10 goes exactly to 10628640 over 9!.

.

I was looking at the continuous equations again and I think there's a pattern forming. The equations for a three sided die have similar form:

1: 1 / [3 ^ (n - 1)]
2: 2 * (2 ^ (n - 1) - 1) / [3 ^ (n - 1)]
3: (3 ^ (n - 1) - 2 ^ n + 1) / [3 ^ (n - 1)]

And for a two sided die:

1: 1 / [2 ^ (n - 1)]
2: (2 ^ (n - 1) - 1) / [2 ^ (n - 1)]

So the pattern for an X sided die is:

1: 1 / [X ^ (n - 1)]
2: (X - 1) * (2 ^ (n - 1) - 1) / [X ^ (n - 1)]

3 is really interesting, because the way it has 3^ and 2^ makes me think I can find at least a recursive function for S sides numbered. If we look at just the exponential parts of the numerators:

f1: 1 = 1 ^ (n - 1)
f2: 2 ^ (n - 1) - 1 = 1 * 2^ - 1 * 1^
f3: 3 ^ (n - 1) - 2 ^ n + 1 = 3 ^ (n - 1) - 2 * 2 ^ (n - 1) + 1 = 1 * 3^ - 2 * 2^ + 1 * 1^

I see Pascal's triangle! Delicious. All that remains now is to determine the coefficients. For S = 1 it's just 1, for S = 2 it's (X - 1). I would guess that for S = 3 we'd have a second order polynomial, and what I find is X ^ 2 / 2 - 3 * X / 2 + 1. I was kind of hoping a pattern would be immediately obvious from just the first three, but the only thing I can see is due to the zero constraints, so for general S I have:

a * X ^ S + b * X ^ (S - 1) + ... + z
a + b + ... + z = 0 for S > 1
a * 2 ^ S + ... + z = 0 for S > 2

And so on, so for every S I have one less equation than coefficient, but I'm also pretty sure that the first non-zero coefficient will always be 1, so I can derive them out if I don't want to get them analytically. I'm hoping a better pattern will show up, though.

The point (such as it is) in this is that if I can get a general function for S sides number for X sided dice, I can use S = X - 1, multiply by n / X, and have a general expression for the number I was putting in my sum (over n) earlier. Time for more thinking.

[Latrinsorm]

Or I'll just use all these numbers. Thanks Bob! :)
And the first 50 terms of your third column:Mm, I wonder if the zeroes are from a factorial nature or your only having 15 digits to work with in your program. At least some of them are definitely real.

[Bobmuhthol]

It's the 15 digit limit in Excel. Not sure if there's a way around it.

[Poop]

Really? I think I would think it's pretty SOP for me judging from some of my other posts.

I like the sum you did, although you have a redundant term in n/(n-(n-1)) and n/1. It's already cleaned up some of the numerical errors I was running into: 9 goes exactly to 1026576 over 8!, 10 goes exactly to 10628640 over 9!.

.

I was looking at the continuous equations again and I think there's a pattern forming. The equations for a three sided die have similar form:

1: 1 / [3 ^ (n - 1)]
2: 2 * (2 ^ (n - 1) - 1) / [3 ^ (n - 1)]
3: (3 ^ (n - 1) - 2 ^ n + 1) / [3 ^ (n - 1)]

And for a two sided die:

1: 1 / [2 ^ (n - 1)]
2: (2 ^ (n - 1) - 1) / [2 ^ (n - 1)]

So the pattern for an X sided die is:

1: 1 / [X ^ (n - 1)]
2: (X - 1) * (2 ^ (n - 1) - 1) / [X ^ (n - 1)]

3 is really interesting, because the way it has 3^ and 2^ makes me think I can find at least a recursive function for S sides numbered. If we look at just the exponential parts of the numerators:

f1: 1 = 1 ^ (n - 1)
f2: 2 ^ (n - 1) - 1 = 1 * 2^ - 1 * 1^
f3: 3 ^ (n - 1) - 2 ^ n + 1 = 3 ^ (n - 1) - 2 * 2 ^ (n - 1) + 1 = 1 * 3^ - 2 * 2^ + 1 * 1^

I see Pascal's triangle! Delicious. All that remains now is to determine the coefficients. For S = 1 it's just 1, for S = 2 it's (X - 1). I would guess that for S = 3 we'd have a second order polynomial, and what I find is X ^ 2 / 2 - 3 * X / 2 + 1. I was kind of hoping a pattern would be immediately obvious from just the first three, but the only thing I can see is due to the zero constraints, so for general S I have:

a * X ^ S + b * X ^ (S - 1) + ... + z
a + b + ... + z = 0 for S > 1
a * 2 ^ S + ... + z = 0 for S > 2

And so on, so for every S I have one less equation than coefficient, but I'm also pretty sure that the first non-zero coefficient will always be 1, so I can derive them out if I don't want to get them analytically. I'm hoping a better pattern will show up, though.

The point (such as it is) in this is that if I can get a general function for S sides number for X sided dice, I can use S = X - 1, multiply by n / X, and have a general expression for the number I was putting in my sum (over n) earlier. Time for more thinking.

You guys need girlfriends. Badly.

[Latrinsorm]

Ok so the pattern you found between steps can also be expressed:

S1 = 1
S2 = 1 + (1 + 1 / (2 - 1)) = 2 * 1 + 1 * 1 / (2 - 1)
S3 = 1 + (1 + 1 / (2 - 1)) + (1 + 1 / (2 - 1) + 1 / (3 - 1))

Or

SX = X + (X - 1) / (2 - 1) + ... + 1 / (X - 1)
= X + sum ((X - i + 1) / (i - 1)) [i = 2, ... ,X]
= X + sum ((X - i) / i) [i = 1, ... , X - 1]

versus your expression:

X * sum (1 / (X - i)) [i = 0, ... , X - 1]

Why are these equal?!?

[Bobmuhthol]

You guys need girlfriends. Badly.

My girlfriend is just about on par with me on this stuff.

[Tisket]

You guys need girlfriends. Badly.

I know that I can't be the only female to find brains sexy as hell.

Apparently you need a better quality of girlfriend.

edit: the zombie lover in me can't help it: BRAAAIIIINNnsssss!

[Poop]

My girlfriend is just about on par with me on this stuff.

Then she needs a boyfriend. Badly.

[Stanley Burrell]

I like this, because everyone forgets about factorials -- their being so awesome, they need an explanation point.

My problem is that you did not keep things to a coin. As we know, since round circles have been invented, we shall limit ourselves to the heads-or-tails function in any math higher than elementary algebra (Burrell, S. Numbering...1:1 PC. 2010.)

[Latrinsorm]

= X + sum ((X - i) / i) [i = 1, ... , X - 1]
Hey so check this out:
= X + sum (X / i - i / i)
= X + sum (X / i) - sum (1)
= X + sum (X / i) - (X - 1)
= X * sum (1 / i) + 1

Hurr hurr, partial harmonic series. eta: Did Bob say that hours ago? Yes he did. Did I notice? No I did not.
= X * (ln (X - 1) + γ) + 1

This isn't exactly right (because of γ), and the limiting difference appears to be exactly 1/2 (when allowing for rounding errors). I have no idea what that means, if anything, but I'm sure pleased with how clean it turned out.

[Tisket]

Did Latrin just masturbate to math?

[Latrinsorm]

It occurred to me while I was in bed late at night (NOT MASTURBATING) that if our sum is:

X * sum (1 / i) + 1

And we noticed that this can be expressed as:

f(X) / (X - 1)!

Then we can do:

1 + X * sum (1 / i) = f(X) / (X - 1)!
f(X) = (X - 1)! + sum (X! / i)

Which means we will always have an integral number, because i is only an integer between 1 and (X - 1). That's why. :)

Thus we would have:

f(2) = 1 + (2) = 1 + 2 * (1) = 3
f(3) = 2 + (6 + 3) = 2 + 3 * (2 + 1) = 1
f(4) = 6 + (24 + 12 + 8) = 6 + 8 * (3 + 3/2 + 1) = 50
f(5) = 24 + (120 + 60 + 40 + 30) = 24 + 30 * (4 + 2 + 4/3 + 1) = 274

So f(X) = (X - 1)! + (X! / (X - 1)) * S(X)
= (X - 1)! + X * (X - 2)! * S(X)
= (X - 2)! * ((X - 1) + X * S(X))

[Stanley Burrell]

Gosh darnit. Why do you mathematicians always have to wrap parentheses in parentheses and start with an f of X like there was only the twenty-fourth letter of the alphabet. Oh. And your guys' sigma = imaginary #s? Seriously?

All in all, how do you (Latrin) manage to know you're going to type out that many subsets and have the willpower to go through with it? Whole grain and high protein?

Now just find me a right triangle where a^3 + b^3 = c^3.