2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3
 
 Re: Попытка задач
Сообщение28.10.2010, 16:29 
Заслуженный участник


23/07/08
10609
Crna Gora
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}$

 Профиль  
                  
 
 Re: Попытка задач
Сообщение28.10.2010, 17:28 
Заслуженный участник


27/04/09
28128
svv в сообщении #367254 писал(а):
Правильно?
Ага. :-)

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

 Профиль  
                  
 
 Re: Попытка задач
Сообщение28.10.2010, 18:35 
Заслуженный участник


23/07/08
10609
Crna Gora

(Оффтоп)

Кратко:
Номер полки $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$.

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

 Профиль  
                  
 
 Re: Попытка задач
Сообщение28.10.2010, 19:41 
Заслуженный участник


27/04/09
28128
А, ну теперь понятно. :-) Не в ту сторону думал.

 Профиль  
                  
 
 Re: Попытка задач
Сообщение28.10.2010, 20:20 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Попытка задач
Сообщение29.10.2010, 12:56 
Заслуженный участник


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

Допустим, у нас получилась формула для $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}$.

 Профиль  
                  
 
 Re: Попытка задач
Сообщение29.10.2010, 14:17 
Заслуженный участник


27/04/09
28128

(Оффтоп)

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

 Профиль  
                  
 
 Re: Попытка задач
Сообщение30.10.2010, 12:43 
Заслуженный участник


23/07/08
10609
Crna Gora
Да, всё правильно.

 Профиль  
                  
 
 Re: Попытка задач
Сообщение30.10.2010, 15:59 
Заслуженный участник


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

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

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

 Профиль  
                  
 
 Re: Попытка задач
Сообщение08.11.2010, 01:35 
Заслуженный участник


23/07/08
10609
Crna Gora
Я опять немного изменю терминологию. Пустую карточку буду называть белой, а непустые черными, причем различать черные карточки не имеет смысла. В начале игры (на «нулевом» ходу) была одна белая карточка, а затем после каждого хода в коробку либо добавлялась $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$.

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

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

 Профиль  
                  
 
 Re: Попытка задач
Сообщение10.11.2010, 00:42 
Заслуженный участник


23/07/08
10609
Crna Gora
И, в самом деле, явная формула для полного однородного симметрического полинома нашлась - в книге 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)!} $$Я сравнил на компьютере результаты, полученные с помощью этой формулы и рекуррентной, они совпадают.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 41 ]  На страницу Пред.  1, 2, 3

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group