Вероятность: Ненасытный Пончик, карманы и пряники.

[xolodec]

Вопрос, как подойти к решению такой вот задачи:

У Пончика в куртке 10 карманов, в каждый из которых он положил по два пряника. В произвольный момент времени он решает подкрепиться и определяет, из какого кармана вытащить пряник каждый раз наугад.
Найти вероятность, что первые $k$ пряников Пончик вытащит с первой попытки.

Покрутил и так и так, не могу придумать, как к ней подобраться. Смущают эти "по два пряника в каждый".
В случае, если в каждом кармане по одному прянику - тривиален.

[мат-ламер]

А какова вероятность, что в $i$-ый карман Пончик залезет три раза? А после этого попробовать вычислить, что Пончик ни в один карман не залезет три раза.

[xolodec]

Благодярю за наводку ) Однако, как рассчитать эту вероятность, что в $i$-ый карман Поничик может залезть (при условии, что это $k$-ое желание подкрепиться).
Ведь получается, что после второго желания подкрепиться, мы должны рассмотреть два варианта:

когда Пончик два раза залез в один карман и потом попал в тот же самый, т.е. $\frac{1}{N^3}$

когда Пончик на четвертом разе залез в тот же карман, куда уже дважды залез $\frac{(N-1)2}{N^4}$

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

[venco]

мат-ламер в сообщении #921678 писал(а):

А какова вероятность, что в $i$-ый карман Пончик залезет три раза? А после этого попробовать вычислить, что Пончик ни в один карман не залезет три раза.

Врядли это сильно поможет. События "залезть 3 раза в один карман" и "3 раза в другой" зависимы.

[upgrade]

вероятность залезть в конкретный карман $1/10$
вероятность залезть в карман два раза подряд (обнулить карман) $1/10\cdot1/10= 1/100$
вероятность обнулить два кармана подряд $1/10000$

-- 22.10.2014, 16:46 --

то есть вероятность, что с первой попытки он обнулит $n$ карманов - $1/100^n$

[mihiv]

Можно записать рекуррентное соотношение для вероятностей. Пусть $p_n(k)$ - вероятность вытащить $k$ пряников из $n$ карманов с первой попытки. Тогда

$$p_n(k)=p_{n-1}(k-1)+\frac 1np_{n-1}(k-2)$$

-- Ср окт 22, 2014 18:12:34 --

mihiv в сообщении #921935 писал(а):

Можно записать рекуррентное соотношение для вероятностей.

Похоже написал неправильно.

[xolodec]

Странная формула если честно. Можно услышать комментарии автора, как она получилась ? Мне кажется она странной по меньшей мере и кажется неправильной, если я не ошибаюсь.

Кажется тут нужно рассмотреть все последовательности цифр (цифра - номер кармана) длинной $k$, в которой $m$ чисел повторяются дважды, а $k - 2m$ повторяются только единожды.
Но как посчитать количество таких последовательностей?

[mihiv]

Да, формула, скорее всего, неправильная. А рекуррентное соотношение я пытался получить так: представим событие "вытащить $k$ пряников с первой попытки" в виде последовательности двух событий - 1. "вытащить один пряник" и 2."вытащить $k-1$ пряник с первой попытки". Вероятность события 2 должна выражаться через вероятности событий $p_{n-1}(k-1)$ и $p_{n-1}(k-2)$.

[upgrade]

Поскольку все $k$ раз можно попасть в один карман, разрядность процессора $k$ , поскольку карманов $10$ состояний одного разряда $10$ , общее число комбинаций (знаменатель) $10^k$

-- 22.10.2014, 22:07 --

$$ \begin{pmatrix} 1&1&0& \cdots & k \\ 1&1&0& \cdots & k \\ \vdots & \vdots & \vdots & \vdots & \vdots\\ 1&1&0 & \cdots & k \end{pmatrix} ​$$​
$10$ строк

-- 22.10.2014, 22:09 --

Две единицы - это два пирожка, нули - попытки когда пирожков не досталось

[xolodec]

Данное представление, если я правильно его понял, опять же не упрощает расчет, потому что уже в третьем столбце ( читай третьей попытке ) номер кармана из которого Пончик вытащит пряник зависит от того, в каких двух (одном) кармане он побывал до этого.
Потом, интересно почему последним стоит число $k$? Я так понял, что матрица, которую вы предлагаете для решения состоит только из нулей и единиц, откуда тогда на последнем месте число $k$?

[upgrade]

Неверно записал, $k$ попыток, там не $k$, а $0$.
Надо посчитать все комбинации длиной $k$ с нулями (без нулей)

[upgrade]

$$ \begin{pmatrix} 1_{11}&1_{12}&0_{13}& \cdots & 0_{1k}\\ \vdots & \vdots & \vdots & \vdots & \vdots\\ 1_{101}&1_{102}&0_{103} & \cdots & 0_{10k} \end{pmatrix} ​$$


например $k=4$, а карманов $2$ тогда
$$ \begin{pmatrix} 1_{11}&1_{12}&0_{13}& 0_{14}\\ 1_{21}&1_{22}&0_{23} & 0_{24k} \end{pmatrix} ​$$


$1) \quad \quad 1_{11}1_{12}0_{13}0_{14}$

$2) \quad \quad 1_{11}1_{12}0_{13} 1_{21}$

$3)_{\text {раз}} \quad \quad 1_{11}1_{12}1_{21} 1_{22}$

$4) \quad \quad 1_{11}1_{12}1_{21} 0_{13}$

$5) \quad \quad 1_{11}1_{21}1_{22} 0_{23}$

$6)_{\text {два}} \quad \quad 1_{11}1_{21}1_{22} 1_{12}$

$7)_{\text {три}} \quad \quad 1_{11}1_{21}1_{12} 1_{22}$

$8) \quad \quad 1_{11}1_{21}1_{12} 0_{13}$

комбинации с индексом $21$ симметричны, значит в них тоже $3$ случая получения $4$-х пряников подряд. всего таких случаев $6$, а всех комбинаций $16$
вероятность $6/16$

найти число перестановок элементов с номерами $11,12,21,22, ... 101,102$ затем вычесть все перестановки, начинающиеся со столбца $2$.

[upgrade]

нет, не выйдет, вычитать надо не только те которые со второго столбца начинаются...

[xolodec]

xolodec в сообщении #921993 писал(а):

Кажется тут нужно рассмотреть все последовательности цифр (цифра - номер кармана, который посетил Пончик) длинной $k$, в которой $m$ чисел повторяются дважды, а $k - 2m$ повторяются только единожды.

Судя по ответу на эту задачу, рассуждать надо именно таким способом.

1. Выбрать $2m$ можно $C_k^{2m}$ способами. Таким образом в этом ряде цифр мы зафиксировали некоторые $2m$ цифр (читай номера, когда проверялись карманы, которые в итоге были проверены дважды)
2. Таким образом у нас есть $2m$ позиций, на которых расположены $m$ чисел от 0 до 9 (каким-то обазом, причем каждое из $m$ чисел повторяется дважды ). И $k-2m$ чисел, которые встречаются только один раз (также от 0 до 9, но не пересекающиеся с числами, которые на стоят на двойных позициях)
3. Число таких случаев $C_k^{2m} \cdot 10^{[k-2m+m]} \cdot \frac{(2m)!}{(2!)^m \cdot (m!)} $

Выражение под номером 3 можно просто обьяснить:

$10^{[k-2m+m]} = 10 \cdot 9 \cdot 8 \cdot ... \cdot (10 - k +2m -m + 1)$ : варианты выбора $(k-2m) + m $ неповторяющихся чисел

$\frac{(2m)!}{(2!)^m \cdot (m!)} $ : Всего перестановок этих двойных чисел ${(2m)!}$, причем формула ${(2m)!}$ не совсем верная, поскольку считает разными и те случаи, когда переставлена только пара цифр между собой (ну то есть, к примеру 7 и 7 переставлены местами). Соответственно, чтобы это исключить поделим на $(2!)^m$. Однако я так и не могу понять, зачем мы делим (опять же, судя по ответу) на $m!$, хотя и понятно, что это число перестановок $m$ цифр между собой.

То есть все таки не понятно, почему мы делим на $m!$ ? то есть мы считаем одними и теми же случаи, допустим $123321, 132321, 231321, 213321, 312321, 321321$. Почему ?

В смысле исходов конкретных ревизий Пончиком своих карманов, это должны быть разные случаи.

[mihiv]

Удалось получить рекуррентное соотношение для вероятностей $p_n(k)$. Оно имеет вид:

$$p_n(k)=\left (\dfrac {n-1}n\right )^{k-1}p_{n-1}(k-1)+\frac {k-1}n\left (\dfrac {n-1}n\right )^{k-2}p_{n-1}(k-2)$$

Учитывая, что $p_n(2)=p_n(1)=1$ для любого $n$, получим, например, что $p_n(3)=1-\dfrac 1{n^2}$.