Wikipedia:Reference desk/Archives/Mathematics/2020 March 19

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

March 19

Expected sum on a matching dice mechanic

I'm playtesting a game in which, on a turn, you take two statistics, n and s, and then roll nds (that is, n dice of s sides each), summing the result. If all the dice have the same result, then you roll again, adding the new result to the previous sum, and you keep going until not all dice are the same. For example, suppose n = 3 and s = 6. Then, you would start by rolling 3d6:

• Example 1: Suppose you get the result {1, 3, 4}. Then you would stop immediately, and your sum for the turn would be 1 + 3 + 4 = 8.

• Example 2: Suppose you had instead gotten the result {3, 3, 3}. Since all the dice are the same, you would roll again, and suppose this time you get {2, 2, 2}. Again, all the dice are the same, so you roll again, and this time you get {1, 1, 4}. Since not all dice are the same, you would now stop, and your sum for the turn would be 3 + 3 + 3 + 2 + 2 + 2 + 1 + 1 + 4 = 21.

What would be a formula in terms of n and s for calculating the expected value for a turn?

And what would be the expected value for a turn if the rules were modified so that, rather than requiring all the dice to match, you roll again and sum to the previous roll(s) whenever any dice among those rolled match? So in the second example above, you would continue rolling on the third roll since two dice came up with the value 1. (Obviously, with the modified rule, if n is greater than s, then the expected value would be infinite since you are guaranteed to always have a match on each roll in that case, but I would still like to know about the expected value for the cases where n is less than or equal to s.)

—SeekingAnswers (reply) 05:00, 19 March 2020 (UTC)

The probability of all dice matching is $s^{-(n-1)}$. If X is the expected value, then $X=n(s+1)/2+Xs^{-(n-1)}$. Solving for X, $X={\frac {n(s+1)}{2(1-s^{-(n-1)})}}$.

The probability of any dice matching is $1-{\frac {s!}{s^{n}(s-n)!}}$, so with the modified rules we have $X={\frac {n(s+1)}{2}}+X\left(1-{\frac {s!}{s^{n}(s-n)!}}\right)$. So $X={\frac {s^{n}n(s+1)(s-n)!}{2s!}}$.163.47.115.73 (talk) 11:18, 19 March 2020 (UTC)

Confirmed by Monte Carlo experiment for n = 3 and 5, and s = 7.  --Lambiam 20:55, 19 March 2020 (UTC)

For the re-roll condition of any two matching dice, we must impose the condition that n ≤ s. Otherwise the game diverges (never stops) and the formula becomes meaningless.  --Lambiam 08:40, 20 March 2020 (UTC)

And the original re-roll condition, all dice showing equal values, requires that both n > 1 and s > 1.  --Lambiam 14:20, 20 March 2020 (UTC)

Thank you so much for the answers! But I have a couple follow-up questions, which I hope will not be too much trouble: what are the expected values if we only reroll the dice with a match, rather than all dice? The motivation is that this prevents divergence to infinity in the case of n greater than s.

Also, this question has two variations: in the first, the rerolled dice replace the previous results, while in the latter, the rerolled dice are added to the previous results.

For example, if n = 5 and s = 4, suppose for our first roll we got {4, 1, 3, 4, 3}. Four of those five dice match another, so we reroll those, this time getting {2, 1, 2, 4}. This time, only two among those dice match, so we roll those two again, getting {2, 4}, all different and thus bringing the rolling to an end.

For this example, the final sum under the replacement variation would be (1) + (1 + 4) + (2 + 4) = 12. The final sum under the addition variation would be (4 + 1 + 3 + 4 + 3) + (2 + 1 + 2 + 4) + (2 + 4) = 30.

—SeekingAnswers (reply) 18:42, 20 March 2020 (UTC)

It is possible to compute the exact expected value for any given values of n and s (for example, n = 4 and s = 6 gives an expected value for the addition variation of exactly 108/5 = 21.6), but I doubt there is a helpful closed formula.  --Lambiam 11:02, 22 March 2020 (UTC)

The same approach used by the IP gives a recursive formula: for a given s, one has $X(n)={\frac {s+1}{2}}\cdot n+\sum _{i=0}^{n}P(n\to i)\cdot X(i)$ where $P(n\to i)$ is the probability that, after one roll of n dice, you end up with i for the next roll. You can compute this probability by inclusion-exclusion: for a given collection S consisting of exactly i dice, the probability that only dice in S get reused is $(s)_{n-i}\cdot (s-n+i)^{i}/s^{n}$ (where $(s)_{n-i}$ is a falling factorial). Therefore, the probability that a particular set of k dice are the ones that survive is $\sum _{i=0}^{k}(-1)^{k-i}{\binom {k}{i}}(s)_{n-i}\cdot (s-n+i)^{i}/s^{n}$, and $P(n\to k)$ is exactly ${\binom {n}{k}}$ times this number. If you've computed X(1), X(2), ..., X(n – 1), you can solve for X(n) in terms of them. I have not experimented to see if the result might be nice. Not carefully proofread, so caveat emptor. --JBL (talk) 01:02, 23 March 2020 (UTC)

I did not check the details of the maths of this inclusion–exclusion argument, but can report that applying the above formula to the case $n=4$ and $s=6$ I find the same value for $P(4\to 4)$ as I obtained before using a different method, viz. $96/6^{4}$. This instills confidence in the correctness. ($P(4\to 4)$ is the lowest case where it starts to get tricky, since all dice in the retained set need not show the same value.)  --Lambiam 03:58, 23 March 2020 (UTC)

I was thinking some more about this, and I think in the replacement variation only, we don't actually need to calculate any complicated formula at all: the expectation will be the same as for a normal roll of nds with no rerolls, that is, n(s + 1) / 2. We can see this by considering the output space of all possible roll results: you're basically excluding matches from that output space, since any matches get rerolled for specifically the dice that match, and the non-matching results replace the results with matches. This wouldn't change the overall expectation: matching ones {1, 1, ...} are equally as likely as matching s's {s, s, ...}, so when excluding them, their total change to expectation cancels out; matching twos cancel out with matches showing (s - 1); and so forth.

For example, consider a roll of 2d6. We can construct a table of possible sums...:

	1	2	3	4	5	6
1	2	3	4	5	6	7
2	3	4	5	6	7	8
3	4	5	6	7	8	9
4	5	6	7	8	9	10
5	6	7	8	9	10	11
6	7	8	9	10	11	12

...and the average sum is the expectation: 7. The replacement variation basically removes the matches (since they will be rerolled, and the possible results with no matches have their probabilities unchanged relative to each other), changing the table to:

	1	2	3	4	5	6
1		3	4	5	6	7
2	3		5	6	7	8
3	4	5		7	8	9
4	5	6	7		9	10
5	6	7	8	9		11
6	7	8	9	10	11

...which still has the same average sum and expectation: 7. With n >= 4, you can get more complicated matches, simultaneous matches of different values like {2, 2, 3, 3}, but low matches will still cancel out high matches, leaving expectation unchanged when they are removed from the output space.

That still leaves open the question of expectation in the addition variation, though, wherein dice that match don't just get effectively removed.

—SeekingAnswers (reply) 20:01, 25 March 2020 (UTC)

Right. It is a consequence of the underappreciated property that the expected value of a sum equals the sum of the expected values; symbolically, EΣ = ΣE. This is a special case of the linearity of expectation. So if we just know how many times a die is counted, the expected outcome is that number multiplied by the expected value for a single die, which is (s+1)/2. In the replacement version, each of the n dice gets counted once. In the additive version, it gets counted each time it is rolled, so if we know the expected number of rolls for any individual die, we'll also have the solution. Perhaps this opens a road to solving the additive version.  --Lambiam 11:55, 26 March 2020 (UTC)

For the very special case of $s=2$, the expected value $R_{n}$ of total dice rolled for the additive version is given by a simple formula:

$R_{1}=1,~R_{n}=2^{n}~\mathrm {for} ~n>1.$

This suggests it is not fruitful to study the expected number of rolls for an individual die.  --Lambiam 17:28, 26 March 2020 (UTC)