[Из песочницы] Вероятность того, что 2 шахтёра имеют одинаковый мир

Всем привет! Недавно меня заинтересовал вопрос: «может ли быть такое, что 2 игрока в Minecraft имеют один и тот же одиночный мир?»

Дело в том, что мир Minecraft генерируется случайным образом из заданного семени. Его можно задать вручную или получить казённый псевдослучайный. Стоит отметить, что одно и то же семя генерирует один и тот же мир.

Эта игра очень популярна, поэтому напрямую опросить всех игроков и сравнить их одиночные миры не представляется возможным. Однако, мы всегда можем посчитать вероятность этого события. Казалось бы: всё, что нам нужно — это посчитать количество элементарных исходов, удовлетворяющих данному событию, и поделить на множество всех элементарных исходов. К сожалению, это весьма нетривиальная задача, поэтому я вспомнил про «Парадокс дней рождения».

Сам парадокс заключается в том, что в группе из 23 человек с вероятностью 50% у двух людей совпадает день рождения. Очевидно, что задача похожа на нашу. Как же она была решена? Очень просто: оказалось, что посчитать вероятность того, что у каждого человека в группе уникальный день рождения намного проще. Для этого нужно взять одного человека и запомнить его день рождения, затем взять второго, причём вероятность того, что его день не совпадает с первым будет равна

$\$\$display\$\$p\_2=1-frac\{1\}\{365\}\$\$display\$\$$

Т.е. 100% минус вероятность, того, что их день рождения совпадает. Берём третьего и считаем вероятность того, что его день рождения не совпадает с двумя предыдущими

$\$\$display\$\$p\_3=1-frac\{2\}\{365\}\$\$display\$\$$

И так далее до n-го человека

$\$\$display\$\$p\_n=frac\{n-1\}\{365\}\$\$display\$\$$

Тогда вероятность того, что не совпадёт ни у одного человека в группе

$\$\$display\$\$p\; =\; 1*(1-frac\{1\}\{365\})*(1-frac\{2\}\{365\})*\dots *(1-frac\{n-1\}\{365\})\$\$display\$\$$

А вероятность того, что хотя бы у 2 совпадает

$\$\$display\$\$p\_\{искомое\}=1-p\$\$display\$\$$

Осталось только применить это решение для нашего случая. В Minecraft всего 2^64 возможных семян, а игроков около двухсот миллионов. Таким образом, наша формула будет выглядеть

$\$\$display\$\$p\; =\; 1*(1-frac\{1\}\{2^\{64\}\})*(1-frac\{2\}\{2^\{64\}\})*\dots *(1-frac\{2*10^8\}\{2^\{64\}\})\$\$display\$\$$

Вручную это считать весьма трудоёмко, поэтому я написал небольшую программу на языке Python 3, которая сделала это вместо меня.

Если кому-то интересно — вот код программы, но он очень простой.

a = 2**64 n = 200000000 p = 1  for i in range(n):     p *= (1 - i/a)  print('Chance that 2 players of minecraft have the same seed: ' + str((1-p)*100) + '%')

Получилось 0.1%, что, кстати, довольно много, учитывая количество возможных семян.

Спасибо за внимание!

Ссылки:

Парадокс дней рождения
Сколько людей играют в Minecraft
Сколько семян в Minecraft