如何實際計算統計距離？
我有一個我定義的離散採樣算法。這就是說 $ A $ , 在輸入一些 pdf $ p(x) $ , 從 pdf 輸出樣本 $ p(x) $ . 有一些細微差別（你必須支持 $ p $ 有限，所以你實際上只是從某個統計距離內的某個分佈中採樣 $ SD $ 的分佈 $ p $ )，但沒什麼太複雜的。通過統計距離，我的意思是“總變化距離”：
$$ d(D_1,D_2) = \sum_{x\in\mathsf{supp}(D_1)\cup\mathsf{supp}(D_2)}\lvert \Pr[D_1 =x] - \Pr[D_2 = x]\rvert $$
想像一下，我可以（理論上）證明這個過程確實確實從內部的分佈中採樣 $ SD $ 的真實分佈，我想實現這個採樣器。典型的表現方式是什麼 $ A $ 產生理論上應該的分佈？給定一個完美的實現，這不會是一個問題，但我希望用它來捕捉錯誤。
有一些簡單的天真的事情可以做——例如，抽取一些樣本 $ (x_1,\dots,x_n) $ ，將此視為經驗分佈，併計算該分佈與（真實）pdf之間的統計距離 $ p(x) $ . 我對此的擔心是複雜類統計零知識的統計距離問題已經完成（請參閱Vadhan 論文的第 4 章進行調查），這可能暗示這是一種查找錯誤的糟糕方法。
當然：
- 可能是我的問題實例很簡單
- 我的問題以稍微不同的形式呈現（我相信 SZK 是一個電路類）
儘管如此，這讓我擔心檢查統計距離 $ A $ 從 $ p(x) $ 是一個棘手的問題。這是真的？有沒有比我上面提到的幼稚算法更好的算法？
- 證明你的方法是正確的。
- 將您的程式碼分解為非確定性統一位採樣器和確定性邏輯。
- 您可以使用全套標準軟體測試技術來測試確定性部分。
- 您可以使用自動形式驗證工具來證明確定性部分已正確實現。
- 您可以使用經過充分研究的密碼學（也可以使用確定性已知答案測試向量），這些密碼學由來自均勻位採樣器的經過充分研究的不可預測物理模型的觀察結果播種。
“好吧，”你說，“但是雪莉，你應該也可以使用隨機樣本的經驗假設檢驗——畢竟，目標是測試分佈的隨機抽樣器是否正確，所以為什麼不執行它並應用樣本分佈的標準經驗假設檢驗？具體來說，我們可以考慮軟體從預期分佈中正確採樣的原假設，並對該原假設應用具有指定統計顯著性水平的假設檢驗！
這沒有錯。但它有幾個問題。
- 分佈的經驗假設檢驗與您在軟體工程中可能熟悉的正常類型的自動測試在質量上有所不同，因為它們必然有誤報：
- 對確定性軟體屬性的測試會拒絕某些樣本，因為正確的軟體無法產生它們——因此如果遇到它們就是一個錯誤。
- 對零假設分佈的隨機檢驗會拒絕某些樣本，即使正確的軟體可以產生它們——當然，自負是有缺陷的軟體產生這些被拒絕的樣本的機率比正確的軟體高得多。那麼，當您的測試套件拒絕零假設並發出警報時，您會怎麼做？好吧，這可能是一個錯誤，也可能只是一個僥倖！最好重複執行它以確保警報率正是設置的顯著性水平 - 所以也許我們應該對 iid Bernoulli 試驗的原假設進行假設檢驗，由顯著性水平加權，但是如果那個測試失敗了？好吧，這可能是一個錯誤，也可能只是一個僥倖……
- 為了使這些經驗測試有用，它們需要高統計能力來檢測程序中可能存在的錯誤。因此，您需要假設合理的錯誤，並確認測試具有很高的統計能力來檢測這些錯誤。
- 您可以假設在開發過程中發生的特定錯誤，並相對容易地對它們進行測試。
但是，您也可以只在程序的確定性部分中測試那些。
- 您可以假設統計距離的界限：零假設， $ D(P \mathbin| Q) \leq \varepsilon $ ; 替代假設， $ D(P \mathbin| Q) \geq \varepsilon + \delta $ . 然後，您可以選擇假設檢驗，以保證這些替代假設具有一定的誤報率和統計功效。您甚至可以選擇這兩個界限來使用不同的統計距離，例如，原假設可能是有界 KL 散度，而備擇假設是海靈格距離過大的錯誤。
但是，這些測試達到規定的誤報率和統計功效所需的樣本數量通常是超線性的 $ 1/\varepsilon $ 和 $ 1/\delta $ ——如果它們存在這樣的保證，對於某些統計距離 $ D $ 他們不！
- 您可以只應用標准假設檢驗，並盲目地希望它們能發現錯誤。實際上，這在開發過程中非常有效，可以及早發現明顯的錯誤。
但是，它不會讓你走得很遠。 3. 隨著您的系統變得越來越大，您會很想擴展您所做的測試。
對於確定性屬性測試，將測試案例添加到測試套件僅意味著測試套件的每次執行都需要更多時間。
和 $ n $ 隨機假設檢驗，如果每個測試案例都有誤報率 $ \alpha $ ，測試套件有誤報率 $ 1 - (1 - \alpha)^n $ 迅速接近 $ 1 $ ——即，幾乎所有時間都出現誤報——如 $ n $ 增加。添加新測試時可以做什麼？
- 不理會測試案例的誤報率。
但是，如果您已經校準了測試案例以使測試套件具有規定的誤報率，那麼該誤報率會隨著您添加更多測試而上升——即使軟體執行良好！
- 每當您添加測試案例時，重新校準所有測試案例以具有誤報率 $ \alpha’ < \alpha $ 以便 $ 1 - (1 - \alpha)^n = 1 - (1 - \alpha’)^{n + 1} $ ，即選擇 $ \alpha’ = 1 - (1 - \alpha)^{n/(n + 1)} $ .
但是，在每個測試案例中，為了在較低的誤報率下保持相同的統計功效所需的樣本數量往往會隨著 $ n $ .
- 放棄“測試通過”的概念，而是記錄測試案例執行的詳細歷史記錄，以便以後進行元分析。
但是，當測試套件的答案不僅僅是通過或失敗時，軟體人員不喜歡它，並且沒有像 Jenkins 這樣的標準工具旨在應對測試結果概念的這種非二進制流動性，這是典型的矽谷主導軟體工程工具的白人 cismale 文化。
- 我叫嬌嬌，不是雪莉。
- 如果我們談論的是密碼學，那麼統計距離通常會非常小，以至於在夏天的一天，你根本沒有機會在曼哈頓的垃圾桶裡滾雪球來檢測它們。所以回到第一步：證明你的方法是正確的。
當然，所有這些都取決於有關您正在做什麼的更多細節。也許，對於您的應用程序、您的分佈、您的採樣器以及您的統計距離類型和您的界限 $ \varepsilon $ 關於統計距離的大小和您的容忍度 $ \delta $ 關於統計距離的大小以及您的開發過程和您的工具鏈，您實際上可以解決所有這些問題，在這種情況下，太好了！去吧！
使用 Pearson 的卡方檢驗。（自由度比可能結果的數量小一。）
統計距離指標會給你一個數字，但你應該使用哪個指標？您應該如何解釋使用該指標定義的距離？多大的距離才算太多？
一個 $ \chi^2 $ test 基本上是一種用 p 值來解釋距離（平方誤差的加權和）的方法。在這種情況下，您可以將該 p 值解釋為正確實施的採樣算法將產生與您觀察到的輸出類似的機率。（至少與觀察到的*“加權平方和誤差”一樣多。）*
您可以選擇要使用的樣本數量。然後計算您希望看到每個單獨結果的次數。你把每一個加起來 $ (observed - expected)^2 / expected $ 學期。得到的總和應該遵循卡方分佈，只要每個 $ expected $ 足夠大。
如果任何給定結果的預期發生次數太少，則合併低機率結果（合併）或增加採樣數。對於預期出現的最小數量（5、10、20、100），存在不同的經驗法則。由於您始終可以通過算法生成更多樣本，因此我建議 100-1000。（一些消息來源建議使用較低的最小值，因為通常很難獲得盡可能多的樣本，並且卡方分佈近似仍然足夠好。））
每個結果至少有 1000 次預期發生，測試應該適用於任何任意分佈。
然而，在密碼學的背景下，不應依賴經驗測試。我們關心非常微小的偏差。要獲得該級別的精度，您需要一個太大而無法實際生成的樣本量。
更重要的是，它們不能被依賴，因為沒有測試可以保證算法在對抗條件下是安全的。
未通過統計測試應被解釋為危險信號。然而，通過這些測試並不能保證算法是安全的。您只能檢測極端錯誤，例如實施問題。其他一切都與“不是非常破碎”沒有區別。
然而，許多實施錯誤不會導致統計測試失敗。我們正在處理隨機數。嚴重的缺陷可能會被人和機器漏掉，因為輸出看起來仍然是隨機的。相反，您應該將 99.99% 的精力集中在分析原始碼上。
幸運的是，您描述的算法類型並不難實現。我能想到六種“眾所周知的”算法來完成這項工作。每個只需要從均勻分佈中採樣的能力。這些算法中最複雜的別名方法仍然相當簡單。