nbvehbectw

Привет, пикабушники! Как вы, возможно, уже знаете, разработчики Пикабу в преддверии нового года запустили мини-игру, в которой надо кидаться друг в друга снежками. Игра забавная, но порождает довольно интересную математическую задачку - сколько в среднем очков можно получить за один снежок? Результат расчета довольно неожиданный, поэтому если не хотите читать выкладки, советую хотя бы просто пролистать пост почти в конец до жирного шрифта, которым написан ответ.

Хочу однако сразу заметить, что я оказался сам себе злобным буратиной, начав решать задачу и пилить пост до уточнения всех условий. Как оказалось, шансы попасть и промахнуться - не 50%, как я думал, а высчитываются более сложно. Поэтому давайте будем считать, что я решаю задачу не непосредственно для мини-игры, а свою собственную, которая, однако, близка к исходной и может быть использована для примерной оценки ее результата.

Итак, для начала посмотрим на правила. Каждый день нам дается 5 снежков, их можно запускать в других людей, оставляя комментарии. За каждый запущенный снежок с вероятностью 50% может произойти одно из следующих событий:

1. Промах - снежок потратится, и на этом все.

2. Попадание - снежок не тратится, нам дается 10 очков к общей сумме, и еще один дополнительный снежок.

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

Эти правила порождают дерево возможных вариантов для каждого снежка, которое приведено ниже. На нем черным цветом написано количество снежков ка каждом шаге, зеленым - количество полученных очков на каждом шаге. Стрелки показывают возможные варианты событий, синие дроби над ними - вероятности, с которыми может произойти каждый из вариантов.

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

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

Не буду приводить весь путь своих рассуждений о том, как выразить эту последовательность вероятностей в виде формулы, скажу сразу результат. Это последовательность C_n/2^(2n+1), где C_n - числа Каталана. То есть с вероятностью C_n/2^(2n+1) мы получаем 10n очков, где n⩾0. Тогда, чтобы посчитать среднее количество очков, которые можно получить за один снежок, нужно помножить количество очков на вероятность, с которой можно его получить, и просуммировать все такие произведения:

Проблема в том, что с числами Каталана я не был знаком до этого момента, и, насколько я могу судить, явная их формула слишком нетривиальна, чтобы ее можно было использовать для вычисления суммы этого ряда в явном виде. Однако на Википедии написана их асимптотика, которую можно использовать для оценки суммы:

Тогда сумму ряда можно оценить как:

А из курса матанализа известно, что вот такие ряды, где имеется n в знаменателе в какой-то степени, сходятся только тогда, когда n>1. Этот же ряд, расходится, или другими словами его сумма равна бесконечности.

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

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

Но на этом задачка не заканчивается, дальше еще интереснее. Как я писал выше, в оригинальной мини-игре шансы не 50/50, так давайте и мы рассмотрим разные вероятности. Пусть шанс промахнуться будет α, а шанс попасть - 1-α, где 0⩽α⩽1. Конечно, это тоже вряд ли в полной мере описывает реальные условия, там вероятности, скорее всего, вообще не фиксированы. Но для нашей модельной задачки рассмотреть это все равно будет интересно.

Этот пост, полагаю, уже вышел за рамки понимания среднестатистическим пикабушником, так что выкладок приведу еще меньше. Они в целом аналогичны выкладкам выше, так что кто желает, может проделать их самостоятельно, остальным это и не надо. Но результат меня поразил настолько, что я просто не могу им не поделиться. Вероятность получить 10n очков получилась равной C_n * (1-α)^n * α^(n +1). А со средним картина получается следующая:

1. При α⩾1/2 среднее количество очков получается конечным и равным 10(1-α)/(2α-1).

2. При α=1/2 игра заканчивается с вероятностью 1, и среднее количество очков получается равным бесконечности.

3. При α⩽1/2 с вероятностью (1-2α)/(1-α) игра будет продолжаться бесконечно и не завершится никогда. Среднее количество очков тогда также будет расти бесконечно.

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

За сим все, надеюсь, хоть кто-то дочитал и что-то понял. Кидайтесь снежками реальными или виртуальными, не болейте, с новым годом.

P.S. Для помощи в решении этой задачки я написал небольшую программку на C++ для вычисления вероятностей, код можете взять вот тут, если интересно  https://pastebin.com/RhJCzJ8u (кто будет ругаться на говнокод, тот бака)