задача: комбинаторика, вероятности (шары в урне)

[vladiko]

Всем доброго времени суток. Второй день ломаю голову над этой задачей. Не могли бы подтолкнуть на путь истинный. Спасибо.
Собственно сама задача:
Коробка содержит 10 черных шаров и 10 белых шаров. Вытаскиваем один шар: если он черный, то он возвращается в коробку, а если белый, то не возвращается в коробку . Найти формулу вероятности того, что коробка будет пустая от белых шаров после 20 этапов в соответствии с этим законом .

[dovlato]

Если не ставить обязательную задачу получение всеобъемлющего закона, то практичным часто бывает использование рекурсий.
Пусть $p_{n}(k)$ - распределение числа оставшихся белых шаров $k$ после $n$ испытаний. Тогда, согласно ф-ле полной вероятности,
получаем рекуррентное ур-ние:

$$p_{n+1}(k)=p_{n}(k)\frac {10}{10+k}+p_{n}(k+1)\frac {k+1}{11+k}$$

.
При этом, очевидно, $p_0(10)=1$, и $p_0(k)=0$, если $k\ne 10$. На ближайшие 20 шагов можно получить решение этого ур-ния на компьютере. То есть вычислить 11-мерный вектор, с элементами, равными тем самым вер-стям. Ну, а если есть настроение - можно попытаться найти какое-то аналитическое решение, с помощью производящих функций, абы ищо как.

[vladiko]

Спасибо за ответ. Задача стоит найти аналитическое выражение.

[_hum_]

По сути, задача сводится к проблеме расчета вероятности попадания за 20 шагов марковской цепи в заданное состояние.

[vladiko]

_hum_
Можно пожалуйста по подробнее. Я новичок в этой сфере.

[dovlato]

Хорошее замечание.. Лучше всего - построить матрицу перехода $M$, согласно рекуррентному уравнению. И тогда вероятностный вектор, соответствующий произвольному числу попыток $n$, выразится как

$$\vec P_{n}=M^n \vec P_0$$

[_hum_]

vladiko в сообщении #422284 писал(а):

_hum_
Можно пожалуйста по подробнее. Я новичок в этой сфере.

Рассматриваете марковскую цепь $(S,\mathbb{P},\Pi)$, в которой множество состояний $S = \{0,1,\dots,10\}$, каждое $s\in S$ соответствует числу вытянутых белых шаров на очередном шаге; матрица переходных вероятностей $\mathbb{P} = ||p_{i,j}||, i,j \in S$, $p_{i,j}$ -- вероятность того, что на очередном шаге вытянутых белых шаров станет $j$ штук при условии, что до этого уже было вытянуто $i$ белых шаров; ну и начальное распределение $\Pi = (\pi_i), i \in S$, $\pi_i = \delta_{0,i}$. В такой постановке Ваша задача эквивалентна классической задаче расчета вероятности попадания марковской цепи за 20 шагов в состояние $s = 10$. Решением, если не ошибаюсь, будет$p_{0,10}^{(20)} = \big(\Pi\mathbb{P}^{20}\big)_{10}$

[vladiko]

_hum_
Спасибо за объяснение, загвоздка в том что я только начал изучать предмет и про Марковские цепи в первый раз услышал от вас. Может есть ещё какие нибудь идеи ,но с использованием базовых знаний в теории вероятностей.

[PAV]

В явном виде требуемая вероятность будет выглядеть примерно так. Каждый элементарный исход - это двоичная последовательность длины 20, в которой поровну нулей и единиц. Беда в том, что их вероятности разные. А именно, белым шарам соответствуют вероятности

$$ \frac{10}{20},\,\frac{9}{19},\ldots,\frac{1}{11} $$

А вот вероятности черных шаров зависят от того, в каком порядке относительно белых они извлекались. Точнее, всем черным шарам, извлеченным перед первым белым, соответствует вероятность $10/20$; шарам между первым и вторым белым - вероятность $10/19$ и так далее; черным шарам после последнего белого - вероятность $10/10=1$.

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

$$ P=\frac{(10!)^2\cdot 10^{10}}{20!}\sum_{\mathbf{x}}\frac{1}{x_1x_2\cdots x_{10}}, $$

где сумма берется по всем векторам $\mathbf{x}=(x_1,x_2,\ldots,x_{10})$, где $10\le x_1\le x_2\le\cdots\le x_{10}\le 20$.

Что можно сделать с этой суммой - я не вижу.

[dovlato]

Я добавлю конкретики своим равенствам. Матрица перехода - квадратная, размера $11\times 11$. Её диагональ имеет вид $M_{i,i}=10/(10+i)$.
Далее, $M_{i,i+1}=(i+1)/(i+11)$; $0\le i\le 10$.
Разумеется, её надо бы её прогнать по очевидным значениям и проверить. Ну, например, очевидно,
что вер-сть $P_n(k=10)=(1/2)^n$. Но зато потом уж можно ею пользоваться для любых $n,\quad k$.

[vladiko]

Всем большое спасибо, разобрался с цепями Маркова (на начальном уровне). Действительно выходит изящное решение, и благодаря вам узнал , то чего не знал.

[dk-dw]

Я так на глаз прикинул, вродь 1 к 50 вероятность. Интересно правильный ответ узнать.

-- Вт мар 15, 2011 14:01:01 --

Или 1 к 512 ))

-- Вт мар 15, 2011 14:01:17 --

Или 1 к 512 ))

[dk-dw]

Пришла вот мысль в голову. Вы только не серчайте на бедного школьника. Вопрос есть у меня. Если есть два события, вероятность того что одно событие исполнится - x, а второе - y. Тогда выходит что вероятность того что оба события исполнятся - xy?

Вообщем я от этого отталкивался. Рассмотрит вероятность того что нужный шарик вытащат два раза подряд. Вероятность того что в первый раз вытащат - 1 к 2, а вероятность что вытащат второй - 9 к 19(всего 19 шариков и 9 из них нужные). Можно принять два вытаскивания за два события и вероятность того что они оба исполнятся равна 9 к 38( $1/2*9/19$. и так можно рассмотреть все десять вытаскиваний, т.к. чтобы вытащить все шарики нужно 10 попыток(найдем сначала вероятность того что за десять вытаскиваний будет вытащено 10 шариков нужных). Тогда получится такая штука - $1/2*9/19*8/18*7/17*6/16*5/15*4/14*3/13*2/12*1/11$ я посчитал, это выходит вероятность $1/184756$, а так как у нас попыток в два раза больше то нашу вероятность умножаем на 2, выходит 1 к 92378. Вообще в некоторых моментах не уверен, не знаю теории вероятности, но мысль я думаю понятна.

[Joker_vD]

dk-dw в сообщении #423234 писал(а):

Если есть два события, вероятность того что одно событие исполнится - x, а второе - y. Тогда выходит что вероятность того что оба события исполнятся - xy?

Не-а. Шанс выкинуть единицу на кубике — одна шестая. Шанс выкинуть двойку — одна шестая. Шанс выкинуть одновременно и единицу, и двойку — ноль.

[dk-dw]

Что вероятность равна нулю - понятно. Но это не совсем то о чем я говорил, если показывать на кубиках, то есть два кубика. Какова вероятность что на одном кубике выпадет 2, а на втором 3 к примеру. 1/6 * 1/6 = 1/36? Вот что меня интересует, умножаются они?