Expected Sum of 30 sided die rolls

Question

Roll a 30-sided die. Add up each consecutive outcome. Stop rolling when the sum >= 300. What's the most likely result of the sum?

Answer 1

Clearly $300$. You have $30$ chances for what the sum was before, while for $329$ you only have one. If the target is above the maximum value on the die, the most likely stopping place is the target. Let $P(n)$ be the chance that $n$ is the last total before you hit or pass $300$. It may depend on $n$, but is greater than zero for all $270 \le n \le 299$. The chance you hit $300$ is $\sum_{i=270}^{299}P(i)\frac 1{i-269}.$ The $\frac 1{i-269}$ term comes because we know we must roll a large enough number to hit or exceed $300$, but the acceptable numbers are equally distributed. The chance you hit $301$ is $\sum_{i=271}^{299}P(i)\frac 1{i-269}.$ The chance you hit $302$ is $\sum_{i=272}^{299}P(i)\frac 1{i-269}.$ and so on until the chance you hit $329$ is $\sum_{i=299}^{299}P(i)\frac 1{i-269}.$ Each successive sum has one less positive term, so the sums are strictly decreasing.

Answer 2

Ross Millikan's answer is based on the mathematical analysis, but to understand his solution I wrote a program and tested it anyway. Here are my results.

Matlab Code Used

trials = 1000000;
results = zeros(1,trials);
for n = 1:trials
   sum = 0;
   while sum < 300
       sum = sum + ceil(30*rand);
   end
   results(n) = sum;
end
hist(results,30);

Results

As stated by Ross Millikan, it is easy to see that 300 is the most likely result.

Answer 3

Let $p_n$ be the probability of attaining the total $n$. Then we can reach $300$ by getting to $299$ and rolling $1$, or getting to $298$ and rolling $2$, or ... so that $$p_{300}=\frac 1{30}(p_{299}+p_{298}+ \dots + p_{270})$$

Then we get to $301$ by throwing $2$ from $299$ etc $$p_{301}=\frac 1{30}(p_{299}+p_{298}+\dots+p_{271})$$

The pattern is now obvious, as is the fact that the probabilities diminish as the target number increases.

I didn't post this originally because Ross Millikan had posted the essential insight. The probabilities below $300$ need not all be identical, but they are positive, and are intuitively similar in magnitude. This explains the steplike structure of the graph in Phil's solution. But because we know they are positive, we don't need to know their exact values to answer the question.

Answer 4

Count the number of roll sequences (of some fixed but arbitrary lengtzh $l$) that lead to an outcome $s\ge 300$. For each such sequence that ends in $s>300$, we obtain a sequnce that ends in exactly $300$ by replacing the last roll $x$ (which must be $>s-300$) with $x+300-s$. This shows that the end sum $300$ is at least as probably as the end sum $s$. Now since $300>30$, there is at least one sequence that ends in a sum of $300$ with a last roll of $30$. This sequence is not obtained from a sequence leading to end sum $s>300$ in the ways described above. Therefore, the number of sequences (of at least one specific length) leading to $300$ is strictly larger thanthe number of sequences of the same length leading to end sum $s$ if $s>300$. Consequently, $300$ is the most likely end sum.

Answer 5

I saw this question on the Statistics Blog twitter feed and thought it would be fun to sim. I see someone already did so in matlab. Here is the code for an R simul (10 reps of 50,000 simulations) and ggplot2 output with 2sd errorbars.

require(data.table)
require(ggplot2)
set.seed(1)

## PARAMETERS
reps   <- 10   # number of reps to conduct
simuls <- 5e4  # number of simulations per rep
Sides <- 30    # number of dungeons and dragon playing friends that I have
StopVal <- 300 # the min value to reach before stopping

## FUNCTIONS
rollDie <- function(StopVal=300) {
  total <- 0
  while (total < StopVal) {
    total <- total + sample(Sides, 1, TRUE)
  }
  return(c(total=total))
}

tally <- function(res, i) {
    ret <- rev(table(res))
    ret / sum(ret)
    data.frame(Roll=as.numeric(names(ret)), Prob=ret/sum(ret), Trial=i)
}

## SIMULATE
rolls   <- lapply(seq(reps), function(i) replicate(simuls, rollDie(StopVal)))
results <- lapply(seq(reps), function(i) tally(rolls[[i]], i))

## AGGREGATE
dat <- do.call(rbind, results)
dat <- data.table(dat, key="Roll")
dat[, c("MeanProb", "SDProb") := list(mean(Prob), sd(Prob)), by=Roll]


## PLOT
P <- ggplot(dat[Trial==1], aes(x=as.factor(Roll), y=MeanProb)) + 
    geom_bar(stat="identity", fill="lightblue") +
    geom_errorbar(aes(ymin=MeanProb-(2*SDProb), ymax=MeanProb+(2*SDProb)), width=.3, color="red") +
    theme(axis.text.x = element_text(angle = 45, size=rel(0.75))) + 
    labs(x="Roll Total", y="Prob") + 
    ggtitle(paste0("d", Sides, " rolling X, X ≥ ", StopVal))

ggsave("~/d30_exceed300.png", plot=P)

P

Answer 6

I computed the exact probabilities for this problem. They involve nearly 1000 digits.

The probability that the final number is $300$ is approximately $$\frac{30}{\sum_{i=1}^{30} i} = \frac{2}{31}$$ to about thirty parts in a trillion. The analogous expression holds for the other numbers, namely that the probability for $300+i$ is proportional to $30-i$.

Interpreting the question as about the expectation instead of most likely sum (as in the current question title), the answer is approximately $309 + 2/3$, again with the same margin of error.