如何測試一些數字是否沿間隔均勻分佈？

Question

我正在尋找一種算法（最好在C++中使用一個庫）或一些想法來告訴我，統計數據是否以統一的方式分佈在一個區間中。想象一下，我有兩個字符串：第一個沒有錯誤，第二個在某些點上有一些錯誤。我想檢查字符串中錯誤的位置是否具有統計意義。

考慮下面的例子。在第一種情況下，錯誤是均勻分佈的，第二種情況下，它們都在字符串的末尾，我的算法應該給出一些警告。

error-free string: 0110110101010110101 (3 errors occur at pos:5,12,15) 
erroneous string : 0110010101000100101 

sedond例如：

error-free string: 0110110101010110101 (3 errors occur at pos:17,18,19) 
erroneous string : 0110110101010110010 

我可以說在第一數據中的錯誤是正常的，但不是在第二個。

到目前爲止，我已經完成了這個想法：我想將字符串拆分爲相等的bin，假設字符串長度爲100.我選擇10個bin大小爲10.然後，我查看我們可以假設爲10的字符串。我希望在每個bin中看到1個錯誤。現在我計算我的預期距離統計有多遠。任何人有任何想法，如果這種方法是正確的？如果有效，每個垃圾箱應該有多大。它是否也取決於錯誤的數量？

Answer 1

您建議的方法，即將字符串分成多個分檔，希望能夠看到在分檔間差不多均勻分佈的錯誤數量，這種方法對諸如「每第十個位置都有錯誤」等模式視而不見。我相信你需要一種更一般的方法來區分錯誤發生與錯誤發生的位置之間的差異情況，從存在某種模式的情況到錯誤發生的位置。

換句話說，我認爲你實際上在尋找一種方法來衡量一個二進制字符串是隨機的，或者更準確地說，無模式的程度。字符串無花樣的最終數學定義是字符串Kolmogorov complexity，定義爲輸出字符串的最短程序的長度。可悲的是，Kolmogorov的複雜性是不可計算的。

計算二進制字符串無花樣的一種可行方法是使用Linear Hadamard Spectral Test。該測試可以使用Fast Fourier Transform在O(n logn)時間內執行，其中n是字符串的長度。但是，在我看來，似乎沒有準備好使用C++中的測試實現。

假設你願意妥協的測試易於實現的緣故穩健一點，你可以用下面的辦法：衡量字符串的patternlessness，只需gzip一個其內容是文件字符串，然後檢查壓縮率。壓縮越差，則字符串越無模式。該方法依賴於gzip包含Kolmogorov複雜性的某些方面的事實。特別是，有些容易檢測圖案的存在改善了壓縮比。