掉落率 1%，為什麼挖一百次還是沒有：幾何分布與加權抽樣

掉落率 1%，平均挖 100 次會出一個，但挖滿 100 次還沒出的人約有 37%。只看平均值，很容易忽略有人要等多久：一半的人 69 次內就拿到，最倒楣的 5% 要挖到 299 次以上，即使亂數本身完全公平也是如此。

這裡先假設亂數沒有問題，單看同一個機率落到很多玩家身上之後的分布，以及怎麼從掉落表裡正確地抽一個結果。亂數本身的品質，包括 seed、狀態和 modulo bias，另見〈洗牌只有 8,640 萬種：遊戲 RNG 認證在檢查什麼〉。

「用數學描述遊戲世界」系列到了第三篇，採礦遊戲開始有了隨機性。前兩篇〈朝向不等於位置〉和〈同一艘船在 30 FPS 和 144 FPS 開起來不一樣〉處理的是空間與時間，接下來要算的是稀有礦等多久才挖得到。

「平均一百次」和「一百次內」

延續前面的太空採礦遊戲：每次鑽探有 1% 機率挖到稀有礦。每次獨立、機率固定，第一次挖到之前要鑽幾次，就是幾何分布（geometric distribution）：

第 k 次才第一次挖到的機率是 (1-p)^(k-1)·p。
k 次內至少挖到一次的機率是 1 - (1-p)^k。
平均要 1/p 次。

把 p = 0.01 代進去，100 次內至少一次是 1 - 0.99^100 ≈ 63.4%。平均要挖 100 次，並不保證在 100 次內拿到，實際上只有 63.4% 的玩家會在這之前取得。

幾何分布還有一個性質叫無記憶性：已經挖了 200 次沒出，下一次的機率還是 1%，之後平均還要再挖 100 次。玩家會覺得「這麼久了應該快了」，但先前的失敗不會改變後面的機率，下一篇談的保底才會刻意讓系統記住歷史，打破這個性質。

用分位數看玩家實際等多久

要知道玩家實際等多久，可以看分位數：中位數表示一半玩家在這之前就拿到，P95 則表示只有 5% 的人還沒拿到。幾何分布的分位數有封閉解，下面另外跑模擬，對照算出的結果：

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

十萬個模擬玩家裡，中位數 69、平均 99.6，最倒楣的那個挖了 1,142 次。挖了 300 次還兩手空空的有 4,877 人，約 4.9%，和公式算出的 P95 = 299 吻合。如果遊戲有一百萬個活躍玩家，就有大約五萬人挖了 300 次還沒拿到，這是正常機率下就會出現的情況。

亂數公平屬於工程與認證的問題，玩家能不能接受這樣的等待時間，則要回到設計上討論。同樣平均 100 次，規則不同，長尾和那端玩家的感受也會不同，下一篇會算出這些差異。

從掉落表抽一個結果：累積權重加二分搜尋

實際的掉落很少是單一機率，通常是一張表：

結果	權重	機率
stone	7000	70.0%
iron	2200	22.0%
copper	600	6.0%
crystal	190	1.9%
void ore	10	0.1%

最常見的寫法是把權重累加成 [7000, 9200, 9800, 9990, 10000]，抽一個 0 到 9999 的整數，再用二分搜尋找它落在哪一格。建表是 O(n)，每次抽是 O(log n)。權重用整數、亂數也用整數，可以避開浮點數在區間邊界上的誤差；整數亂數本身要沒有 modulo bias，Python 的 randrange 已經處理了，其他語言要確認（RNG 那篇有實測）。

另一種做法是 alias method，Alastair Walker 在 1974 年發表，Michael Vose 1991 年提出線性時間的建表方法。它把每一格補成剛好一樣高，不足的部分「借」另一格來填，每次抽樣只要擲兩次：選一格，再決定用這格本身還是它的 alias。建表 O(n)，抽樣 O(1)，但只要一個權重改變，就得整張重建。

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]}")

以下是 Python 3.13.16 的執行結果：

== 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

兩種方法抽一百萬次的比例都貼近設定值，正確性沒問題，速度卻跟教科書給人的印象有些落差。五格的小表和十萬格的大表都是二分搜尋比較快，alias 的建表還多花了十倍時間。比較可能的原因（沒有分開量測）是 Python 的 bisect 用 C 實作，log₂(100,000) 也才 17 次比較，而 alias 每次要呼叫兩次 randrange，呼叫本身的成本蓋過了省下的比較。

這組數字只代表 CPython 上的情況，每次計時也會有些起伏。在編譯語言、GPU 或每秒要抽上億次的場合，O(1) 的優勢才比較容易顯現，換成 alias 前仍要在自己的環境量測。一般遊戲的掉落表只有幾格到幾十格，又常隨活動調整權重，累積權重加二分搜尋通常就夠了，別人也比較容易讀懂程式、核對結果。

公告的機率要從同一份設定產生

掉落表寫在程式裡，公告寫在網頁上，兩邊分開維護遲早會對不上。台灣 2022 年 7 月修正《網路連線遊戲服務定型化契約應記載及不得記載事項》，公視報導指出，付費取得的機率型商品要在官網、登入頁、購買頁等處以數字百分比公告機率，起因之一是當年《天堂M》的機率爭議。RNG 那篇也提過，亂數通過認證，不代表公告的數字是對的。

公告可以直接從正式環境使用的權重表產生，表格裡的百分比用 weight / total 計算，省去人工抄寫；正式環境再按二項分布監控實際掉落率有沒有偏離設定。有了這些資料，玩家在論壇上貼出挖了 400 次沒出的截圖時，就能核對設定與實際掉落率，說明這是 P98 左右的正常長尾。

補充筆記

1% 挖 100 次，至少一次的機率約 63.4%，不能把平均 100 次當成期限。同一個分布的中位數是 69 次。
每次獨立且機率固定，首次命中次數就符合幾何分布，先前失敗不會影響後面；P95 是 299 次，P99 是 459 次。
工程與認證要確認亂數公平，設計則要判斷玩家能否接受長尾，這兩件事得分開討論。
整數權重的累積和加二分搜尋能正確抽樣，也容易讀懂和對帳；alias method 雖然是 O(1)，權重改了就得重建。在 CPython 實測，五格和十萬格的表都是二分搜尋較快，選演算法仍要看自己的量測結果。
公告機率由正式環境的同一份設定產生，實際掉落率也要持續監控。