17
$\begingroup$

So for example:

  • if $N = 3$
  • I roll and get -> $1,2,3$
  • I re-roll the $2$ and $3$ -> $1,4,4$
  • I re-roll the $1$ -> $2,4,4$
  • I re-roll the $2$ -> $4,4,4$

In this case, it took $4$ rolls for $N=3$ but what is the average number of rolls for $N$?

Note that this question is a little trickier than it seems.

$\endgroup$
7
  • 9
    $\begingroup$ I vote this to reopen because I think this might be an interesting (and indeed tricky!) math puzzle. I thought they have to show a certain value of $X$ let's say $4$ then it become a bit "trivial" as a math problem. But here, let's say rolling $10$ dices resulting $6$ dice showing $6$ and the rests are other numbers, what should be our next strategy? Is it always good to reroll other $4$ dice? Should we perhaps reroll all of them? Those questions make me think this will be a nice math puzzle. $\endgroup$ – athin Jun 21 '20 at 2:19
  • 2
    $\begingroup$ Another example is if you have 5 1's and 5 2's and 4 of everything else. Are you better off keeping both your 1s and 2s and rolling 16 dice or should you keep just your 1's and roll 21 dice? $\endgroup$ – GroovyDotCom Jun 21 '20 at 23:06
  • 1
    $\begingroup$ The answer might depend on what goal the person rolling the dice is trying to achieve. Should we assume that they are trying to minimize the average number of rolls it will take them? This seems like the most obvious goal given the question being asked, but e.g. they might instead try to minimize the worst-case number of rolls and doing that might lead to a different strategy whose average number might be higher. $\endgroup$ – Gareth McCaughan Aug 29 '20 at 23:44
  • $\begingroup$ Do you believe that you know the correct answer? $\endgroup$ – Gareth McCaughan Aug 29 '20 at 23:51
  • $\begingroup$ My math is not up to it, but I'll try to write a brute-force + pruning simulator. $\endgroup$ – GroovyDotCom Sep 2 '20 at 13:09
5
$\begingroup$

Here are results for small $n$: \begin{matrix} n & \text{minimum expected number of rolls} \\ \hline 1 & 1 \\ 2 & 6 \\ 3 & 63/8 = 7.875 \\ 4 & 1388/143 \approx 9.706 \\ 5 & 191283/17248 \approx 11.090 \\ 6 & 12.2178200960107 \\ 7 & 13.155830198755 \\ \end{matrix}

At least for these small values of $n$, an optimal strategy is to keep only the most frequently appearing value, breaking ties arbitrarily, and reroll the rest.

I used linear programming (LP) to solve the Markov decision problem. Given states $S$, actions $A_s$ for $s\in S$, and transition probabilities $p_{s,t}(a)$, let decision variable $V_s$ represent the expected number of rolls, starting in state $s$. The Bellman equation is $$V_s = \min_{a\in A_s} \left(1 + \sum_t p_{s,t}(a) V_t\right)$$ The LP problem is to maximize $\sum_s V_s$ subject to \begin{align} V_s &= 0 &&\text{for terminal states $s$} \\ V_s &\le 1 + \sum_t p_{s,t}(a) V_t &&\text{for non-terminal states $s$ and actions $a\in A_s$} \end{align} The desired expectation is $$1+\frac{1}{|S|}\sum_s V_s$$

$\endgroup$
4
  • $\begingroup$ Could you provide any proof? An explanation of how you got these numbers? etc. $\endgroup$ – bobble Aug 30 '20 at 16:12
  • $\begingroup$ I confirm your answer for n=4: wolframalpha.com/input/… $\endgroup$ – classicalMpk Aug 30 '20 at 20:31
  • $\begingroup$ is it a typo? I think you meant that the The LP problem is to minimize the expected number of rolls. $\endgroup$ – Cohensius Sep 3 '20 at 5:34
  • 1
    $\begingroup$ @Cohensius maximize is correct. Think of minimum as greatest lower bound. $\endgroup$ – RobPratt Sep 3 '20 at 5:47
3
$\begingroup$

Complicated indeed. My calculations:

n = 3 
20/36 chance of three different values    20/16 rolls on average before progress 

1/36 chance of triple -> 1 turn
15/36 chance of pair -> 7 turns  (6 extra rolls needed) on average

Average: (20 + 1 + 15*7)/16 =  63/8

n = 4

60/216 chance of four different values    60/156 rolls on average before progress 

1/216 chance of quadruple -> 1 turn
20/216 chance of triple -> 7 turns on average
135/216 chance of on or two pairs -> 37 turns on average

Average: (60 + 1 + 20*7 + 135*37)/156 = 5352/156  (= +/- 33.3)

n = 5

120/1296 chance of five different values   120/1176 rolls on average before progress 

1/1296 chance of 5 -> 1 turn
25/1296 chance of 4 -> 7 turns on average
200/1296 chance of 311 -> 37 turns on average
50/1296 chance of 32 -> 37 turns on average

this leaves
900/1296 chance of on or two pairs 
then 
5/216 on other triplet -> 37 turns on average
1/216 on 5 -> 1 turn
15/216 on 4 ->  7 turns on average
75/216 on 3 -> 37 turns on average
120/216 chance on no progress
thus on average (216 + 5*37 + 1*1 + 15*7 + 75*37)/96 turns
 
for the entire 5 
 
(120+ 1*1+ 25*7 + 250*37 + 900 * 3282/96) /1176 

Now: Wondering what I did wrong (assuming Rob is right)

Edit: Stupid me, 37 is wrong. Both remaining dice don't have to be right in the same throw. 37 should be replaced by

1+(25(no progress) + 10*7(1 success) + 1*1(2sucesses))/11 

and then I can confirm Rob's 9.706

For 5 I then get

pair to 5 : (216 + 5*107/11 + 1*1 + 15*7 + 75*107/11)/96  =  1841/176 turns 
start to 5: 120+ 1*1+ 25*7 + 250*107/11 + 900 * 1841/176) /1176 (= +/- 11.09)
$\endgroup$
3
$\begingroup$

Asymptotic behavior:

1. We expect the avg waiting time to be logarithmic in the number of dice because the number of newly aligned dice should be proportional to the number of dice rolled. Numerical experiments confirm this, see below. 2. The single-most-frequent-number strategy is asymptotically optimal. Indeed, for large numbers of dice the overwhelming number of rolls will fall within a narrow window around the expected values. As the most frequent number will occupy at least a sixth of the dice and since the two-(or-more)-best-numbers strategy will be most competitive when the second best and best numbers are equally numerous, these strategies will have approx. 20% fewer free dice. As this percentage is fixed and translates to a higher-by-a-fixed-ratio expected number of new hits in the single number strategy over the multiple number strategy while the relative variance becomes arbitrarily small as the number of dice increases the single number strategy will outperform the other strategies almost always and by a fixed margin. QED My suspicion is that this is not only asymptotically true but indeed generally. It could in principle be established by checking finitely many cases with a computer, but it's probably messy.

Assuming the assertion holds not only asymptotically but in fact always, the first $100$ values were obtained by dynamic programming:

$$\begin{matrix} 1.00000 & 6.00000 & 7.87500 & 9.70629 & 11.09016 \\ 12.21782 & 13.15583 & 13.95850 & 14.66347 & 15.29440 \\ 15.86463 & 16.38300 & 16.85693 & 17.29365 & 17.69950 \\ 18.07901 & 18.43507 & 18.76990 & 19.08568 & 19.38460 \\ 19.66865 & 19.93934 & 20.19772 & 20.44471 & 20.68121 \\ 20.90815 & 21.12636 & 21.33653 & 21.53916 & 21.73471 \\ 21.92364 & 22.10642 & 22.28347 & 22.45516 & 22.62176 \\ 22.78356 & 22.94079 & 23.09374 & 23.24265 & 23.38773 \\ 23.52916 & 23.66710 & 23.80172 & 23.93318 & 24.06163 \\ 24.18722 & 24.31007 & 24.43027 & 24.54794 & 24.66318 \\ 24.77611 & 24.88681 & 24.99537 & 25.10186 & 25.20636 \\ 25.30894 & 25.40968 & 25.50864 & 25.60588 & 25.70146 \\ 25.79543 & 25.88785 & 25.97876 & 26.06822 & 26.15628 \\ 26.24297 & 26.32833 & 26.41241 & 26.49524 & 26.57686 \\ 26.65731 & 26.73662 & 26.81481 & 26.89193 & 26.96799 \\ 27.04303 & 27.11708 & 27.19016 & 27.26229 & 27.33351 \\ 27.40382 & 27.47326 & 27.54185 & 27.60961 & 27.67655 \\ 27.74270 & 27.80807 & 27.87268 & 27.93656 & 27.99971 \\ 28.06216 & 28.12391 & 28.18498 & 28.24540 & 28.30517 \\ 28.36430 & 28.42281 & 28.48071 & 28.53802 & 28.59475 \end{matrix}$$

Plot:

Note the log scale on the x axis. enter image description here Expected asymptotic logarithmic behavior is apparent.

Below an auxiliary calculation that speeds up part of the process.

Once half or more of the dice show the same number it is clear that we can't do better than rerolling all the others. In this scenario we can more or less directly compute the expected number of rolls:

Let's write $n$ for the number of dice left and $p=1/6$ for the probability a single die rolls the right number. Then the probability for a single die to survive at least the next $k$ rolls is independent of the other dice and equals $(1-p)^k$. The probability for all $n$ to finish in at most $k$ rolls is therefore $[1-(1-p)^k]^n$ and the expected number of rolls is $$\sum_{k=0}^{\infty} \left(1-[1-(1-p)^k]^n\right) = \sum_{j=1}^{n}\binom{n}{j}\frac{(-1)^j}{(1-p)^j-1}.$$

$\endgroup$
1
  • 1
    $\begingroup$ And the average result of 30,000,000 trials of a simple greedy algorithm consisting 1) throw the dice once and choose the most common value X, 2) throw the rest of the dice and always keep those that show an X, agrees with your dynamic programming solution for N=100 to four significant figures (28.5925). For large N (100..1000), the number of throws T fits the logarithmic equation T = 2.966+6.5723*ln(N) $\endgroup$ – Penguino Sep 3 '20 at 2:35
2
$\begingroup$

This problem gets increasingly more complex as n gets higher. Finding the pattern, if it exists, could be really difficult. Here's what I have for now:

n=1: 1 (trivial)
n=2: 6
n=3: 63/8
n=4: 1388/143
n=5: 191283/17248

It looks like there are no complications for now. I have proven experimentally that for n=5, it's better to re-roll a pair + the single number when we have 2 pairs.

Example: 2,2,5,3,3 -> It's better to roll 5,3,3 rather than just 5.

Maybe there are tricky things for higher values of n.

$\endgroup$
1
  • $\begingroup$ I confirm your answer for $n=5$. $\endgroup$ – RobPratt Aug 31 '20 at 4:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.