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

[vamoroz]

Рассмотрим случайное блуждание одного измерения с двумя экранами. Такой процесс традиционно представляется перемещением частицы вдоль прямой в форме серии шагов одинаковой длины, причем каждый шаг может быть совершен в одну или другую сторону с одинаковой вероятностью, равной 0,5. В результате описанного перемещения частица может достигнуть некого фиксированного положения, которое определим как экран. Различают два вида экранов
1. Отражающий экран. В этом случае частица, достигнув определенного положения, перемешается на следующем шаге с вероятностью равной единице.
2. Поглощающий экран. В этом случае частица, достигнув определенного положения, прекращает свое дальнейшее перемещение.
В темах «Доска Гальтона» (topic105812.html) и «Как распределятся падающие шарики» (topic111233.html) аналогичная задача рассматривалась с точки зрения случайного блуждания с отражающими экранами. В настоящей теме предложен алгоритм получения равновероятных траекторий, основанный на случайном блуждании с поглощающими экранами.

Не будем разделять экраны на отражающие и поглощающие, а факт попадания частицы на экран учтем следующим образом. Серию испытаний, приводящих к попаданию на экран, объявляем «неудачной» или «плохой». После того, как частица попала на экран, серию начатых испытаний прерываем и начинаем новую. Таким образом, в задаче определен старт частицы, левый и правый экран и бесконечное множество шагов, которые может совершить частица.
Рассматриваемый процесс можно наглядно продемонстрировать с помощью устройства, полученного из доски Гальтона. В качестве примера возьмем доску Гальтона на 11 накопителей. Она изображена на нижнем рисунке справа. Удалим из нее крайние гвоздики так, как показано на левом нижнем рисунке. В результате из 11-ти накопителей осталось всего 7, которые обозначим латинскими буквами. Падающие шарики распределяться неким образом по этим 7-ми накопителям. В накопителях Y и Z собираются шары, которые в процессе падения стукнулись с экранами. После того, как все имеющиеся в наличии шары брошены, шары, попавшие в накопители Y и Z, перебрасываются до тех пор, пока в них не останется ни одного шара. Бросая шары по такому правилу можно обеспечить равную вероятность всех траекторий падения шара.


С помощью горизонтальных и вертикальных линий условно разделим наше устройство на прямоугольные участки, которые обозначим двойной нумерацией. Столбцы обозначим латинскими буквами, а строки пронумеруем по порядку. В результате каждому прямоугольнику однозначно будет соответствовать пара значений, что-то вроде шахматной нумерации, с помощью которой будем отслеживать перемещение шарика. Например, такие события как
1. Бросок шарика на самый верхний гвоздь
2. Отскок шарика от верхнего гвоздя влево
можно записать как E1-D1. С помощью введенных обозначений можно отследить перемещение шарика до его попадания в накопитель. Назовем траекторией перемещения шарика ломаную линию, схематически фиксирующую перемещение шарика по обозначенным участкам. Одна из возможных траекторий перемещения шарика изображена синими стрелочками на левом рисунке. Траекторию также можно описать перечнем участков, на которые попадает шарик (E1-D2-C3-D4-C5-D6-C7-B8-C9-B10-C11). Каждой траектории можно поставить в соответствие некое число, - вероятность того что шарик поскачет именно по этой траектории. Так как у нас отскок вправо и влево от гвоздя имеет равную вероятность по условию и любые случаи касания экрана исключаются (при касании экрана шарик перебрасывается), то все траектории падения шарика равновероятны. По мере того, как шарик, случайным способом отскакивая от текущего гвоздика на каждом уровне, растет общее количество возможных траекторий, по которым он теоретически может перемещаться. На правом рисунке приведен подсчет этого количества траекторий на каждый участок, а также количество траекторий, приходящийся на каждый уровень устройства.

Например, попасть в самый левый накопитель, что нарисован на рисунке, шарик может 75-ю способами (75 траекторий заканчиваются на A11), а в центральный накопитель (участок E11) идут 250 траекторий. При бросании определенного количества шаров можно предположить, что в центральном накопителе окажется шаров больше, чем в крайнем.
Подсчитать количество траекторий $U$ на участок, определенный координатами $i,j$ ($i$ – номер ряда участка, где окажется шарик, а, $j$ – номер столбца участка), можно с помощью формулы

$$U(i,j)=U(i-1,j-1)+U(i-1,j+1) \eqno (1)$$

Здесь столбцы для удобства пронумерованы. Так как столбцы ранее были обозначены буквами латинского алфавита, то между буквенным и цифровым обозначением существует некоторое соответствие (A — 1,…, I — 9). j изменяется от 1 до L, которое также может быть сколь угодно большим. В случае, если$ j-1 <1$ и $j+1>L$, то $U(i-1, j-1)$ и $U(i-1, j+1)$ равны нулю.

Для возвратного уравнения (1) начальные условия могут быть любыми. Например, для случая с 5-ю накопителями начальные условия (0,0,1,0,0) соответствует варианту бросания одного шара из участка Е1. Начальные условия (1,1,1,1,1) соответствует случаю бросания 5-ти шаров, которые соответственно находятся на участках A1, C1, E1, G1, I1.

для 9-ти столбцов A,B,C,D,E,F,G,H,I и бросания шарика из участка E1,
количество траекторий на участки A и I равны $U(i,A) = U(i,I)$
количество траекторий на участки B и H равны $U(i,B)=U(i,H)$
количество траекторий на участки C и G равны $U(i,C)=U(i,G)$
количество траекторий на участки D и F равны $U(i,D)=U(i,F)$
Поэтому, систему из 9-ти возвратных уравнений типа (1) можно свести к системе из 5-ти возвратных уравнений

$$\begin{cases} U(i,B)=U(i-1,A)+U(i-1,C)\\ U(i,D)=U(i-1,C)+U(i-1,E)\\ U(i+1,A)=U(i-1,B)\\ U(i+1,C)=U(i,B)+U(i,D)\\ U(i+1,E)=2U(i,D) \end{cases}\eqno (2)$$

где $i$ четное, больше или равно 2.

Значения $U(i,B)$ и $U(i,D)$ в дальнешем не интересуют. Интересуют только значения $U(i,A)$, $U(i ,C)$ и $U(i ,E)$. Выразим $U(i,A)$, $U(i ,C)$ и $U(i ,E)$ как функции от $U(i-1,A), U(i-1 ,C)$ и $U(i-1 ,E)$. В результате система из 5-ти рекуррентных уравнений трансформируется в систему из трех рекуррентных уравнений.

Данные преобразования можно наглядно представить в виде следующих действий. Если из таблицы вариантов возможных траекторий убрать четные строки и столбцы B, D, F, H, то получается более компактная таблица

\begin{tabular}{|c| c || c | c | c | c |c |} \hline n& i & A & C & E & G & I \\ \hline 1 & 1 & 0 & 0 & 1 & 0 & 0 \\ \hline 2 & 3 & 0 & 1 & 2 & 1 & 0 \\ \hline 3 & 5 & 1 & 4 & 6 & 4 & 1 \\ \hline 4 & 7 & 5 & 15 & 20 & 15 & 5 \\ \hline 5 & 9& 20 & 55 & 70 & 55 & 20 \\ \hline 6 & 11& 75 & 200 & 250 & 200 & 75 \\ \hline \end{tabular}
Строки данной таблицы имеют двойную нумерацию. Это старая нумерация строк по $i$ и новая нумерация по $n$, которая в отличается тем, что идет по порядку. Этой таблице соответствует полученная ранее система из трех возвратных уравнений

$$\begin{cases} U_{n,A}=U_{n-1,C}+U_{n-1,A} \\ U_{n,C}=U_{n-1,A}+2U_{n-1,C}+U_{n-1,E}\\ U_{n,E}=2U_{n-1,E}+2U_{n-1,C} \\ \end{cases} \eqno (3)$$

$n =2, 3, 4, … $

Распишем первое уравнение данной системы для $n=2, 3, …$
$U_{2,A}=U_{1,C}+U_{1,A}$
$U_{3,A}=U_{2,C}+U_{2,A}$
$U_{4,A}=U_{3,C}+U_{3,A}$
...
$U_{n,A}=U_{n-1,C}+U_{n-1,A}$
...
Умножим первое уравнение на $S^2$, второе на $S^3$, $n$-е уравнение на$S^n$ . В результате получим
$S^2U_{2,A}=S^2U_{1,C}+S^2U_{1,A}$
$S^3U_{3,A}=S^3U_{2,C}+S^3U_{2,A}$
$S^4U_{4,A}=S^4U_{3,C}+S^4U_{3,A}$
...
$S^nU_{n,A}=S^nU_{n-1,C}+S^nU_{n-1,A}$
...
Просуммируем строки

$$\sum\limits _{n=2}^{\infty} {S^n U_{n,A}}=S\sum\limits _{n=1}^{\infty} {S^n U_{n,A}}+S\sum\limits _{n=1}^{\infty} {S^n U_{n,C}} \eqno (4)$$

К левой и правой части уравнения (4) прибавим нулевые значения, которые запишем в виде $S^0 U_{0,A} , S^1 U_{1,A}, S^1 S^0 U_{0,A}, S^1 S^0 U_{0,С}$. Это позволит уравнение (4) преобразовать к виду

$$\sum\limits _{n=0}^{\infty} {S^n U_{n,A}}=S\sum\limits _{n=0}^{\infty} {S^n U_{n,A}}+S\sum\limits _{n=0}^{\infty} {S^n U_{n,C}} \eqno (5)$$

Обозначим ряд
$S^0 U_{0,A}+S^1 U_{1,A}+S^2 U_{2,A}+ …+S^n U_{n,A}+\cdot \cdot \cdot = A(S)$
$S^0 U_{0,C}+S^1 U_{1,C}+S^2 U_{2,C}+ …+S^n U_{n,C}+\cdot \cdot \cdot = C(S)$
В результате получаем
$A(S)=S A(S)+ S C(S)$
Аналогичные действия произведем со вторым и третьим рекуррентными уравнениями системы. В результате получим
$C(S)=S A(S)+ 2S C(S)+ S E(S)$
$E(s)=2S C(S)+ 2S E(S)+1$
где
$ E(S)=S^0 U_{0,E}+S^1 U_{1,E}+S^2 U_{2,E}+ …+S^n U_{n,E}+\cdot \cdot \cdot $
В результате проведенных манипуляций система возвратных уравнений превратилась в систему алгебраических уравнений от производящих функций $A(S),C(S),E(S)$

$$\begin{cases} (S-1)A(S) +\hphantom{(2-1)} SC(S) \hphantom{+ (2S-1)E(S)S } =\hphantom{-}0 \\ \hphantom{S-S} S A(S) + (2S-1) C(S)+ \hphantom{(21 S-)}S E(S)=\hphantom{-}0\\ \hphantom{(S-1)A(S)+(2S-)} 2S C(S)+ (2S-1)E(S)= -1\\ \end{cases}\eqno (6) $$

с главным определителем системы равным $-5S^2+ 5S-1$, что позволяет написать единое возвратное уравнение

$$U(n) = 5U(n-1)- 5U(n-2) \eqno (7)$$

для столбцов А, C, E, с начальными значениями по строкам таблицы с номерами 2 и 3 (новая нумерация по $n$). Здесь $n$ – номер ряда, на котором можно расположить накопитель.
Например,
$U_{n=4}=5U_{n=3}-5U_{n=2}$
Для столбца А и I это $5 \cdot 1-5 \cdot 0=5$
Для столбца С и G это $5 \cdot 4-5 \cdot 1=15$
Для столбца Е это $5 \cdot 6-5 \cdot 2=20$

Для определения общего члена возвратной последовательности в зависимости от $n$, вычислим корни характеристического многочлена

$$x_1=\frac {5+\sqrt 5} 2 , x_2=\frac {5-\sqrt 5} 2 \eqno (8)$$

а каждый член исследуемых последовательностей представим как

$$U_i,_n=a_i,_1 (\frac {5+\sqrt 5 } 2 )^n + a_i,_2( \frac {5-\sqrt 5} 2)^n \eqno (9)$$

Определим коэффициент при большем корне $a_j,_1$ для каждой рассматриваемой последовательности. Таких последовательностей всего четыре
1. Последовательность количества траекторий на крайние накопители(столбцы A и I)
2. Последовательность количества траекторий на накопители, соседствующие с крайними (столбцы C и G)
3. Последовательность количества траекторий на центральный накопитель (столбец E).
4. Последовательность общего количества траекторий на все накопители

$$a_1_,_1= \frac {\sqrt 5} 5 , a_2_,_1= \frac { 3\sqrt 5 +5} {10} , a_3_,_1= \frac {\sqrt 5+5} 5 , a_s_,_1= \frac {6\sqrt 5+10} 5$$

Предельную вероятность попадания в каждый накопитель определим как

$$P_j=\lim \limits_{n \to \infty} \frac {U_j_,_n} {U_s_,_n }$$

Получились следующие значения

$$P_1=P_5=\frac {3-\sqrt 5} 8 , P_2=P_4=\frac 1 4 , P_3=\frac {\sqrt 5-1} 4$$

которые в совокупности составляют распределение типа «симметричный холмик. Полученный результат имеет место для случая, когда накопителей всего пять. Можно увеличить число накопителей. В результате получается некое семейство симметричных распределений с явным «горбом» посередине. Единственное, что можно сказать, - это не биномиальное распределение. Для наглядности, приведем сравнение полученного распределения с биномиальным в виде гистограммы.

При желании можно попытаться перейти к непрерывному распределению. Для этого необходимо фиксированный отрезок разбить на бесконечное множество участков, и для каждого отрезка определить необходимую вероятность. Полученное распределение по форме напоминает нормальное, но это не нормальное распределение, так как у него нет «хвостов». Если описано известное распределение, то было бы любопытно узнать, как оно называется.

[GAA]

Тема возвращена из Карантина.
У меня получилось такое же предельное условное распределение.

(начальные условия для рекуррентного уравнения)

В качестве начальных условий для рекуррентного уравнения $u_{n+2, k} - 5 u_{n+1, k} + 5u_{n, k}=0$ [для столбцов A ($k = 1$), C ($k = 2$), E ($k = 3$)] брались значения с $i=3$, $(n=2)$ и $i=5$ $(n=3)$:
для столбца (A) $u_{2, 1} = 0$, $u_{3, 1} = 1$;
для столбца (Б) $u_{2, 2} = 1$, $u_{3, 2} = 4$;
для столбца (С) $u_{2, 3} = 2$, $u_{3, 3} = 6$.

$$p_k = \lim_{n \to \infty} \frac {u_{n,k}} {\sum_{k=1}^5 u_{n, k}}$$

$k$ пробегает значения 1, 2, 3, 4, 5.

К сожалению, специальное название для этого распределения мне не известно.

Поскольку эта тема является продолжением темы «Доска Гальтона», через некоторое время ветки будут объединены.

[vamoroz]

Возможно, в стартовом сообщении распределение описано не очень наглядно.
Поэтому в одинаковом масштабе даю цветные гистограммы данного распределения для n=5, 7, 9
и накладываю отдельные гистограммы друг на друга.

[Лукомор]

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

Поэтому в одинаковом масштабе даю цветные гистограммы данного распределения для n=5, 7, 9
и накладываю отдельные гистограммы друг на друга.

"В одинаковом масштабе" - это если бы у Вас ширина каждого столбца была одинаковая...