多少ķķk-我們希望在所有之前提取隨機位串的位字2ķ2ķ2^k可能出現的話？

讓 $ C(X) $ 表示集合的基數 $ X $ . 例如， $ C({0}) = 1, C({0, 2}) = 2 $ 等等

讓 $ S $ 表示一個（可能是無限的）隨機位序列。分裂 $ S $ 進入 $ k $ 位詞 $ w_1, w_2, w_3, \ldots $ 例如，如果 $ k = 4 $ 和 $ S = 0001111010100100\ldots $ ， 然後 $ w_1 = 0001, w_2 = 1110, w_3 = 1010, \ldots $

在每一步 $ i $ （這裡 $ i \geq 1 $ )，請執行以下子步驟：

1. 提煉 $ w_i $ 並進入子步驟2；
2. 如果 $ C(X) < 2^k $ 和 $ X $ 包含 $ w_i $ , 不做任何事情並繼續執行 $ (i+1) $ ; 如果 $ C(X) < 2^k $ 和 $ X $ 不含 $ w_i $ ， 放 $ w_i $ 在 $ X $ 並進入子步驟3；
3. 如果 $ C(X) < 2^k $ , 走一步 $ (i+1) $ ; 如果 $ C(X) = 2^k $ ， 停止。

問：期望值是多少 $ i $ 上述算法何時停止？換句話說，如果 $ S $ 是真正隨機或無偏偽隨機位的來源，我們應該提取多少字來填充 $ X $ 盡一切可能 $ k $ 位元素？

這被稱為優惠券收集者的問題，優惠券的數量被替換為 $ 2^k $ 和 $ k $ 是繪製的獨立位數（ $ k=4 $ 在問題的範例中）。

預計 $ (k\log(2)+\gamma),2^k+\frac12+\mathcal O(2^{-k}) $ 提取物，其中 $ \gamma\approx0.5772 $ 是歐拉常數，並且 $ \log(2)\approx0.6931 $ .

當進行很少的實驗時，對期望的粗略近似通常就足夠了，例如 $ 0.7,k,2^k $ . 分佈有一條長尾。我認為標準差是 $ \approx\frac\pi{\sqrt6},2^k\approx1.3\times 2^k $ .

引用自：https://crypto.stackexchange.com/questions/98696