100 подбрасываний Какая вероятность, что решка выпадет 7 раз

[arseniiv]

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

[mustitz]

Intercooler в сообщении #897680 писал(а):

Или сначала мы должны попытаться их вывести?

Там ничего сложного. Пусть $Q_n$ это множество всех последовательностей длины $n$, $Q_{n, k} \subset Q_n$ это множество последовательностей из нулей и единиц длины $n$, в которой $k$ единиц идут подряд. Множество $Q_{n, k}$ ($n>k$) легко получить как объединений двух множеств $A$ и $B$. Во-первых, мы может ко всем элементам множества $Q_{n-1, k}$ приписать либо нуль, либо единицу, получив тем самым множество $A$. Во-вторых, мы можем к тем элементам из $Q_{n-1}$, которые заканчиваются на нуль и $k-1$ единиц приписать единицу, получив множество $B$. Получим $Q_{n, k} = A \cup B$. Или $|Q_{n, k}| =|A| + |B| - |A \cap B|$.

Далее, сразу получаем $|A| = 2 |Q_{n-1, k}|$. Также $|B| = 2^{n-k-1}$ (первые $n-k-1$ элементов последовательности мы вправе выбирать по желанию, далее идет нуль, $k$ единиц). В качестве упражнения посчитайте $|A \cap B|$ и получите рекуррентную формулу, по которой можно считать $Q_{n, k}$ за $O(n)$ операций:

$$ |Q_{n, k}| = 2 |Q_{n-1, k}| + 2^{n-k-1} - \hbox{???} $$

[Shadow]

В худшем случае можно воспользоватся приближенной формулой $P\approx \exp(-nqp^k)$ при больших $n$. В случае при $n=100,p=\frac 1 2, q=\frac 1 2, k=7$
Вероятность, что в серии из 100 испытаний не будет цепочка из 7 или более последовательных единиц, $P \approx 0.68$

[Yadryara]

venco в сообщении #897670 писал(а):

Aritaborian в сообщении #897655 писал(а):

То есть так: для данных $m,n\in\mathbb{N}, m\geqslant n$ найти количество чисел, не превосходящих $2^m-1$, в двоичной записи которых встречаются $n$ единиц подряд. Кажется, правильно сформулировал. Может быть, формула существует, но у меня нет идей, как её вывести.

Формула существует, но не тривиальная. Начинаем с рекурсивной формулы типа Фибоначчи с суммированием семи предыдущих членов.
...
Для длины 16 вероятность получается $\frac{2811}{65536}$.

Я в прошлом году занимался такими обощениями и нашёл формулу:

$$1 - \frac{F_n^{m+n}}{2^m}$$

Где $F_n^{m+n}$ — $n$-боначное число с номером $m+n$.

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

Поскольку в данных частных случаях $n=7$, нам нужна последовательность Гептаначчи(Heptanacci) A122189

В первом случае $m=8$, а $8+7=15$. Значит нам надо брать $15$-й член этой последовательности. Не забывая, что нумерация в OEIS традиционно идёт с 0-го члена, видим, что $F_7^{15}=253$. Подставляем

$$1 - \frac{253}{2^8}=\frac{3} {256}$$

Сходится с результатом ручного подсчёта Aritaborian, igrok77.

Во втором случае $m=16$, $16+7=23$. Видим, что $23$-й член этой последовательности $F_7^{23}=62725$. Подставляем

$$1 - \frac{62725}{2^{16}}=\frac{2811} {65536}$$

Сходится с результатом venco.

[Aritaborian]

Yadryara, спасибо.