Исходы, события и подсчёт

Вводная заметка определила вероятность события в случае, когда все исходы равновозможны, как отношение двух количеств: $P(A) = |A| / |\Omega|$. Определение простое, а подсчёт — нет. Задаче о днях рождения уже понадобилось произведение 23 дробей, а небрежный выбор того, что считать исходом, даёт неверные ответы с полной уверенностью. В этой заметке мы вводим язык исходов и событий и четыре правила подсчёта, на которые опираются все дальнейшие вычисления.

Обозначения. $\Omega$ — пространство элементарных исходов (sample space), т. е. множество всех исходов эксперимента; событие — подмножество $A \subseteq \Omega$. $A \cup B$ означает «$A$ или $B$», $A \cap B$ — «$A$ и $B$», $A^c = \Omega \setminus A$ — «не $A$». $n! = 1 \cdot 2 \cdots n$, причём $0! = 1$, и $\binom{n}{k} = \frac{n!}{k!\,(n-k)!}$.

Исходы и события#

Исход — один полный результат эксперимента; пространство элементарных исходов $\Omega$ перечисляет их все. При двух бросках кости исход — упорядоченная пара, $\Omega = \{(1,1), (1,2), \dots, (6,6)\}$, и $|\Omega| = 36$. Событие — любое множество исходов: «сумма равна 7» — это $\{(1,6), (2,5), (3,4), (4,3), (5,2), (6,1)\}$, поэтому $P = 6/36 = 1/6$.

Операции над множествами — это логические операции над событиями. «Хотя бы одна шестёрка» — объединение событий «в первом броске шестёрка» и «во втором броске шестёрка»; «две шестёрки» — их пересечение; «ни одной шестёрки» — дополнение к «хотя бы одной шестёрке». Два события несовместны, если не могут произойти одновременно, $A \cap B = \varnothing$. Законы де Моргана связывают «и» и «или» через отрицание, $(A \cup B)^c = A^c \cap B^c$, и часто это самый быстрый путь к подсчёту: у события «хотя бы одна шестёрка» $36 - 25 = 11$ исходов, потому что у события «ни одной шестёрки» их $5 \cdot 5 = 25$.

Как выбрать равновозможные исходы#

Формула $|A| / |\Omega|$ верна, только если исходы действительно равновозможны, а это зависит от того, как их записать. Подбросим две монеты и запишем число орлов: в $\Omega = \{0, 1, 2\}$ три исхода, но вероятность события «ровно один орёл» не равна одной трети. Если записывать монеты по порядку, $\{\mathrm{HH}, \mathrm{HT}, \mathrm{TH}, \mathrm{TT}\}$ (H — орёл, T — решка), получаются четыре равновозможных исхода, и «ровно одному орлу» соответствуют два из них: $P = 1/2$. Эта ошибка так стара, что носит имя Даламбера, который в XVIII веке отстаивал ответ $2/3$ для события «хотя бы один орёл»; правильный ответ — $3/4$.

Надёжное правило: записывать исходы так, чтобы физический эксперимент обращался с ними симметрично. Обычно это значит учитывать порядок и то, какой объект какой, даже когда вопросу это безразлично, и подсчитывать событие внутри этого большего симметричного пространства.

Правило умножения#

Если исход строится в $k$ этапов, с $n_1$ вариантами на первом этапе, $n_2$ на втором — что бы ни произошло на первом, — и так далее, то число исходов равно

$$n_1 \cdot n_2 \cdots n_k .$$

Две кости: $6 \cdot 6 = 36$. Пароль из 8 символов, каждый из которых — одна из 62 букв и цифр: $62^8 = 218\,340\,105\,584\,896$, около $2.2 \cdot 10^{14}$. Расстановка $n$ различных объектов в ряд: $n \cdot (n-1) \cdots 1 = n!$. Правилу нужно только, чтобы число вариантов на каждом этапе не зависело от предыдущих выборов; то, какие именно варианты доступны, зависеть может.

Четыре способа выбрать $k$ из $n$#

Большинство задач на подсчёт — это выбор $k$ элементов из $n$, и формулу определяют два вопроса: важен ли порядок выбора и можно ли выбрать элемент повторно?

Порядок	Возвращение	Число способов	$n = 4$, $k = 2$
упорядоченный	с возвращением	$n^k$	16
упорядоченный	без возвращения	$\dfrac{n!}{(n-k)!} = n (n-1) \cdots (n-k+1)$	12
неупорядоченный	без возвращения	$\dbinom{n}{k}$	6
неупорядоченный	с возвращением	$\dbinom{n+k-1}{k}$	10

Рисунок показывает четыре случая в том же порядке — 16, 12, 6 и 10:

Рисунок

Четыре способа выбрать 2 предмета из 4

Три формулы следуют из правила умножения. Упорядоченный выбор с возвращением (размещения с повторениями): $n$ вариантов на каждом из $k$ этапов. Упорядоченный без возвращения (размещения): на каждом этапе на один вариант меньше. Неупорядоченный без возвращения (сочетания): каждое неупорядоченное множество из $k$ элементов встречается в $k!$ порядках, поэтому $\binom{n}{k} = \frac{n!}{(n-k)!\,k!}$. Четвёртая формула, для неупорядоченного выбора с возвращением (сочетания с повторениями), считает способы разложить $k$ одинаковых меток по $n$ ящикам («звёзды и перегородки», stars and bars): у ряда из $k$ звёзд и $n - 1$ перегородок $\binom{n+k-1}{k}$ расстановок. При $n = 4$, $k = 2$ в ряду две звезды и три перегородки, всего пять символов, и перегородки делят ряд на четыре ящика: ★|★|| — одна метка в ящике 1 и одна в ящике 2, выбор $\{1, 2\}$; ★★||| — обе метки в ящике 1, выбор $\{1, 1\}$; ||★|★ — выбор $\{3, 4\}$. Каждый выбор — это выбор 2 позиций для звёзд из 5, поэтому их $\binom{5}{2} = 10$.

Четвёртое количество — это число различных результатов, а не равновозможных исходов. Две кости дают 21 неупорядоченный результат, но у $\{1, 2\}$ вероятность $2/36$, а у $\{1, 1\}$ — только $1/36$. Биномиальный коэффициент $\binom{n}{k}$, напротив, считает именно равновозможные исходы, когда $k$ элементов выбираются случайно без возвращения, потому что каждое неупорядоченное множество возникает из одного и того же числа $k!$ упорядоченных выборок.

Разобранные примеры#

Совпадение дней рождения. Для $n$ человек упорядоченный выбор с возвращением даёт $365^n$ равновозможных списков дней рождения; списки, в которых все дни рождения различны, — это упорядоченный выбор без возвращения, $365!/(365-n)!$. При $n = 23$:

$$P(\text{все разные}) = \frac{365 \cdot 364 \cdots 343}{365^{23}} = 0.4927 ,$$

так что совпадение дней рождения имеет вероятность $0.5073$ — то самое число из вводной заметки.

Лотерея. Шесть чисел из 49, без учёта порядка и без возвращения: $\binom{49}{6} = 13\,983\,816$ возможных билетов. Один билет выигрывает джекпот с вероятностью примерно один к 14 миллионам.

Два туза в раздаче из пяти карт. Раздача — неупорядоченное множество из 5 карт колоды в 52 карты: всего $\binom{52}{5} = 2\,598\,960$ раздач. Раздача ровно с двумя тузами — это выбор 2 из 4 тузов и 3 из 48 остальных карт:

$$P = \frac{\binom{4}{2} \binom{48}{3}}{\binom{52}{5}} = \frac{6 \cdot 17\,296}{2\,598\,960} = 0.0399 .$$

Это гипергеометрический подсчёт — распределение числа особых элементов в выборке без возвращения; заметка о дискретных распределениях ставит его рядом с биномиальным.

С возвращением и без возвращения. В урне 3 красных и 2 синих шара; вынимаем два. Без возвращения $P(\text{оба красные}) = \frac{3}{5} \cdot \frac{2}{4} = 0.30$; с возвращением $\left(\frac{3}{5}\right)^2 = 0.36$. Разница уменьшается с ростом урны, поэтому выборку из большой генеральной совокупности можно считать выборкой с возвращением.

Что изменилось#

	Перечисление исходов вручную	Правила подсчёта
Две кости	36 исходов, выписанных явно	$6^2$
Раздачи из 5 карт	перечислить невозможно	$\binom{52}{5} = 2\,598\,960$
Равновозможны ли исходы?	нужно обосновывать для каждого списка	верно для упорядоченного выбора и для выборок $\binom{n}{k}$; неверно для неупорядоченного выбора с возвращением

Ограничения#

• Только равновозможные исходы. Подсчёт даёт вероятности, только когда исходы симметричны; нечестной кости или несимметричной монете нужны общие правила следующей заметки.
• Только конечные пространства исходов. У случайной точки на отрезке или времени ожидания автобуса бесконечно много исходов; отношения количеств там не имеют смысла.
• Легко посчитать дважды. Большинство ошибок подсчёта — это скрытый порядок (одна пара засчитана дважды, как $(a, b)$ и как $(b, a)$) или скрытая различимость (одинаковые объекты считаются разными). Проверка подсчёта на маленьком случае — перечислением или симуляцией — ловит большинство таких ошибок.

Что нужно запомнить#

• Исходы — полные результаты эксперимента; события — множества исходов; «или», «и» и «не» — это объединение, пересечение и дополнение.
• Исходы нужно записывать так, чтобы они были равновозможны, — обычно учитывая порядок и различимость объектов, — и подсчитывать событие внутри этого пространства.
• Правило умножения: $n_1 n_2 \cdots n_k$ исходов для $k$ этапов.
• Выбор $k$ из $n$: $n^k$, $n!/(n-k)!$, $\binom{n}{k}$, $\binom{n+k-1}{k}$ для упорядоченного выбора с возвращением, упорядоченного без возвращения, неупорядоченного без возвращения и неупорядоченного с возвращением; последняя формула считает результаты, а не равновозможные исходы.

Код#

Все подсчёты заметки, проверенные перебором с помощью itertools:

import itertools, math

items = 'abcd'
print(len(list(itertools.product(items, repeat=2))),                # 16  ordered, with replacement
      len(list(itertools.permutations(items, 2))),                  # 12  ordered, without replacement
      len(list(itertools.combinations(items, 2))),                  # 6   unordered, without replacement
      len(list(itertools.combinations_with_replacement(items, 2)))) # 10  unordered, with replacement

dice = list(itertools.product(range(1, 7), repeat=2))
print(round(sum(a + b == 7 for a, b in dice) / 36, 4), sum(6 in d for d in dice))   # 0.1667 11

# two coins: "exactly one head" among the ordered outcomes HH, HT, TH, TT
coins = list(itertools.product('HT', repeat=2))
print(sum(c.count('H') == 1 for c in coins) / len(coins))                 # 0.5

print(round(math.perm(365, 23) / 365**23, 4), math.comb(49, 6))           # 0.4927 13983816

hands = math.comb(52, 5)
two_aces = math.comb(4, 2) * math.comb(48, 3)
print(two_aces, hands, round(two_aces / hands, 4))                        # 103776 2598960 0.0399

# urn with 3 red and 2 blue balls, two draws: both red
print(3 / 5 * 2 / 4, (3 / 5) ** 2)                                        # 0.3 0.36

Дальше#

Подсчёту нужны равновозможные исходы и конечное пространство исходов. Нечестная кость нарушает первое условие, случайная точка на отрезке и время ожидания — второе. Следующая заметка заменяет подсчёт тремя аксиомами, которым должна удовлетворять любая вероятность, объясняет, почему вероятность приписывают одним множествам исходов, а не всем, и выводит правила (дополнение, объединение, формула включений–исключений), которыми подсчёт пользовался без доказательства.

Литература#

• J. K. Blitzstein, J. Hwang. Introduction to Probability, 2nd ed. CRC Press, 2019. Глава 1 (наивное определение вероятности, подсчёт, четыре способа выбора).
• W. Feller. An Introduction to Probability Theory and Its Applications, Vol. 1, 3rd ed. Wiley, 1968. Глава II (элементы комбинаторного анализа, задачи о размещении).
• A. N. Shiryaev. Probability-1, 3rd ed. Springer, 2016. Глава 1, §1 (классические модели и комбинаторика).