如何確定二進制字符串的統計隨機性？

Question

如何確定二進制字符串的統計隨機性？

Ergo，我該如何編碼我自己的測試，並返回一個對應於統計隨機性的單值，一個介於0和1.0之間的值（0不是隨機的，1.0是隨機的）？

測試需要在任何大小的二進制字符串上工作。

當您使用筆和紙做的，你可能會探討這樣的字符串：
    0（任意隨機性，唯一的選擇是1）
    00（不是隨機的，它的重複和火柴大小）
    01（更好，兩個不同的值）
    010（少隨機的，迴文）
    011（少隨機的，更1的，還是可以接受的）
    0101（少隨機的，圖案）
    0100（更好的，那些更少，但任何其它的分佈引起的圖案）

事例：

大小：1，可能性：2
    0：1.0（隨機）
    1：1.0（隨機）

大小：2，P：4
    00：？
    01：1.0（隨機）
    10：1.0（隨機）
    11：？

S：3，P：8
    000：？非隨機
    001：1.0（隨機）
    0123：？少隨機
    011：1.0（隨機）
    100：1.0（隨機）
    101：？隨機性較差
    110 1.0（隨機）
    0123：非隨機

依此類推。

我覺得這可能玩了很多破入串入所有可能子和比較頻率，但似乎這種基礎的應該已經在計算機科學的早期完成。

Answer 1

這會給你從0到1.0熵數：

你可能想嘗試尋找到Shannon Entropy，這是應用於數據和信息的熵度量。事實上，它實際上幾乎是熵的物理公式的直接模擬，這是由熱力學最公認的解釋所定義的。

更具體地說，就你而言，使用二進制字符串，你可以看到Binary Entropy Function，這是一個涉及二進制數據位隨機性的特殊情況。

這是通過

H(p) = -p*log(p) - (1-p)*log(1-p) 

計算值（對數在基座2;假設0*log(0)是0）

哪裏p是您的1（或0的百分比;該圖是對稱的，所以你的答案是一樣的兩種方式）

這裏是什麼功能得到：

正如你所看到的，如果p是0.5（等於0的1），那麼你的熵是最大值（1.0）。如果p是0或1.0，則熵是0。

這似乎正是你想要的，對吧？

唯一的例外是您的大小1例，這可能只是作爲一個例外。然而，100％0和100％1對我來說似乎不是太熵。但是如你所願地實施它們。

此外，這並沒有考慮到位的任何「排序」。只有它們的總和。所以，重複/迴文不會得到任何提振。您可能想爲此添加額外的啓發式。

這裏是你的另一事例：

 
00: -0*log(0) - (1-0)*log(1-0)    = 0.0 
01: -0.5*log(0.5) - (1-0.5)*log(1-0.5)  = 1.0 
010: -(1/3)*log(1/3) - (2/3)*log(2/3)   = 0.92 
0100: -0.25*log(0.25) - (1-0.25)*log(1-0.25) = 0.81 

Answer 2

好像你有一堆隨機性的啓發式。簡單地通過這些啓發式方法做出一些事情，並對所有啓發式方法的平均得分進行評分？

Answer 3

您可能會嘗試對字符串進行壓縮算法。有更多的重複（更少的隨機性），可以壓縮的字符串越多。

Answer 4

您似乎在尋找一種方法來查找二進制字符串的Kolmogorov複雜性。可悲的是，這是incomputable。通過壓縮算法運行後，字符串的大小可讓您瞭解它的隨機程度，因爲更多隨機字符串的可壓縮性較差。

Answer 5

前一段時間，我開發了一個簡單的啓發式，爲我的目的工作。

您只需計算0和1的「均勻性」，不僅在字符串本身中，而且還在字符串的導數上。例如，01010101的一階導數爲11111111，因爲每一位都改變，二階導數爲00000000，因爲一階導數中沒有位發生變化。然後，你只需根據你的口味來衡量這些「平衡」。

下面是一個例子：

#include <string> 
#include <algorithm> 

float variance(const std::string& x) 
{ 
    int zeroes = std::count(x.begin(), x.end(), '0'); 
    float total = x.length(); 
    float deviation = zeroes/total - 0.5f; 
    return deviation * deviation; 
} 

void derive(std::string& x) 
{ 
    char last = *x.rbegin(); 
    for (std::string::iterator it = x.begin(); it != x.end(); ++it) 
    { 
     char current = *it; 
     *it = '0' + (current != last); 
     last = current; 
    } 
} 

float randomness(std::string x) 
{ 
    float sum = variance(x); 
    float weight = 1.0f; 
    for (int i = 1; i < 5; ++i) 
    { 
     derive(x); 
     weight *= 2.0f; 
     sum += variance(x) * weight; 
    } 
    return 1.0f/sum; 
} 

int main() 
{ 
    std::cout << randomness("00000000") << std::endl; 
    std::cout << randomness("01010101") << std::endl; 
    std::cout << randomness("00000101") << std::endl; 
} 

你的示例輸入分別得到的0.129032，0.133333和3.2 「隨機性」。

在一個側面說明，您可以通過派生琴絃涼分形圖形;）

int main() 
{ 
    std::string x = "0000000000000001"; 
    for (int i = 0; i < 16; ++i) 
    { 
     std::cout << x << std::endl; 
     derive(x); 
    } 
} 

0000000000000001 
1000000000000001 
0100000000000001 
1110000000000001 
0001000000000001 
1001100000000001 
0101010000000001 
1111111000000001 
0000000100000001 
1000000110000001 
0100000101000001 
1110000111100001 
0001000100010001 
1001100110011001 
0101010101010101 
1111111111111111