Попытка задач

[svv]

arseniiv, если я Вас правильно понял, это эквивалентно Вашей задаче:

На табличке написано число $1$, затем на каждом шаге оно либо увеличивается на $1$, либо не меняется.
Правило изменения: если число сейчас равно $n$, то оно с вероятностью $1/n$ увеличится на $1$, а с вероятностью $(n-1)/n$ не изменится.

Найти вероятность, что после $i$-го шага число равно $k$. Каково мат.ожидание после $i$-го шага?

Правильно?

-- Чт окт 28, 2010 18:17:41 --

И, если это правильно, ещё одна эквивалентная переформулировка.

Имеется шкафчик с бесконечным количеством полок, каждая полка = емкость для сыпучего вещества (пусть это будет сахар).
В начале процесса имеется $1$ кг сахара на первой полке, а остальные полки пусты.
При каждом встряхивании шкафчика содержимое каждой полки частично остается на месте, а частично перепрыгивает на $1$ полку выше.
Более конкретно, из всего сахара $n$-й полки $1/n$ часть сахара попадает на $(n+1)$-ю полку, остальное остается на месте (но, понятно, к нему добавляется некоторое количество снизу).

Сколько сахара будет на каждой полке после $i$-го встряхивания? Какова высота (измеряемая в полках) центра тяжести сахара после $i$-го шага?

Ясно, что количество сахара $q_i^k$ (где $i$ - номер итерации, $k$ - номер полки) подчиняется простому правилу:

(Оффтоп)

$q_{i+1}^{k+1} = \frac{1}{k} q_i^k + \frac{k}{k+1} q_i^{k+1}$

[arseniiv]

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

Правильно?

Ага.

С сахаром что-то непонятное. Точнее, сейчас я не пойму. Может, потом дойдёт.

[svv]

(Оффтоп)

Кратко:
Номер полки $k$ - это количество карточек в коробке.
Количество сахара $q_i^k$ после $i$-й итерации на $k$-й полке - это в точности вероятность того, что после $i$-й итерации в коробке будет $k$ карточек.

Подробно:
Рассмотрим одну песчинку сахара. Ее поведение подчиняется вероятностному закону. После очередного встряхивания она с вероятностью $1/k$ взлетит на полку выше, а с вероятностью $(k-1)/k$ останется на той же полке. Это соответствует тому, что количество карточек в Вашей коробке с вероятностью 1/k увеличится, а с вероятностью $(k-1)/k$ останется прежним.

Сахаринок огромное количество, мы их не различаем. И поведение этой массы (если нас интересуют не отдельные песчинки, а килограммы) уже детерминированно. Там, где у одной песчинки есть два пути с вероятностями $p_1$ и $p_2$, мы видим для большого количества сахара $Q$ разделение на два количества $p_1 Q$ и $p_2 Q$. Здесь произведение (взятие какой-то части от количества) соответствует умножению вероятностей последовательных событий (например, с некоторой вероятностью имеем 5 карточек и умножаем на вероятность того, что добавим шестую).

А если одно количество сахара сливается с другим количеством (скажем, на 9-ю полку "досыпался" сахар снизу, с 8-й полки), это соответствует сложению вероятностей альтернативных путей, ведущих к одному результату - количеству карточек. То есть 9 карточек в коробке может быть и потому, что их только что было 8 и я вытащил пустую; и также потому, что их было 9 и я вытащил непустую.

Пути одной песчинки с полки на полку соответствует одна случайная реализация процесса Вашей игры. Сахара больше на тех полках, где больше вероятность попадания одной песчинки. Например, после $4$-й итерации на $5$-й полке будет совсем мало сахара - всего лишь $1/24$ кг. Это то количество, которое умудрялось подниматься вверх после каждого встряхивания. И это в точности вероятность того, что после $4$-й итерации в коробке будет $5$ карточек. Такое возможно только если $4$ раза подряд Вам попадалась пустая карточка, вероятность чего равна $\frac{1}{1} \frac{1}{2} \frac{1}{3} \frac{1}{4}= \frac{1}{24}$.

Наконец, общее количество сахара по всем полкам равно $1$ кг - это значит, что сумма вероятностей всех исходов (возможных количеств карточек) после любой итерации равна $1$.

Конечно, все это только рассуждения вокруг задачи, но еще не решение.

[arseniiv]

А, ну теперь понятно. Не в ту сторону думал.

[svv]

Прекрасно! И к рекуррентному соотношению $q_{i+1}^{k+1} = \frac{1}{k} q_i^k + \frac{k}{k+1} q_i^{k+1}$ комментарии тоже не нужны, всё понятно?

[arseniiv]

Ага (по крайней мере, кажется, что понятно).

Допустим, у нас получилась формула для $q_i^k$. Пусть случайная величина $X_i \colon \Omega_i \to \mathbb N$ — количество карточек на $i$-ом ходу. Попробую найти математическое ожидание, поправите, если что?
$EX_i = \sum_{\omega \in \Omega_i} {X_i(\omega) P(\omega)} = \sum_{k = 1}^{i + 1} {k q_i^k}$.

[arseniiv]

(Оффтоп)

(Если всё, конечно, правильно найдено.) По сравнению графиков весьма похоже, что $EX_i = O(\sqrt i)$.

[svv]

Да, всё правильно.

[arseniiv]

Осталось выразить $q_i^k$ в замкнутой форме. Читал-читал «Конкретную математику», с первого раза уже забыл, какие можно пытаться применить приёмы, чтобы что-то сделать с этой рекуррентностью.

-- Сб окт 30, 2010 19:04:57 --

Ну, если, конечно, такая, выражаемая через "приемлемые" функции, есть.

[svv]

Я опять немного изменю терминологию. Пустую карточку буду называть белой, а непустые черными, причем различать черные карточки не имеет смысла. В начале игры (на «нулевом» ходу) была одна белая карточка, а затем после каждого хода в коробку либо добавлялась $1$ черная карточка (если из коробки вынималась белая карточка), либо ничего не добавлялось (если из коробки вынималась черная). Значит, если после $i$ ходов имеется $k$ карточек, то белая карточка вынималась $m=k-1$ раз, а черная $n=i-k+1$ раз. Числа $m$ и $n$ для меня более удобны, и я буду ими пользоваться. Итак, ищется вероятность $p_n^m$ того, что при заданном количестве ходов белая карточка вынималась $m$ раз, а черная $n$ раз.

Вероятность $p_n^m$ равна сумме вероятностей всех различных взаимоисключающих вариантов-реализаций, при которых достигаются нужные $m$ и $n$. Эти варианты отличаются порядком вынимания $m$ белых и $n$ черных карточек. Например, пусть $m=4$, $n=7$. Тогда последовательность может быть такой:
$1$ белая, $2$ черных,
$1$ белая, –
$1$ белая, $3$ черных,
$1$ белая, $2$ черных.
В этом случае будем записывать: $(2, 0, 3, 2)$. Эта краткая запись полностью описывает некоторую реализацию: из записи видно, что $m=4$ (количество чисел), а $n=7$ (сумма чисел), и каждое число означает количество черных карточек, вынутых после очередной белой. Ясно, что каждое число может принимать значения от $0$ до $n$, но их сумма должна быть равна $n$ – таковы ограничения.

Вероятность вынуть белую карточку равна $1/k$, а черную $(k-1)/k$, где $k$ – текущее количество карточек, причем вначале $k=1$, а после каждой белой оно увеличивается. Выпишем вероятности, с которыми извлеченные карточки в нашем примере на каждом ходу имели именно такой цвет:
$1/1$ (белая), $1/2$ (черная), $1/2$ (черная),
$1/2$ (белая),
$1/3$ (белая), $3/4$ (черная), $3/4$ (черная), $3/4$ (черная),
$1/4$ (белая), $4/5$ (черная), $4/5$ (черная), $4/5$ (черная).
Вероятность данной реализации, т.е. последовательного осуществления этих событий, равна произведению выписанных чисел. После группировки "белых" множителей имеем $\frac{1}{m!} a_1^2 a_2^0 a_3^3 a_4^2$, где $a_k=k/(k+1)$, а их степени берутся последовательно из краткой записи $(2, 0, 3, 2)$. Внимание У $p_1^2$ вверху индекс, у $a_1^2$ -- степень.

В общем случае вероятность реализации $(x_1, x_2, …, x_m)$ равна $\frac{1}{m!} a_1^{x_1} a_2^{x_2} … a_m^{x_m}$.

Одну и ту же пару $m, n$ могут давать различные взаимоисключающие варианты-реализации, им соответствуют различные записи $(x_1, x_2, …, x_m)$ с $m$ числами, сумма которых равна $n$. Поэтому для нахождения $p_n^m$ надо просуммировать выражения $\frac{1}{m!} a_1^{x_1} a_2^{x_2} … a_m^{x_m}$ для всевозможных комбинаций целых неотрицательных чисел $x_k$, сумма которых равна $n$.

Если $\frac{1}{m!}$ как общий множитель вынести за скобку, то в скобках останется как раз то, что называется полный однородный симметрический многочлен степени $n$ от $m$ переменных $a_1, a_2, …, a_m$ (http://en.wikipedia.org/wiki/Complete_homogeneous_symmetric_polynomial, рекомендую начать с пункта Examples). Он обозначается $h_n(a_1, a_2, …, a_m)$. Здесь мы попадаем в хорошо изученную область симметрических многочленов.

Итак, $p_n^m=\frac{1}{m!} h_n(a_1, a_2, …, a_m)$, где $a_k=k/(k+1)$.

Пример. Найти вероятность получить после $4$-го хода $3$ карточки.
Имеем: $m=2$, $n=2$. Общий факториальный множитель равен $1/2!=1/2$.
Полином $h_2(a_1, a_2)$ -- это сумма всех $a_1^{x_1} a_2^{x_2}$ с целыми неотрицательными степенями $x_1$ и $x_2$, сумма которых равна $2$. То есть $h_2(a_1, a_2)=a_1^2 a_2^0 + a_1^1 a_2^1 + a_1^0 a_2^2$. Подставляя $a_1=1/2$, $a_2=2/3$, получим $h_2(a_1, a_2)=37/36$.
Искомая вероятность $p_2^2=(1/2) (37/36)=37/72$.

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

Я также нарисовал красивую картинку, которая наглядно поясняет правила формирования вероятности одной реализации, но я не знаю, как ее вставить в сообщение.

[svv]

И, в самом деле, явная формула для полного однородного симметрического полинома нашлась - в книге Richard Stanley "Enumerative Combinatorics", том 2, страница 450, упражнение 7.4. В наших обозначениях:

$$h_n(a_1, a_2, …, a_m)=\sum\limits_{k=1}^m \frac {a_k^{n+m-1}} {\prod\limits_{i \ne k} (a_k - a_i)}$$

Так как $a_k=k/(k+1)$ известны, их можно подставить и упростить выражение. В результате для вероятности $p_n^m$ найдем формулу, которую не стыдно назвать явной:

$$p_n^m=(m+1) \sum\limits_{j=1}^m \frac {(-1)^{m-j} j^{n+m}} {(j+1)^n (j+1)! (m-j)!} $$

Возвращаясь к первоначальным переменным $i, k$, которые вводил arseniiv, получим:

$$q_i^k=k \sum\limits_{j=1}^{k-1} \frac {(-1)^{k-j-1} j^i} {(j+1)^{i-k+1} (j+1)! (k-j-1)!} $$

Я сравнил на компьютере результаты, полученные с помощью этой формулы и рекуррентной, они совпадают.