如何解釋 NIST 測試文件的熵結果？
NIST 提供了從 pi 派生的測試數據，用於驗證 NIST用於隨機位生成的熵源的建議中列出的熵測量公式。數據採用以下十六進制格式（每個字節一個不同的位）：-
01 01 01 00 00 01 00 01 00 00 00 01 01 00 00 00 01 00 01 00 01 00 01 01 00 01 00 00 00 01 00 01 00 00 01 01 00 01 01 00 00 00 01 00 00 00 01 01 00 01 01 01 00 01 01 01 00 00 01 00 01 00 00 00 00 01 01 00 00 01 01 01 00 01 01 01 01 00 00 00 01 00 01 01 01 01 01 00 00 00 00 00 01 00 01 00 00 00 00 00 01 00 00 00 01 01 00 01 00 01 00 01 00 00 00 01 00 01 01 01 01 01 01 00 00 01 01 00 01 01 00 00 01 00 00 00 01 00 01 00 01 01 00 …
- 我檢查了數據是否被認為是獨立同分佈 (IID)，並且它未通過 IID 測試。
- 然後我測量了熵（將文件視為非 IID），得到了 0.57 位/字節和 0.083 位/字節的兩個測量值。他們的工具有兩個版本，因此有兩個數字。它們分別是碰撞測試和壓縮測試的輸出。
- 我還使用自己的壓縮技術估計了熵，得到 0.98 位/字節。
簡單的推論意味著這樣一個 pi 文件的真實熵約為 1 位/字節。NIST 的措施都沒有接近。為什麼這三項措施截然不同？
1165666 字節 pi 文件上的原始 I/O，每個符號 1 位：-
./non_iid_test ~/nist_h_tests/bin/data.pi.bin 1 -v Opening file: .../nist_h_tests/bin/pi_1bit.bin Running non-IID tests... Entropic statistic estimates: Most Common Value Estimate = 0.810967 Collision Test Estimate = 0.287049 Markov Test Estimate = 0.723549 Compression Test Estimate = 0.0828647 #### t-Tuple Test Estimate = 0.704954 Longest Reapeated Substring Test Estimate = 8.5665 #### Predictor estimates: Multi Most Common in Window (MultiMCW) Test: 100% complete Correct: 568135 P_avg (global): 0.569447 P_run (local): 0.461426 Multi Most Common in Window (Multi MCW) Test = 0.812367 Lag Test: 100% complete Correct: 500378 P_avg (global): 0.501667 P_run (local): 0.427246 Lag Prediction Test = 0.995199 MultiMMC Test: 100% complete Correct: 533117 P_avg (global): 0.534403 P_run (local): 0.461426 Multi Markov Model with Counting (MultiMMC) Prediction Test = .903999 LZ78Y Test: 99% complete Correct: 494588 P_avg (global): 0.495884 P_run (local): 0.427246 LZ78Y Prediction Test = 1.01192 #### Min Entropy: 0.0828647 #### indicates peculiar result. (I added these flags)並確定這是否實際上是一個 IID 文件：-
./non_iid_test /tmp/mentropy/bin/data.pi.bin 1 -v Calculating baseline statistics... Beginning initial tests... Threading is off Beginning permutation tests... these may take some time ** Failed IID permutation tests使用 fp8.exe 和 paq8px_v112.exe 進行 DIY 壓縮測試會創建一個 ~143000 字節的文件（正如假設 pi 是隨機的那樣）。
第一：熵是物理過程中隨機變數的屬性或具有*多個可能結果的知識狀態*，而不是確定性函式或固定已知值的屬性。** 如果你將一個固定的已知值視為一個隨機變數，其機率分佈微不足道，只有一種可能的結果，那麼它的熵正好為零。在這個意義上，二元展開的熵 $ \pi $ 為零：根據該描述，任何人都可以以 100% 的成功機率猜出它們。
類似地，獨立同分佈，或獨立同分佈，是物理過程或知識狀態中幾個隨機變數的屬性。
- 如果您想像自己公平地擲出一對硬幣，那麼該物理過程的可能結果就是 IID。一旦你自己進行了實驗，你記錄的實際結果就不再是獨立同分佈——它們只是固定的已知值。
- 如果我告訴你我相當投擲了一對硬幣，但不是結果是什麼，它們在你的知識狀態下是獨立同分佈的，只要你相信我沒有對你撒謊。一旦我告訴你我的第一個結果是什麼，第一個和第二個結果在你的知識狀態下不再是獨立同分佈——第一個是固定的已知值，第二個是在你的知識狀態下的公平伯努利試驗.
現在假設您看到一個黑盒子，當您轉動曲柄時它會向您吐口水。這裡有兩個涉及黑盒的場景：
- 你在太平洋的另一邊有一位同事，你想通過電報向他發送比特，這是在幾年的合作過程中，對陌生鳥類分發的黑匣子進行社會學研究。電報需要花錢，因此您希望通過壓縮算法為它們提供最小化成本，該算法平均減少了您必須傳輸的比特數。
如果您有一個關於黑盒如何運作的模型，那麼該模型中的*（香農）熵*是您必須在電報中發送的每比特由黑盒吐出的平均最小比特數。如果您的模型與黑匣子的運作方式不同，您的實際平均成本將乘以從您的模型到黑匣子實際運作方式的 KL 散度。 2. 正確猜出第 100 萬個 87 位序列可獲得 100 萬歐元獎金。你可以用一百萬歐元買很多電報，所以你的社會學研究得這個獎會很方便，因此你想最大限度地提高猜對那個位的機率。
如果您有一個模型來說明黑盒將如何在第 100 萬個 87 位序列上執行，則該模型中的最小熵減去最可能結果的機率的對數。
大部分資訊論和編碼理論都致力於研究場景（1）中的香農熵，因為將盡可能多的像素壓縮到光碟和光纖鏈路上以在大片中擁有大的俯衝動作場景是一大筆錢，而且因為物理世界充滿了黑匣子，就像氫原子的電子軌道一樣，瑞士的胖手指猿只是勉強弄明白。
大多數密碼學都與場景（2）中的最小熵最大化有關，而不是與黑盒有關，而是與將比特混合在一起的特定算法有關。但是有幾個世紀以來為場景 (1) 建構的數學工具可以作為 (2) 的代理，因為香農熵是最小熵的上限。
任何假定的“熵測試”工具的工作原理如下：*
- 從黑盒輸出的一組分佈族開始。這是工具的假設空間，它的建模假設。
- 給定來自黑盒的數據樣本，擬合每個假設系列的參數。
- 分析計算或數值估計每個特定假設分佈的熵。
以下是一些隨機過程，這些工具可能會被程式為假設為黑匣子如何工作的模型：
- 內部的小精靈通過以未知機率擲硬幣獨立生成具有相同分佈的每個位 $ p $ .
- 內部的小精靈通過以未知機率擲硬幣來獨立生成具有相同分佈的每一對位 $ p $ ，並重複：如果是正面，00；如果是尾巴，11。
- 內部的小精靈通過滾動具有未知面機率的 256 面骰子獨立生成具有相同分佈的每個八位字節 $ p_i $ .
- 內部的 gremlin 使用具有未知轉換機率的隱藏馬爾可夫模型連續生成每個八位字節 $ p_{ij} $ .
- 裡面的小鬼有一頂裝滿八位字節的帽子。它將它們倒在盒子的地板上，然後隨機撿起它們，報告每一個，直到它們回到帽子裡。然後它重複折磨。
對於這些過程中的每一個，都有各種標準技術用於估計參數或後驗，計算輸出的熵，計算一個輸出的條件熵給定另一個等。
假設您有一個熵估計工具，在其建模假設中具有以下單一假設族：
- 內部的小精靈通過以未知機率擲硬幣獨立生成具有相同分佈的每個位 $ p $ .
如果常客編寫該工具，他們可能會對其進行程式以進行點估計 $ p = #\text{heads}/(#\text{heads} + #\text{tails}) $ 用最大概似估計然後列印出熵 $ H = -p\log p - (1 - p)\log (1 - p) $ . 如果貝氏†編寫了該工具，他們可能會使用 $ B(1,1) $ 對這個伯努利模型進行共軛先驗並使其列印後驗預測分佈的熵，結果證明是完全相同的 $ H = -p\log p - (1 - p)\log (1 - p) $ 和 $ p = #\text{heads}/(#\text{heads} + #\text{tails}) $ .
擲硬幣的 gremlin可以產生二進制展開 $ \pi $ , 拋硬幣次數的機率呈指數下降。當拋硬幣的小鬼用 $ p = 1/2 $ ，它的輸出每輸出一位熵。 這個小鬼的一個可能結果是二進制展開 $ \pi $ ——但是“固定結果的熵”（總是完全為零）不是過程的熵。
如果你給這個工具一個黑盒子，裡面有一個總是吐出確定性交替序列 0, 1, 0, 1, 0, 1等的 gremlin ，它總是會準確地報告每一位輸出的 1 位熵，即使這種內部帶有確定性交替 gremlin 的黑盒模型（不在工具的假設空間中）的熵為零。
另一方面，如果該工具還考慮了隱馬爾可夫假設
- 內部的 gremlin 使用具有未知轉換機率的隱藏馬爾可夫模型連續生成每個八位字節 $ p_{ij} $ .
那麼對於一個帶有交替 gremlin 的盒子，它可能會根據對轉換機率的經驗估計報告接近零的熵。
如果你給這個工具一個黑盒子，裡面有一個總是吐出二進制展開的小精靈 $ \pi $ ——也在它的建模假設之外，以及零熵——它會報告每比特輸出接近1 比特的熵，因為在二進制擴展的任何有限截斷中，1 比特與 0 比特的比率 $ \pi $ 任何人都檢查過的比例非常接近 1:1，馬爾可夫模型也不太可能有太大幫助。
這些工具中的大多數在其假設空間中不包含零熵確定性過程，這是一個忠實地計算 $ \pi $ . 物理學家在放大鏡下觀察氫原子時往往不會發現這樣的小精靈，因此將它們包含在通用工具中並不是很有用。如果您確實包含了該建模假設，該工具可以告訴您您的樣本與 $ \pi $ -gremlin 模型， $ \Pr[X = \operatorname{trunc}_{1000}(\pi) \mathrel| \text{box yields binary expansion of $\pi$}] = 1 $ 在哪裡 $ X $ 是黑盒的前 1000 位。‡
同樣，當應用於您知道是由 cryptography 生成的樣本時，例如 $ \operatorname{MD5}(0) \mathbin\Vert \operatorname{MD5}(1) \mathbin\Vert \cdots $ ，這些工具在確切意義上是*愚蠢的，因為它們不知道您使用了密碼學***，因此它們將涉及 MD5 的計算排除在可能的假設空間之外，並且如果它們有下一位猜測器，則不太可能像 MD5 一樣執行而不被明確程式為這樣。
那麼，一個黑匣子的熵是多少，裡面有一個 gremlin 盡職盡責地計算二進制展開 $ \pi $ ? 零！想節省電報成本嗎？給你的同事發一封電報告訴他們，你不必再給他們發一個額外的資訊*；*他們可以自己猜。
為什麼不同的工具列印不同的熵估計？因為它們都有不同的建模假設，並且每個估計都與工具的建模假設相關。
*高級的甚至可以進行貝氏模型選擇來結合所有的分佈族，但是上世紀的傳統統計學家傾向於厭惡有凝聚力的貝氏世界觀，更喜歡在你的終端上亂扔難以理解的行話和數字，讓你自己解釋。事實上，許多統計工具甚至沒有闡明他們的建模假設，而是盲目地使用由受人尊敬的統計學家開發的標準化測試，沒有人因為購買而被解僱。相比之下，上世紀的貝氏反叛者不斷地問一些你永遠不知道如何回答的關於先驗的煩人問題，所以他們不再被邀請回到晚宴上。
†某些高級貝氏主義者可能會選擇 $ B(1/2,1/2) $ ，或生活在不適當的不可採樣邊緣 $ B(0,0) $ . 更高級的可能會選擇 $ B(\alpha, \beta) $ 具有超先驗 $ \alpha $ 和 $ \beta $ ，如果走極端，就一直站在超級海龜的背上，他們乾巴巴地稱之為“分層建模”，而不是聽我的建議，因為我在他們頭上扔了太多烏龜後，他們開始避開我。
‡在進行貝氏模型選擇的工具中，這種可能性非常高，以至於假設框生成 $ \pi $ 即使該假設具有很小的先驗機率，也可能會超過後驗中的所有其他假設系列，並且使用貝氏模型選擇來猜測下一位的統一工具可能會為 $ \pi $ - 生成黑匣子。
簡而言之， $ \pi $ 不是隨機的，因為它是單個對象。不僅如此，甚至連一個鹼基都沒有證明是否正常 $ b. $
本質上，一個數字被認為是簡單的正常基數 $ b $ 如果它的基礎 $ -b $ 擴展使每個數字出現的平均頻率趨於 $ b^{-1}. $ 顯然，沒有任何有理數是正常的。
正常數是一個無理數，任何有限的數字模式都會在給定基數的擴展中以預期的極限頻率出現。眾所周知，幾乎所有實數都是正態的，但展示正態數存在巨大困難，就像設計程式碼實現通道容量時存在困難一樣，儘管香農的可實現性證明可以追溯到 1949 年。
回到 $ \pi, $ 實驗表明，它的數字接近於均勻分佈在所有已檢查的鹼基上，但這忽略了二階依賴效應
$$ which would have exponential complexity to check $$，並且隨機流的熵擷取了這些屬性，並且可能已經設計了測試來擷取這些影響，儘管每個測試都有不同的假設。