Геометрическое распределение и минимальное число попыток (geometrische Verteilung)

15 мин · 2 упражнения

Введение

Одно и то же испытание повторяют в одинаковых условиях: бросают кубик, вынимают шар с возвращением, покупают лотерейный билет. Каждое испытание удаётся с одной и той же вероятностью $p$, независимо от остальных. Геометрическое распределение (нем. geometrische Verteilung) описывает, сколько приходится ждать первого успеха.

Задачи EPM по этой теме почти всегда задают один вопрос: сколько раз нужно попробовать как минимум, чтобы хотя бы один успех случился с вероятностью больше $90\%$, $95\%$ или $99\%$? Ответ даёт неравенство, которое решают логарифмированием и затем округляют вверх. Часто перед этим отдельным пунктом нужно найти $p$ одного испытания, например для двух кубиков или для выбора двух шаров.

---

Геометрическое распределение

Обозначим через $X$ номер испытания, в котором успех наступает впервые. $X$ принимает значения $1,2,3,\dots$ Первый успех в $k$-м испытании означает, что первые $k-1$ испытаний неудачны, а $k$-е удачно. Испытания независимы, поэтому вероятности перемножаются:

$$\boxed{P(X=k)=(1-p{)}^{k-1}\cdot p}$$

Пример: кубик бросают, пока не выпадет первая шестёрка. Вероятность того, что она выпадет именно при третьем броске, равна

$$P(X==3)=={\left(\frac{5}{6}\right)}^2\cdot \cdot \frac{1}{6}==\frac{25}{216}\approx \approx 0,1157$$

Для минимального числа попыток нужны две суммы. «После $k$ испытаний успеха ещё нет» значит, что все $k$ испытаний неудачны. Отсюда противоположное событие (нем. Gegenereignis) «первый успех наступает не позже $k$-го испытания»:

$$\boxed{P(X>k)=(1-p{)}^k}\boxed{P(X\le k)=1-(1-p{)}^k}$$

$P(X\le k)$ и есть вероятность получить в $k$ испытаниях хотя бы один успех (нем. mindestens einmal). Это то же число, что $P(Y\ge 1)=1-P(Y=0)$ для биномиально распределённого числа $Y$ успехов в $k$ испытаниях. Поэтому в некоторых решениях неравенство записано через число попаданий; расчёт в обоих случаях одинаковый.

Математическое ожидание (нем. Erwartungswert) показывает, сколько испытаний в среднем нужно до первого успеха:

$$\boxed{E(X)=\frac{1}{p}}$$

Если бросать кубик до шестёрки, в среднем понадобится $6$ бросков.

Задачи этой темы всегда считают испытания вместе с удачным: спрашивают, сколько всего бросков, выборов или билетов нужно. Поэтому в статье везде используется первая строка таблицы.

---

Минимальное число попыток

Ищем наименьшее $n$, при котором вероятность хотя бы одного успеха в $n$ испытаниях больше порога $s$:

$$1--(1--p{)}^n>>s$$

Переносим степень в одну сторону и логарифмируем обе части:

$$(1--p{)}^n<<1--s$$ $$n\cdot \cdot \ln (1--p)<<\ln (1--s)$$

Оба логарифма отрицательны, потому что $1-p$ и $1-s$ лежат между $0$ и $1$. При делении на отрицательное число $\ln (1-p)$ знак неравенства меняется на противоположный:

$$\boxed{n>\frac{\ln (1-s)}{\ln (1-p)}}$$

Дробь почти никогда не бывает целым числом. Число $n$ натуральное, поэтому берут ближайшее целое сверху, то есть всегда округляют вверх, даже при $18,01$. Вместо $\ln$ подойдёт любой другой логарифм, например $\lg$: частное от этого не меняется.

Порядок действий

1. Найти $p$: вероятность успеха в одном испытании, если она не дана прямо.
2. Найти противоположную вероятность $1-p$: вероятность того, что испытание неудачно.
3. Записать неравенство $1-(1-p{)}^n>s$ и привести его к виду $(1-p{)}^n<1-s$.
4. Прологарифмировать и разделить на $\ln (1-p)$, поменяв знак.
5. Округлить вверх и проверить $n-1$ и $n$: при $n-1$ вероятность ещё ниже порога, при $n$ уже выше.

Особый случай возникает, когда частное оказывается ровно целым, и тогда решает знак. При $p=\frac{1}{2}$ и условии «больше $87,5\%$» получается ${\left(\frac{1}{2}\right)}^n<\frac{1}{8}$, то есть $n>3$ и $n=4$. При условии «не меньше $87,5\%$» хватает $n=3$.

---

Вероятность p одного испытания

«Испытание» само может состоять из нескольких частей: два кубика сразу, два шара из урны, монета и кубик. Тогда сначала находят вероятность $p$ того, что удастся один такой раунд, и только потом подставляют её в неравенство. Раунды независимы друг от друга, потому что перед каждым раундом всё возвращают или бросают заново.

Правила подсчёта описаны в теме «Комбинаторика», теорема сложения и полная вероятность в теме «Условная вероятность», «ровно $k$ раз» в нескольких испытаниях в теме «Биномиальное распределение».

---

Примеры

Пример 1: Первый успех в k-м испытании

У колеса удачи пять одинаковых секторов, один из них выигрышный. Колесо крутят, пока не выпадет выигрыш. Значит, $p=\frac{1}{5}$ и $1-p=\frac{4}{5}$.

Первый выигрыш ровно при четвёртом вращении:

$$P(X==4)=={\left(\frac{4}{5}\right)}^3\cdot \cdot \frac{1}{5}==\frac{64}{625}==0,1024$$

Вероятность того, что за три вращения выигрыша ещё нет, и противоположного события:

$$P(X>>3)=={\left(\frac{4}{5}\right)}^3==\frac{64}{125}==0,512,P(X\le \le 3)==1--\frac{64}{125}==\frac{61}{125}==0,488$$

Для проверки сложим отдельные значения: $\frac{1}{5}+\frac{4}{25}+\frac{16}{125}=\frac{25+20+16}{125}=\frac{61}{125}$.

В среднем нужно $E(X)=\frac{1}{p}=5$ вращений.

Пример 2: Чуть больше целого числа

В лотерейном киоске каждый билет выигрывает с вероятностью $12\%$. Сколько билетов нужно купить как минимум, чтобы с вероятностью больше $90\%$ выиграть хотя бы один раз?

$$1--0,88^n>>0,9$$ $$0,88^n<<0,1$$ $$n>>\frac{\ln (0,1)}{\ln (0,88)}==\frac{-2,302585}{-0,127833}\approx \approx 18,01$$ $$\boxed{n=19}$$

Проверка показывает, почему и здесь нужно округлять вверх. С $18$ билетами $1-0,88^{18}\approx 0,89984$, это чуть меньше $90\%$, и только с $19$ билетами $1-0,88^{19}\approx 0,91186$.

Пример 3: p для двух кубиков

Два кубика бросают одновременно. Раунд удачен, если сумма очков равна 9. Сколько раз нужно бросить как минимум, чтобы сумма 9 выпала хотя бы один раз с вероятностью больше $95\%$?

Сумму 9 дают четыре исхода из 36: $(3,6)$, $(4,5)$, $(5,4)$ и $(6,3)$.

$$p==\frac{4}{36}==\frac{1}{9},1--p==\frac{8}{9}$$ $${\left(\frac{8}{9}\right)}^n<<0,05$$ $$n>>\frac{\ln (0,05)}{\ln (8/9)}==\frac{-2,995732}{-0,117783}\approx \approx 25,43$$ $$\boxed{n=26}$$

Пример 4: Два шара сразу

В урне 5 белых и 3 чёрных шара. Одновременно вынимают два шара, записывают цвета и возвращают оба. Раунд удачен, если оба шара чёрные. Нужно найти минимальное число раундов для вероятности больше $90\%$.

Внутри одного раунда шары вынимают без возвращения, поэтому считаем выборки:

$$p==\frac{\left(\genfrac{}{}{0ex}{}{3}{2}\right)}{\left(\genfrac{}{}{0ex}{}{8}{2}\right)}==\frac{3}{28},1--p==\frac{25}{28}$$ $$n>>\frac{\ln (0,1)}{\ln (25/28)}==\frac{-2,302585}{-0,113329}\approx \approx 20,32$$ $$\boxed{n=21}$$

Между раундами шары возвращают. Поэтому у каждого раунда одно и то же $p$, и формула применима.

Пример 5: «Или» с пересечением

Из колоды в 52 карты вынимают карту и возвращают её обратно. Раунд удачен, если карта червовая или это картинка (валет, дама, король), а порог вероятности равен $99,9\%$.

Червовых карт 13, картинок 12. Три червовые картинки вошли в оба числа, и их вычитают один раз:

$$p==\frac{13+12-3}{52}==\frac{22}{52}==\frac{11}{26},1--p==\frac{15}{26}$$ $$n>>\frac{\ln (0,001)}{\ln (15/26)}==\frac{-6,907755}{-0,550046}\approx \approx 12,56$$ $$\boxed{n=13}$$

Пример 6: Полная вероятность

Торговец получает $70\%$ товара от поставщика A, у которого $2\%$ брака, и $30\%$ от поставщика B, у которого $6\%$ брака. Он проверяет случайно выбранные изделия, каждое независимо от предыдущего. Сколько изделий нужно проверить как минимум, чтобы с вероятностью больше $90\%$ найти хотя бы одно бракованное?

$$p==0,7\cdot \cdot 0,02++0,3\cdot \cdot 0,06==0,014++0,018==0,032$$ $$0,968^n<<0,1$$ $$n>>\frac{\ln (0,1)}{\ln (0,968)}==\frac{-2,302585}{-0,032523}\approx \approx 70,80$$ $$\boxed{n=71}$$

---

Задача EPM: полный разбор

Задача: два правильных кубика бросают одновременно. Бросок считается успехом, если среди них есть хотя бы одна шестёрка. Бросок независимо повторяют.

a) С какой вероятностью бросок будет успешным? b) Сколько раз нужно бросить как минимум, чтобы хотя бы один успех случился с вероятностью больше $99\%$? c) Сколько бросков в среднем нужно до первого успеха? d) С какой вероятностью первый успех наступит именно при третьем броске?

Решение:

a) Через противоположное событие, когда ни на одном кубике нет шестёрки:

$$p==1--{\left(\frac{5}{6}\right)}^2==1--\frac{25}{36}==\frac{11}{36}\approx \approx 0,3056$$

Проверка подсчётом: из 36 исходов хотя бы одну шестёрку содержат $6+6-1=11$, потому что $(6,6)$ считается только один раз.

b) Бросок неудачен с вероятностью $\frac{25}{36}$:

$$1--{\left(\frac{25}{36}\right)}^n>>0,99$$ $${\left(\frac{25}{36}\right)}^n<<0,01$$ $$n>>\frac{\ln (0,01)}{\ln (25/36)}==\frac{-4,605170}{-0,364643}\approx \approx 12,63$$ $$\boxed{n=13}$$

Проверка: при $12$ бросках вероятность $\approx 0,98742$, при $13$ бросках $\approx 0,99127$.

c) $$E(X)==\frac{1}{p}==\frac{36}{11}\approx \approx 3,27\text{броска}$$

d) Первые два броска неудачны, третий удачен:

$$P(X==3)=={\left(\frac{25}{36}\right)}^2\cdot \cdot \frac{11}{36}==\frac{6875}{46656}\approx \approx 0,1474$$

---

Типичные вопросы EPM

Немецкое условие почти всегда построено так: «Berechnen Sie, wie oft man mindestens ... muss, damit die Wahrscheinlichkeit, mindestens einmal ... zu erhalten, größer als ... ist!»

• Минимальное число без подготовки: $p$ дано в процентах или простой дробью по Лапласу (монета, кубик, колесо удачи). Вся задача сводится к неравенству.
• Пункты a) и b): в a) спрашивают $p$ одного раунда, в b) минимальное число (нем. Mindestanzahl). Работа в a) состоит из комбинаторики, теоремы сложения или полной вероятности, как в примерах с 3 по 6.
• Два события в одной задаче: например, «$A$ и $B$» в a) и «$A$ или $B$» в b), каждое со своим порогом. Один и тот же порядок действий проходят дважды с разными $p$.
• «С возвращением», «независимо», «одновременно ... потом всё вернуть»: эти слова говорят, что у каждого раунда одно и то же $p$. Без них формула $1-(1-p{)}^n$ неприменима.
• Запись ответа: $n$ натуральным числом, $p$ дробью или десятичным числом.

---

Типичные ошибки

Ошибка 1: Знак не поменяли

Из $n\cdot \ln (0,88)<\ln (0,1)$ после деления получается $n>18,01$, а не $n<18,01$. Если оставить знак, выйдет верхняя граница, и искать придётся наибольшее $n$ вместо наименьшего. Проверка $n-1$ и $n$ сразу выдаёт ошибку.

Ошибка 2: Округлили вниз

Частное $18,01$ из примера 2 подталкивает ответить $18$. Но с $18$ билетами вероятность равна $0,89984$, то есть не больше $90\%$. Минимальное число попыток всегда округляют вверх.

Ошибка 3: Перепутали $p$ и $1-p$ или $s$ и $1-s$

В степень идёт вероятность неудачи, в правую часть остаток $1-s$. Неравенства $0,12^n<0,1$ или $0,88^n<0,9$ описывают другое событие. Из $0,88^n<0,9$, например, получается $n=1$, а это явно неверно.

Ошибка 4: Линейный расчёт вместо степени

При $p=0,15$ и пороге $90\%$ запись $n\cdot 0,15>0,9$ даёт ответ $n=7$. Правильный ответ $n=15$: события отдельных испытаний пересекаются, и их вероятности нельзя складывать. Математическое ожидание $\frac{1}{p}\approx 6,67$ тоже не минимальное число. Оно говорит, сколько ждать в среднем, а не сколько ждать, чтобы быть почти уверенным.

Ошибка 5: Слишком раннее округление

Если в примере 6 округлить логарифм $\ln (0,968)\approx -0,032523$ до $-0,033$, получится $n>69,8$ и ответ $70$. Но с $70$ изделиями вероятность всего $0,89737$. Берите в логарифмах не меньше четырёх значащих цифр или считайте частное сразу на калькуляторе.

Ошибка 6: Пересечение при «или» посчитали дважды

В примере 5 сумма $13+12=25$ карт вместо $22$ даёт $p=\frac{25}{52}$ и ответ $n=11$ вместо $13$. Теорема сложения вычитает общую часть один раз.

---

Проверьте себя

Ваша очередь1 из 2

Баскетболист попадает одним броском с вероятностью $20\%$. Сколько раз ему нужно бросить как минимум, чтобы с вероятностью больше $95\%$ попасть хотя бы один раз?

A$n=5$B$n=13$C$n=14$D$n=1$

Проверить

Ваша очередь2 из 2

Кубик бросают, пока не выпадет первая шестёрка. С какой вероятностью она выпадет именно при третьем броске?

A$\frac{1}{216}$B$\frac{25}{216}$C$\frac{75}{216}$D$\frac{91}{216}$

Проверить

---

Формулы для запоминания

Первый успех в $k$-м испытании:

$$P(X==k)==(1--p{)}^{k-1}\cdot \cdot p$$

Успеха ещё нет после $k$ испытаний, хотя бы один успех в $k$ испытаниях:

$$P(X>>k)==(1--p{)}^k,P(X\le \le k)==1--(1--p{)}^k$$

Математическое ожидание:

$$E(X)==\frac{1}{p}$$

Минимальное число попыток для порога $s$:

$$1--(1--p{)}^n>>s⟺⟺n>>\frac{\ln (1-s)}{\ln (1-p)},\text{затем округлить вверх}$$