Stacking Prompts

Suppose I have a game that involves rolling on a table of prompts. The table has ten entries and I’m going to roll eleven times. Necessarily, at least one prompt will be repeated.

We can write one more prompt and select them in a random order. This guarantees there are no repeats, but doesn’t allow for a twelfth selection, and “shuffling” is different from rolling. We would like to keep the flexibility of a variable number of rolls while minimizing the number of repetitions.

We could write 90 more prompts,¹ but that’s a lot of work. Let’s say that I’ve got ten more prompts in me. How best can I use these?

Option One: Twenty Prompts

We can add our ten prompts to the end of the list, selecting randomly from all twenty. If we do this, the odds of a repeated prompt in eleven rolls are the odds of rolling at least one duplicate.

This can be solved like the birthday problem: we calculate the number of ways we can roll no duplicates, and then invert it to find the odds of rolling a duplicate. There are

\frac{20!}{(20 - 11)!}

permutations of 11 different items selected from 20. There are

20^{11}

total ways to select 11 items, different or the same, in any order. So the probability of rolling 11 times with no duplicated prompts is then

P = \frac{1}{2 0^{11}} \frac{20!}{9!} \approx 3.27 %

Option Two: Ten Prompts, Two Deep

Suppose instead that we take our ten additional prompts and put one after each of our first ten prompts, as a backup. You will still necessarily repeat at least one roll, but the second time you roll it, you use the “backup” prompt. So the odds of receiving a duplicated prompt are now the odds of rolling a triplicate number.

The solution is similar to the first one: we count the total number of acceptable rolls and then divide by the total number of possible rolls. But counting acceptable rolls is more complicated here. In a collection with

d

doubles in it, there are

(\binom{10}{11 - d})

values. For each of those collections, we then need to select

d

values to be doubled, which can be done

(\binom{11 - d}{d})

ways. Then there are

\frac{11!}{2^{d}}

permutations of each one and

10^{11}

total ways to select 11 items any number of times in any order. Putting this all together, we get the probability of rolling with no triplicate prompts:²

P = \frac{1}{1 0^{11}} \sum_{d = 1}^{5} (\binom{10}{11 - d}) (\binom{11 - d}{d}) \frac{11!}{2^{d}} \approx 28.4 %

Conclusions

In general, raising the bar for repetition from “doubles,” which are surprisingly common, to “triples” seems to be much more effective than trying to make the odds of doubles smaller directly. Prompts will still be repeated in any scheme, but we’ve lowered it from a practical certainty (~97%) to merely something frequent (~72%) while conserving the amount of prompt-writing needed.³

There’s another benefit to nesting prompts like this, and it’s that it gives the structure a “memory.” The second prompt can refer back to the first, with certainty that it’s already been used. (I understand this is what Thousand Year Old Vampire does, but I haven’t read it.)

There are some complications also. The structure is a little harder to explain, and while prompts are less likely to be exhausted, not all prompts are equally likely to be selected.

…

What about triples?

I was going to stop there, but suppose I find ten more prompts in me, and we nest them three deep. This math is similar. First we choose $11-d-2t$ values from our ten options. From those, we pick $t$ triples. Then from the remaining $11-d-3t$ values we choose $d$ doubles. There are now $=$ permutations. Putting it together, we get:⁴

P = \frac{1}{1 0^{11}} \sum_{t = 0}^{3} \sum_{d = 0}^{5} (\binom{10}{11 - d - 2 t}) (\binom{11 - d - 2 t}{t}) (\binom{11 - d - 3 t}{d}) \frac{11!}{2^{d} 6^{t}} \approx 81.8 %

It’s a little more complicated than I could casually evaluate, so I wrote a Python script:

#!/usr/bin/python3

# March 2024
# Ian McDougall

# Calculate the odds of drawing a single item no more than three times when drawing from 10 items 11 times (with replacement).

from scipy.special import comb
from math import factorial

P = 0
f11 = factorial(11)

for t in range(4):
    for d in range(6):
        val = 11 - d - 2*t
        part = comb(10, val)
        part *= comb(val,t)
        part *= comb(val-t,d)
        part *= f11/(2**d * 6**t)
        P += part
P *= 1/10**11

print(P)

If I did the math right, this is by far the most efficient thing to do! Exhausted prompts are still inevitable, but we’ve made them rarer than if we’d written 100 prompts, for only a third of the effort.

It’s also worth noting that these “nested” prompts don’t need to be ordered. Ten pick-lists of three has the same odds as ten sequences of three.

This raises the odds of not a repeating prompt to $P = \frac{1}{10 0^{11}} \frac{100!}{89!} \approx 56.5 %$
up from zero, which isn’t terrible.↩︎
Many, many thanks to TEST on the MSE Discord server, who helped me work through this math when I had misconstructed it, multiple times. They also proposed a different, equivalent formulation: $P = \frac{1}{1 0^{11}} \sum_{d = 1}^{5} (\binom{10}{d}) (\binom{10 - d}{11 - 2 d}) \frac{11!}{2^{d}}$
in which we first choose our doubled numbers in $(\binom{10}{d})$ ways and then choose our remaining single items in $(\binom{10 - d}{11 - 2 d})$ ways. Perhaps you will find this more intuitive.↩︎
In the “flat” prompt structure, you’d need 47 prompts total to reach the same odds as the nested structure. I have no work to show here, I just asked Wolfram Alpha.↩︎
We’re allowed to be a little loose with the limits of our summations here because $= = 1$ and $= 0$ when $k > n$ (more or less).↩︎

Date

May 14, 2024

Up next

Recovered: PALACE RUN 0.2 I wrote this game that I’m very pleased with. I’m hoping to enter it in the 200 word RPG competition when submissions are open. Until then, I’ll be

Previously

Recovered: Black Ships and Bad Hydrodynamics I was going to make a quick fun game about boats. Treasure Island, The Odyssey, One Piece. I wasn’t going to get caught up in the details of how