Без кейворда

Задача Uniform Plinko Генерация асимптотически равномерных распределений из плат Plinko. О Plinko Plinko - это азартная игра с доской, мячом и ведрами. Доска

Генерация асимптотически равномерных распределений из плат Plinko.

О Плинко

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

Большинство вариантов игры:

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

В действии

Несколько ярких примеров этой игры в действии:

    , «худший из» обзор фильмов, в котором просмотренные фильмы выбираются через Plinko. Этот вариант вызвал у меня интерес к проблеме; ни один рецензент не хочет брать на себя ответственность за выбор плохого фильма для просмотра (хотя один должен быть выбран). Плинко, как мы вскоре увидим, не является «справедливым» при условии, что исходная привязка. Поэтому рецензенты несут в некоторой степени личную ответственность за просмотренный фильм. Моя цель - полностью снять эту ответственность, сделав распределение выборки однородным. , потребительское игровое шоу. Их вариант интересен тем, что вычислить ожидания вручную и тем самым выбрать оптимальную стартовую привязку нетривиально.

Статистические свойства

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

На любой реальной доске Plinko, которую я наблюдал, вероятность пойти влево при любом колышке составляет приблизительно 0,5 (и 0,5 для правого дополнения). Это означает, что колышки можно рассматривать как испытания IID Бернулли, индуцирующие биномиальное распределение, определяющее последнее приземление ковша (путем суммирования количества падений влево / вправо). К сожалению, Plinko часто упоминается как демонстрация Центральной предельной теоремы (CLT). Это правда, но предполагать такую ​​прямоту - неискренне. Прямое распределение является биномиальным (n = глубина доски, p = 0,5), которое асимптотически аппроксимируется нормальным распределением через CLT (как линейная комбинация испытаний Бернулли IID) при больших n и n * p.

Вот асимптотика выхода из корзины для платы Plinko с ограниченной глубиной 10 при разделении 50/50:

И визуальное распределение:

Единая проблема Плинко

Большой! В скучном мире у нас биномиальное распределение. Можем ли мы сконструировать платы Plinko для других дистрибутивов? В частности, можем ли мы построить равномерное распределение для доски Plinko любой глубины?

Мысли

Некоторые мысли, относящиеся к этой проблеме:

  • Наш единственный рычаг контроля (для фиксированной глубины) - это вероятность, связанная с левым и правым падением.
    • Когда вероятности больше не равны 50/50, испытания Бернулли на каждом уровне доски перестают быть независимыми.
    • Настройка высокой вероятности на доске оказывает существенное влияние на результаты на более низких уровнях доски.
    • т.е. испытания Бернулли на пути остаются независимыми

    Подход

    Был выбран метод грубой силы и числовой:

    • Пройдите каждый начальный колышек ->путь ведра на доске Plinko
    • Для каждого пути создайте исполняемый продукт вероятностей на пути
    • Для каждого сегмента постройте исполняемое суммирование продуктов пути.

    На данный момент у нас есть система уравнений! То есть уравнение на ведро, где каждое уравнение равно равномерной плотности 1 / (1 + n). Например, плата глубины 2 с 3 узлами имеет следующую систему, где x_i - это вероятность падения влево для i-го узла, обозначенного 1. 3 сверху вниз, слева направо:

    В общем, эта система будет недоопределенной. Для доски глубины n существует n + 1 ведра, что приводит к n + 1 уравнениям n (n + 1) / 2 параметров. Итак, мы предпочитаем оптимизационный подход. Я решил определить функцию потерь для результатов ведра B_i как: (1 / (n + 1) - B_i) ^ 2, что является просто квадратом потерь при равномерной плотности. В зависимости от используемого метода численной оптимизации другие функции потерь могут быть более идеальными. Имея под рукой функцию потерь, все, что остается, - это применить оптимизатор на основе градиента. Я добился успеха с BFGS, ограничив пространство состояний до [0,1] (допустимые вероятности) для всех параметров.

    Решения

    Решения представлены только с правильной вероятностью падения; Вероятности левого падения просто выводятся как дополнение. Обратите внимание, что решения округлены до двух знаков после запятой для чистого рендеринга. Чтобы воспроизвести эти результаты и графику, см. Uniform_plinko.py.

    Глубина 3

    Глубина 5

    Глубина 10

    Используя приведенный выше код Python, вычисление этого решения заняло около 10 секунд.