A 1% Drop Rate and 100 Tries Without Luck: The Geometric Distribution and Weighted Sampling

A 1% drop rate means one rare item per hundred attempts on average. It also means that about 37% of players have still got nothing after a hundred. Half of all players get lucky within 69 tries, and the unluckiest 5% have to keep going past 299. The random number generator can be perfectly fair and all of that is still true.

This post takes a fair RNG for granted. The quality of the randomness itself, meaning seeds, state and modulo bias, is covered in Only 86 Million Ways to Shuffle. Here the question is what one probability looks like once it has landed on a lot of players, and how to draw a correct result from a loot table.

It is the third post in the series that started with vectors and frame rates, and the space-mining game finally gets some randomness.

”A hundred on average” is not “within a hundred”

Each drill in the mining game has a 1% chance of hitting rare ore. If every drill is independent and the chance never changes, the number of drills up to and including the first hit follows a geometric distribution:

The chance that the first hit is on drill k is (1-p)^(k-1)·p.
The chance of at least one hit within k drills is 1 - (1-p)^k.
The mean is 1/p drills.

With p = 0.01, the chance of at least one hit in 100 drills is 1 - 0.99^100 ≈ 63.4%. So 100 is the average, and only 63.4% of players are done by then.

The distribution is also memoryless. A player who has drilled 200 times without luck still has a 1% chance on the next drill and, on average, another 100 to go. It feels as if a hit must be due; the earlier misses change nothing. Pity systems, the subject of the next post, exist precisely to give the system a memory and break this property.

How long players actually wait

Quantiles answer that better than the mean. The median is the point by which half the players have their ore; P95 is the point by which all but 5% do. The geometric distribution has closed-form quantiles, and a simulation alongside serves as a check. Run on Python 3.13.16:

import bisect
import math
import random
import sys
import time
from collections import Counter
from itertools import accumulate

p = 0.01   # rare ore: 1% per drill

print("== 1. what 1% means over 100 drills ==")
print(f"P(at least one in 100)   = {1 - (1 - p) ** 100:.4f}")
print(f"P(none in 100)           = {(1 - p) ** 100:.4f}")
print(f"P(none in 200)           = {(1 - p) ** 200:.4f}")
print(f"mean drills to first hit = {1 / p:.0f}")


def quantile(q):
    """Smallest k with P(first hit <= k) >= q, for a geometric distribution."""
    return math.ceil(math.log(1 - q) / math.log(1 - p))


for q in (0.5, 0.9, 0.95, 0.99, 0.999):
    print(f"P{q*100:g}: {quantile(q)} drills")

print("\n== 2. 100,000 simulated players, drills until the first rare ore ==")
rng = random.Random(20261007)
waits = []
for _ in range(100_000):
    n = 1
    while rng.random() >= p:
        n += 1
    waits.append(n)
waits.sort()
pick = lambda q: waits[int(q * len(waits)) - 1]
print(f"mean {sum(waits)/len(waits):.1f}  median {pick(0.5)}  P90 {pick(0.9)}"
      f"  P99 {pick(0.99)}  worst {waits[-1]}")
print(f"players still empty-handed after 300 drills: {sum(w > 300 for w in waits)}")

== 1. what 1% means over 100 drills ==
P(at least one in 100)   = 0.6340
P(none in 100)           = 0.3660
P(none in 200)           = 0.1340
mean drills to first hit = 100
P50: 69 drills
P90: 230 drills
P95: 299 drills
P99: 459 drills
P99.9: 688 drills

== 2. 100,000 simulated players, drills until the first rare ore ==
mean 99.6  median 69  P90 229  P99 456  worst 1142
players still empty-handed after 300 drills: 4877

Across 100,000 simulated players the median is 69 and the mean 99.6, and the unluckiest player drilled 1,142 times. 4,877 players, about 4.9%, were still empty-handed after 300 drills, which matches the formula’s P95 of 299. A game with a million active players will have roughly fifty thousand people in that position, and every one of them is seeing exactly the advertised odds.

A fair RNG is an engineering and certification matter; whether players will put up with that tail is for design to decide. Two rules with the same average of 100 can have very different tails, and the next post puts numbers on that.

Drawing from a loot table: cumulative weights and binary search

Real drops are rarely a single probability. They are a table:

Result	Weight	Probability
stone	7000	70.0%
iron	2200	22.0%
copper	600	6.0%
crystal	190	1.9%
void ore	10	0.1%

The usual approach turns the weights into a running total, [7000, 9200, 9800, 9990, 10000], draws an integer from 0 to 9999 and binary-searches for the bucket it falls in. Building the table is O(n) and each draw is O(log n). Integer weights and an integer draw avoid floating-point trouble at bucket boundaries, provided the integer draw itself has no modulo bias; Python’s randrange handles that, and in other languages it is worth checking (the RNG post measures the bias).

The alternative is the alias method, published by Alastair Walker in 1974, with a linear-time construction from Michael Vose in 1991. It levels every bucket to the same height by lending the excess of tall buckets to short ones, so a draw needs only two random numbers: one to pick a bucket and one to choose between the bucket and its alias. Construction is O(n) and each draw O(1), but changing a single weight means rebuilding the whole table.

print("\n== 3. weighted drop table: cumulative weights + binary search ==")
TABLE = [("stone", 7000), ("iron", 2200), ("copper", 600), ("crystal", 190), ("void ore", 10)]
names = [n for n, _ in TABLE]
cum = list(accumulate(w for _, w in TABLE))          # 7000, 9200, 9800, 9990, 10000
TOTAL = cum[-1]


def draw_bisect(r):
    x = r.randrange(TOTAL)                            # integer: no float edge cases
    return names[bisect.bisect_right(cum, x)]


def build_alias(weights):
    """Vose's alias method with integer arithmetic. Setup O(n), draw O(1)."""
    n, total = len(weights), sum(weights)
    scaled = [w * n for w in weights]                 # compare against total
    prob, alias = [0] * n, [0] * n
    small = [i for i, s in enumerate(scaled) if s < total]
    large = [i for i, s in enumerate(scaled) if s >= total]
    while small and large:
        s, l = small.pop(), large.pop()
        prob[s], alias[s] = scaled[s], l
        scaled[l] -= total - scaled[s]
        (small if scaled[l] < total else large).append(l)
    for i in small + large:
        prob[i] = total
    return prob, alias, total


prob, alias, tot = build_alias([w for _, w in TABLE])


def draw_alias(r):
    i = r.randrange(len(prob))
    return names[i] if r.randrange(tot) < prob[i] else names[alias[i]]


N = 1_000_000
for label, fn in (("bisect", draw_bisect), ("alias", draw_alias)):
    r = random.Random(42)
    t0 = time.perf_counter()
    c = Counter(fn(r) for _ in range(N))
    dt = time.perf_counter() - t0
    print(f"{label:6} {dt*1000:5.0f} ms  " + "  ".join(
        f"{n} {c[n]/N*100:.3f}%" for n in names))
print("expected     " + "  ".join(f"{n} {w/TOTAL*100:.3f}%" for n, w in TABLE))

print("\n== 4. a 100,000-entry table (e.g. per-player loot rolls), 200,000 draws ==")
r = random.Random(7)
big = [r.randint(1, 1000) for _ in range(100_000)]
t0 = time.perf_counter()
big_cum = list(accumulate(big))
t1 = time.perf_counter()
bp, ba, bt = build_alias(big)
t2 = time.perf_counter()
rb, ra = random.Random(1), random.Random(1)
for _ in range(200_000):
    bisect.bisect_right(big_cum, rb.randrange(big_cum[-1]))
t3 = time.perf_counter()
for _ in range(200_000):
    i = ra.randrange(len(bp))
    _ = i if ra.randrange(bt) < bp[i] else ba[i]
t4 = time.perf_counter()
print(f"bisect: build {(t1-t0)*1000:5.1f} ms, draws {(t3-t2)*1000:5.0f} ms")
print(f"alias : build {(t2-t1)*1000:5.1f} ms, draws {(t4-t3)*1000:5.0f} ms")
print(f"\nPython {sys.version.split()[0]}")

== 3. weighted drop table: cumulative weights + binary search ==
bisect   430 ms  stone 70.002%  iron 21.977%  copper 5.992%  crystal 1.925%  void ore 0.105%
alias    676 ms  stone 70.028%  iron 22.017%  copper 5.976%  crystal 1.880%  void ore 0.099%
expected     stone 70.000%  iron 22.000%  copper 6.000%  crystal 1.900%  void ore 0.100%

== 4. a 100,000-entry table (e.g. per-player loot rolls), 200,000 draws ==
bisect: build   3.7 ms, draws   151 ms
alias : build  34.8 ms, draws   227 ms

Python 3.13.16

Both methods land within a whisker of the configured proportions over a million draws, so correctness is fine. The timings are not what the textbook would suggest. Binary search wins on the five-entry table and on the 100,000-entry one, and building the alias table takes ten times longer. The likely reason, which I haven’t measured separately, is that Python’s bisect is written in C and needs only 17 comparisons for 100,000 entries, while the alias draw makes two randrange calls whose overhead outweighs the comparisons it saves.

These numbers describe CPython, and the timings wobble a little between runs. In a compiled language, on a GPU or at hundreds of millions of draws a second the O(1) draw has a better chance of paying off, but measure on your own platform before switching. A typical game’s loot table has a handful to a few dozen entries and is re-weighted for events. For that, cumulative weights with binary search are usually enough, and much easier for the next person to read and reconcile.

Publish the odds from the same configuration

A loot table in code and a list of odds on a web page, maintained separately, will drift apart sooner or later. In July 2022 Taiwan amended its mandatory terms for online game service contracts. According to PTS, paid chance-based items must now show their odds as numeric percentages on the official site, the login page and the purchase page, among other places; the dispute over Lineage M’s odds was one of the triggers. As the RNG post argued, a certified RNG does not make the published numbers right.

The odds page can be generated from the weight table production actually uses, each percentage computed as weight / total with nobody copying numbers by hand, while production monitors the real drop rate against the configuration using the binomial distribution. With both in place, when a player posts a screenshot of 400 drills without a rare find, you can check the configuration and the observed rate and point out that it sits around P98, an ordinary part of the tail.

Notes

With 1% per try, the chance of at least one success in 100 tries is about 63.4%. The mean is 100 and the median of the same distribution is 69.
Independent tries at a fixed rate give a geometric distribution with no memory of earlier misses; P95 is 299 tries and P99 is 459.
Fair randomness is for engineering and certification to establish; whether the tail is acceptable is for design to decide.
Cumulative integer weights with binary search sample correctly and are easy to read and audit. The alias method draws in O(1) but needs a rebuild when weights change, and on CPython binary search was faster at both table sizes tested.
Generate published odds from the production configuration, and keep monitoring the real drop rate against it.