Another dice problem
March 28th, 2020 at 9:04:15 AM
permalink
The website www.fivethirtyeight.com has riddlers each week that are usually math related. Here's one from this week. I'm thinking you'd need to take a Markov Chain approach to this? It's been too long though, don't remember how to do them.
You start with a fair 6-sided die and roll it six times, recording the results of each roll. You then write these numbers on the six faces of another, unlabeled fair die. For example, if your six rolls were 3, 5, 3, 6, 1 and 2, then your second die wouldn’t have a 4 on it; instead, it would have two 3s.
Next, you roll this second die six times. You take those six numbers and write them on the faces of yet another fair die, and you continue this process of generating a new die from the previous one.
Eventually, you’ll have a die with the same number on all six faces. What is the average number of rolls it will take to reach this state?
Extra credit: Instead of a standard 6-sided die, suppose you have an N-sided die, whose sides are numbered from 1 to N. What is the average number of rolls it would take until all N sides show the same number?
You start with a fair 6-sided die and roll it six times, recording the results of each roll. You then write these numbers on the six faces of another, unlabeled fair die. For example, if your six rolls were 3, 5, 3, 6, 1 and 2, then your second die wouldn’t have a 4 on it; instead, it would have two 3s.
Next, you roll this second die six times. You take those six numbers and write them on the faces of yet another fair die, and you continue this process of generating a new die from the previous one.
Eventually, you’ll have a die with the same number on all six faces. What is the average number of rolls it will take to reach this state?
Extra credit: Instead of a standard 6-sided die, suppose you have an N-sided die, whose sides are numbered from 1 to N. What is the average number of rolls it would take until all N sides show the same number?
March 28th, 2020 at 1:05:10 PM
permalink
Good problem. I'm on it.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
March 28th, 2020 at 3:43:18 PM
permalink
I'll let you guys do the math (because I can't) but I come up with an average number of rolls of 9.662... which seems a little seems low to me.
March 28th, 2020 at 4:14:53 PM
permalink
Quote: EdCollinsI'll let you guys do the math (because I can't) but I come up with an average number of rolls of 9.662... which seems a little seems low to me.
Ed, your answer appers to be the number of dice used; the number of rolls would be 6 times that
I did it with a Markov chain, using eleven "states":
State 0 is {6}
State 1 is {5,1}
State 2 is {4,2}
State 3 is {4,1,1}
State 4 is {3,3}
State 5 is {3,2,1}
State 6 is {3,1,1,1}
State 7 is {2,2,2}
State 8 is {2.2.1.1}
State 9 is {2,1,1,1,1}
State 10 is {1,1,1,1,1,1}
The numbers indicate how many times a particular number appears on a die - for example, {5,1} could be 226262, or 344333, or 155551 - any permutation of 4 of one number and 2 of another
The initial state is state 10; the question is, how many rolls (which is 6 times the number of dice) are needed to get to state 0
This is 10 equations in 10 unknowns:
23,328 = 13,938 E(1) - 4,875 E(2) - 1,250 E(4)
729 = - 204 E(1) + 429 E(2) - 160 E(4)
7,776 = - 2,058 E(1) - 1,365 E(2) + 6,456 E(3) - 430 E(4) - 1,680 E(5) - 240 E(7)
32 = - 6 E(1) - 15 E(2) + 22 E(4)
23,328 = - 2,586 E(1) - 4,335 E(2) - 3,240 E(3) - 2,510 E(4) + 14,688 E(5) - 1,620 E(7)
3,888 = - 372 E(1) - 345 E(2) - 660 E(3) - 140 E(4) - 1,200 E(5) + 3,528 E(6) - 210 E(7) - 540 E(8)
243 = - 12 E(1) - 30 E(2) - 30 E(3) - 20 E(4) - 120 E(5) + 213 E(7)
23,328 = - 798 E(1) - 1,575 E(2) - 2,640 E(3) - 970 E(4) - 8,400 E(5) - 2,400 E(6) - 1,800 E(7) + 18,648 E(8)
11,664 = - 222 E(1) - 345 E(2) - 990 E(3) - 190 E(4) - 2,880 E(5) - 1,800 E(6) - 630 E(7) - 3,510 E(8) + 10,584 E(9)
7,776 = - 30 E(1) - 75 E(2) - 300 E(3) - 50 E(4) - 1,200 E(5) - 1,200 E(6) - 300 E(7) - 2,700 E(8) - 1,800 E(9) + 7,656 E(10)
Solving gets E(10) = 9.65699, so there are 6 x 9.65699 = about 57.94 die rolls needed
March 28th, 2020 at 4:22:53 PM
permalink
Don: Thanks. I assumed each "roll" was a roll of six dice all at once. And yet when I re-read the question... I still think that's the case. :)
March 28th, 2020 at 4:26:29 PM
permalink
Quote: EdCollinsDon: Thanks. I assumed each "roll" was a roll of six dice all at once. And yet when I re-read the question... I still think that's the case. :)
“ You start with a fair 6-sided die and roll it six times, recording the results of each roll.”
?
The race is not always to the swift, nor the battle to the strong; but that is the way to bet.
March 28th, 2020 at 4:27:58 PM
permalink
Yea, and then after re-reading it again I realized I completely misread it.
Thanks.
Thanks.
March 28th, 2020 at 4:36:35 PM
permalink
There must be a trick/formula for this, especially to solve the extra credit problem of n sided die
I can only think of listing out the various combinations of the unfair die then doing a Markov chain with many states, which is basically brute forcing it IMO
I can only think of listing out the various combinations of the unfair die then doing a Markov chain with many states, which is basically brute forcing it IMO
It’s all about making that GTA
March 28th, 2020 at 9:06:17 PM
permalink
As usual, I only can find the answer by simulations, rolls required = 57.943
March 28th, 2020 at 10:18:30 PM
permalink
Quote: Ace2There must be a trick/formula for this, especially to solve the extra credit problem of n sided die
I can only think of listing out the various combinations of the unfair die then doing a Markov chain with many states, which is basically brute forcing it IMO
The best equation(but not that accurate), Rolls required = 1.955*N^2 - 2.085*N, for N sided die
March 29th, 2020 at 6:39:47 AM
permalink
I agree with Don. Here is my transition matrix.
Here is the expected turns and rolls from each possible state.
| Initial State | aaaaaa | aaaaab | aaaabb | aaabbb | aaaabc | aaabbc | aabbcc | aaabcd | aabbcd | aabcde | abcdef |
|---|---|---|---|---|---|---|---|---|---|---|---|
| aaaaaa | 1.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
| aaaaab | 0.334919 | 0.402521 | 0.208976 | 0.053584 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
| aaaabb | 0.089163 | 0.279835 | 0.411523 | 0.219479 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
| aaabbb | 0.031250 | 0.187500 | 0.468750 | 0.312500 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
| aaaabc | 0.087834 | 0.264660 | 0.175540 | 0.055298 | 0.169753 | 0.216049 | 0.030864 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
| aaabbc | 0.017018 | 0.110854 | 0.185828 | 0.107596 | 0.138889 | 0.370370 | 0.069444 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
| aabbcc | 0.004115 | 0.049383 | 0.123457 | 0.082305 | 0.123457 | 0.493827 | 0.123457 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
| aaabcd | 0.015689 | 0.095679 | 0.088735 | 0.036008 | 0.169753 | 0.308642 | 0.054012 | 0.092593 | 0.138889 | 0.000000 | 0.000000 |
| aabbcd | 0.002786 | 0.034208 | 0.067515 | 0.041581 | 0.113169 | 0.360082 | 0.077160 | 0.102881 | 0.200617 | 0.000000 | 0.000000 |
| aabcde | 0.001457 | 0.019033 | 0.029578 | 0.016289 | 0.084877 | 0.246914 | 0.054012 | 0.154321 | 0.300926 | 0.092593 | 0.000000 |
| abcdef | 0.000129 | 0.003858 | 0.009645 | 0.006430 | 0.038580 | 0.154321 | 0.038580 | 0.154321 | 0.347222 | 0.231481 | 0.015432 |
Here is the expected turns and rolls from each possible state.
| State | Exp. Turns | Exp. Rolls |
|---|---|---|
| aaaaab | 4.6230005626557 | 27.7380033759344 |
| aaaabb | 6.5848404469094 | 39.5090426814565 |
| aaabbb | 7.2050277308898 | 43.2301663853388 |
| aaaabc | 6.9626146636615 | 41.7756879819688 |
| aaabbc | 8.0527353906356 | 48.3164123438138 |
| aabbcc | 8.5226688336294 | 51.1360130017765 |
| aaabcd | 8.4305096073877 | 50.5830576443261 |
| aabbcd | 8.9004430503815 | 53.4026583022888 |
| aabcde | 9.2782172671335 | 55.6693036028011 |
| abcdef | 9.6559914838856 | 57.9359489033134 |
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
March 29th, 2020 at 7:47:15 AM
permalink
For those of you who solved, you can go to the website and submit your answer for a potential shout out in the following week, if that appeals to you.
March 29th, 2020 at 8:08:56 AM
permalink
Quote: WizardI agree with Don. Here is my transition matrix.
Initial State aaaaaa aaaaab aaaabb aaabbb aaaabc aaabbc aabbcc aaabcd aabbcd aabcde abcdef aaaaaa 1.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 aaaaab 0.334919 0.402521 0.208976 0.053584 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 aaaabb 0.089163 0.279835 0.411523 0.219479 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 aaabbb 0.031250 0.187500 0.468750 0.312500 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 aaaabc 0.087834 0.264660 0.175540 0.055298 0.169753 0.216049 0.030864 0.000000 0.000000 0.000000 0.000000 aaabbc 0.017018 0.110854 0.185828 0.107596 0.138889 0.370370 0.069444 0.000000 0.000000 0.000000 0.000000 aabbcc 0.004115 0.049383 0.123457 0.082305 0.123457 0.493827 0.123457 0.000000 0.000000 0.000000 0.000000 aaabcd 0.015689 0.095679 0.088735 0.036008 0.169753 0.308642 0.054012 0.092593 0.138889 0.000000 0.000000 aabbcd 0.002786 0.034208 0.067515 0.041581 0.113169 0.360082 0.077160 0.102881 0.200617 0.000000 0.000000 aabcde 0.001457 0.019033 0.029578 0.016289 0.084877 0.246914 0.054012 0.154321 0.300926 0.092593 0.000000 abcdef 0.000129 0.003858 0.009645 0.006430 0.038580 0.154321 0.038580 0.154321 0.347222 0.231481 0.015432
Here is the expected turns and rolls from each possible state.
State Exp. Turns Exp. Rolls aaaaab 4.6230005626557 27.7380033759344 aaaabb 6.5848404469094 39.5090426814565 aaabbb 7.2050277308898 43.2301663853388 aaaabc 6.9626146636615 41.7756879819688 aaabbc 8.0527353906356 48.3164123438138 aabbcc 8.5226688336294 51.1360130017765 aaabcd 8.4305096073877 50.5830576443261 aabbcd 8.9004430503815 53.4026583022888 aabcde 9.2782172671335 55.6693036028011 abcdef 9.6559914838856 57.9359489033134
Help me get from the top table to the bottom table. Are you multiplying the matrix by itself?
March 29th, 2020 at 8:34:57 AM
permalink
Quote: Wizard...9.6559914838856 57.9359489033134...
9.6559914838856 is your final answer.
Do not multiply by 6, because the goal of the game is only to get one die with all faces the same. (See, "Eventually, you’ll have a die with the same number on all six faces. What is the average number of rolls it will take to reach this state?")
Good work on your answer, though. I'm still trying to complete my transition matrix.
March 29th, 2020 at 9:13:56 AM
permalink
Quote: rsactuary
Help me get from the top table to the bottom table. Are you multiplying the matrix by itself?
My Calcs in Google Sheets
I heart Crystal Math.
March 29th, 2020 at 9:29:58 AM
permalink
Quote: rsactuary
Help me get from the top table to the bottom table. Are you multiplying the matrix by itself?
Let me see if I can answer this one...
A "state" is how the numbers appear on a die. State "aaaaaa" is the same number on all six sides; state "aaaaab" is one number on five sides and another on the sixth; state "aabbcd" is two numbers on two sides each, and two numbers on one side each; and so on.
Look at the "state aaaaab" row - rolling a die in state aaaaab six times will result in:
* the same number appearing six times, with probability 0.334919
* one number being rolled five times and another once (state aaaaab), with probability 0.402521
* one number being rolled four times and another twice (state aaaabb), with probability 0.208976
* two numbers each being rolled three times (state aaabbb), with probability 0.053584
Let E(x) be the expected number of turns needed to get from state x to state aaaaaa;
E(aaaaab) = 1 + 0.334149 * E(aaaaaa) + 0.402521 * E(aaaaab) + 0.208976 * E(aaaabb) + 0.053584 * E(aaabbb)
Note that E(aaaaaa) = 0, and you can subtract E(aaaaab) from both sides, to get:
0 = 1 + 0.334149 * E(aaaaaa) + (0.402521 - 1) * E(aaaaab) + 0.208976 * E(aaaabb) + 0.053584 * E(aaabbb)
Do this with every row in the matrix except for the top one, and you have ten equations in ten unknowns; solve for E(abcdef).
A method for solving N equations in N unknowns is available on request...
March 29th, 2020 at 9:37:09 AM
permalink
Quote: ThatDonGuyLet me see if I can answer this one...
A "state" is how the numbers appear on a die. State "aaaaaa" is the same number on all six sides; state "aaaaab" is one number on five sides and another on the sixth; state "aabbcd" is two numbers on two sides each, and two numbers on one side each; and so on.
Look at the "state aaaaab" row - rolling a die in state aaaaab six times will result in:
* the same number appearing six times, with probability 0.334919
* one number being rolled five times and another once (state aaaaab), with probability 0.402521
* one number being rolled four times and another twice (state aaaabb), with probability 0.208976
* two numbers each being rolled three times (state aaabbb), with probability 0.053584
Let E(x) be the expected number of turns needed to get from state x to state aaaaaa;
E(aaaaab) = 1 + 0.334149 * E(aaaaaa) + 0.402521 * E(aaaaab) + 0.208976 * E(aaaabb) + 0.053584 * E(aaabbb)
Note that E(aaaaaa) = 0, and you can subtract E(aaaaab) from both sides, to get:
0 = 1 + 0.334149 * E(aaaaaa) + (0.402521 - 1) * E(aaaaab) + 0.208976 * E(aaaabb) + 0.053584 * E(aaabbb)
Do this with every row in the matrix except for the top one, and you have ten equations in ten unknowns; solve for E(abcdef).
A method for solving N equations in N unknowns is available on request...
Thanks TDG, I think I can take it from here.
March 29th, 2020 at 3:00:52 PM
permalink
I know Oliver Roeder (the previous "riddler" at 538) was a lurker here. Not sure if the new guy is too, but it wouldn't be surprising. Gambling and game theory are big topics over there, in the background if not overtly on the site.
"So as the clock ticked and the day passed, opportunity met preparation, and luck happened." - Maurice Clarett
March 29th, 2020 at 8:17:06 PM
permalink
Quote: rsactuaryHelp me get from the top table to the bottom table. Are you multiplying the matrix by itself?
Simple matrix algebra. Multiplying my transition matrix by 6^6, the expected number of turns is determ(A)/determ(B).
Where A =
| -27876 | 9750 | 2500 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 13056 | -27456 | 10240 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 8748 | 21870 | -32076 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 12348 | 8190 | 2580 | -38736 | 10080 | 1440 | 0 | 0 | 0 | 0 |
| 5172 | 8670 | 5020 | 6480 | -29376 | 3240 | 0 | 0 | 0 | 0 |
| 2304 | 5760 | 3840 | 5760 | 23040 | -40896 | 0 | 0 | 0 | 0 |
| 4464 | 4140 | 1680 | 7920 | 14400 | 2520 | -42336 | 6480 | 0 | 0 |
| 1596 | 3150 | 1940 | 5280 | 16800 | 3600 | 4800 | -37296 | 0 | 0 |
| 888 | 1380 | 760 | 3960 | 11520 | 2520 | 7200 | 14040 | -42336 | 0 |
| 180 | 450 | 300 | 1800 | 7200 | 1800 | 7200 | 16200 | 10800 | -45936 |
B =
| -27876 | 9750 | 2500 | 0 | 0 | 0 | 0 | 0 | 0 | -46656 |
| 13056 | -27456 | 10240 | 0 | 0 | 0 | 0 | 0 | 0 | -46656 |
| 8748 | 21870 | -32076 | 0 | 0 | 0 | 0 | 0 | 0 | -46656 |
| 12348 | 8190 | 2580 | -38736 | 10080 | 1440 | 0 | 0 | 0 | -46656 |
| 5172 | 8670 | 5020 | 6480 | -29376 | 3240 | 0 | 0 | 0 | -46656 |
| 2304 | 5760 | 3840 | 5760 | 23040 | -40896 | 0 | 0 | 0 | -46656 |
| 4464 | 4140 | 1680 | 7920 | 14400 | 2520 | -42336 | 6480 | 0 | -46656 |
| 1596 | 3150 | 1940 | 5280 | 16800 | 3600 | 4800 | -37296 | 0 | -46656 |
| 888 | 1380 | 760 | 3960 | 11520 | 2520 | 7200 | 14040 | -42336 | -46656 |
| 180 | 450 | 300 | 1800 | 7200 | 1800 | 7200 | 16200 | 10800 | -46656 |
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
