Доска Гальтона

[arseniiv]

vamoroz в сообщении #1125505 писал(а):

Есть решение, что при достаточно большом количестве рядов с гвоздиками можно получить равномерное распределение.
Имитационное моделирование данного процесса опровергло это решение.

Интересно знать, как оно это сделало. «Поставил 100500 рядов — гистограмма не плоская», сами понимаете, аргументом не будет. Как минимум потому что гистограмма моделирования даже по-настоящему равномерно распределённой величины нечасто будет плоской. Так что интересно, каково опровержение.

vamoroz в сообщении #1125505 писал(а):

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

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

Хоть бы на ideone вставили: http://ideone.com/0xaOgW.

[Евгений Машеров]

Прошу прощения, но ещё раз повторю. Доска Гальтона не научный, а демонстрационный прибор. Доказывать ею ничего нельзя, только иллюстрировать. Доказательство тут может быть только формально-математическим. Оно несложно.

[Александрович]

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

[tolstopuz]

vamoroz в сообщении #1122730 писал(а):

- количество падающих шаров 800

Возьмите хотя бы $10000$. При $800$ можно получить график любого вида, хоть двугорбый.

-- Ср май 25, 2016 17:19:26 --

Легкий способ это проверить:

1. Заходите на http://try.jupyter.org.
2. В правой части экрана выбираете New -> Python 3.
3. В появившееся окно вставляете следующий текст:

import matplotlib.pyplot as plt
%matplotlib inline
import random
n = 13
k = 21
m = 100000
def test():
    i = n // 2
    for _ in range(k):
        if i == 0:
            i += random.choice([0, 1])
        elif i == n - 1:
            i += random.choice([-1, 0])
        else:
            i += random.choice([-1, 0, 0, 1])
    return i
plt.hist([test() for _ in range(m)], bins=[x-0.5 for x in range(n+1)], normed=True)

4. Нажимаете Ctrl-Enter любое желаемое количество раз.
5. Меняете значения $n$, $k$ и $m$ и повторяете пункт 4.

[vamoroz]

Выражаю признательность всем участникам дискуссии.
Хочу особенно выделить информацию tolstopuz-а. Он не только выложил свой алгоритм моделирования, но и предоставил возможность каждому желающему провести по нему расчеты. Все рекомендации tolstopuz-а мною выполнены. В результате получено распределение, гистограмму которого для тех, кто по каким-то причинам не выполнил его рецепт, привожу ниже.

Данную статистику воспринимаю, как равномерное распределение (без учета двух крайних карманов).
Хочу отметить, что алгоритм, предложенный tolstopuz-ом не является моделью доски Гальтона. Согласно версии выложенного алгоритма, из крайних участков шарику случайным образом с вероятностью 0,5 предлагается выбрать свою траекторию движения.
Реальная доска Гальтона состоит из разного количества участков(тех, что между гвоздиками в одном ряду). Есть четные ряды гвоздиков и нечетные. В нечетном ряду участков на 1 больше. В реальной доске Гальтона шарик из крайних участков четного ряда выбирает траекторию движения с вероятностью 0,5. Из нечетного ряда он с вероятностью 1 скатывается в крайние участки четного ряда. Данное свойство доски Гальтона в модели не учтено.

[Александрович]

Вот однократная реализация доски Гальтона для 500 шаров, 9-ти рядов гвоздей и 7-ью ящиками.

[atlakatl]

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

[Александрович]

atlakatl в сообщении #1130509 писал(а):

Нормальная доска при 500 шарах должна быть гораздо гауссевее.

Это голословное утверждение. Попробуйте проверить гипотезу.

[arseniiv]

(Оффтоп)

Мне сегодня чрезвычайно повезло. Я накидал 100500 шариков в доску с 894 гвоздями и столькими же ящиками — и что вы думаете? — левый ящик мгновенно переполнился, а в остальные не попало ничего! Там даже образовался вакуум и затянул моё любимое одеяло, равномерно распределив его между этими остальными ящиками, так что теперь мне придётся жить без него.

То есть, вообще-то, не повезло.

[Александрович]

arseniiv, заслуженных участников редко банят за флуд, оффтопик и публикацию бессодержательных сообщений, так что развлекайтесь пока.

[svv]

Пора перейти от накопления реализаций к вычислению вероятностей. Вероятности уже обладают доказательной силой.

На левой картинке изображена доска Гальтона, которую я рассматриваю. Кружочки изображают гвоздики, кроме самого нижнего ряда — это ячейки (для простоты всё называю гвоздиками). Задача — найти вероятность попадания на каждый гвоздик. Я покажу правила, которые позволяют для доски небольших размеров сделать это вручную.

Средняя картинка. Из каждого гвоздика проводим линии вниз к тем гвоздикам, в которые из него может попасть шарик. Если вариантов два, линии синие, если один — линия красная.
Возле гвоздика, с которого начинается маршрут, пишем $1$. Далее правило такое: число у каждого гвоздика равно сумме чисел у его верхних соседей (из которых в него можно попасть), НО, если из верхнего соседа идёт красная линия, значение этого соседа берём с коэффициентом $2$. Например, во втором снизу ряду $28$ получается как $6\cdot 2+16$.

Правая картинка. Если в каком-то ряду все числа чётные, можно все разделить на 2. Если все делятся на 4 — можно все разделить на 4. И так далее. Но можно этого и не делать.

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

[arseniiv]

Ещё можно сделать хитрую вещь: поставить зеркала поверх крайних гвоздиков:

Все красные линии превращаются в синие! Более того, мы можем и сверху надобавлять гвоздей, но написать около них нули. Дальше мы можем чётные ряды сдвинуть на полшага относительно нечётных — и вот она перед нами, циклическая свёртка. Если в $n$-м ряду $m$ гвоздей подписаны числами $a_i$, то в $(n+1)$-м ряду они будут подписаны числами $a'_i$ такими, что

$$a'_i = a_i + a_{i+1}$$

(или $a_{i-1}$ для любителей вычитания), где сложение берётся по модулю $m$. Можно даже сразу нормализовать это всё, поделив на два. Получили простейший гауссов размыватель. Если применить его несколько раз, получим всё большее размытие. В пределе числа на гвоздях будут одинаковыми.

[tolstopuz]

vamoroz в сообщении #1130476 писал(а):

Реальная доска Гальтона состоит из разного количества участков(тех, что между гвоздиками в одном ряду). Есть четные ряды гвоздиков и нечетные. В нечетном ряду участков на 1 больше. В реальной доске Гальтона шарик из крайних участков четного ряда выбирает траекторию движения с вероятностью 0,5. Из нечетного ряда он с вероятностью 1 скатывается в крайние участки четного ряда.

Я считаю сразу два ряда - нечетный и следующий четный. Если шарик находится в крайнем участке нечетного ряда, то в следующем нечетном ряду с вероятностью $1/2$ он останется с краю и с вероятностью также $1/2$ сместится в соседний участок. Если же не в крайнем, то за два ряда с вероятностью $1/2$ он окажется строго ниже, а с вероятностями по $1/4$ - левее и правее.

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

[--mS--]

tolstopuz в сообщении #1130626 писал(а):

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

Так в любом случае геометрически быстрая, ибо ЦМ конечная.

[vamoroz]

Уважаемые участники дискуссии.
Хочу поблагодарить svv за прекрасные рисунки, которые наглядно иллюстрируют движение шарика по доске Гальтона.
С их помощью можно попытаться от «гвоздей», которые являются датчиками случайного передвижения шарика, перейти к «участкам между гвоздями».
Однако, цифры, которые приводит svv не совпали с моими. Для наглядного сравнения привожу два варианта



От рисунка перехожу к таблице



Черные квадратики в таблице соответствуют гвоздикам на рисунке.
Белые клетки таблицы соответствуют «участкам между гвоздиками».
Например, попасть на участок B6 можно только с участков A5 и С5.
Как заметил arseniiv, числа в данной таблице подчинены рекуррентному уравнению

$a(i,j) = a(i-1,j-1) + a(i+1,j-1)$

где j – номер строки , i – номер столбца.
У числа $a(i,j)$ есть физический смысл. Это количество вариантов попадания шарика на данный участок.
Количество вариантов попадания на участок возрастает, если участок приближается к центральному столбцу и убывает, если участок приближается к краю . В рассматриваемом примере значения в столбцах C и G значительно отличаются значения в столбце E. При желании вычисленные в таблице значения можно построчно просуммировать и вычислить вероятности попадания шарика в каждый участок на любом интересующем уровне доски.
Вычислить количество вариантов попадания шарика на участок, можно методом tolstopuz-а и считать сразу по «два ряда». Такой подход несколько усложнит расчет, но даст тот же результат. Можно еще усложнить задачу и считать по любому четному числу рядов.
По просьбе tolstopuz-а публикую матрицу переходов для его метода - расчета сразу по двум рядам, четному и нечетному.

$\lVert \ a_i_,_j \rVert =\left( \begin{array}{ccccc} 1 & 1 & 0 & 0 & 0 \\ 1 & 2 & 1 & 0 & 0\\ 0 & 1 & 2 & 1 & 0\\ 0 & 0 & 1 & 2 & 1\\ 0 & 0 & 0 & 1 & 1 \end{array} \right) $