Rolling a Die Until a Total, $T$, Is Achieved or Succeeded

Question

I'm working on a side project right now which requires calculating the sum of random numbers.

Given a goal, $T$, one rolls a fair die with $s$ sides until the cumulative sum of rolls is at least $ T$. Let the number of rolls be $R$. I'm looking specifically at the game D&D where one must attack a creature (assuming there's always a hit) until the sum of the damage is greater than or equal to the HP of the creature.

Take a Badger in the game. It has 3HP, thus we can set $T=3$. If one attacks with a weapon that deals 1d4 of damage, we know that we can kill the Badger in just one hit 50% of the time by rolling either a 3 or 4. However, if we roll a 1 or 2, we would need to roll again, thus increasing $R$ to at least 2. We can see that, with a 1, we can kill the Badger 75% of the time, and with a 2, we can kill it 100% of the time. In the case where we rolled two 1s in a row, we know that we can kill the Badger 100% of the time with any roll.

Thus, the $R=(1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3)$. If we treat this like a set of data and find ratios, we can find $R=1$ ~15.3% of the time; $R=2$ ~53.8% of the time, and $R=3$ the remaining ~30.8% of the time. (Exact values being $\frac{2}{13}, \frac{7}{13}$, and $\frac{4}{13}$, respectively.)

It's very clear that one could brute-force this problem by mapping all possibilities until $T$ is reached, but my question is whether there exists a generalised formula for the percentages of values of $R$ when one rolls a $s$-sided die until the sum of rolls is at least $T$.

I realise that this may be a trivial question, but I don't have a lot of experience in probability and statistics, so I'm truly at a loss as to where to begin. Googling the question yielded no results, so I came here for guidance ^_^

Answer 1

Let $$ p(r,T)=\text{the probability it takes exactly $r$ rolls to kill a monster with $T$ health} $$ You want to compute the full list $$ p(1,T),p(2,T),\dots,p(T,T) $$ There is no direct formula to compute $p(r,T)$, as far as I can tell. However, there is a recursive equation you can use to compute these values easily with the aid of a computer. The recursive equation is $$ p(r,T)=\frac1{s}\sum_{i=1}^s p(r-1,T-i), $$ because if the first roll of the die is $i$ (where $i\in \{1,\dots,s\}$), then the conditional probability it will takes $r$ rolls total is the probability that you will take $r-1$ further rolls to exceed the remaining total of $T-i$. This formula works as long as you define the following base cases: $$ T\le 0\implies \begin{array}{l} p(0,T)=1,\\ p(r,T)=0 \text{ for $r > 1$} \end{array} $$ That is, if the monster's health is zero or negative, you will certainly need $0$ further rolls.

I've included some Python code to illustrate the effectiveness of this method.

from functools import lru_cache


@lru_cache(maxsize = None) #Cache results to speed up computation (memoization)
def p_num_rolls(r,s,t):
    # Returns the probability that when you roll a standard s-sided die 
    # until the cumulative sum is at least t,
    # that exactly r rolls are required.

    if t <= 0: # Base case 
        return int(r == 0) # When t is nonpositive, the result is 1 if r is zero, 0 otherwise

    else: # Otherwise, use recursive equation 
        return sum([p_num_rolls(r - 1, s, t - i) for i in range(1, s + 1)])/s

def num_rolls_distribution(s, t):
    # Returns a list L = [p_0, p_1, ..., p_t], 
    # where L[r] = p_r = p_num_rolls(r,s,t)
    return [p_num_rolls(r,s,t) for r in range(t+1)]

s = 4
t = 3
L = num_rolls_distribution(s, t)

print('When rolling a d{} until the total is {},\n'.format(s,t))
for r in range(1, t+1):
    prob_percent = round(100 * L[r], 4)
    print('  The probability it will take {:3} rolls is {:8}%.'.format(r, prob_percent))

Output:

When rolling a d4 until the total is 3,

  The probability it will take   1 rolls is     50.0%.
  The probability it will take   2 rolls is    43.75%.
  The probability it will take   3 rolls is     6.25%.