Странные результаты у Mersenne-Twister prng

gvkonder

Кто-нибудь может сказать, почему в результате выполнения
<?php
//настройки. $count - количество итераций, $start и $end - диапазон, в котором генерируются случайные числа
$start=1; $end=5; $count=625000;

//отладочный массив - просто генерируем случайные числа; после цикла
// в счётчиках $acc_debug - количество выпаданий конкретного числа
$acc_debug=array; for($i=$start;$i<=$end;$i++) $acc_debug[$i]=0; //заполняем $acc_debug нулями
for($i=0;$i<$count;$i++) { //цикл - $count генераций случайного числа
$acc_debug[mt_rand($start,$end)]++; //увеличиваем счётчик
}
$acc=array; for($i=$start;$i<=$end;$i++) $acc[$i]=0;

//массив, полученный более хитрым способом - предположим, что автор кода
// ошибся, и не вынес генерацию случайного числа за пределы цикла
for($i=0;$i<$count;$i++) {
for($j=0;$j<=mt_rand($start,$end);$j++) { //тот самый ошибочный цикл
}
$j--; //смотрим, когда нас оттуда выкинули...
$acc[$j]++; //...и увеличиваем соответствующий счётчик
}

//такой же массив, что и два предыдущих - только вместо количества выпаданий
// конкретного числа тут будет храниться вероятность выпадения этого числа
// во втором цикле, посчитанная по формуле, приведённой ниже
$real=array;
for($i=$start;$i<=$end;$i++) {
$real[$i]=($i-$start+1)/($end-$start+1);
for($j=($end-$start);$j>($end-$i);$j--) {
$real[$i]*=$j/($end-$start+1);
}
//считаем по формуле p(k)n-1)/n)*n-2)/n)*n-3)/n)*...*n-k+1)/n)*(k/n)
// где n - количество возможных значений (это $end-$start+1
// k - число от 1 до n, вероятность выпадения которого нужно установить
// (оно равно $i-$start+1)
}

//считаем среднеквадратичное отклонение от нормы для первого варианта
$deviation1=0;
for($i=$start;$i<=$end;$i++) {
//$deviation - отклонение от стандартного значения.
//Стандартное значение для первого массива равно $count/n=$count/($end-$start+1)
$deviation=($count/($end-$start+1-$acc_debug[$i];
$deviation1+=($deviation*$deviation);
}
//нормируем по $count и количеству счётчиков
$deviation1=sqrt($deviation1)/($count*($end-$start+1;

//...и для второго
$deviation2=0;
for($i=$start;$i<=$end;$i++) {
//здесь стандартное значение - $count*$real[$i] ($real[$i] - стандартная вероятность)
$deviation=$count*$real[$i]-$acc[$i];
$deviation2+=($deviation*$deviation);
}
$deviation2=sqrt($deviation2)/($count*($end-$start+1;

echo $deviation1."\r\n".$deviation2."\r\n\r\n";
?>

$deviation1 в среднем в полтора раза больше, чем $deviation2?

Sanych

$deviation1 в среднем в полтора раза больше, чем $deviation2?
Не должно быть такого. Оба значения должны сильно меняться от запуска к запуску. И в каком тогда смысле в одно в полтора раза больше другого?
PS. Если я правильно посчитал, при данных параметрах мат.ожидания сравниваемых сумм квадратов отличаются на 7%, а это никак не заявленные 1.5раза для корней.

gvkonder

Оба значения должны сильно меняться от запуска к запуску. И в каком тогда смысле в одно в полтора раза больше другого?
Меняются не очень сильно, раза в два.
Больше в таком странном смысле - почти при каждом запуске наблюдается такое отличие...

Sanych

Может просто приведёшь значений по 30, можно ведь вывод в файл записать? Заодно и по порядку величины можно будет их проверить. А вообще все это очень и очень странно .

gvkonder

Ну вот сколько-то:
0.00029442121662679
0.00014385557201582

0.00030964592940971
0.00012429353643693

0.00016041226885747
9.4057140079854E-005

0.00018074307068322
0.00017598254458894

0.00028921096521398
0.00028785880983565

0.00025092571012154
0.00031074026710421

0.00025985379273738
0.00019608664207436

0.00014099404810133
0.00012151828833553

9.3248021962933E-005
0.00013221926032163

0.00014174735835281
8.8123840134211E-005

0.00023841352981742
0.00015837058312704

0.00026175256713163
0.00016949007758567

0.00019241129280788
0.00040324647351218

0.00023382958580984
7.1365022244796E-005

0.00047992148691219
0.00011744305173147

0.00025839083575081
0.00023019768895452

0.00033538228933562
0.00017817248272391

gvkonder

О, вообще жесть
function rand_vals(array $vals,$rand_count=false) {
if(!$rand_count) {
return $vals[array_rand($vals)];
} else {
$rand=mt_rand(1,count($vals;
$rand_keys=array_rand($vals,$rand);
if($rand==1) $rand_keys=array($rand_keys);
$rand_vals=array;
foreach($rand_keys as $key) $rand_vals[]=$vals[$key];
return $rand_vals;
}
}

function fakeDescription { return implode(' ',self::rand_vals(explode(' ','В области программирования для Сети PHP — один из популярнейших скриптовых языков наряду с JSP Perl и языками используемыми в ASP благодаря своей простоте скорости выполнения богатой функциональности и распространению исходных кодов на основе лицензии PHP PHP отличается наличием ядра и подключаемых модулей расширений для работы с базами данных сокетами динамической графикой криптографическими библиотеками документами формата PDF Любой желающий может разработать своё собственное расширение и подключить его Существуют сотни расширений однако в стандартную поставку входит лишь несколько десятков хорошо зарекомендовавших себя Интерпретатор PHP подключается к веб-серверу либо через модуль созданный специально для этого сервера например для Apache или IIS либо в качестве CGI-приложения'true; }
Результат:
В области программирования для PHP — один популярнейших языков наряду JSP Perl и языками используемыми в ASP своей простоте выполнения функциональности и распространению исходных основе лицензии PHP наличием ядра подключаемых базами данных сокетами динамической графикой криптографическими Любой может разработать собственное и подключить его сотни расширений стандартную входит лишь несколько хорошо зарекомендовавших себя к веб-серверу либо через для например Apache или
Что там было про миллион обезъян за печатными машинками?
Обычно оно вроде довольно нормально генерит...

Sanych

К сожаление, выборка гипотезу и не подтверждает, и не опровергает - слишком велик разброс. Отношение в полтора раза ничем не хуже других, почему бы и ему не попадаться время от времени. Переписав на C++ и сделав 300 итераций, посчитал разницу в 8% для среднего арифметического квадратов и 6% для среднего геометрического. Во второй раз -1,5% и 5%. В третий - 18% и 11,5%
Таким образом, в реализации на C полтора раза тоже не подтверждаются.
В общем, сдаюсь. Либо "эффекта полутора" не существует, либо я его не нашел, но похоже, что второе объясняется первым.
Оставить комментарий
Имя или ник:
Комментарий: