確定觀察用於一組字元串輸入的字元空間的機率的數學計算
我正在設計一些方法來根據用於生成無線路由器安全密碼片語的字元空間來確定它們的組成。
我遇到的問題是我不確定我可以使用什麼公式或技術來計算我需要觀察的字元串數量，以確定用於生成這些密碼的完整字元集。
我在考慮生日悖論，但我不確定這是否適用於我的問題。
推斷字元串組合的算法很簡單：將讀取密碼字元串並處理每個字元。如果之前沒有見過這個角色，它將被添加到一個臨時數組中，如果之前已經看過這個角色，則不會添加它。因此，最後，該數組將儲存處理過的字元串（有問題的密碼）中所有唯一看到的字元。
假設路由器製造商用於生成這些密碼片語的字元空間大小為 62 個不同的字元。例如：
abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789
（az 小寫、AZ 大寫和 0-9）
這些生成的密碼只是這樣的字元串，例如：
- 2UAYnCtL
- YR3kLX49
- MJLDJIgt
- xouq9KOV
考慮到每個密碼片語的長度為 8 個字元，並且這些密碼片語是通過從上述範例字元空間中隨機選擇字元來隨機生成的，我的算法需要查看多少個字元串才能建構上述字元的完整表示空間 ？
或者換句話說，我如何確定需要觀察的最小字元串數才能使我的算法有很高的機率（或接近 1 的機率）能夠重新創建上述字元空間？
如果有任何不清楚的地方，請告訴我。感謝您的輸入 ！
好吧，假設路由器以均勻且獨立分佈的方式選擇密碼的每個字元，那麼單個字元不是特定字元的機率 $ c $ 是：
$$ 1 - 1/62 $$ （其中字母大小為 62）。
因此，如果我們生成 $ n $ 字元，機率 $ c $ 永遠不會發生是：
$$ (1 - 1/62)^n $$ 現在，我們有 62 個可能的值 $ c $ ，並且我們希望所有這些都發生在某個地方的機率很高（例如， $ >0.99 $ )，所以我們有：
$$ 62 (1 - 1/62)^n < 1 - 0.99 $$ 評估這個，我們得到 $ n > 537 $ , 或 67 個 8 個字元的密碼。
您獲得的確切值將取決於字母表的大小（您在開始時可能不確切知道）以及所需的失敗機率。此外，從某種意義上說，這是悲觀的，如果您看到除 之外
n的每個字母字元，則可能n會發生這種情況（而您只是碰巧沒有看到）。另一方面，路由器可能被程式為避免使用1,I,l字元（因為它們在某些字型中很容易混淆），因此這可能不會那麼悲觀。學究們會注意到，這種分析並不完全正確（因為機率不是獨立的；密碼的每個字元都是一些 $ c $ ，因此將每個字元的不出現機率乘以字元數實際上是不合理的），但是我相信它很接近。