Random-Number-Generator
是否保證可以產生所有可能的隨機數？
據我所知，PRG 獲得輸入（種子）並生成比輸入更大的輸出值。因此，是否有可能永遠不會生成某些輸出？基於輸入小於輸出的事實。
PRG 獲得輸入（種子）並生成比輸入更大的輸出值。
的確。PRG 的標准定義使其成為確定性多項式時間算法，其中輸入種子 $ {0,1}^n $ 並輸出 $ {0,1}^{\ell(n)} $ 和 $ \forall n, \ell(n)>n $ ; 和另一個特徵（偽隨機性）。
是否有可能永遠不會產生某些輸出？
這不僅是可能的，而且是肯定的，對於所有人 $ n $ . 為了證明這一點，我們只需要計算可能的輸入：有 $ 2^n $ ; 和輸出數量：有 $ 2^{\ell(n)} $ . 條件 $ \ell(n)>n\ge 0 $ 暗示 $ 2^{\ell(n)}>2^n $ . 而且由於算法是確定性的，因此可能的輸出不能多於可能的輸入。
是否保證可以產生所有可能的隨機數？
也是，但在另一種意義上**。**
如果我們將輸出截斷為 $ \lfloor\ell(n)/k\rfloor $ 位串 $ k $ 位，那麼就有可能每個 $ 2^k $ 的潛在輸出位串 $ k $ 當某些輸入達到位時 $ n $ 長得足夠高。事實上，偽隨機性意味著成立¹。任何固定大小的每個可能的輸出 $ k $ 位達到¹對於足夠大 $ n $ 當我們考慮所有 $ 2^n $ 可能的輸入。
現在我們只需要選擇 $ k $ 這樣所有認為的隨機數都在 $ [0,2^k) $ ，然後產生所有可能的隨機數¹。
¹ 或許除了極少數 $ n $