От чего зависит корреляция в выпадении случайных чисел?

Question

[Web Lizard]

Короче, написал прогу на php. Вот ее код.

<?
$one = 0;
$two = 0;
for ($i=0; $i < 10000; $i++) { 
	$a = rand(1,2);
	if ($a == 1) {
		$one++;
	} else {
		$two++;
	}
}
echo "1:".$one." | 2: ".$two;
?>

Прога выводит какое количество раз выпала едеинца, а какое двойка.

Запустив эту прогу несколько десятков раз я заметил, что выпадают вот такие значения.

1:5082 | 2: 4918
1:5052 | 2: 4948
1:5033 | 2: 4967
1:4945 | 2: 5055
1:5010 | 2: 4990

То есть, корреляция никогда не превышает 100 едениц. Уже не говоря о том, что никогда не выпадает равное количество. Т.е. 5000 и 5000.

Но почему?? Почему не 400 едениц? Не 500 и не 600? Почему так ровно?
И почему если есть вероятность в 50% выпадения числа 1, то число 1 не может выпасть 100% раз?

Объясните пожалуйста.

Answer 1

[vasiliev]

То, что вы называете корреляцией, лучше назвать разбросом.

Распределение случайной величины "число появления единиц" описывается биномиальным распределением.

Математическое ожидание такой величины равно n*p, в вашем случае n=10000, p=0.5, получается в среднем единица будет появляться 5000 раз в серии из 10000 испытаний.

Разброс можно оценить, посчитав среднеквадратичное отклонение. Для биномиального распределения оно равно sqrt(n*p*(1-p)), для вашего случая получается 50. Правило трех сигм в данном случае должно действовать, поэтому с вероятностью 68% среднее значение величины "число появления единиц" будет отличаться от 5000 не более, чем на 50, и с вероятностью 99% не более, чем на 150. Это согласуется с числами, которые вы получили в вашем эксперименте.

Answer 2

[Денис Загаевский]

Всё это объясняется тем, что rand возвращает не случайное число, а псевдослучайное. в РНР реализован один из генераторов псевдослучайных чисел(ГПСЧ). А желаемое поведение свойственно настоящим случайным числам.
Простейший игрушечный ГПСЧ может выглядеть так

var next = 0;
for(;;){ 
    next = (next*9 + 3) % 256; 
}

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

Comments

[Денис Загаевский]

Антон: теоретически, может выпасть орёл много-много раз подряд. Результаты будут близки к 50/50. И что?

[Денис Загаевский]

Антон: нет, дело в гпсч. Монетка может выпасть 100 из 100 на одну сторону. Псевдослучайный генератор такого не даст.

[Денис Загаевский]

Антон: возможно, вихрь Мерсенна даст. Будет зависеть от инициализации. А монетка не будет зависеть ни от чего.