然而排除已使用元素是固定成本，在已使用元素會變多的情況下更是越來越大的成本。隨機抽一個，再查看有沒有撞上已經使用的位置反而更有效。但這樣做的界線到底在哪裡？

對於空間大小 $N$ 與已使用的 $U$，隨機抽一個位址命中未使用元素的機率是

假設每次抽樣互相獨立，那「抽到第 $k$ 次才第一次成功」服從幾何分布

連續 $k$ 次都失敗（選到已使用的位置）的機率是 $(1 - p)^k$，期望次數是

所以我們可以看到 $|U|$ 只佔 $N$ 一小部分時，期望次數幾乎是常數，$|U| = N/2$ 時也只是2次，跟排除法的 $O(N)$ 差距明顯。要等到 $N - |U|$ 幾乎為 $0$ 時，這才開始稱得上成本

$(1 - p)^k$ 隨 $k$ 遞減趨近 $0$，但對任何有限的 $k$ 都不等於 $0$，也就是不存在有限次數可以保證我們抽到未使用的數字。所以這裡要找的不是「幾次一定會中」，而是「願意接受多大的失敗機率」

給定可以接受的失敗機率 $\varepsilon$tr-notes 取 $10^{-9}$，我們想找出滿足 $(1 - p)^k \le \varepsilon$ 的最小 $k$

先對兩邊取 $\ln$，$\ln$ 單調遞增所以不等號方向不變

根據Logarithm power rule可以得出

$p \in (0, 1)$ 時 $\ln(1 - p) < 0$，所以同除要翻轉不等號

第二個等號來自分子分母同乘 $-1$，讓兩邊都寫成正數。取ceiling就是可拿來做嘗試次數的最小 $k$

但計算 $\ln(1/(1 - p))$ 太麻煩了，所以實作上用 $m/p$ 當上限這裡 $m = \ln(1/\varepsilon)$，而 $1/p$ 就是上面的期望次數。這個做法是因為如果把分母展開成無限級數注意收斂條件

$p \in (0, 1)$ 時每一項都是正的，因此可以看出 $\ln(1/(1 - p)) \ge p$被砍掉的高次項正好說明了高估多少

分母變大則整體變小，所以 $m / \ln(1/(1 - p)) \le m/p$，也就是 $m/p$ 大於等於 $k$ 總是成立。因此這是安全的高估，代價是最壞情況多重試幾次，但讓我們不必計算 $\ln(1 - p)$在 $p \to 1$ 時數值上也不穩，這是另一個不採用的理由

最後這個上限還要跟 $N$ 取 min。期望次數 $1/p = N/(N - |U|)$ 本身其實永遠不會超過 $N$（最壞的 $N - |U| = 1$ 時剛好等於），但 $m/p$ 可能會超過：$N - |U| < m \approx 20.7$ 時就有 $m/p > N$。既然這時候成本已經比掃過整個空間還高，應該放棄然後退回過濾再抽取的演算法

我們分析了抽取的上限是怎麼推導出來的，並且計算超過上限就退回一開始的排除法。所以最壞情況是 $O(N)$ 而不是不會停；另外空間真的滿了會直接報錯，這也是為什麼上面的分析不涉及 $p = 0$

這個演算法用在 raco tr next 的 --random 功能上