Комбинаторные штучки

[EtCetera]

arseniiv в сообщении #375024 писал(а):

но ведь это только в данном!

Далеко не только в данном! Но, конечно, способ универсальным назвать нельзя. Тем не менее, Ш. Холмс им как-то пользовался и не сильно жаловался.

[arseniiv]

Снова возникла рекуррентность!

$$\left\{ \begin{array}{l} P_{n, 0} = 0 \\ P_{1, 0} = 1 \\ P_{n, i + 1} = \sum_{k \in \mathbb N} {P_{k, i} \binom{k}{n - k} p^{n - k} (1 - p)^{2k - n}} \end{array} \right.$$

Подскажите, как её разрешить.

А появилась она в задаче про клетки. Пусть в баночке живёт одна клетка. При наступлении каждого следующего момента времени каждая клетка в банке делится на две с вероятностью $p$ и не делится с вероятностью $1 - p$. Получится, что после наступления $i$-ого момента времени вероятность найти в банке $n$ клеток как раз $P_{n, i}$, если ничего не напутал.

(Оффтоп)

Ой, пока писал, родилась задача пострашнее (эта-то должна, наверно, быть простой?) — каждая клетка превращается в $m \ne 0$ клеток с вероятностью $2^{-m}$. Тут должен быть более красивый график у плотности распределения [количества клеток], плавно уходящий в бесконечность. Кстати, такое дискретное распределение случайно не будет чем-то похоже на распределение Максвелла?

[svv]

arseniiv, в обеих Ваших задачах -- с карточками и с клетками -- явно просматривается общий момент. А именно, задача определяется некоторой матрицей вероятностей переходов, назовем её $A$. Каждый её элемент $a_{kn}$ – это вероятность того, что $k$ объектов (карточек, клеток) после очередного хода превратятся точно в $n$ объектов.

В Ваших задачах матрица $A=\{a_{kn}\}$ обладает такими свойствами:
1) Она бесконечна: $k=1..\infty, n=1..\infty$.
2) Она верхнетреугольна (количество объектов не может уменьшаться).
3) Элементы не зависят от номера хода. Мне кажется, с точки зрения какой-нибудь высокой теории это большое упрощение (типа отсутствия явной зависимости уравнения движения от времени).

В задаче с карточками $a_{k,k} = (k-1)/k$, $a_{k,k+1} = 1/k$, остальные равны нулю. Двухдиагональная матрица.
В задаче с клетками $a_{k,n} = \binom{k}{n - k} p^{n - k} (1 - p)^{2k - n}$, $k \leqslant n \leqslant 2k$, остальные равны нулю.

Справедлива рекуррентная формула: $P_{n, i + 1} = \sum_{k \leqslant n} {P_{k, i} a_{k, n}$. К сожалению, она не очень-то помогает найти явную формулу, зато незаменима, если надо быстро вычислить вероятности с помощью компьютера.

Кстати, для задачи с карточками явную формулу удалось-таки найти, видели?

[arseniiv]

Ой, не увидел раньше. Потрясающе!

Да, заметил, что задачи похожи, но про матрицу не сообразил.

Надо будет ещё найти рекуррентность для модификации второй задачи.

[svv]

У меня для "страшного" варианта второй задачи получилось:

(Оффтоп)

Вероятность превращения $k$ клеточек в $n$:

$$a_{k, n}=\binom {n-1} {k-1} 2^{-n}$$

И отсюда рекуррентность:

$$P_{n, i + 1} = 2^{-n}\sum_{k=1}^n {P_{k, i} \binom {n-1} {k-1}$$

Похоже?

[arseniiv]

Мне кажется, вы правы, хотя пока не вникну.

[svv]

"$k$ клеток превращаются после очередного хода в $n$ клеток" - такое может произойти различными взаимоисключающими способами.

Вероятность такого превращения в каждом из конкретных способов ($1$-я клетка превратилась в $n_1$ клеток, $2$-я в $n_2$ и т.д., причем $\sum_j n_j = n$) равна $\prod_j 2^{-n_j}=2^{-n}$.

Удивительно, что вероятность каждого способа одна и та же. Это все из-за формулы $2^{-m}$. Ваш выбор -- гениальный. Представьте, что клеточка рождает потомков не мгновенно, а последовательно, хоть и очень быстро (за наносекунду ). Тогда в этом микропроцессе вероятность того, что у клетки появится еще хотя бы один потомок, равна $1/2$ и не зависит от уже имеющегося количества потомков. Этот процесс можно промоделировать с помощью монетки. Решка -- остается только исходная клетка. Орел -- добавляется еще один потомок. И так далее до первого выпадения решки. Тогда и получится, что после серии бросаний из одной клеточки будет $m$ клеточек с вероятностью $2^{-m}$. Монетка, как известно, предыстории не помнит. Так и при последовательном распределении рождений между клетками-предками на очередном ходу клетки не помнят, сколько у кого уже есть потомков, и принимают каждого следующего потомка с равной вероятностью, поэтому важно только общее количество рождений.

Раз для превращения $k$ в $n$ вероятность каждого способа $2^{-n}$, остается только умножить её на количество различных способов. А их столько, сколько существует вариантов распределить $n-k$ рождений между $k$ предками. Это в точности количество сочетаний с повторениями из $k$ по $n-k$:

$$\binom {k+(n-k)-1} {n-k}=\binom {n-1} {n-k}=\binom {n-1} {k-1}$$

[arseniiv]

Редко у меня интуиция работает! Как знал, что надо выбрать $2^{-m}$. Тут больше сыграло то, что это самая простая форма из тех, которые бы дали возможность зарождения сколь угодно большого количества клеток без всяких махинаций. Например, ряд из $3^{-m}$ сходится лишь к $1/2$, пришлось бы умножать его на $2$, а тут всё и атк готово.

Спасибо за интересное объяснение!

[svv]

И, мне кажется, Вы еще здорово сделали, что допустили вариант, когда клетка вообще не порождает потомков, только сама и остается. То есть что $m \geqslant 1$ в $2^{-m}$ -- это не количество добавившихся клеточек, а вместе с родителем. Это как-то красивее и фундаментальнее. Бик якшы.

[arseniiv]

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

[svv]

Хотел поделиться с Вами впечатлениями от созерцания рекуррентной формулы $p_{n, i + 1} = \sum_k {p_{k, i} a_{k, n}$. Она справедлива для целого класса аналогичных задач.

Когда я вводил матрицу $A$, надо было индексы вводить наоборот -- так более естественно. Второй индекс, нумерующий столбцы, обычно "входной" (так как по нему матрица сворачивается со стоящим справа вектором-воздействием), а первый индекс - "выходной", общий с индексом вектора-результата. Если исправить эту идейную ошибку и записать в "тензорных" обозначениях, получим:

$$p^n_{(i + 1)} = a^n_k {p^k_{( i)} }$$

Понимать это предлагается так: имеется последовательность векторов $\mathbf{p}_{(i)}$. Индекс в скобках -- не тензорный (и потому в скобках), он просто нумерует вектор в последовательности. Все остальные индексы надо рассматривать как обычные контра- и ковариантные. Знак суммы опущен по соглашению Эйнштейна о суммировании. Тензор $\mathbf{A}=\{a^n_k\}$ типа $(1, 1)$ (аффинор) является линейным оператором, преобразующим вектор $\mathbf{p}_{(i)}=\{p^k_{(i)}\}$ в вектор $\mathbf{p}_{(i+1)}$. Вышеприведенная формула -- просто запись в компонентах. Если же в безындексной форме, то --

$$\mathbf{p}_{(i+1)}=\mathbf{A} \mathbf{p}_{(i)}.$$

И вот, представьте, у нас есть начальный вектор $\mathbf{p}_{(0)}$ в бесконечномерном пространстве. Его компоненты равны: первая -- $1$, остальные $0$. Это детерминированное состояние. Хотя вовсе не обязательно начинать именно с такого. А дальше с каждым ходом линейный оператор начинает этот вектор в нашем пространстве поворачивать, благодаря чему его компоненты как-то меняются. Знание оператора позволяет рассчитать, как изменится после очередного хода (или, возведя его в степень -- после нескольких ходов) состояние с любым распределением вероятностей.

Дальше, сумма компонент любого нашего вектора равна 1. Хочется эту сумму назвать нормой. Так как в наших примерах норма сохраняется, я назвал активное преобразование вращением. Красота!

[arseniiv]

Интересно, что вращение теми тремя $\mathbf A$, которые в «моих» задачах, никогда не «зациклится». (Интересно, есть ли такие вращения, тензор которых всегда представим матрицей, содержащей бесконечное количество ненулевых элементов, которые имеют период?) А у преобразования, задаваемого тензором $\mathbf A$, есть неподвижная точка или мне кажется? Точнее, для первой задачи, наверно, нет, а вот для второй, как вам кажется? Наверно, это равносильно тому, что существует предел $\mathbf A^n$ при $n \to \infty$? Хотя, конечно, факт того, что вращение с помощью этого тензора куда-нибудь в конечном счёте приводит или не приводит, вряд ли поможет найти замкнутое выражение для $\mathbf A^i \mathbf p_{(0)}$.

[svv]

Да, интересные вопросы. Но, похоже, для задач, аналогичных нашим, ответ на все эти вопросы -- "нет". Я изложу свои интуитивные соображения, а Вы, возможно, их подтвердите более аккуратно или опровергнете.

Ключ к решению этих вопросов -- это математическое ожидание. (Не случайно Вы им интересовались в самом начале, всё в мире взаимосвязано.) Наша матрица теперь, после исправительного транспонирования, будет нижнетреугольной. Класс таких матриц замкнут относительно умножения (и, стало быть, возведения в степень). Нижнетреугольность выражает тот факт, что после одного или нескольких ходов количество объектов не убывает (вероятность перехода 42 клеточек в 27 равна нулю). Измерения нашего пространства (и тем самым компоненты векторов) упорядочены по естественному признаку - им соответствует количество объектов. Так вот, все это заставляет произвольное распределение необратимо сползать под действием оператора в направлении увеличения количества объектов. Мне кажется, можно доказать в случае нижнетреугольности, что критерий этого сползания -- математическое ожидание -- строго растет при действии оператора. А тогда -- "покой нам только снится".

Итак, тезис: если $a^n_k=0$ при $n<k$, и $E\mathbf{p}=\sum_k k p^{k \text{(это индекс)}}$, то $E\mathbf{A}\mathbf{p}}>E\mathbf{p}}$.

[svv]

Всё просто.

$$E(\mathbf A \mathbf p)=\sum_{n,k} n a^n_k p^k =\sum_k \left\{p^k \sum_{n\geqslant k} n a^n_k \right\}>\sum_k \left\{p^k \sum_{n\geqslant k} k a^n_k \right\}=\sum_k \left\{k p^k \sum_{n\geqslant k} a^n_k \right\}=\sum_k k p^k =E\mathbf p$$

Комментарии.
a) В предпоследнем переходе использовано важное свойство матрицы $A$, о котором я забыл упомянуть: $\sum_n a^n_k=1$. Оно следует из того, что действие оператора на $k$-й базисный вектор (у которого $k$-я компонента равна $1$, остальные $0$) должно сохранять единичность "нормы".

b) Неравенство строгое -- с некоторыми натяжками. Я вижу два случая, когда оно превращается в равенство, то есть мат.ожидание остается прежним. Их надо иметь в виду как исключения:
Во-первых, когда оператор тождественный, т.е. $a^n_k=\delta^n_k$.
Во-вторых, когда вектор $p^k$ таков, что все его ненулевые компоненты приходятся на единичные элементы $a^n_k$. Пример: Пусть на каждом ходу количество клеток увеличивается на 1, если их хотя бы две. Но у нас одна клетка...

[arseniiv]

(Оффтоп)

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

Как думаете, можно ли найти рекуррентность для $S_{m, i} = \sum_{m = 0}^n {P_{m, i}}$? Тогда я бы попробовал вывести производящую функцию для неё, а потом замкнутый вид развернуть обратно и узнать его и для $P$. В текущем виде так ничего в голову и не пришло.