7
$\begingroup$

I was recently commenting on game mechanics, when I realized that I actually underestimated this particular part.

Given an unbalanced die (in this case, some of the sides are 0), what is the expect number of rolls to reach a total sum of N.

As an example. What is the expected number of dice rolls with a die having sides [0,0,0,1,2,6] to reach the sum 24.

I can do this for a balanced die, because that is uniform distribution, so the expected number of rolls is ceil(N/((1+2+3+4+5+6)/6)) so in this example it would be ceil(24/3.5)=7 rolls.

$\endgroup$
2
  • $\begingroup$ 1. There's not enough information, though ceil(N/mean) will be pretty close. 2. Your expectation for the uniform still doesn't look quite right (though it's close now that you fixed it). $\endgroup$
    – Glen_b
    Commented Jan 18, 2016 at 11:39
  • $\begingroup$ @Glen_b I have added more information. $\endgroup$ Commented Jan 18, 2016 at 11:42

2 Answers 2

4
$\begingroup$

Let $N$ be the number of rolls it takes to reach a total of $T=24$ or greater using a die $X$ with non-negative integral values. Suppose $n \ge 0$ rolls have occurred and the value of $T$ has not yet been reached. Let $p_n$ be the probabilities of the totals, which therefore range from $0$ to $T-1,$ and set $p_n(T)$ to be the chance $T$ has already been reached. Because this is an exhaustive description of the possibilities, $p_n$ is a probability distribution. (This describes a stopped process.)

The next roll updates $p_n$ to $p_{n+1}$ by adding the random variable $X$ and capping its results at $T.$ This addition is performed by means of a convolution of the distribution of $X$ and $p,$ thereby requiring $O(T\log(T))$ effort, because all probabilities associated with totals of $T$ or greater may be ignored.

The expected number of rolls to attain $T$ will be somewhere around $T/E[X],$ as suggested in the question. Thus, this calculation will need to be repeated around that many times, resulting in $O(T^2\log(T)/E[X])$ effort, which is practicable for $T/E[x]$ up to many thousands.

The sum $p_n(0)+p_n(1) + \cdots + p_n(T-1)$ is the chance that the total has not reached $T$ or greater after $n$ rolls. In other words, it is the survival function,

$$S(n) = \Pr(N\gt n) = \sum_{k=0}^{T-1} p_n(k).$$

This gives us full information about the distribution of $N.$ In particular, its expectation is

$$E[N] = \sum_{n=0}^\infty S(n).$$

Here, for instance, is the survival function for the example in the question:

Figure


As proof of concept, here is R code to carry out the calculation for the example in the question. Its arguments are a representation of the die (a vector of its possible values) and the target value. Its output gives values of the survival function at $n=0, 1, 2, \ldots$ up to a point where cutting off its infinite tail likely makes an error less than a specified small threshold value.

die <- c(0,0,0,1,2,6)
target <- 24

f <- function(die, target, n.max, threshold=1e-12) {
  X <- c(1, rep(0, target-1))
  d <- rev(tabulate(die+1) / length(die))

  P <- list(1)
  repeat {
    X <- convolve(X, d, type="open")[1:length(X)]
    P <- c(P, p <- sum(X))
    if (p < threshold / target) break
  }
  unlist(P)
}

p <- f(die, target)

The expected number of rolls is the sum:

sum(p)

17.18552

Incidentally, for an ordinary die, the expected number of rolls to reach $24$ is a little greater than $7:$

sum(f(1:6, target))

7.333484

$\endgroup$
1
  • $\begingroup$ Can be this solution easily extended/modified for example where the states (here 6 integers) are returns and one would want to obtain number of next steps required to obtain positive return, namely @rate>0. Here in this case order of the series of returns would matter of course. $\endgroup$
    – Maximilian
    Commented Jan 9, 2020 at 9:00
2
$\begingroup$

The expected number of rolls of a normal (and fair) six-sided die (i.e. the uniform case you mention) to reach a total of at least 24 is not 7; that's an underestimate -- several million simulations indicates it's actually about 7.33

Several million simulations also indicates that the expected number of rolls for your modified die to reach at least 24 is about 17.19.

[By contrast ceil(N/mean) would be 16.]

$\endgroup$
2
  • $\begingroup$ That is strange. Shouldn't it statistically be N/E(X)? Where N is the total sum, E(X) is the expected value of the random variable? Or am I missing something obvious? $\endgroup$ Commented Jan 18, 2016 at 12:53
  • $\begingroup$ No, it really shouldn't be N/E(X). I'll add some further discussion (it may have to wait some hours before I can do it). $\endgroup$
    – Glen_b
    Commented Jan 18, 2016 at 15:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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