Mersenne Twister (MT) 的熵是多少？
來自嚴重密碼學：“當分佈均勻時，熵最大化，因為均勻分佈使不確定性最大化：沒有結果比其他結果更有可能。因此，n 位值的熵不能超過 n 位。”
MT 力求具有盡可能均勻的分佈，因此人們會認為熵已最大化並且等於種子的比特長度。
但是 MT 在 624 次迭代後變得完全可預測，此時它的熵應該被認為是零，但隨後的分佈仍然是均勻的。
這兩個想法似乎相互矛盾。
但是 MT 在 624 次迭代後變得完全可預測，此時它的熵應該被認為是零，但隨後的分佈仍然是均勻的。
事實上，隨後的分佈並不是獨立均勻的。
給定 624 個 32 位輸出$$ V = V_1 \mathbin| V_2 \mathbin| \cdots \mathbin| V_{624}, $$我可以通過以下方式確定性地恢復梅森撚線器狀態$$ S(V) = \tau^{-1}(V_1) \mathbin| \tau^{-1}(V_2) \mathbin| \cdots \mathbin| \tau^{-1}(V_{624}), $$在哪裡 $ \tau $ 是回火變換，然後通過確定性地執行生成器來計算下一個輸出 $ G $ 關於恢復狀態 $ S(V) $ . 如果 $ V_i $ 是獨立均勻分佈的，我們會有$$ \Pr[V_{625} = G(S(V))] = 1/2^{32}, $$但如果 $ V_i $ 而是由具有均勻隨機初始狀態的梅森撚線器生成，我們有$$ \Pr[V_{625} = G(S(V))] = 1. $$
這個測試——評估是否 $ V_{625} = G(S(V)) $ ——將均勻隨機初始狀態下的梅森撚線器與成功率高的均勻隨機串區分開來。
這種不均勻性對您正在進行的蒙地卡羅物理模擬有影響嗎？也許不是：您的物理模型不太可能碰巧與 Mersenne twister 輸出生成函式互動 $ G $ 在某種程度上，這將是一個問題，因為物理本身通常不會以對抗性的方式試圖把你個人搞砸，不管研究生院的多年痛苦看起來有多大。
另一方面，如果有一個聰明的對手，就像我們在密碼學中假設的那樣，那個聰明的對手會利用這種關係來破譯你的資訊，通過偽造簽名竊取你的錢等等。
換句話說，Mersenne twister 被設計成對愚蠢的算法來說是統一的，這些算法甚至不知道他們試圖區分的是 Mersenne twister，但是當它絆倒一個知道它是 Mersenne twister 的對手時，它就會倒下。但只是不知道初始狀態。
但是 MT 在 624 次迭代後變得完全可預測，此時它的熵應該被認為是零，但隨後的分佈仍然是均勻的。
您在這裡混合了兩個不同的“熵”概念。
- 第一個是隨機變數的“真實”（資訊論）熵 $ X\colon;\Omega\to A $ ， 定義為 $$ H(X) = -\sum_{a\in A};p_a\cdot\log_2 p_a \text, $$ 在哪裡 $ p_a=\Pr[X=a] $ 和 $ \log_2 p_a $ 被認為是 $ 0 $ 如果 $ p_a=0 $ .
在這種情況下，您會考慮例如 $ A $ 成為輸出範圍內所有（無限）數字序列的集合 $ [0,\dots,2^{32}-1] $ Mersenne Twister 和 $ X $ 應該是從某個隨機內部狀態開始輸出所有 MT 值的隨機變數（即 $ 624 $ 均勻隨機 $ 32 $ 位字）。那麼，確實有 $ 2^{32\cdot 624} $ 的不同結果 $ X $ ，並且它們都具有相同的可能性，因此熵 $ X $ 是 $ 32\cdot624=19968 $ 位。
- 另一方面，有些東西可以稱為“統計熵”或“經驗熵”：這基本上包括“猜測”一個隨機變數 $ X $ 這可能已用於生成具體的觀察結果，然後計算該變數的熵。
具體來說，給定一個長度為 MT 的輸出序列 $ n $ ，人們可能（錯誤地！）猜測它是 $ n $ 獨立同分佈隨機變數 $ X_1,\dots,X_n $ , 每次給予 $ 32 $ 位詞 $ i $ 根據觀察到的相對頻率分佈 $ p_i $ ，然後是隨機變數的熵 $ (X_1,\dots,X_n) $ 將會$$ n\cdot\sum_{i=0}^{2^{32}-1}-p_i\log_2 p_i $$位。這與資訊論熵（上圖）明顯不同，但並不矛盾——這只是基於不完整資訊對真實熵的*猜測。*還有其他一組假設（例如，不同的單詞大小；均勻分佈而不是基於頻率的估計；基數不同於 2 的冪；序列中單詞之間的依賴關係；…）通常會導致對熵的不同估計。
總之，任何 MT 實例（沒有重新播種）的資訊論熵的上限為 $ 19968 $ 位，但在不知道它來自 MT 的情況下，生成的序列可能看起來像統計測試的均勻隨機序列。
請注意，這與確定密碼的“熵”本質上是相同的問題：除非您自己使用已知的隨機過程生成密碼，否則根本無法判斷密碼是否“足夠隨機”。只需查看字元，例如 $ \mathrm{SHA256}(w) $ 對於隨機字典單詞 $ w $ 可能看起來很“隨機”，但是一旦你知道生成它的過程，熵顯然是由 $ \log_2 $ 字典中單詞的數量。