# Expected Sum of 30 sided die rolls

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?

-
are the values of the dice's sides $1\ldots 30$? – Alex Jul 31 '13 at 16:19
This seems related to this question. – robjohn Jul 31 '13 at 17:55
The expected sum and the most likely result are completely different things. Expected sum, at least for me, seems that should be interpreted as expectation while most likely is the value which maximizes the probability. – Guy Aug 1 '13 at 19:06

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.

-
Roll a 6-sided die. Stop rolling when the sum >= 2. What's the most likely result of the sum? It's not 2. – Eric Tressler Jul 31 '13 at 16:28
@Phil: The question was for the most likely, not the average. I think your average is very close. – Ross Millikan Jul 31 '13 at 16:52
Alright, it looks like I was wrong and Ross' answer is correct. @RossMillikan I still think your answer would benefit from a little elaboration. It's not "clearly" to me, or, I assume, some other people. – Eric Tressler Jul 31 '13 at 16:59
@acolyte: This is a different question. The number of dice being rolled is not given. You keep rolling until the total exceeds $300.$ That can only happen when the existing total is $270-299$. The argument above shows why it is more likely to hit $300$ than any higher number. – Ross Millikan Jul 31 '13 at 20:09
@Did: That is correct. I think when one talks of rolling a die one assumes it is fair unless specified otherwise. – Ross Millikan Jul 31 '13 at 20:53

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.

-
– Captain Giraffe Jul 31 '13 at 17:09
For those interested, the triangular shape is not an accident and corresponds to the limit of the distribution of the overshoot of $n$ when $n\to\infty$. – Did Jul 31 '13 at 18:09
+1. The graph makes it clear that the average (aka arithmetic mean) is going to be higher than 300, but the mode is what the question was actually asking about. This is one of the sticking points in the comments on @RossMillikan answer. – Patrick M Jul 31 '13 at 18:52
Nice. Some tips: Use randi(30) to generate random integers drawn uniformly from [1 30]. Always set a seed. You can use the rng function for that is recent versions of Matlab. – horchler Jul 31 '13 at 21:35

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.

-

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.

-

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


-
Interesting. The question asks for $\ge 300$, not $>300$, but I think the right answer is clear nonetheless. – Potato Aug 1 '13 at 19:19
@Potato, thanks for pointing that out. Simple enough to change the parameter and re run with the correct value. (answer has been edited to reflect correct value) – Ricardo Saporta Aug 1 '13 at 19:38

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.

-