19
\$\begingroup\$

I have what is chiefly a probability / game-design query, but one with a clear RPG gaming purpose behind it.

Assume I have a check in some game system, using a single 20-sided dice, that requires rolling greater than or equal to a target number. That target number starts at 20, but with every subsequent try it gets reduced by 1.

Essentially, the target to beat/equal (on a D20) = 20 - a, where a is number of attempts made already (starting at 0).

Assume I can keep trying indefinitely (although there is some limitation, such as once per day or cost to try).

What is the expected average number of rolls to get a success in this case (beat or equal the target), and can you show how to work this out generically? How might it vary if the target changed, or the reduction rate (eg. >= 15 - 2a)?

I'd also be interested to hear if have you encountered this sort of mechanic before, and how it was used.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Welcome to the stack! Feel free to check out the tour for a better understanding of how this site works. Any additional question may be answered in the help center, in comments or in chat. Happy stacking! \$\endgroup\$
    – Matthieu
    Oct 13, 2022 at 12:16

5 Answers 5

24
\$\begingroup\$

The average number of rolls is approximately 5.294 for the specific case in the question.

The probability distribution for the specific case is:

$$ p(1) = \frac{1}{20} $$

for \$n=1\$, and

$$ p(n) = \frac{n}{20} \prod_{i=1}^{n-1} \left( \frac{20-i}{20} \right) $$

for \$n>1\$, and \$p(n)\$ indicates the probability that the success occurs on the n'th roll.

The general structure is

$$ p(n) = q_n \prod_{i=0}^{n-1} (1-q_i) $$ where \$0 \le q_i \le 1\$ is the probability of success on the i'th roll, with the convention \$q_0=0\$ (you can't have succeeded before your first roll)

You can think of the process in terms of this sort of tree:


        (1-q_0)=1
       /   \
     q_1  (1-q_1)                    # first roll
            /  \
           q_2 (1-q_2)               # second roll
                /   \ 
               q_3  (1-q_3)          # third roll
                      ...

Where the branches to the left indicate success on that particular roll, and the branches to the right indicate failure on this particular roll. Evaluating the probability of success on a given roll is just taking the product of the factors along the path to the "success" branch on that level.

For the specific case called out in the question:


        start=1
       /   \
     1/20  19/20                    # first roll
            /  \
           2/20 18/20               # second roll
                /   \ 
               3/20  17/20          # third roll
                      ...

From here we can tabulate the probabilities for the specific case:

n p(n) \$n p(n)\$
1 0.05 0.05
2 0.095 0.19
3 0.12825 0.38475
4 0.14535 0.5814
5 0.14535 0.72675
6 0.130815 0.78489
7 0.106832 0.747824
8 0.0793611 0.6348888
9 0.0535687 0.4821183
10 0.0327364 0.327364
11 0.0180050 0.198055
12 0.00883884 0.10606608
13 0.00383016 0.04979208
14 0.00144368 0.02021152
15 0.000464039 0.006960585
16 0.000123743 0.001979888
17 2.62956e-05 0.0004470252
18 4.17635e-06 7.51743e-5
19 4.40937e-07 8.377803e-6
20 2.32020e-08 4.6404e-7

From, this you can get the average of 5.294 as the sum of \$n p(n)\$.

\$\endgroup\$
8
  • \$\begingroup\$ This would argue nicely for a "take 10 (tries)" rule of thumb in this system =) \$\endgroup\$
    – nitsua60
    Oct 13, 2022 at 15:10
  • 1
    \$\begingroup\$ It's probably worth noting that 5 is also the median. \$\endgroup\$ Oct 14, 2022 at 2:27
  • 4
    \$\begingroup\$ Of course, your formula for \$p(1)\$ is just what your formula for \$p(n)\$ simplifies to when \$n=1\$: an empty product is equal to the multiplicative identity, i.e. \$1\$. (If you don't like empty products, you could of course also start the product from \$i=0\$; \$\frac{20-0}{20}\$ also equals \$1\$.) \$\endgroup\$ Oct 14, 2022 at 18:47
  • 2
    \$\begingroup\$ @Alexander done \$\endgroup\$
    – Dave
    Oct 14, 2022 at 21:55
  • 1
    \$\begingroup\$ @Alexander it is the definition of expected value: you average all the possible values with their probability to happen, in this way the values with higher probability have more "weight" in the computation. You may have a look here (linked also in my answer). \$\endgroup\$
    – Eddymage
    Oct 15, 2022 at 21:09
19
\$\begingroup\$

For this kind of question it's probably easiest to plug it into a computer. That also makes it easy to tinker with your scenario as well. Here's some python code:

import random
from statistics import mean

results = []
rounds = 1000000

for _ in range(rounds):
    tries = 0
    while True:
        target = 20 - tries
        tries += 1
        if random.randint(1,20) >= target: # randint includes endpoint
            results.append(tries)
            break
print(f"Mean of {rounds:,} turns is {mean(results):.3f}")

A million rounds takes a couple of seconds and tells me that the expected number of rolls is about 5.3.

Mean of 1,000,000 turns is 5.295

If I change the target to 20 - (2*attempts) that results in 4.1 expected rolls. 15 - (2*attempts) is 2.4 expected rolls.

If you don't have python, there are sites that will let you execute code. If you set the number of rounds too high, they'll terminate your script. Ten million rolls will take ten times as long and will probably only change the third or fourth digit. You can even share the code for others to inspect, modify and run.

Another alternative is AnyDice, which is a site that makes it easy to create scenarios like you describe. You can also look at anydice tagged questions.

EDIT: Adding distribution, continuing from earlier python:

import matplotlib.pyplot as plt
import numpy as np
text = f"Mean of {rounds:,} rounds, [20 - a] is {mean(results):.3f}"
fig, ax = plt.subplots()
ax.set_xlabel('Rolls')
ax.set_title(text)
labels, counts = np.unique(results, return_counts=True)
ax.bar(labels, counts, align='center')  # bar > hist
plt.gca().set_xticks(labels)
plt.show()

Distribution Graph

\$\endgroup\$
5
  • 1
    \$\begingroup\$ +1 but it would be nice if you could add a distribution. We know that chance for success at first roll is 1/20, but chance that sequence will end at second one, third and so on would be pretty cool, too. \$\endgroup\$
    – Mołot
    Oct 13, 2022 at 14:32
  • \$\begingroup\$ @Mołot I've added the code to create a plot, but I had trouble with uploading the image so I had to upload it manually to imgur and link it. \$\endgroup\$ Oct 13, 2022 at 15:07
  • \$\begingroup\$ @importrandom I am trying to upload an image and I am having troubles too: there are some server errors. \$\endgroup\$
    – Eddymage
    Oct 13, 2022 at 15:09
  • 1
    \$\begingroup\$ @Eddymage I was able to embed the image by uploading to imgur, then using the link to the PNG ![title](https://i.imgur.com/7uzEok0.png). \$\endgroup\$ Oct 13, 2022 at 15:18
  • 1
    \$\begingroup\$ Although I was definitely looking for more of a maths formula here, this answer gives some great practical help in actually testing the real-world outcome of the equations. \$\endgroup\$
    – Alexander
    Oct 14, 2022 at 1:04
11
\$\begingroup\$

On average ~5.294 rolls

This isn't actually that complicated to work out, but there's some number crunching later you'll want to outsource to a computer (unless you're into that kind of thing).

The first thing we'll consider is the probability of getting it in exactly k rolls, which requires us to first fail k - 1 rolls, and succeed on the kth.

$$ P(k) = \rho(k) \prod_{i=1}^{k-1} (1-\rho(i)) $$

Where \$\rho(x)\$ is the probability that the xth roll succeeds: $$ \rho(x) = \frac{20-T+n(x-1)+1}{20} $$ where T is our initial target and n is the step down per previous attempt.

We can now find the expectation value of our probability distribution (ie. average number of attempts) as: \begin{align} E &= \sum_k k P(k) = \sum_k\left[ k \rho(k)\prod_{i=1}^{k-1} (1-\rho(i))\right]\\ &=\sum_k\left[ k \frac{21-T+n(k-1)}{20}\prod_{i=1}^{k-1} \frac{T+n-ni-1}{20}\right] \end{align} At which point we tell a computer to run the numbers. The calculation simplifies quite a lot for n=1 at which point the product part can be rewritten in terms of factorials. Worth noting that you'll need to sum over all valid values for k, which is as long as \$k\leq 1+ \frac{T-1}{n}\$. Running the computation for T = 20, n = 1 we get \$E\approx5.294\$.

\$\endgroup\$
3
  • 2
    \$\begingroup\$ @Kirt you're guaranteed success on the 20th roll so the domain of the distribution is bounded between 1 and 20 (inclusive). \$\endgroup\$
    – Dave
    Oct 13, 2022 at 14:59
  • \$\begingroup\$ @Dave Indeed, thank you. \$\endgroup\$
    – Kirt
    Oct 13, 2022 at 15:00
  • 1
    \$\begingroup\$ @Kirt the mode is 4.5, I didn't plot it, but my answer has the full table, so the upper tail does pull on it a bit. \$\endgroup\$
    – Dave
    Oct 13, 2022 at 15:00
6
\$\begingroup\$

Basic probability tools (with the help of a calculator) can provide an easy answer.

Let's analyze the case of success at the 1st attempt, at the second attempt and at the 3rd attempt, and then we can generalize.

The target at the first attempt (\$a=1\$) is 20, hence the probability of success is 1/20.

In case of failure, with a probability of 19/20, the target becomes 19: the success at the 2nd roll is given by

$$ \begin{eqnarray} P(\text{success at 2nd roll}) &=& P(\text{failure at 1st roll})\,P(\text{success at 2nd roll}) \\ &=&\frac{19}{20}\,\frac{1}{20}= \frac{19}{400}. \end{eqnarray} $$

If we need a 3rd attempt, then the formula becomes $$ \begin{eqnarray} P(\text{success at 3rd roll}) &=& P(\text{failure at 1st roll})\,P(\text{failure at 2n roll})\,P(\text{success at 3rd roll})\\ &=& \frac{19}{20}\frac{18}{20}\frac{3}{20}\\ &=& \frac{1026}{8000}. \end{eqnarray} $$

We can generalize, obtaining that the probability of success at the \$i\$-th roll is $$ P(\text{success at } i \text{-th roll}) = \frac{\displaystyle\prod_{k=1}^{i-1}(20-k)}{20^{i-1}} \frac{i}{20}. $$ Then, by classical formula for the expected value gives us $$ {\rm E}[\text{number of rolls before getting a success}] = \sum_{i=1}^{20} iP(\text{success at } i \text{-th roll}) = 5.2936, $$

So you have to wait between 5 and 6 rolls before achieving a success: the computational answer by import random confirms this computation.

Below you can find the plot if the distribution, together with a comparison with respect to the Poisson distribution.

Plot of the distribution, comparison with Poisson distribution for reference.

As justforplaylists notes, the median is 5: it means that 50% of the time you expect a number of rolls less or equal than 5 for having a success, in the other 50% you have to wait from 6 to 19 rolls.

\$\endgroup\$
2
\$\begingroup\$

If I'm reading correctly, the fundamental prompt centers around the ability to (efficiently) iterate on variations of a game mechanic. Those more skilled than I am are better suited to derive a generalized formula mathematically, but I can at least provide some means for tinkering, in this case using dyce¹ for computation and anydyce² for rudimentary interaction.

You can try it out in your browser: Try dyce [source]

base screenshot

While admittedly a little clunky, the interface allows the user to select a die from the standard polygonal dice, define a target, and select an adjustment function from one of two predefined methods identified in the initial question. It also affords custom inputs for advanced users (more on this below).

Using dyce to Model the Mechanic

dyce uses discrete computation, meaning it achieves precision without randomized sampling. It doesn't do continuous distributions, but it will get you precise results, assuming it can adequately model the problem.

First Attempt - Naive (Non-Performant) Approach

When defining the mechanic in terms that dyce can understand, one might do something like the following:

from dyce import H
from dyce.evaluation import HResult, foreach

def degrading_target_nonperformant(
  die: H,
  initial_target: int,
  prior_tries: int = 0,
) -> H:
  adjusted_target = initial_target - prior_tries
  current_tries = prior_tries + 1

  def _callback(d_result: HResult):
    if d_result.outcome >= adjusted_target:
      return current_tries
    else:
      return degrading_target_nonperformant(d_result.h, initial_target, prior_tries=current_tries)

  return foreach(
    _callback,
    die,
    limit=-1,  # do not limit recursion
  )

While the above is technically accurate, branching at whether each outcome meets the threshold leads to performance of roughly O(n!). In practice, this will only work for small dice or small targets. A die of H(20) and target of 20 will take eons (maybe literally).

d20 with target 3 --> 343 µs ± 3.51 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
d20 with target 4 --> 1.09 ms ± 5.63 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
d20 with target 5 --> 4.32 ms ± 149 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
d20 with target 6 --> 20.8 ms ± 240 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
...

Second Attempt - Refined (Performant) Approach

The good news is that we can introduce a counting trick to make things easier on ourselves. Rather than branch on each outcome, we can branch on the likelihood of hitting a particular target:

def degrading_target_performant(
  die: H,
  initial_target: int,
  prior_tries: int = 0,
) -> H:
  adjusted_target = initial_target - prior_tries
  current_tries = prior_tries + 1
  succeeds_or_fails_at_adjusted_target_h = die.ge(adjusted_target)

  def _callback(ge_result: HResult):
    if ge_result.outcome == 1:
      return current_tries
    elif ge_result.outcome == 0:
      return degrading_target_performant(die, initial_target, proir_tries=current_tries)
    else:
      assert False, "should never be here"

  return foreach(
    _callback,
    succeeds_or_fails_at_adjusted_target_h,
    limit=-1,  # do not limit recursion
  )

This takes our branching factor from n (the number of sides of our die) to 2, which leads to a performance of O(n), which is totally reasonable.

d20 with target 3 --> 85.1 µs ± 685 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
d20 with target 6 --> 171 µs ± 756 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
d20 with target 9 --> 272 µs ± 2.17 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
d20 with target 12 --> 366 µs ± 2.84 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
d20 with target 15 --> 461 µs ± 2.22 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
d20 with target 18 --> 563 µs ± 4.93 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
...

This gives us what we want:

>>> d20 = H(20)
>>> h = degrading_target_performant(d20, 20)
>>> print(h.format(scaled=True))
avg |    5.29
std |    2.59
var |    6.68
  1 |   5.00% |#################
  2 |   9.50% |################################
  3 |  12.83% |############################################
  4 |  14.54% |##################################################
  5 |  14.54% |##################################################
  6 |  13.08% |############################################
  7 |  10.68% |####################################
  8 |   7.94% |###########################
  9 |   5.36% |##################
 10 |   3.27% |###########
 11 |   1.80% |######
 12 |   0.88% |###
 13 |   0.38% |#
 14 |   0.14% |
 15 |   0.05% |
 16 |   0.01% |
 17 |   0.00% |
 18 |   0.00% |
 19 |   0.00% |
 20 |   0.00% |

Improvement - Parameterized Adjusted Target Function

Now we can turn to enabling experimentation. We have already parameterized the die and target we're using. Astute coders will note that we can refactor the above to also parameterize the means by which we compute the adjusted target. The substantive source to our version can be found here.

Custom Inputs

For those familiar with Python and dyce, one can input one's own custom histogram for the die (e.g., 2 @ H(6) for 2d6) and one can even define one's own custom target adjustment function that takes two arguments (target and prior_tries) and returns the adjusted target. The custom function can either be defined as a lambda expression, or it can contain full-fledged Python code (so long as it defines or assigns a callable of the appropriate signature to the _ symbol).

For example, to see how the mechanic would work with a d8 plus a d12 and an adjustment function that reduces the target ever other try, one could use a custom die of H(8) + H(12) and a custom adjustment function of lambda target, prior_tries: target - prior_tries // 2, or, if one prefers, something like:

def my_adjustment_func(target: int, prior_tries: int) -> int:
  return target - prior_tries // 2

_ = my_adjustment_func  # <-- "export" the function by assigning it to the _ variable

customization screenshot

One word of caution when experimenting with your own adjustment function: it must converge, meaning it must eventually result in a 100% chance of success (e.g., a target of the minimum value of the die range), or the computation will never finish. I'll leave it as an exercise to the reader to think about how one might go about introducing a safeguard. 😉

Parting Thoughts

I have never found a stand-alone mean to be a useful tool for evaluating a game mechanic. What one often really cares about is distributions. d20 and 4d4 both have the same means, but are very different animals. In game design, play-testing is essential, but a good visualization tool can help you eliminate a lot of junk before it even gets to the table. While probably a matter of taste, anydyce's "burst" graphs are my best attempt (so far) to get a "feel" for informing that process of elimination. I hope this helps in exploring your mechanic more thoroughly!


¹ dyce is my Python dice probability library.

² anydyce is my visualization layer for dyce meant as a rough stand-in for AnyDice.

\$\endgroup\$
4
  • \$\begingroup\$ This is a fantastic answer with a lot to unpack! Thanks so much for those resources and the in-depth explanation \$\endgroup\$
    – Alexander
    Oct 15, 2022 at 20:45
  • \$\begingroup\$ Please try to spread out your updates a bit, now the front page is flooded with stats questions. \$\endgroup\$ Oct 28, 2022 at 0:04
  • \$\begingroup\$ Yikes! I did not realize that merely editing an existing answer bumps the associated question on the home page! I was merely trying to update screenshots, but will be much more judicious in the future. Thanks so much for bringing this to my attention! \$\endgroup\$
    – posita
    Oct 28, 2022 at 1:32
  • \$\begingroup\$ No worries. Since everything here is in some sense community owned, edits will move a question to the front page so that they can be reviewed by other users. Imagine a scenario where a user decided to vandalize a bunch of answers, but those edits stayed buried - no bueno. \$\endgroup\$ Oct 28, 2022 at 12:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .