Извращенная серия испытаний Бернулли для построения деревьев

[From]

Ломаю голову над противоречием, которое не могу уладить в голове.
Итак, как ясно из заглавия темы, я провожу некоторую серию испытаний Бернулли.

Для начала - описание процесса на пальцах. У меня есть некоторая точка. С некоторой вероятностью я позволяю ей стать плодотворной. Далее из этой точки с некоторой вероятностью я позволяю распуститься двум росткам (независимо). Тут уже возможны четыре варианта (думаю, ясно, какие). Из тех точек, к которым первой точке удалось выпустить ростки, я снова пытаюсь с некоторой вероятностью выпустить новые ростки. Так я продолжаю до тех пор, пока каждая из точек дерева не упустит все свои шансы.

Теперь более формально.
В принципе, последовательный рост дерева можно описать, как подбрасывание монеты несколько раз подряд. Вероятность успеха - $p$, как обычно. Соответственно, неуспеха - $(1-p)$ или, для краткости, $q$. Теперь зададим регламент испытаний, чтобы последовательность успехов/неуспехов (с некоторыми оговорками) однозначно давала нам дерево.
Будем считать, что ростки из точки распускаются по диагонали вверх: один влево, другой в право. Распускаем их так, чтобы абсолютно все точки, испущенные (сквозь сколь угодно длинную цепочку поколений) из более левой точки, располагались левее абсолютно всех точек, испущенных более правой точкой. То есть, так, как, например, располагаются дерево Штерна-Броко:
, -
только в нашем случае растут они вверх, а не вниз.

Теперь задаем регламент:
1. Берем самую левую точку уже имеющегося дерева, у которой не все шансы упущены. Если таких точек нет, завершаем последовательность.
2. Пробуем испустить левый росток подбрасыванием монеты;
если левый уже не может испуститься (в предыдущем испытании выпал неуспех), даем шанс правому.
3. Переходим к шагу 1.

Итак, у нас получится конечная последовательность $T = \{ p q p p q p q ... \}$, которая однозначно определяет дерево.

По поводу разрешенных последовательностей. Назовем количеством шансов сумму по всем точкам количеств возможностей испустить росток (представим, как из точки вырастает мертвый пунктир, когда она терпит неудачу).
Дальше.
Количество шансов равно $N_c = N_p - N_q + 1$
Дерево выращено, когда $N_c = 0$. Дерево имеет шанс вырасти еще, когда $N_c > 0$
Так как каждому выращенному дереву предшествует дерево, которое имеет шанс вырасти еще, то на окончательную последовательность $T_n = \{ x_1 x_2 ... x_n\}$ накладывается условие:
$\forall i<n, T_i = \{x_1 x_2 \dots x_i\} \Rightarrow N_p(T_i) > N_q(T_i) - 1$.
Соответственно, такая и только такая последовательность определит одно и только одно дерево. Обратно, любое дерево определяется какой-то последовательностью, и только ей.


Теперь к делу.

У нас определено пространство элементарных исходов, и сумма вероятностей всех различных деревьев должна быть равна единице. А именно:
$S = \sum\limits_{n=0}^{\infty}C_n p^n q^{n+1} = 1, \forall p\in[0,1)$,
где $C_n$ - количество деревьев с n точками.
Первый вопрос: так ли это? Да, мне уже понятно, что единица странным образом выпадает, и это меня настораживает.

Второй вопрос. Если это так, то одна вещь не дает мне покоя:
$pS = \sum\limits_{n=0}^{\infty}C_n {(pq)}^{n+1} = p$,
но с другой стороны:
$pS = \sum\limits_{n=0}^{\infty}C_n {(pq)}^{n+1} = q\sum\limits_{n=0}^{\infty}C_n q^n p^{n+1} = q$,
причем это должно работать для любого $p\in(0,1)$.

Один из моих вариантов ответа на этот вопрос: следует учитывать и бесконечные деревья, и в случае $p>0.5$ они имеют ненулевую вероятность в пространстве элементарных исходов.

Другой вопрос.
Я получил одно выражение для $C_n$ (с учетом своей догадки о том, что сумма $S$ равна единице только при $p<0.5$):
$C_n = 2^n \frac{(2n - 1)!!}{(n+1)!}$.
Для $n = 4$ оно дает $C_n = 14$, однако мне удается построить только 12 деревьев. Где может быть ошибка? Или тут с самого начала все неверно?

Спасибо.

-- 06.07.2016, 13:13 --

Так, со вторым вопросом я разобрался. Нашел недостающие деревья. Конкретно с этим пунктом помощь больше не нужна, спасибо.

[svv]

Уточните, пожалуйста, кое-какие моменты.

From в сообщении #1136108 писал(а):

У меня есть некоторая точка. С некоторой вероятностью я позволяю ей стать плодотворной.

Это сбило с толку, нигде ниже я не увидел подтверждений, что точке необходима ещё какая-то «валидация» или «фертилизация», помимо попытки вырастить из неё ростки.

Регламент вроде бы понятен, но мои выводы из этого описания не стыкуются с дальнейшим. Вы начинаете с одной точки. Чтобы с самого начала загубить дерево, надо получить две неудачи: $\{qq\}$. Первая неудача не даст вырасти левому ростку, вторая правому. Но у Вас последовательности с двумя $q$ и без $p$ запрещены.

Может, у Вас самое первое подбрасывание монетки определяет, будет ли вообще первая точка?

Вы перечислили три вопроса: первый, второй и другой. Похоже, Вы разобрались не со вторым, а с «другим», верно?

[From]

svv в сообщении #1136202 писал(а):

Уточните, пожалуйста, кое-какие моменты.

From в сообщении #1136108 писал(а):

У меня есть некоторая точка. С некоторой вероятностью я позволяю ей стать плодотворной.

Это сбило с толку, нигде ниже я не увидел подтверждений, что точке необходима ещё какая-то «валидация» или «фертилизация», помимо попытки вырастить из неё ростки.

Тот факт, что первой точке надо прорасти, выражается в том, что суммирование в $S$ начинается с нуля. Это отвечает дереву $\{q\}$

Таким образом отвечаю на следующее Ваше замечание:

svv в сообщении #1136202 писал(а):

Вы начинаете с одной точки. Чтобы с самого начала загубить дерево, надо получить две неудачи: $\{qq\}$. Первая неудача не даст вырасти левому ростку, вторая правому. Но у Вас последовательности с двумя $q$ и без $p$ запрещены.

Первая неудача не дает появиться начальной точке - получится пустое дерево.
Заглубленному на корню дереву без ростков отвечает последовательность $\{pqq\}$

Цитата:

Может, у Вас самое первое подбрасывание монетки определяет, будет ли вообще первая точка?

Ну, я туманно сказал об этом в "предисловии":

Цитата:

У меня есть некоторая точка. С некоторой вероятностью я позволяю ей стать плодотворной. Далее из этой точки с некоторой вероятностью я позволяю распуститься двум росткам (независимо).

Да, согласен, надо было уточнить это в регламенте. То есть что-то типа:
0. Если дерево пустое, то подбрасываем монетку, определяя возможность появления первой точки. Если дерево пустое и упустило возможность появиться, закончить последовательность. Если ни одно из этого, переходить к шагу 1.
...
...
3. Перейти к шагу 0.
Или же считать, что мы начинаем с дерева с одним шансом, но без точек.
Ну, это, в общем-то, уже немного преувеличенное причесывание. Но уточнение было нужно, согласен.

Цитата:

Вы перечислили три вопроса: первый, второй и другой. Похоже, Вы разобрались не со вторым, а с «другим», верно?

Да, да, именно))

[svv]

Спасибо, теперь с условиями всё понятно. Очень красивая задача. Соответствие, о котором Вы сказали, позволяет рассматривать вместо деревьев последовательности — это проще (во всяком случае, приятнее). Всё прозрачно: вначале у нас один шанс. Каждый успех увеличивает количество шансов на 1, каждая неудача — на 1 уменьшает. Когда шансов больше нет — game over.

From в сообщении #1136108 писал(а):

следует учитывать и бесконечные деревья, и в случае $p>0.5$ они имеют ненулевую вероятность в пространстве элементарных исходов

Да. Взгляните на эту задачу.

[From]

svv в сообщении #1136278 писал(а):

Спасибо, теперь с условиями всё понятно. Очень красивая задача. Соответствие, о котором Вы сказали, позволяет рассматривать вместо деревьев последовательности — это проще (во всяком случае, приятнее). Всё прозрачно: вначале у нас один шанс. Каждый успех увеличивает количество шансов на 1, каждая неудача — на 1 уменьшает. Когда шансов больше нет — game over.

From в сообщении #1136108 писал(а):

следует учитывать и бесконечные деревья, и в случае $p>0.5$ они имеют ненулевую вероятность в пространстве элементарных исходов

Да. Взгляните на эту задачу.

Вижу, что задача про кроликов очень похожа. Хотя в моем случае мы выпускаем ростки поочередно.

Теперь по поводу бесконечных деревьев. Их несчетное множество. Не могу сообразить, как описывать это по теории вероятностей. Я, конечно, знаю про непрерывные распределения и плотность вероятности. Но тут... тут что-то ни то, ни се. Есть ли идеи? Хотя мне известно, что при $p>0.5$ выполняется: $S = \frac{q}{p}$, то есть на долю бесконечных деревьев приходится $\frac{2p-1}{p}$.

В принципе, у меня есть желание попробовать обобщить это на случай k ростков. Правила будут абсолютно теми же, только в этом случае $N_q = (k-1)N_p + 1$. Также мне любопытно количество возможных деревьев с $n$ точек. Я его могу получить из $S$ путем представления $\dfrac{S}{q}$ рядом Тейлора относительно переменной $t = pq^{k-1}$ (Подозреваю, что $S=1$ при $p<\frac{1}{k}$) Выходит следующее:
$\sum\limits_{n=1}^{\infty}C_n t^n = \dfrac{1-q(t)}{q(t)}$,
где $q(t)$ - наибольший корень уравнения относительно $q$:
$q^{k}-q^{k-1}+t=0$

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


Вопрос № $\mathbb{S}$ (я уже давно сбился со счета)
Часто слышу о методе производящих функций, но плохо образован в этом отношении. Имею представление, но хотелось бы поосновательнее разобраться. Какую литературу порекомендуете?


Вопрос № $\mathbb{S}^{\mathbb{T}}$
С чего, вообще говоря, все начиналось.
Я хочу попытаться каким-то образом описать рост некоей "частицы" на прямоугольной сетке. Ну, еще можно взять шестиугольную сетку, либо кубическую, либо тетраэдрическую... ну, можно много чего придумать. Но пока поговорим про прямоугольную. Сначала я делал это, случайно заполняя "сито" из MxM клеток точками, а далее выбирая оттуда связные куски. Делал это, сочиняя алгоритмы для Matlab, выбирающие связные куски из случайно заполненной матрицы. Но это не так продуктивно.
Абсолютно эквивалентно будет начинать с того, чтобы давать шанс появиться точке. В случае успеха дать шанс четырем окружающим ее точкам. Далее мы сформируем "облако возможностей" вокруг успешных точек (как если бы мы обводили кораблик в морском бое пустыми точками, по которым нет смысла стрелять), которые находятся в непосредственной близости от имеющихся ("деревянный" подход тут уже не поможет, так как возможные точки для ростков будут перекрываться), и будем давать шанс каждой точке из "облака". И так далее мы продолжаем, пока частица не перестанет расти.
Ну что меня вообще интересует... Например, та вероятность $p$, при которой происходит "взрыв". То есть, так же, как в задаче с кроликами или деревьями, только теперь более сложные условия размножения. Или же средний размер частицы (решив задачу с размером, получим и порог "взрыва" для вероятности $p$). Или же вообще какая форма частицы предпочтительнее...
Есть ли какие-нибудь идеи на этот счет?

Ну а для чего я вообще всем этим занимаюсь?.. Как говорится, Just for lulz

[svv]

Дополнение к предыдущему ответу.

From в сообщении #1136108 писал(а):

Я получил одно выражение для $C_n$ (с учетом своей догадки о том, что сумма $S$ равна единице только при $p<0.5$):
$C_n = 2^n \frac{(2n - 1)!!}{(n+1)!}$.

Да, это числа Каталана. Одна из интерпретаций — $n$-е число Каталана равно количеству правильных скобочных последовательностей длины $2n$. Эта интерпретация легко связывается с Вашей задачей. Открывающей скобке соответствует успех, закрывающей неудача (плюс — у Вас всегда присутствует одна непарная закрывающая скобка в конце).

From в сообщении #1136339 писал(а):

Вижу, что задача про кроликов очень похожа. Хотя в моем случае мы выпускаем ростки поочередно.

Легко понять, что это не имеет значения. Вот вариант задачи про кроликов с последовательным размножением. Осенью каждый кролик либо отправляется в иной мир, либо продолжает существование. Решение принимается с помощью генератора случайных чисел, к которому выстраивается очередь кроликов. Если кролик остаётся, он на радостях тут же размножается. Далее — незачем ждать осени, описанный процесс можно организовать безостановочно. Так как для количества кроликов не имеет значения, какой именно кролик исчез или размножился, то и очередь кроликов не нужна, ГСЧ лишь последовательно решает: $+1$ или $-1$.

[svv]

Кстати, не рисуете ли Вы для себя граф состояний задачи, вроде такого?:

Здесь каждой точке соответствует состояние — определённое количество успехов (горизонтальная координата) и неудач (вертикальная). Начинаем всегда с синего кружка $(0,0)$. Успеху соответствует шаг вправо, неудаче — шаг вниз. Достижение красных кружков — конец игры. Конкретный маршрут движения соответствует дереву и последовательности (возможно, недостроенным). На картинке изображён законченный маршрут $\{pqppqpqqq\}$. Понятно, изображён не весь бесконечный граф, а только часть. Эта картинка будет полезнее, если кружочки заменить числами, равными вероятности попадания в них.

From в сообщении #1136339 писал(а):

Теперь по поводу бесконечных деревьев. Их несчетное множество. Не могу сообразить, как описывать это по теории вероятностей. Я, конечно, знаю про непрерывные распределения и плотность вероятности. Но тут... тут что-то ни то, ни се. Есть ли идеи?

Здесь надо сформулировать правильные вопросы. Вероятность каждого бесконечного маршрута равна нулю. Но нужна ли нам эта вероятность?

[svv]

From в сообщении #1136339 писал(а):

Часто слышу о методе производящих функций, но плохо образован в этом отношении. Имею представление, но хотелось бы поосновательнее разобраться. Какую литературу порекомендуете?

Риордан, Введение в комбинаторный анализ.

[From]

svv в сообщении #1136346 писал(а):

Дополнение к предыдущему ответу.
Да, это числа Каталана. Одна из интерпретаций — $n$-е число Каталана равно количеству правильных скобочных последовательностей длины $2n$. Эта интерпретация легко связывается с Вашей задачей. Открывающей скобке соответствует успех, закрывающей неудача (плюс — у Вас всегда присутствует одна непарная закрывающая скобка в конце).

Да, и впрямь!
Хех, а также: "Количество неизоморфных упорядоченных бинарных деревьев с корнем и n+1 листьями".

Цитата:

Кстати, не рисуете ли Вы для себя граф состояний задачи, вроде такого?:

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

Цитата:

Здесь надо сформулировать правильные вопросы. Вероятность каждого бесконечного маршрута равна нулю. Но нужна ли нам эта вероятность?

В принципе, не особо нужна. Но просто любопытно, как решать такие задачи в принципе.
Да, вероятность бесконечного маршрута равна нулю, но вероятность того, что маршрут будет бесконечным, ненулевая. Если мы сгруппируем бесконечные маршруты в классы, например, по количеству точек ветвления (то есть тех точек, из которых оба ростка удачно испущены), то вероятность того, что дерево попадет в некоторый класс, уже ненулевая. И еще должен быть еще класс с бесконечным числом точек ветвления. Но чтобы выразить вероятность какого-нибудь класса, нам придется записывать несчетную сумму, причем каждое слагаемое равно нулю - это нечто интегралоподобное. Тут у меня и возникает любопытство: как это вообще сделать?
Основной вопрос тут такой: можно ли связать с каждым бесконечным деревом какую-нибудь функцию, которая исчерпывающе описывала бы распределение деревьев по вероятностям? Да, для каждого дерева была бы нулевая вероятность, но функция позволяла бы рассчитать вероятность для любого интересующего класса деревьев.

Цитата:

Легко понять, что это не имеет значения. Вот вариант задачи про кроликов с последовательным размножением...

Гм, ну да... Правда, в таком подходе не так видна структура дерева. Хотя и по последовательсти из $+1$ и $-1$ можно всегда построить дерево...
Либо же можно ввести дополнительную опцию для кролика: порождать только одного потомка. И считать при этом, что умершие кролики остаются в истории, а далее интересоваться средним количеством кроликов в истории.

Цитата:

Риордан, Введение в комбинаторный анализ.

Спасибо!

[svv]

Хорошая книжка для начинающих:
С. К. Ландо. Лекции о производящих функциях.
Там некоторые пункты имеют прямое отношение к Вашей задаче, например, Числа Каталана, Треугольник Дика.

[From]

svv в сообщении #1136667 писал(а):

Хорошая книжка для начинающих:
С. К. Ландо. Лекции о производящих функциях.
Там некоторые пункты имеют прямое отношение к Вашей задаче, например, Числа Каталана, Треугольник Дика.

Спасибо большое!