給定統計測試的 P 值和測試的位數，估計每比特的熵？
假設某個統計 RNG 測試（例如來自NIST Statistical Test Suite、Dieharder等）給了我們一個特定的P 值（根據定義
$$ * $$用於NIST 特別出版物 800-22 )，經過測試 $ n $ RNG的位；說， $ P=0.001 $ （以高可信度表示測試失敗）和 $ n=2^{20} $ . 僅基於這些資訊，我們能說什麼關於每比特的（最大）熵 $ H $ 以某種規定的信心測試的 RNG？我的意思是，更準確地說：被測生成器至少具有熵率的假設 $ H $ 可以以公平的信心被拒絕；也許，與一些P 值相關（可能高於 $ P $ 在測試中獲得，說兩次）。
給定P 值，我們如何改進這一點 $ P_i $ 對於那個重複的實驗 $ k $ 次？
更新：如果這不能回答，當我們在被測 RNG 的結構上添加一些非常一般的假設時，它是否仍然如此，例如：它輸出具有一些未知恆定偏差的獨立位？根據需要細化這個額外的假設以獲得一些關係 $ P $ , $ n $ 和 $ H $ !
更新：我確實意識到，如果任何統計測試 RNG 通過，那麼對於測試的 RNG 的每比特熵根本沒有任何保證；並且如果它在我的數值範例中的值失敗，那麼它可能給出的每比特熵的任何暗示將是它至多是 $ H $ ， 接著就，隨即 $ H $ 危險地接近 1，因此不是很能說明問題（即使現在降低了P-value）。
$$ * $$我的理解是，用於統計 RNG 測試的P 值的正確定義是統計測試承諾對於任何 $ \alpha $ 和 $ 0\le\alpha\le 1 $ ，它最多輸出一個P值 $ \alpha $ 最多賠率 $ \alpha $ 當應用於完美的 TRNG 時。 此外，我相信NIST SP 800-22 第 1-4 頁的這句話中只有第二句話是正確的
對於P 值≥ 0.001，序列將被認為是隨機的，可信度為 99.9%。對於P 值< 0.001，序列將被認為是非隨機的，可信度為 99.9%。
必要時糾正我！
首先，方式（如果有的話）“ $ P $ -值”取決於 $ H $ （當然）取決於正在使用的統計測試。對於每個測試，結果會有所不同，我無法在此進行真正有意義的一般性討論，因為不同的測試考慮了輸出比特隨機過程的完全不同的方面。
一般來說，確實， $ P $ -value 不必依賴於 $ H $ . 最初我（可能是錯誤的）認為你只是指一個特定的測試（單比特頻率測試），這就是我的評論所指的。我將在我的回答中使用這個特定的測試來說明 $ P $ -值可以取決於 $ H $ 希望您能夠將我的方法推廣到您感興趣的其他測試。許多測試的分析都是相同的，但通常不可能得到任何與 $ P $ -價值和 $ H $ .
在我開始分析單比特頻率測試之前，我還要回答你關於句子真實性的問題
對於 P 值 ≥ 0.001，序列將被認為是隨機的，可信度為 99.9%。
一個 $ P $ 大於 0.001 的值意味著我們不能拒絕序列在顯著性水平為 0.001 時是隨機的假設。從這個意義上說，這句話是不精確的：並不是因為我們的測試很可能會產生我們的觀察結果，所以觀察結果是由 TRNG 產生的。任何時候都應該記住計算公式 $ P $ -值是在假設為真的假設下得出的。
單比特頻率測試分析
我現在將討論 NIST SP 800-22（第 2.1 節）中定義的單比特頻率測試。我的符號有時會有點不同，但我認為應該足夠清楚（如果不是，請評論）。
在最一般的意義上，即使是這種分析也很困難：最多可以說 $ P $ -值取決於熵 $ H $ ，但您可能應該忘記在一般情況下獲得簡單的關係（某種公式）。
您問題的以下部分（適用於單比特頻率測試）雖然有一個相當“不錯”的答案：
如果這無法回答，那麼當我們在被測 RNG 的結構上添加一些非常一般的假設時，它是否仍然如此，例如：它輸出具有一些未知恆定偏差的獨立位？根據需要細化這個額外的假設以獲得一些關係 $ P $ , $ n $ 和 $ H $ !
所以我們已經做出了使用特定統計測試的假設，因為否則我們無法回答這個問題。現在我將對RNG做出以下假設：
- 隨機數發生器的輸出位之間沒有任何依賴關係。
- RNG 輸出一個 $ 1 $ 以固定機率 $ q $ 和機率為零 $ 1-q $ . 為了得到一個很好的公式，我假設 $ q = 1/2 + \epsilon $ 和 $ \epsilon $ 足夠小，使得 $ \epsilon^4 \approx 0 $ . 我會參考 $ \epsilon $ 作為偏差。
- $ n $ 足夠大，但無論如何這個假設都隱含在測試中。
我將展示的是，在這些假設下， $ P_n $ （這只是 $ P $ 對於特定值 $ n $ ) 取決於熵 $ H $ . 請注意，我將使用 $ P_n $ 作為隨機變數和 $ p_n $ 用於此測試統計的實例化。一旦分佈 $ P_n $ 已知，我們可以回答以下問題：
源熵的機率是多少 $ H $ 鑑於觀察到的值 $ P $ -統計是 $ p_n $ ?
為了得到這個問題的答案，我們需要採取以下步驟
- 寫出偏差 $ \epsilon $ 就熵而言 $ H $ .
- 計算有偏 RNG 的檢驗統計量的機率分佈。
- 計算機率分佈 $ P $ - 有偏 RNG 的值。
熵和偏差
熵 $ H $ RNG 的一位由下式給出
$$ H = q \log_2\left(\frac{1}{q}\right) + (1-q)\log_2\left(\frac{1}{1 - q}\right) = 1 - \frac{2\epsilon^2}{\log 2} + \mathcal{O}(\epsilon^4), $$ 在哪裡 $ \log $ 是自然對數。因此，我們大約有： $$ \epsilon \approx \pm\sqrt{\frac{\log 2}{2}(1 - H)}. $$ 有兩個偏差對應於相同的熵，這不足為奇。為方便起見，我將在此答案的其餘部分中使用正值。這意味著我假設已知RNG 是正偏的。
檢驗統計
讓我們稱我們的輸出位序列 $ X_i $ . 我們正在尋找以下總和的分佈：
$$ S_n = \sum_{i = 1}^n (-1) ^ {X_i} = 2\left[\sum_{i = 1}^n X_i\right] - n $$ 由於 $ X_i $ 假設我們有獨立同分佈，漸近為 $ n \to \infty $ :
$$ S_n \sim \mathcal{N}\left(\epsilon , n, 4p(1 - p) , n\right). $$ 然後可以根據熵重寫均值和變異數 $ H $ （回想一下，實際上有兩種可能性）。用以下方式表達變異數 $ H $ ， 注意
$$ p(1 - p) = 1/4 - \epsilon^2 \approx 1/4 - \frac{\log 2}{2} (1 - H). $$
$ P $ -價值
這 $ P_n $ - 我們測試的值可以計算為
$$ P_n = 2\Phi\left(\frac{-S_n}{\sqrt{n}}\right). $$ 所以我們可以計算出機率 $ P_n \le p_n $ 為了一些價值 $ p_n $ :
$$ \Pr[P_n \le p_n] = \Pr\left[2\Phi\left(\frac{-S_n}{\sqrt{n}}\right) \le p_n\right] = \Pr\left[S_n \ge -\sqrt{n}\Phi^{-1}(p_n/2)\right]. $$ 現在我們可以使用分佈 $ S_n $ 我們之前得出的：
$$ \Pr[S_n \le s_n] = \Phi\left(\frac{s_n/\sqrt{n} - \sqrt{\frac{n\log 2}{2}(1 - H)}}{\sqrt{1 - 2(1 - H)\log 2}}\right). $$ 所以我們得到
$$ \Pr[P_n \le p_n] = \Phi\left(\frac{\Phi^{-1}(p_n/2) + \sqrt{\frac{n\log 2}{2}(1 - H)}}{\sqrt{1 - 2(1 - H) \log 2}}\right) $$ （在不太可能的情況下，我的計算沒有錯誤，我稍後會檢查它們）。
請注意，作為 $ n \to \infty $ , 上述機率為 $ 1 $ （為了 $ H \neq 1 $ ) 所以給定足夠的樣本位，我們最終會得出結論，該序列不是隨機的。所以這也應該回答你的問題
鑑於 $ P $ -價值觀 $ P_i $ 對於那個重複的實驗 $ k $ 次？
（至少在這種特定情況下）