coding: Насколько случайны данные, сгенерированные таким образом?

четверг, 12 декабря 2019 г.

Насколько случайны данные, сгенерированные таким образом?

#алгоритм #net #многопоточность #случайные_числа



  Внимание!
  
  Код в этом вопросе содержит баг, связанный с многопоточностью. Как оказалось, этот
баг оказывает влияние на генерацию случайных чисел, что делает затруднительным его
устранение без инвалидации существующих ответов.
  
  Исправленная версия вопроса: Дедлочная генерация случайных чисел


Есть два потока, захватывающие блокировку в разном порядке, что приводит к дедлокам.
Для генерации каждого следующего бита производится ожидание дедлока и проверка чётности
числа инкрементов в первом потоке. Для увеличения длины цепочки на каждой итерации
делается sleep(0).

Сгенерированные таким образом данные являются случайными или псевдослучайными?
Как можно оценить, насколько они случайны?

Imports System.Threading

Module All
  Dim Value1 As Integer, Value2 As Integer
  Dim Sem1 As New SemaphoreSlim(1, 1), Sem2 As New SemaphoreSlim(1, 1)
  Dim Count As Integer

  Private Sub Inc(SemA As SemaphoreSlim, SemB As SemaphoreSlim, ByRef Value As Integer)
    Do
      Thread.Sleep(0)
      SemA.Wait()
      Interlocked.Increment(Count)
      SemB.Wait()
      Interlocked.Decrement(Count)
      Interlocked.Increment(Value)
      If SemB.CurrentCount = 0 Then SemB.Release() Else Interlocked.Increment(Count)
      If SemA.CurrentCount = 0 Then SemA.Release() Else Interlocked.Increment(Count)
    Loop
  End Sub

  Private Sub Init()
    Call (New Thread(Sub() Inc(Sem1, Sem2, Value1))).Start()
    Call (New Thread(Sub() Inc(Sem2, Sem1, Value2))).Start()
  End Sub

  Public Function GetRandBit() As Integer
    If Thread.VolatileRead(Count) = 2 Then
      Thread.VolatileWrite(Value1, 0)
      Thread.VolatileWrite(Value2, 0)
      Interlocked.Decrement(Count)
      Sem2.Release()
    End If

    Do Until Thread.VolatileRead(Count) = 2
      Thread.Sleep(16)
    Loop

    Return Thread.VolatileRead(Value1) And 1
  End Function

  Sub Main()
    Init()
    Do
      Console.Write(GetRandBit())
    Loop
  End Sub
End Module


Пример сгенерированных данных:


  11001010110011011111011100100100011001101111010001001110011101000000001010111010010000100110010001100111011101011000111111111110100010011110111001001001011111000001101011011010101000111001001010100000110111111011100111010001011000001111001101000101000100101010110101100110010110110011011110101111011011010011000101101101100010000010001110011001100100000101001110110011101110101110111011011001111001100011111001101101001100100101100001111100111101101001011110111100111100100111110110100100000010110010011001100010110010110010111010111101101101111000101011010101111000000010101010101110110111000010000110001000111001001110100001011110011101111001100101100111001001010101111110011110110011000011110110000111010011111010000010111010110010010011110111011001110001011010011101101110001001101000101111001100110011100011110101000100100011110011000000000100011110111000000100010111000000110011110001100100111010111100101110010001110100010001000001101001101100111101111101101100011100110011011001000111101100111011110011111001110111011011110010110101110110101111110000101101001100101000111010111000001010010011001010101000111001011010100100111011100010110101001110111111111110001111101111111011001110111011001010010001000010011111110111010001111011101001001101110001010101000001001011100011101100011111111110101010110111000100100110000101101101101001010001010001111001111000000101000111000001101000101010001111100110010111001101001000111000111011101111001011101101011111000110111011010001100111000111001100011001001100011000001001111001100101101000010111000111101010111001101011100101011000001111100111100111100101110010001011000101010101011111110010111110111111000100000101011000111011010111100101001111011101011101111101110111011011100110110111001011110010100110111110001010000010101110001000101010001000100100110001011100111100100000011100000011011101111101101011000011111100110101011011110000011110101000100110110100100010110101011000100011100001011001001011100000000001110010011001000101100000111001010101100000010000011110100101111111010100101011000100111100

Ответы

Ответ 1


Насколько случайны данные, сгенерированные таким образом?


Можно сравнить с тем, что выдает RNGCryptoServiceProvider -- криптографический генератор
случайных чисел.
Можно вывести в виде рис. результат работы генератора. И если есть паттерны, то они
сразу будут заметны.



см. Псевдослучайно vs. По-настоящему Случайно.


Ответ 2


UPD
Протестировал выборку на сходство с детерминированной и случайной последовательностями,
имеющими примерно такое же соотношение нулей (972) и единиц (1081).

Сравнение велось по следующим тестам.


Тест на подпоследовательности и их корреляцию с последующим элементом (до 7 элементов).
Количество и степень детерминированности подпоследовательностей совпали со случайной
выборкой, в то время как синусная выборка проявила большое количество полностью детерминированных
подпоследовательностей.
Тест на максимумы автокорреляционной функции (АКФ).
Тест АКФ совпал со случайной выборкой (отсутствие существенных корреляций), в то
время как в синусной выборке присутствуют практически полные корреляции.
Тест на авторегрессию данных по Левинсону - Дарбину, подробные объяснения здесь
Темпы падения СКО при увеличении порядка авторегрессии совпали с таковыми для случайной
выборки, в то время как синусная выборка обнаружила наличие авторегрессий, резко снижающих
СКО остатка.


Вывод: Выборка реальных данных проявила полное сходство со случайной последовательностью
и явное отличие от детерминированной (синусной).

Программа:

set_time_limit(300);
$str_real = "11001010110011011111011100100100011001101111010001001110011101000000001010111010010000100110010001100111011101011000111111111110100010011110111001001001011111000001101011011010101000111001001010100000110111111011100111010001011000001111001101000101000100101010110101100110010110110011011110101111011011010011000101101101100010000010001110011001100100000101001110110011101110101110111011011001111001100011111001101101001100100101100001111100111101101001011110111100111100100111110110100100000010110010011001100010110010110010111010111101101101111000101011010101111000000010101010101110110111000010000110001000111001001110100001011110011101111001100101100111001001010101111110011110110011000011110110000111010011111010000010111010110010010011110111011001110001011010011101101110001001101000101111001100110011100011110101000100100011110011000000000100011110111000000100010111000000110011110001100100111010111100101110010001110100010001000001101001101100111101111101101100011100110011011001000111101100111011110011111001110111011011110010110101110110101111110000101101001100101000111010111000001010010011001010101000111001011010100100111011100010110101001110111111111110001111101111111011001110111011001010010001000010011111110111010001111011101001001101110001010101000001001011100011101100011111111110101010110111000100100110000101101101101001010001010001111001111000000101000111000001101000101010001111100110010111001101001000111000111011101111001011101101011111000110111011010001100111000111001100011001001100011000001001111001100101101000010111000111101010111001101011100101011000001111100111100111100101110010001011000101010101011111110010111110111111000100000101011000111011010111100101001111011101011101111101110111011011100110110111001011110010100110111110001010000010101110001000101010001000100100110001011100111100100000011100000011011101111101101011000011111100110101011011110000011110101000100110110100100010110101011000100011100001011001001011100000000001110010011001000101100000111001010101100000010000011110100101111111010100101011000100111100";

function samples($flow, $k){
    $trans = [];
    for($i=1; $i<65536; $i++){ 
        $str = sprintf("%016b", $i);
        $trans[$str] = $i;
    }
    $len = strlen($flow);
    $cnt_num = (1 << $k);
    for ($num = 0; $num < $cnt_num; $num++){ // для каждого сэмпла
        $st = substr(sprintf("%016b",$num), -$k, $k);
        $sum = 0;
        $sum1 =0;
        for($i = $k; $i < $len; $i++){
            $n = substr($flow,$i-$k,$k);
            $n = str_pad($n, 16, "0", STR_PAD_LEFT);
            $n = $trans[$n];
            if($n == $num){
                $sum++;
                $sum1 += $flow[$i];
            } 
        }
        if($sum) $result[$st] = sprintf("%5.3f = $sum1/$sum", $sum1/$sum);
    }
    return $result; 
}

function test_samples($arr, $n){
    print "
АНАЛИЗ ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ
";
    for($k=1; $k <= $n; $k++){
        $sam = samples($arr, $k);
        arsort($sam);
        print "
$k-битовые предвестники и антагонисты единичного бита:";
        $order = 0;
        $prn = 0;
        foreach($sam as $key=>$item){
            if($order == $k){
                $prn = 0;
            }
            if(($order < $k) || ($order >= ((1<<$k)-$k))){
                if(($prn++ % 5) == 0) print"
";
                $kk = substr(sprintf("%016d",$key),-$k, $k); 
                print "\"$kk\" => $item ";
            }
            $order++;
        }
    }
}

function center(&$arr){
    $len = count($arr);
    $aver = array_sum($arr) / $len; 
    foreach($arr as &$item){
        $item -= $aver;
    }
}

function scalar_prod($a, $b, $shift = 0, &$c = null){
    $scal = 0;
    if(is_null($c)) $cc = []; else $cc = &$c;
    foreach($a as $key => $item){
        $cc[] = $item * $b[$key+$shift];
        $scal += end($cc);
    }
    return  $scal;  
}

function print_array($arr, $str, $n = 11){
    print $str."[";
    foreach($arr as $key => $item){
        if(!(($key+1) % $n)) print "
"; 
        printf ("\"%03d\" => %.3f, ", $key, $item);
    }
    print "]";  
}   

function print_s($a, $b, $str){
    print("

$str");
    printf("
 %.3f f0 + %.3f f1 = %.3f", $a[0][0], $a[0][1], $b[0]);
    printf("
 %.3f f0 + %.3f f1 = %.3f", $a[1][0], $a[1][1], $b[1]);
    $det = $a[0][0]*$a[1][1] - $a[1][0]*$a[0][1];
    $det0 = $b[0]*$a[1][1] - $b[1]*$a[0][1];
    $det1 = $a[0][0]*$b[1] - $a[1][0]*$b[0];
    printf("
Решение: f = [%f, %f]", (float)$det0 / $det, (float)$det1/$det);
}

function acf($ar_flow, $k, $center = -1, $len = null){
    if(is_null($len)){
        $len = count($flow);
    }
    $slice = array_slice($ar_flow, $k, $len-$k);
    for($lag = 0; $lag <= $k; $lag++){
        $result[$lag] = scalar_prod($slice, $ar_flow, $k-$lag);
    }
    if($center != -1){
        $denom = 1.0/$result[0];
        foreach($result as &$res){
            $res *= $denom;
        }
    } 
    return $result;
}

function compare_s($test){
    $m = count($test);  
    $acf2 = acf($test, 0, -1, $m-2);
    $acf1 = acf($test, 1, -1, $m-1);
    $acf = acf($test, 2);
    $a_exact = [ [$acf1[0],$acf1[1]], [$acf1[1],$acf2[0]] ];
    $a = [ [$acf[0],$acf[1]], [$acf[1],$acf[0]] ];
    $b = [-$acf[1], -$acf[2]];
    print_s($a_exact, $b, "Контроль симметрии матрицы

Точная система (порядок
2):");
    print_s($a, $b, "Тёплицева система (порядок 2):");
}

function durbin($acf, $n){
    $ff = [];
    $f = [-$acf[1]/$acf[0]];
    $ff[] = $f;
    for($r = 1; $r < $n; $r++){
        $acr = array_reverse(array_slice($acf, 0, $r+1));
        $fr = array_reverse($f);
        $fr[] = 1;
        $f[] = 0;
        $beta = - ($acf[$r+1] + scalar_prod($f, $acr))/scalar_prod($fr, $acr);
        $f = array_map(function($a,$b) use($beta){
            return $a+$beta*$b;
        },$f,$fr);
        $ff[] = $f;
    }
    return $ff;
}

function test_durbin($arr, $a, $n, $center=0){
    printf("АВТОРЕГРЕССИЯ ПО ДАРБИНУ");
    compare_s($arr);    
    $len = count($arr);     
    if($center){
        center($arr);
    } 
    $eps_arr = 0;
    foreach($arr as $item){
        $eps_arr += $item*$item;
    }
    printf("

Порядок АР = %d, длина выборки = $len, СКО выборки = %f):", $n,
sqrt($eps_arr/($len-1)));
    $s = [];
    $ff = durbin($a,$n);
    foreach($ff as $key => $f){
        $c = array_reverse($f);
        $eps = 0;
        $brr = [];
        for($j=$n; $j<$len; $j++){
            $brr[$j] = $arr[$j]+scalar_prod($c, $arr, $j-$n);
            $eps += pow($brr[$j],2);
        }
        $k = count($f)-1;
        $s[$key+1] = sqrt($eps/($len-$n));
    }
    return $s;
}

function analytics($str_data){
    print $str_data;
    $len_data = strlen($str_data);
    printf("
Длина последовательности = %d 
", $len_data);
    $array_data = [];
    for($i=0; $i<$len_data; $i++){
        $array_data[$i] = (int)$str_data[$i];
    }
    test_samples($str_data, 7);
    $n = 100;
    $a = acf($array_data, $n, 1);
    $acf1 = $a;
    arsort($acf1);
    print("

МАКСИМУМЫ АКФ (из $n):");
    var_dump(array_slice($acf1, 0, 10, TRUE));
    $sko = test_durbin($array_data, $a, $n);
    print_array($sko, "
CKO: 
");
}

print("*** РЕАЛЬНЫЕ ДАННЫЕ ***

");
analytics($str_real);

$m=2054;
$str_sin = "";
for($j=0; $j<$m; $j++) $str_sin .= (sin($j) > -0.08) ? "1" : "0";
print("

*** СИНУСНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ ***

");
analytics($str_sin);

$str_mt_rand = "";
for($i=0; $i<$m; $i++){
    $str_mt_rand .= (mt_rand() > 100e7) ? 1 : 0;
}
print("

*** ДАТЧИК mt_rand() ***

");
analytics($str_mt_rand);


Результаты:


*** РЕАЛЬНЫЕ ДАННЫЕ ***

11001010110011011111011100100100011001101111010001001110011101000000001010111010010000100110010001100111011101011000111111111110100010011110111001001001011111000001101011011010101000111001001010100000110111111011100111010001011000001111001101000101000100101010110101100110010110110011011110101111011011010011000101101101100010000010001110011001100100000101001110110011101110101110111011011001111001100011111001101101001100100101100001111100111101101001011110111100111100100111110110100100000010110010011001100010110010110010111010111101101101111000101011010101111000000010101010101110110111000010000110001000111001001110100001011110011101111001100101100111001001010101111110011110110011000011110110000111010011111010000010111010110010010011110111011001110001011010011101101110001001101000101111001100110011100011110101000100100011110011000000000100011110111000000100010111000000110011110001100100111010111100101110010001110100010001000001101001101100111101111101101100011100110011011001000111101100111011110011111001110111011011110010110101110110101111110000101101001100101000111010111000001010010011001010101000111001011010100100111011100010110101001110111111111110001111101111111011001110111011001010010001000010011111110111010001111011101001001101110001010101000001001011100011101100011111111110101010110111000100100110000101101101101001010001010001111001111000000101000111000001101000101010001111100110010111001101001000111000111011101111001011101101011111000110111011010001100111000111001100011001001100011000001001111001100101101000010111000111101010111001101011100101011000001111100111100111100101110010001011000101010101011111110010111110111111000100000101011000111011010111100101001111011101011101111101110111011011100110110111001011110010100110111110001010000010101110001000101010001000100100110001011100111100100000011100000011011101111101101011000011111100110101011011110000011110101000100110110100100010110101011000100011100001011001001011100000000001110010011001000101100000111001010101100000010000011110100101111111010100101011000100111100
Длина последовательности = 2054 

АНАЛИЗ ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ

1-битовые предвестники и антагонисты единичного бита:
"0" => 0.531 = 516/972 
"1" => 0.522 = 564/1081 
2-битовые предвестники и антагонисты единичного бита:
"00" => 0.558 = 254/455 "01" => 0.541 = 279/516 
"10" => 0.507 = 262/517 "11" => 0.504 = 284/564 
3-битовые предвестники и антагонисты единичного бита:
"101" => 0.576 = 151/262 "100" => 0.563 = 143/254 "011" => 0.552 = 154/279 
"001" => 0.504 = 128/254 "110" => 0.482 = 135/280 "111" => 0.458 = 130/284 
4-битовые предвестники и антагонисты единичного бита:
"1000" => 0.631 = 70/111 "1100" => 0.611 = 88/144 "1101" => 0.600 = 81/135 "0011"
=> 0.586 = 75/128 
"0111" => 0.468 = 72/154 "0001" => 0.459 = 51/111 "0000" => 0.456 = 41/90 "1111"
=> 0.446 = 58/130 
5-битовые предвестники и антагонисты единичного бита:
"00011" => 0.725 = 37/51 "01000" => 0.691 = 38/55 "11101" => 0.667 = 50/75 "11100"
=> 0.615 = 48/78 "01010" => 0.614 = 35/57 
"00001" => 0.439 = 18/41 "10111" => 0.430 = 34/79 "00110" => 0.396 = 21/53 "01111"
=> 0.389 = 28/72 "10000" => 0.317 = 13/41 
6-битовые предвестники и антагонисты единичного бита:
"100011" => 0.788 = 26/33 "101000" => 0.741 = 20/27 "111100" => 0.711 = 27/38 "111101"
=> 0.697 = 23/33 "001100" => 0.656 = 21/32 
"011101" => 0.643 = 27/42 
"100001" => 0.385 = 5/13 "100110" => 0.385 = 15/39 "010100" => 0.364 = 8/22 "110000"
=> 0.333 = 8/24 "001111" => 0.316 = 12/38 
"010000" => 0.294 = 5/17 
7-битовые предвестники и антагонисты единичного бита:
"0100011" => 0.833 = 15/18 "1000011" => 0.800 = 4/5 "0111100" => 0.792 = 19/24 "0101000"
=> 0.786 = 11/14 "0100000" => 0.750 = 9/12 
"0001100" => 0.750 = 6/8 "1001110" => 0.737 = 14/19 
"1010000" => 0.286 = 2/7 "1011110" => 0.278 = 5/18 "1010100" => 0.273 = 3/11 "1110000"
=> 0.231 = 3/13 "1001111" => 0.211 = 4/19 
"0100001" => 0.200 = 1/5 "1000110" => 0.143 = 1/7 

МАКСИМУМЫ АКФ (из 100):
array (size=10)
  0 => float 1
  6 => float 0.560606060606
  15 => float 0.560606060606
  34 => float 0.555555555556
  58 => float 0.554545454545
  18 => float 0.553535353535
  4 => float 0.550505050505
  73 => float 0.547474747475
  16 => float 0.547474747475
  85 => float 0.546464646465
АВТОРЕГРЕССИЯ ПО ДАРБИНУ

Контроль симметрии матрицы

Точная система (порядок 2):
1080.000 f0 + 564.000 f1 = -563.000
564.000 f0 + 1081.000 f1 = -546.000
Решение: f = [-0.353973, -0.320406]

Тёплицева система (порядок 2):
1079.000 f0 + 563.000 f1 = -563.000
563.000 f0 + 1079.000 f1 = -546.000
Решение: f = [-0.354171, -0.321225]

Порядок АР = 100, длина выборки = 2054, СКО выборки = 0.725635):
CKO: 
["001" => 0.619, "002" => 0.579, "003" => 0.562, "004" => 0.548, "005" => 0.541, "006"
=> 0.538, "007" => 0.533, "008" => 0.531, "009" => 0.527, 
"010" => 0.528, "011" => 0.523, "012" => 0.525, "013" => 0.522, "014" => 0.521, "015"
=> 0.524, "016" => 0.518, "017" => 0.522, "018" => 0.521, "019" => 0.518, "020" => 0.522, 
"021" => 0.518, "022" => 0.517, "023" => 0.519, "024" => 0.517, "025" => 0.516, "026"
=> 0.518, "027" => 0.515, "028" => 0.515, "029" => 0.519, "030" => 0.516, "031" => 0.514, 
"032" => 0.518, "033" => 0.513, "034" => 0.519, "035" => 0.516, "036" => 0.517, "037"
=> 0.515, "038" => 0.519, "039" => 0.514, "040" => 0.519, "041" => 0.516, "042" => 0.516, 
"043" => 0.518, "044" => 0.516, "045" => 0.518, "046" => 0.515, "047" => 0.516, "048"
=> 0.516, "049" => 0.514, "050" => 0.518, "051" => 0.516, "052" => 0.516, "053" => 0.518, 
"054" => 0.515, "055" => 0.515, "056" => 0.516, "057" => 0.514, "058" => 0.513, "059"
=> 0.515, "060" => 0.516, "061" => 0.517, "062" => 0.522, "063" => 0.513, "064" => 0.519, 
"065" => 0.515, "066" => 0.517, "067" => 0.515, "068" => 0.512, "069" => 0.517, "070"
=> 0.515, "071" => 0.523, "072" => 0.514, "073" => 0.518, "074" => 0.517, "075" => 0.518, 
"076" => 0.513, "077" => 0.519, "078" => 0.516, "079" => 0.514, "080" => 0.519, "081"
=> 0.516, "082" => 0.516, "083" => 0.519, "084" => 0.517, "085" => 0.517, "086" => 0.515, 
"087" => 0.520, "088" => 0.516, "089" => 0.515, "090" => 0.514, "091" => 0.513, "092"
=> 0.517, "093" => 0.521, "094" => 0.515, "095" => 0.517, "096" => 0.520, "097" => 0.513, 
"098" => 0.516, "099" => 0.521, "100" => 0.489, ]

*** СИНУСНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ ***

11110001110001110001111000111000111000111000111100011100011100011110001110001110001110001111000111000111000111100011100011100011100011110001110001110001111001111000111000111000111100011100011100011110011110001110001110001111000111000111000111000111100011100011100011110001110001110001110001111000111000111000111100011100011100011100011110001110001110001111000111000111000111000111100011100011100011110001110001110001110001111000111000111000111100011100011100011100011110001110001110001111000111000111000111000111100011100011100011110011110001110001110001111000111000111000111000111100011100011100011110001110001110001110001111000111000111000111100011100011100011100011110001110001110001111000111000111000111000111100011100011100011110001110001110001110001111000111000111000111100011100011100011100011110001110001110001111000111000111000111000111100011100011100011110011110001110001110001111000111000111000111100111100011100011100011110001110001110001110001111000111000111000111100011100011100011100011110001110001110001111000111000111000111000111100011100011100011110001110001110001110001111000111000111000111100011100011100011100011110001110001110001111000111000111000111000111100011100011100011110001110001110001110001111000111000111000111100111100011100011100011110001110001110001110001111000111000111000111100011100011100011100011110001110001110001111000111000111000111000111100011100011100011110001110001110001110001111000111000111000111100011100011100011100011110001110001110001111000111000111000111000111100011100011100011110001110001110001110001111000111000111000111100111100011100011100011110001110001110001111001111000111000111000111100011100011100011100011110001110001110001111000111000111000111000111100011100011100011110001110001110001110001111000111000111000111100011100011100011100011110001110001110001111000111000111000111000111100011100011100011110001110001110001110001111000111000111000111100011100011100011100011110001110001110001111001111000111000111000111100011100011100011100011110001110001110001111000111000111000111000111100011100
Длина последовательности = 2054 

АНАЛИЗ ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ

1-битовые предвестники и антагонисты единичного бита:
"1" => 0.698 = 756/1083 
"0" => 0.336 = 326/970 
2-битовые предвестники и антагонисты единичного бита:
"01" => 1.000 = 326/326 "11" => 0.567 = 429/756 
"00" => 0.507 = 326/643 "10" => 0.000 = 0/327 
3-битовые предвестники и антагонисты единичного бита:
"001" => 1.000 = 326/326 "011" => 1.000 = 326/326 "000" => 1.000 = 317/317 
"110" => 0.000 = 0/327 
4-битовые предвестники и антагонисты единичного бита:
"1001" => 1.000 = 9/9 "0011" => 1.000 = 326/326 "0001" => 1.000 = 317/317 "1000"
=> 1.000 = 317/317 
5-битовые предвестники и антагонисты единичного бита:
"10011" => 1.000 = 9/9 "11001" => 1.000 = 9/9 "00011" => 1.000 = 317/317 "11000"
=> 1.000 = 317/317 "10001" => 1.000 = 317/317 
6-битовые предвестники и антагонисты единичного бита:
"110011" => 1.000 = 9/9 "100111" => 1.000 = 9/9 "111001" => 1.000 = 9/9 "110001"
=> 1.000 = 317/317 "111000" => 1.000 = 317/317 
"100011" => 1.000 = 317/317 
7-битовые предвестники и антагонисты единичного бита:
"1111000" => 1.000 = 93/93 "1100111" => 1.000 = 9/9 "1110011" => 1.000 = 9/9 "1111001"
=> 1.000 = 9/9 "1110001" => 1.000 = 317/317 
"1100011" => 1.000 = 317/317 "0111000" => 1.000 = 224/224 

МАКСИМУМЫ АКФ (из 100):
array (size=10)
  0 => float 1
  44 => float 0.994882292733
  88 => float 0.989764585466
  69 => float 0.96417604913
  25 => float 0.959058341863
  19 => float 0.954964176049
  63 => float 0.949846468782
  94 => float 0.924257932446
  50 => float 0.919140225179
  6 => float 0.914022517912
АВТОРЕГРЕССИЯ ПО ДАРБИНУ

Контроль симметрии матрицы

Точная система (порядок 2):
1082.000 f0 + 756.000 f1 = -755.000
756.000 f0 + 1083.000 f1 = -429.000
Решение: f = [-0.821865, 0.177590]

Тёплицева система (порядок 2):
1081.000 f0 + 755.000 f1 = -755.000
755.000 f0 + 1081.000 f1 = -429.000
Решение: f = [-0.822440, 0.177560]

Порядок АР = 100, длина выборки = 2054, СКО выборки = 0.726306):
CKO: 
["001" => 0.406, "002" => 0.695, "003" => 0.890, "004" => 0.749, "005" => 0.469, "006"
=> 0.325, "007" => 0.593, "008" => 0.820, "009" => 0.924, 
"010" => 0.782, "011" => 0.541, "012" => 0.216, "013" => 0.514, "014" => 0.763, "015"
=> 0.945, "016" => 0.837, "017" => 0.619, "018" => 0.247, "019" => 0.435, "020" => 0.713, 
"021" => 0.909, "022" => 0.896, "023" => 0.695, "024" => 0.407, "025" => 0.327, "026"
=> 0.652, "027" => 0.862, "028" => 0.945, "029" => 0.763, "030" => 0.514, "031" => 0.157, 
"032" => 0.579, "033" => 0.808, "034" => 0.964, "035" => 0.820, "036" => 0.595, "037"
=> 0.194, "038" => 0.495, "039" => 0.751, "040" => 0.941, "041" => 0.876, "042" => 0.670, 
"043" => 0.362, "044" => 0.412, "045" => 0.699, "046" => 0.898, "047" => 0.931, "048"
=> 0.740, "049" => 0.480, "050" => 0.281, "051" => 0.630, "052" => 0.846, "053" => 0.970, 
"054" => 0.800, "055" => 0.567, "056" => 0.101, "057" => 0.555, "058" => 0.791, "059"
=> 0.969, "060" => 0.854, "061" => 0.642, "062" => 0.306, "063" => 0.469, "064" => 0.734, 
"065" => 0.926, "066" => 0.905, "067" => 0.708, "068" => 0.429, "069" => 0.363, "070"
=> 0.672, "071" => 0.879, "072" => 0.961, "073" => 0.779, "074" => 0.535, "075" => 0.235, 
"076" => 0.663, "077" => 1.921, "078" => 1.053, "079" => 18.272, "080" => 0.637, "081"
=> 0.273, "082" => 0.543, "083" => 0.777, "084" => 0.956, "085" => 0.883, "086" => 0.676, 
"087" => 0.369, "088" => 0.420, "089" => 0.704, "090" => 0.903, "091" => 0.930, "092"
=> 0.739, "093" => 0.476, "094" => 0.295, "095" => 0.635, "096" => 0.849, "097" => 0.970, 
"098" => 0.796, "099" => 0.563, "100" => 0.080, ]

*** ДАТЧИК mt_rand() ***

11001100110110101100010010001011100011010100100101110010011100000111100110011011110010101111001011000101000101111101011010000001111111011010111001100110011101011010011101100110110110100111000011000000101010110110101010000011111011011101100000110100000110100111100100010110011010010001110111100001011000110101111011100111001100111110111111110000011000000011001000010010100111001011110111111110101101110000011011001111000011101011110111010100110111110001110110011100011111100000110110111110110110111011001101100101000101110111111000111001010000011010011110101110111110011101001010001110111110011011011111010100111111100101100011111010011111000110110001010101110001011010011001111110111001000110011001010010110110011011101001010011100101000110110010101011111111100110110011110101110100001100011100100101001001111001100110111100101010010101010001101011001100110001111100111101110110111010100110110101101000000011010101100010011100010000111111101110100011110101110110101010100101001101101001011110101111001111000000000111111010101000001001100010011101010110111011100010001000010001010111111010101110010011010010000001101011011111010000101010001101101010010111010111110001000001100011101110000110000011100111101001010110000101101110001110001100010111011110100100110100010011101101011010010101010010001100000110011110110010011011001100001001111111000001010110110000001100111111000100001111011011011110100111110100000010111011010011110000000101101110111111110011000011000101111100010111110101000001010010101101110111110011010011100100101010110101111010001011100010110101110011101100011000111100000111110111001111010110110110001010011000010101000100100100000011110001001111001000111100011001001000111110011011001101011001011110111110110111010011001110100101111000010101101110001110011111101110100011010001111011111101110101000111001011101010100011010000011111011010100101000111010101001101111111111011111110111111100111000011011110101011000010111101001011001010101100001000101100011010011110101001011010101011100100001001111010101110011101111100111110101101010000
Длина последовательности = 2054 

АНАЛИЗ ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ

1-битовые предвестники и антагонисты единичного бита:
"0" => 0.552 = 521/943 
"1" => 0.530 = 588/1110 
2-битовые предвестники и антагонисты единичного бита:
"10" => 0.559 = 292/522 "00" => 0.544 = 229/421 
"01" => 0.541 = 282/521 "11" => 0.519 = 305/588 
3-битовые предвестники и антагонисты единичного бита:
"001" => 0.585 = 134/229 "010" => 0.565 = 135/239 "110" => 0.555 = 157/283 
"111" => 0.521 = 159/305 "011" => 0.518 = 146/282 "101" => 0.507 = 148/292 
4-битовые предвестники и антагонисты единичного бита:
"0010" => 0.600 = 57/95 "1001" => 0.587 = 74/126 "0001" => 0.583 = 60/103 "0110"
=> 0.574 = 78/136 
"0000" => 0.517 = 45/87 "0011" => 0.515 = 69/134 "1111" => 0.503 = 80/159 "0101"
=> 0.489 = 66/135 
5-битовые предвестники и антагонисты единичного бита:
"11001" => 0.642 = 43/67 "00001" => 0.622 = 28/45 "00000" => 0.619 = 26/42 "00010"
=> 0.605 = 26/43 "10010" => 0.596 = 31/52 
"00101" => 0.491 = 28/57 "10101" => 0.487 = 38/78 "00011" => 0.483 = 29/60 "11111"
=> 0.475 = 38/80 "10000" => 0.422 = 19/45 
6-битовые предвестники и антагонисты единичного бита:
"000001" => 0.769 = 20/26 "011001" => 0.733 = 22/30 "000010" => 0.647 = 11/17 "010011"
=> 0.645 = 20/31 "010010" => 0.643 = 18/28 
"110100" => 0.636 = 21/33 
"011111" => 0.452 = 19/42 "101011" => 0.447 = 17/38 "100001" => 0.421 = 8/19 "000011"
=> 0.393 = 11/28 "100101" => 0.387 = 12/31 
"010000" => 0.368 = 7/19 
7-битовые предвестники и антагонисты единичного бита:
"0000010" => 0.833 = 5/6 "0000111" => 0.818 = 9/11 "1000001" => 0.812 = 13/16 "0011001"
=> 0.800 = 12/15 "1101111" => 0.739 = 17/23 
"1001101" => 0.737 = 14/19 "1000101" => 0.733 = 11/15 
"0011010" => 0.375 = 6/16 "1000011" => 0.375 = 3/8 "0001100" => 0.357 = 5/14 "0001101"
=> 0.353 = 6/17 "0101100" => 0.308 = 4/13 
"0011011" => 0.300 = 6/20 "1010000" => 0.182 = 2/11 

МАКСИМУМЫ АКФ (из 100):
array (size=10)
  0 => float 1
  20 => float 0.565606361829
  7 => float 0.562624254473
  29 => float 0.561630218688
  13 => float 0.559642147117
  97 => float 0.559642147117
  43 => float 0.557654075547
  39 => float 0.557654075547
  62 => float 0.557654075547
  90 => float 0.557654075547
АВТОРЕГРЕССИЯ ПО ДАРБИНУ

Контроль симметрии матрицы

Точная система (порядок 2):
1109.000 f0 + 588.000 f1 = -587.000
588.000 f0 + 1110.000 f1 = -597.000
Решение: f = [-0.339492, -0.357999]

Тёплицева система (порядок 2):
1108.000 f0 + 587.000 f1 = -587.000
587.000 f0 + 1108.000 f1 = -597.000
Решение: f = [-0.339666, -0.358859]

Порядок АР = 100, длина выборки = 2054, СКО выборки = 0.735304):
CKO: 
["001" => 0.617, "002" => 0.576, "003" => 0.556, "004" => 0.540, "005" => 0.531, "006"
=> 0.525, "007" => 0.522, "008" => 0.521, "009" => 0.521, 
"010" => 0.517, "011" => 0.515, "012" => 0.513, "013" => 0.513, "014" => 0.514, "015"
=> 0.514, "016" => 0.511, "017" => 0.512, "018" => 0.511, "019" => 0.511, "020" => 0.511, 
"021" => 0.513, "022" => 0.510, "023" => 0.508, "024" => 0.507, "025" => 0.507, "026"
=> 0.508, "027" => 0.510, "028" => 0.508, "029" => 0.508, "030" => 0.506, "031" => 0.508, 
"032" => 0.509, "033" => 0.511, "034" => 0.510, "035" => 0.510, "036" => 0.510, "037"
=> 0.508, "038" => 0.507, "039" => 0.507, "040" => 0.509, "041" => 0.509, "042" => 0.506, 
"043" => 0.509, "044" => 0.505, "045" => 0.508, "046" => 0.509, "047" => 0.508, "048"
=> 0.510, "049" => 0.510, "050" => 0.509, "051" => 0.508, "052" => 0.509, "053" => 0.505, 
"054" => 0.507, "055" => 0.513, "056" => 0.512, "057" => 0.508, "058" => 0.508, "059"
=> 0.507, "060" => 0.507, "061" => 0.508, "062" => 0.509, "063" => 0.505, "064" => 0.508, 
"065" => 0.505, "066" => 0.505, "067" => 0.509, "068" => 0.511, "069" => 0.511, "070"
=> 0.510, "071" => 0.511, "072" => 0.507, "073" => 0.511, "074" => 0.512, "075" => 0.514, 
"076" => 0.511, "077" => 0.510, "078" => 0.510, "079" => 0.509, "080" => 0.510, "081"
=> 0.506, "082" => 0.513, "083" => 0.513, "084" => 0.511, "085" => 0.512, "086" => 0.512, 
"087" => 0.511, "088" => 0.512, "089" => 0.516, "090" => 0.516, "091" => 0.512, "092"
=> 0.516, "093" => 0.512, "094" => 0.514, "095" => 0.515, "096" => 0.515, "097" => 0.515, 
"098" => 0.515, "099" => 0.513, "100" => 0.490, ]


Ответ 3


Эти данные полностью детерминированы алгоритмом работы системного планировщика задач
и запущенными процессами в данный момент. 

Очень возможно, что на основе долгого анализа потока этих бит, можно будет научиться
с высокой вероятностью предсказывать следующие биты.


Ответ 4


Похоже не совсем они случайны (но обязательно посмотрите update ниже).

Вместо долгих рассуждений о природе (псевдо)случайности и разных ее научных критериях
сыграем в простую "угадайку".

#include 

#define CHECK1(a) ((a) == '1' || (a) == '0')
#define CHECK(x,y) (CHECK1(x) && CHECK1(y))

int
main (int ac, char *av[])
{
  int chk = 0, tot = 0, guess= 0, r1 = 0, r2;

  while ((r2 = getchar()) != EOF) {
    tot++;
    if (CHECK(r1, r2)) {
      chk++; 
      if (r1 != r2)
        guess++;
      else
        guess--;
    } 
    r1 = r2;
  }

  return printf("I %s %d$ (tot: %d, chk: %d)\n", guess < 0 ? "LOSS" : "WIN", 
        guess > 0 ? guess: -guess, tot, chk) < 0;
}


Вот на исходных данных 

avp@avp-ubu1:hashcode$ ./a.out < rand.txt
I WIN 13$ (tot: 2055, chk: 2053)
avp@avp-ubu1:hashcode$ 


Мешал их (циклически переставляя нос с хвостом, разрезая в случайной(?) точке) несколько
раз и постоянно выигрывал...

Впрочем, поиграйте сами.

UPDATE

Для более "представительских" игр написал генератор '0' и '1':

#include 
#include 
#include 
#include 

int
main (int ac, char *av[])
{
  int rnd = av[1] && strcmp(av[1], "-r") == 0;
  if (rnd) {
    srand(time(0));
    av++;
  }
  int i, j, c, n = atoi(av[1] ? av[1] : "257");

  for (i = 0; i < n && ((c = (rnd ? rand() : getchar())) != EOF); i++)
    for (j = 0; j < 8; j++, c >>= 1)
      putchar('0' + (c & 1));

  return 0;
}


и погоняв его как с наборами, порождаемыми как -r 257, так и с 257

coding

Страницы

Поиск по вопросам

четверг, 12 декабря 2019 г.

Насколько случайны данные, сгенерированные таким образом?

Ответы

Ответ 1

Ответ 2

Ответ 3

Ответ 4

Комментариев нет:

Отправить комментарий

Страницы

Поиск по вопросам

четверг, 12 декабря 2019 г.

Насколько случайны данные, сгенерированные таким образом?

Ответы

Ответ 1

Ответ 2

Ответ 3

Ответ 4

Комментариев нет:

Отправить комментарий

четверг, 12 декабря 2019 г.