🔴 Сложный ⏱️ 55 минут

Теоремы сложения и умножения

📋 Содержание урока

Теоремы сложения и умножения 🎲

Ты выкатил модель в прод. На отложенной выборке она ошибается в 2% случаев — точность 98%, отличный результат, можно идти пить кофе. А через неделю приходит продакт и говорит: «Пользователи жалуются, в каждой второй выдаче что-то не то». Ты лезешь в логи и понимаешь: пользователю показывается не один объект, а батч из 32 штук. И вероятность того, что хотя бы в одном из этих 32 объектов модель ошиблась, — вовсе не 2%. Она равна $1 - 0{,}98^{32} \approx 0{,}476$. Почти половина выдач содержит косяк. Модель не сломалась — сломалась твоя интуиция про то, как вероятности складываются и перемножаются.

Это не редкий и не экзотический случай. Это самая массовая ошибка мышления в прикладной работе с данными. Вероятность одиночного события кажется маленькой и безопасной, но как только событий становится много, а нас интересует «хотя бы одно», маленькие числа начинают вести себя совсем не так, как подсказывает здравый смысл. Ровно та же арифметика объясняет, почему в группе из 23 человек с вероятностью больше половины найдутся двое с одинаковым днём рождения, почему хеш-таблица на миллион корзин начинает ловить коллизии уже на тысяче ключей, и почему дублирование серверов повышает надёжность гораздо сильнее, чем улучшение каждого сервера по отдельности.

В предыдущих трёх уроках мы научились считать вероятность одного события: разобрались, что такое пространство элементарных исходов, освоили классическое определение $P(A) = m/n$ и геометрическую вероятность через отношение мер. Теперь пора собирать события в конструкции. Событие $A$ или событие $B$. Событие $A$ и событие $B$. Хотя бы одно из десяти. Ни одного из ста. Для всех этих конструкций есть ровно два рабочих инструмента — теорема сложения и теорема умножения. Всё остальное в теории вероятностей, включая формулу полной вероятности, формулу Байеса и схему Бернулли, выводится из этих двух теорем комбинированием.

Причём для машинного обучения эти теоремы — не абстрактная формальность, а буквально фундамент. Функция правдоподобия — это произведение вероятностей независимых наблюдений, а логарифмическое правдоподобие (то, что реально минимизируется в градиентном спуске) — сумма логарифмов, получающаяся из теоремы умножения одним взятием логарифма. Наивный байесовский классификатор называется «наивным» ровно потому, что смело применяет теорему умножения для независимых событий там, где независимости на самом деле нет. Давай разберёмся во всём этом по порядку — от простых несовместных событий до тонкого различия между попарной независимостью и независимостью в совокупности, о которое спотыкаются даже опытные аналитики.

🎯 Ты узнаешь:

  • Почему в формуле $P(A \cup B) = P(A) + P(B) - P(A \cap B)$ пересечение вычитается, и как это обобщается на три и более события
  • Как приём «считай через противоположное событие» превращает жуткий перебор в одну строчку арифметики
  • Что такое независимость событий формально ($P(A \cap B) = P(A)P(B)$) и почему она не имеет ничего общего с несовместностью
  • Почему попарная независимость не влечёт независимость в совокупности — с конкретным контрпримером
  • Как из теоремы умножения вырастают функция правдоподобия, наивный байесовский классификатор и расчёт надёжности ансамбля моделей

История: откуда это взялось?

Первым, кто записал правило умножения вероятностей, был Джероламо Кардано — итальянский врач, алгебраист и азартный игрок, который в 1560-х годах написал «Книгу об игре в кости» (Liber de ludo aleae). Книгу, кстати, опубликовали только в 1663 году, почти через сто лет после его смерти. Кардано разбирался с вопросом сугубо практическим: какова вероятность выбросить хотя бы одну шестёрку за несколько бросков? И он честно нащупал ключевую идею — надо считать не «сколько шансов выбросить шестёрку», а «сколько шансов не выбросить ни одной», а потом вычесть из единицы. Правда, в первых расчётах он ошибался, наивно складывая вероятности: раз за один бросок шанс $1/6$, то за три броска будет $3/6$, а за шесть бросков — единица, то есть шестёрка гарантирована. Любой игрок в кости знал, что это неправда, и Кардано пришлось искать правильный ответ — через произведение.

Строгую форму обеим теоремам придали в XVII–XVIII веках. Христиан Гюйгенс в трактате «De ratiociniis in ludo aleae» (1657) — первой печатной книге по теории вероятностей — уже уверенно перемножал вероятности последовательных исходов. Абрахам де Муавр, французский гугенот, бежавший от преследований в Лондон и зарабатывавший консультациями для игроков и страховщиков в кофейне Слотера, в книге «The Doctrine of Chances» (1718) сформулировал правило умножения практически в современном виде и — что важнее — впервые чётко разделил случаи независимых и зависимых событий. Именно де Муавр ввёл в оборот выражение вида «вероятность того, что произойдёт и то, и другое, есть произведение вероятности первого на вероятность второго при условии, что первое произошло» — то есть по сути записал теорему умножения через условную вероятность за полтора века до того, как условная вероятность получила отдельное имя.

Формулу включений-исключений — обобщение теоремы сложения на любое число событий — независимо открывали несколько раз. В комбинаторном виде её опубликовал португальский математик Даниэль Аугусту да Силва в 1854 году, а затем переоткрыл и популяризировал Джеймс Джозеф Сильвестр; сегодня её иногда называют «формулой да Силвы — Сильвестра». Задачу, которая её породила, поставил ещё Пьер Ремон де Монмор в 1708 году: игра «встреча» (le problème des rencontres) — если перетасовать колоду и выкладывать карты, какова вероятность, что хотя бы одна карта окажется на своём «правильном» месте? Ответ оказался удивительным: при росте числа карт вероятность не стремится ни к нулю, ни к единице, а сходится к $1 - 1/e \approx 0{,}632$. Мы решим маленькую версию этой задачи в практике.

Финальную точку поставил Андрей Николаевич Колмогоров в 1933 году в «Основных понятиях теории вероятностей». В его аксиоматике теорема сложения для несовместных событий перестала быть теоремой и стала аксиомой (аксиома аддитивности), а всё остальное — общая формула сложения, формула включений-исключений, свойства противоположного события — выводится из неё чисто логически, без апелляции к костям и картам. Независимость же Колмогоров определил не через «интуитивно не влияют друг на друга», а через равенство $P(A \cap B) = P(A)P(B)$ — и это оказалось решением гениальным: определение стало проверяемым арифметически, а не философски. Именно в таком виде обе теоремы дожили до современного machine learning, где ими пользуются буквально в каждой второй формуле.

Теорема сложения для несовместных событий

Интуиция

Представь, что ты раскладываешь логи по папкам. Есть папка «ошибки таймаута» и папка «ошибки валидации». Каждая запись лога попадает ровно в одну папку — по природе задачи запрос либо отвалился по таймауту, либо не прошёл валидацию, но не то и другое одновременно. Тогда вопрос «какова доля записей, попавших в одну из этих двух папок» имеет очевидный ответ: просто сложи доли. Ничего не считается дважды, потому что папки не пересекаются.

Это и есть вся суть теоремы сложения для несовместных событий. Вероятность ведёт себя как площадь или как масса: если разложить фигуру на непересекающиеся куски, суммарная площадь равна сумме площадей кусков. Кстати, именно эту аналогию мы обкатали в уроке про геометрическую вероятность — там вероятность буквально была площадью. Здесь она работает в общем случае.

Напомню терминологию из урока 226: события $A$ и $B$ называются несовместными, если они не могут произойти одновременно, то есть $A \cap B = \varnothing$. Выпало «2» и выпало «5» на одной кости — несовместные. Пользователь купил и пользователь не купил — несовместные. Пользователь купил и пользователь пришёл с мобильного — вполне себе совместные, тут теорема в такой форме не сработает.

Определение и теорема (сложение для несовместных событий): Если события $A$ и $B$ несовместны, то есть $A \cap B = \varnothing$, то

$$P(A \cup B) = P(A) + P(B).$$

В общем случае для попарно несовместных событий $A_1, A_2, \dots, A_n$ (любые два из них не пересекаются) выполняется

$$P(A_1 \cup A_2 \cup \dots \cup A_n) = P(A_1) + P(A_2) + \dots + P(A_n).$$

Ключевое слово здесь — попарно. Недостаточно, чтобы пересечение всех событий сразу было пустым: нужно, чтобы пустым было пересечение любой пары. Три события могут не иметь общей точки все вместе, но попарно пересекаться — и тогда простое сложение вероятностей даст ерунду.

Два важных следствия, которые понадобятся буквально везде:

  • Если события $A_1, \dots, A_n$ образуют полную группу (попарно несовместны и в объединении дают всё $\Omega$), то $P(A_1) + \dots + P(A_n) = 1$.
  • В частности, для события $A$ и противоположного ему $\bar{A}$: $P(A) + P(\bar{A}) = 1$, откуда $P(\bar{A}) = 1 - P(A)$.

Второе следствие мы через пару разделов превратим в главный вычислительный приём этого урока.

Примеры с разбором

Пример 1 (простой). Классы в датасете.

В обучающей выборке для классификатора изображений 5000 картинок: 2000 кошек, 1800 собак, 1200 птиц. Случайно выбираем одну картинку. Какова вероятность, что это млекопитающее (кошка или собака)?

Разберём по шагам. События:

  • $A$ — «выбрана кошка», $P(A) = 2000/5000 = 0{,}4$;
  • $B$ — «выбрана собака», $P(B) = 1800/5000 = 0{,}36$.

Одна картинка не может быть одновременно кошкой и собакой (в этом датасете классы взаимоисключающие), значит $A$ и $B$ несовместны. Применяем теорему сложения:

$$P(A \cup B) = P(A) + P(B) = 0{,}4 + 0{,}36 = 0{,}76.$$

Проверим ответ другим способом: благоприятных исходов $2000 + 1800 = 3800$, всего $5000$, значит $3800/5000 = 0{,}76$. Совпало.

Ответ: $0{,}76$.

Пример 2 (средний). Кубик и полная группа.

Бросают игральную кость. Найти вероятность события «выпало число, меньшее 3, или число, большее 4».

События $A = \{1, 2\}$ и $B = \{5, 6\}$ явно не пересекаются. $P(A) = 2/6 = 1/3$, $P(B) = 2/6 = 1/3$.

$$P(A \cup B) = \frac{1}{3} + \frac{1}{3} = \frac{2}{3}.$$

А теперь фокус для самопроверки: третье событие $C = \{3, 4\}$ дополняет $A$ и $B$ до полной группы. Значит $P(A) + P(B) + P(C)$ обязано быть равно единице: $1/3 + 1/3 + 1/3 = 1$. Сходится, ошибки в расчёте нет.

Ответ: $2/3$.

Пример 3 (сложный). Тайм-аут батча в распределённом обучении.

Обучение идёт на кластере. Батч может быть отброшен по трём взаимоисключающим причинам: сетевой таймаут (вероятность $0{,}004$), нехватка памяти на GPU ($0{,}002$), повреждённый файл в шарде ($0{,}0005$). Причины по построению системы взаимоисключающие: как только сработала одна, батч отбрасывается и остальные проверки не выполняются. Какова вероятность, что случайно взятый батч будет отброшен? А какова вероятность, что он пройдёт нормально?

Три причины попарно несовместны, значит вероятности складываются:

$$P(\text{отброшен}) = 0{,}004 + 0{,}002 + 0{,}0005 = 0{,}0065.$$

Событие «прошёл нормально» противоположно событию «отброшен», поэтому

$$P(\text{прошёл}) = 1 - 0{,}0065 = 0{,}9935.$$

Обрати внимание на важную деталь: несовместность здесь возникла не сама по себе, а из-за архитектуры системы — проверки идут последовательно и первая же сработавшая прерывает остальные. Если бы система собирала все причины отказа независимо (например, диагностический режим, который проверяет всё до конца), события стали бы совместными: батч мог бы одновременно и упереться в память, и содержать битый файл. И тогда простое сложение завысило бы ответ. Всегда спрашивай себя: точно ли эти события не могут случиться вместе, или мне просто так удобнее считать?

Ответ: $0{,}0065$ и $0{,}9935$.

Почему это важно

Теорема сложения для несовместных событий — это тот кирпич, из которого строится вообще всё. Любой софтмакс на выходе нейросети — это набор вероятностей классов, которые по построению несовместны, и их сумма равна единице ровно из-за этой теоремы. Когда ты хочешь спросить «какова вероятность, что модель отнесла объект к одному из топ-3 классов», ты просто складываешь три числа из софтмакса — и имеешь на это полное право, потому что классы взаимоисключающие. А вот если задача multi-label (у объекта может быть несколько тегов одновременно), классы уже не несовместны, сигмоиды на выходе не обязаны суммироваться к единице, и складывать их напрямую нельзя. Это ровно то различие, из-за которого путают softmax и sigmoid в последнем слое.

Общая теорема сложения: почему вычитается пересечение

Интуиция

Теперь убираем условие несовместности. Представь отдел из 30 человек. Питон знают 18 человек, SQL знают 20. Сколько человек знают хотя бы один из двух языков? Соблазн сказать «$18 + 20 = 38$», но в отделе всего 30 человек — ответ явно бредовый. Что произошло? Люди, знающие оба языка, попали в счёт дважды: один раз как «питонисты», второй раз как «сиквельщики». Чтобы починить, надо вычесть их ровно один раз.

Самая наглядная модель — диаграмма Эйлера — Венна. Нарисуй два перекрывающихся круга $A$ и $B$. Площадь объединения — это площадь первого круга плюс площадь второго, но линза пересечения при таком сложении покрывается дважды. Вычитаем её один раз — получаем честную площадь объединения. Вероятность ведёт себя как площадь, поэтому формула буквально та же.

Есть и второй способ увидеть то же самое — через разложение на несовместные куски, и он мне нравится больше, потому что он выводит формулу, а не иллюстрирует. Объединение $A \cup B$ можно разрезать на три непересекающиеся части:

  • «только $A$»: $A \setminus B$;
  • «только $B$»: $B \setminus A$;
  • «и $A$, и $B$»: $A \cap B$.

По теореме сложения для несовместных: $P(A \cup B) = P(A \setminus B) + P(B \setminus A) + P(A \cap B)$. Но $P(A) = P(A \setminus B) + P(A \cap B)$, откуда $P(A \setminus B) = P(A) - P(A \cap B)$, и аналогично $P(B \setminus A) = P(B) - P(A \cap B)$. Подставляем:

$$P(A \cup B) = \big(P(A) - P(A\cap B)\big) + \big(P(B) - P(A\cap B)\big) + P(A \cap B) = P(A) + P(B) - P(A \cap B).$$

Вот и вся тайна вычитания пересечения: оно вычитается ровно один раз, потому что при сложении $P(A) + P(B)$ было посчитано ровно дважды.

Теорема (общая теорема сложения): Для любых двух событий $A$ и $B$

$$P(A \cup B) = P(A) + P(B) - P(A \cap B).$$

Если $A$ и $B$ несовместны, то $P(A \cap B) = P(\varnothing) = 0$, и формула превращается в частный случай $P(A \cup B) = P(A) + P(B)$.

Из общей формулы немедленно следует полезное неравенство, которое в теории вероятностей называют неравенством Буля (или union bound):

$$P(A \cup B) \leq P(A) + P(B),$$

и в общем случае $P(A_1 \cup \dots \cup A_n) \leq P(A_1) + \dots + P(A_n)$. Простое сложение всегда даёт оценку сверху. Это не «неточная формула», это законная граница, и в теоретическом машинном обучении она используется постоянно: например, при выводе границ обобщающей способности через VC-размерность, где надо оценить вероятность того, что хотя бы одна гипотеза из огромного семейства окажется плохой.

Примеры с разбором

Пример 1 (простой). Кубик: чётное или кратное трём.

Бросают игральную кость. $A$ — «выпало чётное число», $B$ — «выпало число, кратное 3». Найти $P(A \cup B)$.

Разберём по шагам. $A = \{2, 4, 6\}$, значит $P(A) = 3/6 = 1/2$. $B = \{3, 6\}$, значит $P(B) = 2/6 = 1/3$. Пересечение $A \cap B = \{6\}$ — шестёрка и чётная, и кратна трём, — значит $P(A \cap B) = 1/6$.

$$P(A \cup B) = \frac{1}{2} + \frac{1}{3} - \frac{1}{6} = \frac{3 + 2 - 1}{6} = \frac{4}{6} = \frac{2}{3}.$$

Проверим прямым перебором: $A \cup B = \{2, 3, 4, 6\}$ — четыре исхода из шести, $4/6 = 2/3$. Совпало.

Ответ: $2/3$.

Пример 2 (средний). Признаки с пропусками.

В таблице данных 1000 строк. В колонке «возраст» пропуск у 120 строк, в колонке «доход» — у 200 строк, причём у 45 строк пропущены обе колонки. Какова вероятность, что случайно взятая строка содержит хотя бы один пропуск в этих двух колонках? А какова вероятность, что строка полностью заполнена по обеим колонкам?

Обозначим: $A$ — «пропуск в возрасте», $P(A) = 0{,}12$; $B$ — «пропуск в доходе», $P(B) = 0{,}2$; $P(A \cap B) = 0{,}045$.

Хотя бы один пропуск — это объединение:

$$P(A \cup B) = 0{,}12 + 0{,}2 - 0{,}045 = 0{,}275.$$

Полностью заполненная строка — это противоположное событие к объединению:

$$P(\overline{A \cup B}) = 1 - 0{,}275 = 0{,}725.$$

Кстати, сразу маленькое практическое наблюдение: если бы ты по наивности сложил $0{,}12 + 0{,}2 = 0{,}32$, ты бы решил, что после дропа строк с пропусками потеряешь 32% данных, а на самом деле теряешь 27,5%. На выборке в миллион строк это разница в 45 тысяч наблюдений — вполне ощутимо.

Ответ: $0{,}275$ и $0{,}725$.

Пример 3 (сложный). Восстановление пересечения.

Известно, что $P(A) = 0{,}6$, $P(B) = 0{,}5$, $P(A \cup B) = 0{,}8$. Найти: (а) $P(A \cap B)$; (б) вероятность того, что произойдёт ровно одно из двух событий; (в) вероятность того, что произойдёт $A$, но не $B$.

Общая формула сложения — это уравнение с четырьмя величинами, любую из которых можно найти, зная три остальные. Выражаем пересечение:

$$P(A \cap B) = P(A) + P(B) - P(A \cup B) = 0{,}6 + 0{,}5 - 0{,}8 = 0{,}3.$$

(б) «Ровно одно» — это объединение без пересечения, то есть два несовместных куска «только $A$» и «только $B$». Их суммарная вероятность:

$$P(\text{ровно одно}) = P(A \cup B) - P(A \cap B) = 0{,}8 - 0{,}3 = 0{,}5.$$

Можно и по-другому, через формулу: $P(A) + P(B) - 2P(A\cap B) = 0{,}6 + 0{,}5 - 0{,}6 = 0{,}5$. Обрати внимание: здесь пересечение вычитается дважды — один раз чтобы убрать двойной счёт, второй раз чтобы исключить сам случай «оба сразу». Совпало.

(в) «$A$, но не $B$» — это $A \setminus B$:

$$P(A \setminus B) = P(A) - P(A \cap B) = 0{,}6 - 0{,}3 = 0{,}3.$$

Проверим целостность картины. Четыре несовместных куска разбивают всё $\Omega$: «только $A$» $= 0{,}3$, «только $B$» $= 0{,}5 - 0{,}3 = 0{,}2$, «оба» $= 0{,}3$, «ни одного» $= 1 - 0{,}8 = 0{,}2$. Сумма: $0{,}3 + 0{,}2 + 0{,}3 + 0{,}2 = 1$. Всё сходится.

Ответ: (а) $0{,}3$; (б) $0{,}5$; (в) $0{,}3$.

Почему это важно

Разбиение вероятностного пространства на четыре куска из последнего примера — это, по сути, матрица ошибок (confusion matrix) в замаскированном виде. Возьми $A$ = «модель предсказала положительный класс», $B$ = «объект действительно положительный». Тогда «оба» — это true positive, «только $A$» — false positive, «только $B$» — false negative, «ни одного» — true negative. Precision, recall, F1 — всё это отношения между этими четырьмя вероятностями. Когда ты в следующий раз будешь выводить, почему $\text{recall} = TP/(TP+FN)$, ты по сути будешь применять общую теорему сложения. И понимание, что $P(A) + P(B)$ считает пересечение дважды, спасает от классической ошибки «сложил precision и recall, получил больше единицы, испугался».

Три события и формула включений-исключений

Интуиция

Что будет, если событий три? Логика та же самая, но бухгалтерия чуть хитрее. Нарисуй три перекрывающихся круга. При сложении $P(A) + P(B) + P(C)$:

  • области «только $A$», «только $B$», «только $C$» посчитаны по одному разу — это правильно;
  • области попарных пересечений (без третьего события) посчитаны дважды — надо убрать по одному разу;
  • центральная область, где пересекаются все три, посчитана трижды — казалось бы, надо убрать дважды.

Вычитаем три попарных пересечения: $-P(A\cap B) - P(A \cap C) - P(B \cap C)$. Но центральная область входит в каждое из трёх попарных пересечений, значит мы вычли её три раза. Итого центр посчитан $3 - 3 = 0$ раз — он вообще пропал! Приходится добавить его обратно один раз: $+P(A \cap B \cap C)$.

Такой танец «прибавили — вычли — прибавили» и называется формулой включений-исключений. Знаки чередуются, и это не случайность: каждая точка пространства должна быть в итоге посчитана ровно один раз, а чередование знаков биномиальных коэффициентов как раз обеспечивает это тождество.

Теорема (включения-исключения для трёх событий):

$$P(A \cup B \cup C) = P(A) + P(B) + P(C) - P(A \cap B) - P(A \cap C) - P(B \cap C) + P(A \cap B \cap C).$$

В общем случае для $n$ событий:

$$P\Big(\bigcup_{i=1}^{n} A_i\Big) = \sum_i P(A_i) - \sum_{i

Сразу предупрежу: для $n$ событий в формуле $2^n - 1$ слагаемых. При $n = 10$ это уже 1023 слагаемых, при $n = 20$ — больше миллиона. Пользоваться формулой включений-исключений «в лоб» при большом числе событий практически невозможно — и именно поэтому существует приём через противоположное событие, о котором следующий раздел. Формула включений-исключений хороша для трёх-четырёх событий и для теоретических выкладок, а не для реальных вычислений на больших $n$.

Примеры с разбором

Пример 1 (простой). Три канала трафика.

За месяц на сайт заходили пользователи из трёх источников. Доля пользователей, побывавших в поиске, — $0{,}5$; в соцсетях — $0{,}4$; в рассылке — $0{,}3$. Пересечения: поиск и соцсети — $0{,}2$; поиск и рассылка — $0{,}15$; соцсети и рассылка — $0{,}1$; все три канала — $0{,}05$. Какова доля пользователей, побывавших хотя бы в одном канале?

Подставляем в формулу напрямую:

$$P(A \cup B \cup C) = 0{,}5 + 0{,}4 + 0{,}3 - 0{,}2 - 0{,}15 - 0{,}1 + 0{,}05.$$

Считаем по шагам: сумма одиночных $= 1{,}2$; сумма попарных $= 0{,}45$; $1{,}2 - 0{,}45 = 0{,}75$; $0{,}75 + 0{,}05 = 0{,}8$.

Ответ: $0{,}8$.

Пример 2 (средний). Проверка на согласованность данных.

Аналитик принёс цифры: $P(A) = 0{,}3$, $P(B) = 0{,}3$, $P(C) = 0{,}3$, все попарные пересечения по $0{,}25$, тройное $0{,}2$. Может ли такое быть?

Тут формула включений-исключений работает как детектор вранья. Считаем:

$$P(A\cup B \cup C) = 0{,}9 - 0{,}75 + 0{,}2 = 0{,}35.$$

Число вроде бы приличное, меньше единицы. Но проверим кусочки по отдельности. Вероятность «только $A$» равна

$$P(A) - P(A\cap B) - P(A \cap C) + P(A \cap B \cap C) = 0{,}3 - 0{,}25 - 0{,}25 + 0{,}2 = 0.$$

Ноль — само по себе допустимо. А вот вероятность «$A$ и $B$, но не $C$»:

$$P(A \cap B) - P(A\cap B \cap C) = 0{,}25 - 0{,}2 = 0{,}05.$$

Тоже допустимо. Тогда $P(A) = P(\text{только }A) + P(A \cap B \setminus C) + P(A \cap C \setminus B) + P(A\cap B \cap C) = 0 + 0{,}05 + 0{,}05 + 0{,}2 = 0{,}3$. Сходится. Значит набор чисел на самом деле корректный, хотя выглядел подозрительно.

Ответ: $P(A \cup B \cup C) = 0{,}35$, набор данных согласован.

Мораль примера: одной проверки «$P \le 1$» мало. Надёжный способ проверить согласованность — разложить всё на элементарные непересекающиеся куски и убедиться, что каждый неотрицателен и сумма равна единице.

Пример 3 (сложный). Кратные числа.

Из чисел от 1 до 100 случайно выбирают одно. Какова вероятность, что оно делится на 2, на 3 или на 5?

События: $A$ — делится на 2, $B$ — на 3, $C$ — на 5. Считаем количества делением с отбрасыванием дробной части:

  • кратных 2: $\lfloor 100/2 \rfloor = 50$;
  • кратных 3: $\lfloor 100/3 \rfloor = 33$;
  • кратных 5: $\lfloor 100/5 \rfloor = 20$;
  • кратных 6 (то есть 2 и 3): $\lfloor 100/6 \rfloor = 16$;
  • кратных 10 (2 и 5): $\lfloor 100/10 \rfloor = 10$;
  • кратных 15 (3 и 5): $\lfloor 100/15 \rfloor = 6$;
  • кратных 30 (2, 3 и 5): $\lfloor 100/30 \rfloor = 3$.

Количество благоприятных исходов:

$$50 + 33 + 20 - 16 - 10 - 6 + 3 = 74.$$

Считаем аккуратно: $50 + 33 + 20 = 103$; $16 + 10 + 6 = 32$; $103 - 32 = 71$; $71 + 3 = 74$.

$$P = \frac{74}{100} = 0{,}74.$$

Ответ: $0{,}74$.

Это, кстати, ровно тот механизм, по которому работает решето Эратосфена и оценка количества простых чисел — включения-исключения по кратности делителям. А в информатике на этой же формуле построен подсчёт мощности объединения множеств в аналитических запросах.

Почему это важно

В аналитике данных формула включений-исключений — это то, чем считаются пересечения аудиторий. Сколько уникальных пользователей увидели хотя бы одну из трёх рекламных кампаний? Если просто сложить охваты трёх кампаний, получишь завышенную цифру (это и есть знаменитый «раздутый охват» в рекламных отчётах). Вычесть пересечения — единственный честный способ. Ровно та же формула лежит в основе структуры данных HyperLogLog для приближённого подсчёта уникальных элементов: объединение считается напрямую, а пересечение — через формулу включений-исключений, из-за чего ошибка пересечения оказывается больше, чем ошибка объединения. Знание формулы объясняет, почему в аналитических системах пересечения аудиторий всегда менее точны, чем объединения.

Противоположное событие: приём «хотя бы один»

Интуиция

Есть задачи, где прямой счёт превращается в кошмар. «Какова вероятность, что при 10 бросках монеты хотя бы раз выпадет орёл?» Прямо в лоб надо разобрать случаи: ровно один орёл, ровно два, ..., ровно десять. Десять слагаемых, каждое со своими комбинациями. А через противоположное событие — одна строчка.

Секрет в том, что у слова «хотя бы один» есть очень простое отрицание: ни одного. Не «ровно ноль или ровно один», не что-то составное — именно строго «ни одного». И вероятность «ни одного» обычно считается элементарно, потому что это одно конкретное условие на каждый объект, а не хитрая комбинация.

Правило: Для любого события $A$

$$P(\bar{A}) = 1 - P(A).$$

В частности, если $A$ — «произошло хотя бы одно из событий $A_1, \dots, A_n$», то $\bar{A}$ — «не произошло ни одного», то есть $\bar{A} = \bar{A_1} \cap \bar{A_2} \cap \dots \cap \bar{A_n}$, и

$$P(\text{хотя бы одно}) = 1 - P(\bar{A_1} \cap \dots \cap \bar{A_n}).$$

Если события $A_1, \dots, A_n$ независимы в совокупности (об этом ниже) с вероятностями $p_1, \dots, p_n$, то

$$P(\text{хотя бы одно}) = 1 - (1-p_1)(1-p_2)\cdots(1-p_n).$$

А если все $p_i = p$ одинаковы: $P(\text{хотя бы одно}) = 1 - (1-p)^n$.

Формула $1 - (1-p)^n$ — самая полезная формула в этом уроке. Запомни её и научись видеть ситуации, в которых она применима. Её главное свойство: при фиксированном $p > 0$ и растущем $n$ величина $(1-p)^n$ стремится к нулю (потому что $0 < 1-p < 1$), а значит вероятность «хотя бы одного» стремится к единице. Что бы ни было редким — при достаточном числе попыток оно почти наверняка случится хотя бы раз.

Есть удобная оценка для быстрого счёта в уме. При малом $p$ и не слишком большом $np$:

$$1 - (1-p)^n \approx 1 - e^{-np}.$$

Это следует из $\ln(1-p) \approx -p$ при малых $p$. Отсюда народное правило: если $np \approx 1$, то вероятность «хотя бы одного» примерно $1 - 1/e \approx 0{,}63$; если $np \approx 3$, то около $0{,}95$; если $np \approx 5$, то около $0{,}993$.

Примеры с разбором

Пример 1 (простой). Хотя бы одна шестёрка.

Кость бросают 4 раза. Какова вероятность выбросить хотя бы одну шестёрку?

Прямой путь ужасен (ровно одна, ровно две, ровно три, ровно четыре шестёрки — четыре слагаемых с комбинациями). Через дополнение — легко. Вероятность НЕ выбросить шестёрку в одном броске: $5/6$. Броски независимы, поэтому вероятность не выбросить ни разу за 4 броска:

$$\left(\frac{5}{6}\right)^4 = \frac{625}{1296} \approx 0{,}4823.$$

Значит:

$$P(\text{хотя бы одна}) = 1 - \frac{625}{1296} = \frac{671}{1296} \approx 0{,}5177.$$

Именно эту задачу разбирал Кардано и именно на ней он ошибся, получив $4 \cdot 1/6 = 2/3$. Правильный ответ чуть больше половины, а не две трети. Разница в 15 процентных пунктов — и на длинной дистанции игры в кости она разоряет.

Ответ: $\approx 0{,}518$.

Пример 2 (средний). Ошибка на батче — тот самый случай из вступления.

Модель ошибается на отдельном объекте с вероятностью $p = 0{,}02$. Пользователю показывается батч из $n = 32$ объектов. Ошибки на разных объектах будем считать независимыми. Какова вероятность, что в выдаче есть хотя бы одна ошибка?

$$P = 1 - (1 - 0{,}02)^{32} = 1 - 0{,}98^{32}.$$

Считаем $0{,}98^{32}$ последовательным возведением в квадрат:

  • $0{,}98^2 = 0{,}9604$;
  • $0{,}98^4 = 0{,}9604^2 = 0{,}92237$;
  • $0{,}98^8 = 0{,}92237^2 = 0{,}85076$;
  • $0{,}98^{16} = 0{,}85076^2 = 0{,}72380$;
  • $0{,}98^{32} = 0{,}72380^2 = 0{,}52388$.
$$P = 1 - 0{,}52388 = 0{,}47612 \approx 0{,}476.$$

Быстрая проверка через приближение: $np = 32 \cdot 0{,}02 = 0{,}64$, и $1 - e^{-0{,}64} = 1 - 0{,}527 = 0{,}473$. Близко к точному ответу, приближение работает.

Ответ: $\approx 0{,}476$, то есть почти половина батчей содержит хотя бы одну ошибку.

Это тот самый эффект, который ломает интуицию. «Точность 98%» звучит замечательно ровно до момента, когда ты понимаешь, что пользователь оценивает не объект, а всю выдачу целиком. Чтобы вероятность безошибочного батча из 32 объектов была хотя бы 90%, нужно $0{,}9 \le (1-p)^{32}$, то есть $p \le 1 - 0{,}9^{1/32} \approx 0{,}0033$ — точность должна вырасти с 98% до 99,67%. Улучшение метрики на объекте в шесть раз ради того, чтобы метрика на выдаче стала приличной.

Пример 3 (сложный). Сколько объектов выдержит модель.

Модель ошибается с вероятностью $p = 0{,}01$ на объекте. Начиная с какого размера батча $n$ вероятность «хотя бы одной ошибки в батче» превысит $0{,}99$?

Нужно решить неравенство:

$$1 - 0{,}99^n \geq 0{,}99 \quad \Longleftrightarrow \quad 0{,}99^n \leq 0{,}01.$$

Логарифмируем (натуральный логарифм монотонно возрастает, а $\ln 0{,}99 < 0$, поэтому знак неравенства перевернётся при делении):

$$n \ln 0{,}99 \leq \ln 0{,}01 \quad \Longrightarrow \quad n \geq \frac{\ln 0{,}01}{\ln 0{,}99} = \frac{-4{,}60517}{-0{,}0100503} \approx 458{,}2.$$

Значит $n = 459$.

Проверим границу приближением: $1 - e^{-0{,}01n} \geq 0{,}99$ даёт $e^{-0{,}01n} \le 0{,}01$, то есть $0{,}01n \geq 4{,}605$, $n \geq 460{,}5$. Приближение чуть завышает (потому что $\ln(1-p)$ по модулю чуть больше $p$), но порядок величины тот же — около 460.

Ответ: $n = 459$.

Смысл этого числа стоит осознать: на выборке всего в 459 объектов модель с точностью 99% практически гарантированно (с вероятностью 99%) ошибётся хотя бы раз. Именно поэтому в задачах, где недопустима ни одна ошибка (медицинская диагностика, автопилот, финансовые транзакции), не бывает «достаточно хорошей точности» — там строят каскады, пороги отказа от ответа и человеческий контроль. Одиночная модель, какой бы точной она ни была, при большом потоке событий обязательно наберёт ошибок.

Почему это важно

Приём «через противоположное» — это не трюк для экзамена, а способ мышления. Каждый раз, когда в задаче звучит «хотя бы один», «хотя бы раз», «не менее одного», «встретится где-нибудь», твоя первая мысль должна быть: посчитаю вероятность «ни разу» и вычту из единицы. Этот приём буквально экономит часы. А формула $1 - (1-p)^n$ объясняет целый класс явлений: почему при росте объёма данных обязательно всплывают редкие баги, почему при переборе тысяч гипотез обязательно найдётся «статистически значимая» ерунда (проблема множественных сравнений и поправка Бонферрони — это оборотная сторона той же формулы), почему кеш обязательно словит коллизию, и почему любую систему в продакшене рано или поздно кладёт «маловероятное» стечение обстоятельств.

Независимость событий

Интуиция

Интуитивно независимость — это «одно не влияет на другое». Ты бросаешь монету в Москве, а я бросаю кость в Новосибирске: то, что у тебя выпал орёл, никак не меняет мои шансы выбросить шестёрку. Это понятно на пальцах, но такое определение невозможно проверить арифметически. Что значит «не влияет»? А если влияет чуть-чуть? А как быть, когда речь про признаки в датасете, где никакой физической причинности вообще нет?

Колмогоров решил проблему радикально: он определил независимость через формулу, а не через смысл. Событие $A$ не влияет на $B$ тогда и только тогда, когда доля исходов $A$ внутри $B$ такая же, как и во всём пространстве. Если перевести это на язык вероятностей, получится равенство $P(A \cap B) = P(A) \cdot P(B)$.

Давай проверим, что оно действительно выражает «не влияет». Возьмём пространство и посмотрим на кусок $B$. Внутри $B$ доля исходов, где вдобавок случилось $A$, равна $P(A\cap B)/P(B)$ — это и есть условная вероятность $P(A \mid B)$, к которой мы вплотную подойдём в следующем уроке. Если эта доля равна $P(A)$, то знание о том, что $B$ произошло, ничего не поменяло в наших оценках. А равенство $P(A\cap B)/P(B) = P(A)$ — это ровно $P(A \cap B) = P(A)P(B)$. Формула и смысл совпали.

Определение: События $A$ и $B$ называются независимыми, если

$$P(A \cap B) = P(A) \cdot P(B).$$

В противном случае события называются зависимыми.

Обрати внимание: определение симметрично. Если $A$ независимо от $B$, то и $B$ независимо от $A$ — никакого «направления влияния» здесь нет, и никакой причинности тоже. Независимость — это чисто арифметическое свойство трёх чисел: $P(A)$, $P(B)$ и $P(A \cap B)$.

Теперь — про главную путаницу этого урока.

🚨 Независимость и несовместность — это НЕ одно и то же. Более того, они почти противоположны.

Несовместность: $A \cap B = \varnothing$, события не могут случиться вместе. Независимость: $P(A\cap B) = P(A)P(B)$, наступление одного не меняет шансов другого.

Смотри, что происходит, если события несовместны и при этом $P(A) > 0$, $P(B) > 0$. Тогда $P(A \cap B) = 0$, а $P(A)P(B) > 0$. Равенство не выполняется — значит несовместные события с ненулевыми вероятностями всегда зависимы! И это логично: если ты знаешь, что произошло $A$, то ты точно знаешь, что $B$ не произошло. Куда уж сильнее влияние.

Следствие: Если $P(A) > 0$ и $P(B) > 0$, то события $A$ и $B$ не могут быть одновременно несовместными и независимыми.

Полезное свойство, которое часто нужно в задачах:

Теорема: Если $A$ и $B$ независимы, то независимы также пары $\bar{A}$ и $B$, $A$ и $\bar{B}$, $\bar{A}$ и $\bar{B}$.

Докажем первое (остальные — по аналогии). Разложим $B$ на две несовместные части: $B = (A \cap B) \cup (\bar{A} \cap B)$. По теореме сложения $P(B) = P(A\cap B) + P(\bar{A} \cap B)$, откуда

$$P(\bar{A} \cap B) = P(B) - P(A \cap B) = P(B) - P(A)P(B) = P(B)\big(1 - P(A)\big) = P(\bar{A})P(B).$$

Что и требовалось. Это свойство — рабочая лошадка для схемы «хотя бы один»: именно оно позволяет писать $P(\bar{A_1} \cap \dots \cap \bar{A_n}) = (1-p_1)\cdots(1-p_n)$, когда исходные события независимы.

Независимость в совокупности

Для нескольких событий определение усложняется, и вот здесь надо быть внимательным.

Определение: События $A_1, A_2, \dots, A_n$ называются независимыми в совокупности, если для любого поднабора индексов $i_1 < i_2 < \dots < i_k$ выполняется

$$P(A_{i_1} \cap A_{i_2} \cap \dots \cap A_{i_k}) = P(A_{i_1}) \cdot P(A_{i_2}) \cdots P(A_{i_k}).$$

События называются попарно независимыми, если равенство выполняется только для всех пар $i < j$.

То есть для трёх событий независимость в совокупности требует выполнения четырёх равенств: три попарных плюс одно тройное. Попарная независимость требует только трёх первых. Разница выглядит формальной, но она принципиальна — контрпример будет в отдельном разделе, и он того стоит.

Примеры с разбором

Пример 1 (простой). Проверка по определению.

Даны $P(A) = 0{,}5$, $P(B) = 0{,}4$. Независимы ли события, если (а) $P(A\cap B) = 0{,}2$; (б) $P(A \cap B) = 0{,}25$; (в) $P(A \cup B) = 0{,}75$?

(а) Считаем произведение: $P(A)P(B) = 0{,}5 \cdot 0{,}4 = 0{,}2$. Совпало с $P(A \cap B)$ — события независимы.

(б) $P(A\cap B) = 0{,}25 \neq 0{,}2$ — события зависимы. Причём $0{,}25 > 0{,}2$: события «притягиваются», наступление одного повышает шанс другого.

(в) Пересечение не дано напрямую, восстанавливаем через теорему сложения: $P(A \cap B) = 0{,}5 + 0{,}4 - 0{,}75 = 0{,}15$. Сравниваем с $0{,}2$: $0{,}15 < 0{,}2$ — события зависимы и «отталкиваются».

Ответ: (а) независимы; (б) зависимы; (в) зависимы.

Пример 2 (средний). Признаки в датасете.

В выборке из 1000 клиентов банка: 300 имеют высшее образование, 200 взяли кредит, из них 60 — с высшим образованием. Можно ли считать образование и факт взятия кредита независимыми признаками?

Обозначим $A$ — «есть высшее», $B$ — «взял кредит».

$$P(A) = \frac{300}{1000} = 0{,}3, \quad P(B) = \frac{200}{1000} = 0{,}2, \quad P(A\cap B) = \frac{60}{1000} = 0{,}06.$$

Проверяем: $P(A)P(B) = 0{,}3 \cdot 0{,}2 = 0{,}06$. Равенство выполняется точно.

Ответ: в этой выборке признаки независимы.

Тут стоит сделать честную оговорку. Мы проверили независимость на выборке, а не в генеральной совокупности. Реальные данные почти никогда не дают точного равенства: если бы вместо 60 оказалось 63, мы бы формально получили зависимость, хотя расхождение может быть чистой случайностью выборки. Вопрос «достаточно ли отклонение велико, чтобы говорить о реальной зависимости» решается статистическими критериями — например, критерием хи-квадрат для таблиц сопряжённости. В этом уроке мы работаем с точными вероятностями, но в проде помни: наблюдаемая на данных «зависимость» может быть шумом.

Пример 3 (сложный). Два признака и объединение.

Известно, что события $A$ и $B$ независимы, $P(A) = 0{,}4$, $P(A \cup B) = 0{,}64$. Найти $P(B)$.

Пишем общую теорему сложения и подставляем независимость:

$$P(A\cup B) = P(A) + P(B) - P(A)P(B).$$

Обозначим $x = P(B)$:

$$0{,}64 = 0{,}4 + x - 0{,}4x = 0{,}4 + 0{,}6x.$$

Отсюда $0{,}6x = 0{,}24$, значит $x = 0{,}4$.

Проверим: $P(A\cap B) = 0{,}4 \cdot 0{,}4 = 0{,}16$, и $P(A\cup B) = 0{,}4 + 0{,}4 - 0{,}16 = 0{,}64$. Сходится.

Кстати, есть красивая формула-ярлык для независимых событий, вытекающая из приёма «через противоположное»:

$$P(A \cup B) = 1 - P(\bar{A})P(\bar{B}) = 1 - (1 - 0{,}4)(1 - 0{,}4) = 1 - 0{,}36 = 0{,}64.$$

Тот же ответ за одну строчку. Для независимых событий объединение почти всегда быстрее считать через дополнение.

Ответ: $P(B) = 0{,}4$.

Почему это важно

Определение независимости через произведение — это точка, где теория вероятностей стыкуется с машинным обучением напрямую. Вся конструкция «признаки независимы при условии класса» в наивном байесовском классификаторе — это буквально применение этого равенства $k$ раз подряд. Матрица корреляций, которую ты строишь перед обучением модели, — это попытка нащупать зависимость между признаками (правда, корреляция ловит только линейную зависимость: нулевая корреляция не гарантирует независимости, а вот независимость гарантирует нулевую корреляцию). И различие «независимые — несовместные» объясняет, почему one-hot-кодирование категориального признака порождает максимально зависимые между собой колонки: они несовместны по построению (ровно одна единица в строке), а значит зависимы до предела — отсюда мультиколлинеарность и необходимость выбрасывать одну колонку в линейных моделях.

Теорема умножения: независимые и зависимые события

Интуиция

Теорема сложения отвечает на вопрос «или». Теорема умножения отвечает на вопрос «и».

Представь, что вероятность — это доля. Событие $A$ занимает 40% пространства. Теперь мы хотим долю тех исходов, где случилось и $A$, и $B$. Если события независимы, то внутри куска $A$ событие $B$ занимает ту же долю, что и везде — скажем, 30%. Значит от всего пространства это $0{,}4 \cdot 0{,}3 = 0{,}12$. Умножение долей — вот вся механика.

А если события зависимы? Тогда внутри $A$ доля $B$ уже другая, и её надо взять именно ту, что внутри $A$. Эта «доля $B$ внутри $A$» и называется условной вероятностью $P(B \mid A)$. Полный разбор условной вероятности — со всеми её свойствами, интуицией и подвохами — ждёт тебя в следующем уроке 230; здесь нам нужен только рабочий минимум.

Определение (условная вероятность, рабочий минимум): Условной вероятностью события $B$ при условии, что событие $A$ произошло, называется

$$P(B \mid A) = \frac{P(A \cap B)}{P(A)}, \quad \text{при } P(A) > 0.$$

Читается: «вероятность $B$ при условии $A$». Смысл — доля исходов $B$ внутри урезанного пространства $A$.

Из этого определения теорема умножения получается элементарным переносом знаменателя.

Теорема (умножения вероятностей): Для любых событий $A$ и $B$ с $P(A) > 0$

$$P(A \cap B) = P(A) \cdot P(B \mid A) = P(B) \cdot P(A \mid B).$$

Если события независимы, то $P(B\mid A) = P(B)$, и формула упрощается:

$$P(A \cap B) = P(A) \cdot P(B).$$

Для $n$ событий (цепное правило, chain rule):

$$P(A_1 \cap A_2 \cap \dots \cap A_n) = P(A_1)\cdot P(A_2 \mid A_1) \cdot P(A_3 \mid A_1 \cap A_2)\cdots P(A_n \mid A_1 \cap \dots \cap A_{n-1}).$$

Если события независимы в совокупности:

$$P(A_1 \cap \dots \cap A_n) = P(A_1)P(A_2)\cdots P(A_n).$$

Цепное правило заслуживает отдельного внимания: оно верно всегда, без каких-либо предположений. Это просто последовательное применение определения условной вероятности, где каждый следующий множитель учитывает всё, что уже произошло. И именно цепное правило — математическая основа авторегрессионных языковых моделей: вероятность текста $w_1 w_2 \dots w_n$ раскладывается как

$$P(w_1, \dots, w_n) = P(w_1) \cdot P(w_2 \mid w_1) \cdot P(w_3 \mid w_1, w_2) \cdots P(w_n \mid w_1, \dots, w_{n-1}),$$

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

Примеры с разбором

Пример 1 (простой). Независимые испытания.

Два стрелка независимо стреляют по мишени. Первый попадает с вероятностью $0{,}8$, второй — с вероятностью $0{,}7$. Найти вероятность того, что: (а) оба попали; (б) оба промахнулись; (в) попал хотя бы один; (г) попал ровно один.

Обозначим $A$ — попал первый, $B$ — попал второй. События независимы.

(а) $P(A \cap B) = 0{,}8 \cdot 0{,}7 = 0{,}56$.

(б) $P(\bar{A} \cap \bar{B}) = 0{,}2 \cdot 0{,}3 = 0{,}06$ (пользуемся тем, что независимость сохраняется для противоположных).

(в) Хотя бы один — противоположное к «оба промахнулись»: $1 - 0{,}06 = 0{,}94$.

(г) Ровно один — два несовместных варианта: «первый попал, второй нет» или «первый нет, второй попал»:

$$0{,}8 \cdot 0{,}3 + 0{,}2 \cdot 0{,}7 = 0{,}24 + 0{,}14 = 0{,}38.$$

Проверим целостность: $0{,}56 + 0{,}38 + 0{,}06 = 1{,}00$. Все четыре исхода («оба», «ровно один», «ни одного») покрывают пространство — сумма единица, ошибки нет.

Ответ: (а) $0{,}56$; (б) $0{,}06$; (в) $0{,}94$; (г) $0{,}38$.

Пример 2 (средний). Зависимые события: выбор без возврата.

В наборе 20 объектов для разметки, из них 5 относятся к редкому положительному классу. Разметчик берёт подряд 3 объекта наугад (без возврата). Какова вероятность, что среди них не окажется ни одного положительного? А хотя бы один положительный?

Здесь события зависимы: как только объект вынут, состав оставшихся меняется. Применяем цепное правило.

Первый объект отрицательный: $P(A_1) = 15/20$.

Второй тоже отрицательный, при условии что первый был отрицательным (осталось 19 объектов, из них 14 отрицательных): $P(A_2 \mid A_1) = 14/19$.

Третий: $P(A_3 \mid A_1 \cap A_2) = 13/18$.

Перемножаем:

$$P = \frac{15}{20}\cdot\frac{14}{19}\cdot\frac{13}{18} = \frac{15 \cdot 14 \cdot 13}{20\cdot 19 \cdot 18} = \frac{2730}{6840} = \frac{91}{228} \approx 0{,}3991.$$

Хотя бы один положительный — через дополнение:

$$1 - \frac{91}{228} = \frac{137}{228} \approx 0{,}6009.$$

Проверим комбинаторикой: число способов выбрать 3 отрицательных из 15 равно $C_{15}^3 = 455$, всего способов $C_{20}^3 = 1140$. Отношение $455/1140 = 91/228 \approx 0{,}3991$. Совпало.

Ответ: $\approx 0{,}399$ и $\approx 0{,}601$.

Заметь принципиальную разницу: если бы выбор шёл с возвратом, ответ был бы $(15/20)^3 = 0{,}75^3 = 0{,}4219$ — события стали бы независимыми, и множители не менялись бы. Отличие в 2,3 процентных пункта. При выборке в 3 объекта из 20 разница ощутима; при выборке 3 из 20 000 она была бы исчезающе мала. Это, кстати, объясняет, почему при бутстрэпе на больших датасетах разница между сэмплированием с возвратом и без возврата практически не влияет на результат.

Пример 3 (сложный). Цепочка этапов пайплайна.

ML-пайплайн состоит из трёх последовательных этапов. Этап загрузки данных отрабатывает успешно с вероятностью $0{,}9$. Этап предобработки успешен с вероятностью $0{,}85$ при условии, что загрузка прошла. Этап обучения успешен с вероятностью $0{,}8$ при условии, что оба предыдущих прошли. Какова вероятность полного успеха прогона? Какова вероятность, что пайплайн упадёт именно на этапе обучения?

Первая часть — прямое применение цепного правила:

$$P(A \cap B \cap C) = P(A)\cdot P(B\mid A)\cdot P(C \mid A \cap B) = 0{,}9 \cdot 0{,}85 \cdot 0{,}8.$$

Считаем по шагам: $0{,}9 \cdot 0{,}85 = 0{,}765$; $0{,}765 \cdot 0{,}8 = 0{,}612$.

Вторая часть: «упал на обучении» означает, что первые два этапа прошли, а третий нет:

$$P(A \cap B \cap \bar{C}) = P(A)P(B\mid A)\big(1 - P(C\mid A\cap B)\big) = 0{,}765 \cdot 0{,}2 = 0{,}153.$$

Проверим полную картину. Упал на загрузке: $0{,}1$. Прошёл загрузку, упал на предобработке: $0{,}9 \cdot 0{,}15 = 0{,}135$. Упал на обучении: $0{,}153$. Полный успех: $0{,}612$. Сумма: $0{,}1 + 0{,}135 + 0{,}153 + 0{,}612 = 1{,}000$. Идеально.

Ответ: $0{,}612$ и $0{,}153$.

Обрати внимание на характер условности здесь. Она не «математическая», а инженерная: если загрузка упала, предобработка вообще не запустится, поэтому и говорить о её вероятности в отрыве от предыдущего этапа бессмысленно. В таких задачах условные вероятности — это буквально те числа, которые ты видишь в мониторинге («из запущенных задач предобработки успешны 85%»), а безусловные приходится вычислять.

Почему это важно

Теорема умножения — это то место, откуда в машинном обучении берётся функция правдоподобия. Если обучающие примеры $(x_1, y_1), \dots, (x_n, y_n)$ считать независимыми (стандартное предположение i.i.d. — independent and identically distributed), то вероятность увидеть всю выборку целиком при параметрах модели $\theta$ равна произведению:

$$L(\theta) = \prod_{i=1}^{n} P(y_i \mid x_i; \theta).$$

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

$$\ln L(\theta) = \sum_{i=1}^{n} \ln P(y_i \mid x_i; \theta).$$

Вот и всё: знаменитая кросс-энтропийная функция потерь — это ровно минус эта сумма, делённая на $n$. Она выглядит как «средняя ошибка по объектам», но по происхождению это логарифм произведения из теоремы умножения. И у перехода к логарифму есть очень практическая причина: произведение тысяч чисел меньше единицы мгновенно улетает в машинный ноль (при $n = 1000$ и типичных $p \approx 0{,}9$ произведение имеет порядок $10^{-46}$, а при $n = 10^5$ — вообще $10^{-4576}$, что float64 просто не представляет). Сумма логарифмов от переполнения не страдает. Так что если хочешь одну фразу, объясняющую, почему в ML везде логарифмы, — вот она: логарифм превращает теорему умножения в теорему сложения.

Попарная независимость ≠ независимость в совокупности

Интуиция

Кажется логичным: если события независимы попарно, то они независимы и все вместе. Каждое не влияет на каждое — что ещё нужно? Но это неверно, и контрпример на удивление простой.

Суть подвоха вот в чём. Попарная независимость означает, что знание одного события не даёт информации о другом. Но она ничего не говорит про ситуацию, когда ты знаешь два события сразу. Информация может быть «распределена» между событиями так, что каждое по отдельности бесполезно, а два вместе — определяют третье полностью.

Классическая аналогия — схема разделения секрета в криптографии. Секрет — это бит $s$. Ты берёшь случайный бит $a$ и вычисляешь $b = s \oplus a$ (исключающее ИЛИ). Отдаёшь $a$ одному человеку, $b$ другому. Каждый из них по отдельности не знает про $s$ ровно ничего: и $a$, и $b$ выглядят как честная случайная монетка. Но вместе они восстанавливают секрет мгновенно: $s = a \oplus b$. Попарно всё независимо, в совокупности — нет.

Контрпример 1: две монеты (самый компактный)

Бросаем две симметричные монеты. Пространство исходов: $\Omega = \{\text{ОО}, \text{ОР}, \text{РО}, \text{РР}\}$, четыре равновероятных исхода по $1/4$ (О — орёл, Р — решка). Рассмотрим три события:

  • $A$ — «на первой монете орёл» $= \{\text{ОО}, \text{ОР}\}$;
  • $B$ — «на второй монете орёл» $= \{\text{ОО}, \text{РО}\}$;
  • $C$ — «на монетах выпало одинаково» $= \{\text{ОО}, \text{РР}\}$.

Каждое событие содержит два исхода из четырёх, поэтому $P(A) = P(B) = P(C) = 1/2$.

Шаг 1. Проверяем пары.

$A \cap B = \{\text{ОО}\}$, значит $P(A\cap B) = 1/4$. А $P(A)P(B) = 1/2 \cdot 1/2 = 1/4$. Равенство есть — $A$ и $B$ независимы.

$A \cap C = \{\text{ОО}\}$ (первая монета орёл и монеты одинаковы — это только ОО), значит $P(A \cap C) = 1/4 = P(A)P(C)$. Независимы.

$B \cap C = \{\text{ОО}\}$, аналогично $P(B\cap C) = 1/4 = P(B)P(C)$. Независимы.

Итак, все три пары независимы. Попарная независимость есть.

Шаг 2. Проверяем тройку.

$A \cap B \cap C = \{\text{ОО}\}$, значит $P(A \cap B\cap C) = 1/4$.

А произведение: $P(A)P(B)P(C) = 1/2 \cdot 1/2 \cdot 1/2 = 1/8$.

$$\frac{1}{4} \neq \frac{1}{8}.$$

Равенство нарушено. События не независимы в совокупности.

Шаг 3. Понимаем, почему. Знание любых двух событий полностью определяет третье. Если ты знаешь, что на первой монете орёл ($A$) и что монеты одинаковы ($C$), то на второй монете гарантированно орёл — событие $B$ произошло с вероятностью 1, а не 1/2. Каждое событие по отдельности не даёт информации, но любые два — дают полную.

Контрпример 2: тетраэдр Бернштейна (классический)

Этот пример придумал Сергей Натанович Бернштейн, и он вошёл во все учебники. Возьмём правильный тетраэдр (четырёхгранную пирамиду). Три его грани окрашены в чистые цвета: красный, синий, зелёный. Четвёртая грань окрашена во все три цвета сразу — на ней есть и красный, и синий, и зелёный.

Тетраэдр подбрасывают, он падает на одну из граней (все четыре равновероятны, по $1/4$). События:

  • $A$ — «на выпавшей грани присутствует красный»;
  • $B$ — «на выпавшей грани присутствует синий»;
  • $C$ — «на выпавшей грани присутствует зелёный».

Красный есть на двух гранях: чисто красной и трёхцветной. Значит $P(A) = 2/4 = 1/2$. Аналогично $P(B) = P(C) = 1/2$.

Пары. Красный и синий одновременно есть только на трёхцветной грани: $P(A\cap B) = 1/4$. Произведение $P(A)P(B) = 1/4$. Совпало. То же самое для двух других пар.

Тройка. Все три цвета есть только на трёхцветной грани: $P(A\cap B\cap C) = 1/4$. Произведение $P(A)P(B)P(C) = 1/8$. Не совпало.

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

Вывод: Попарная независимость не влечёт независимость в совокупности. Обратное верно: независимость в совокупности всегда влечёт попарную (равенства для пар входят в определение). Чтобы перемножать вероятности всех $n$ событий, нужна именно независимость в совокупности.

Бывает ли обратная ситуация?

Да, и это тоже полезно знать: тройное равенство $P(A\cap B\cap C) = P(A)P(B)P(C)$ может выполняться, когда попарные не выполняются. Простейший пример: пусть $\Omega$ состоит из восьми равновероятных исходов, $A$ и $B$ — одно и то же событие вероятности $1/2$ (то есть максимально зависимые), а $C$ — событие вероятности $1/2$, пересекающееся с $A$ так, что $P(A\cap C) = P(A \cap B \cap C) = 1/8$. Тогда $P(A)P(B)P(C) = 1/8$ — тройное равенство выполнено, а $P(A\cap B) = 1/2 \neq 1/4$ — попарное нарушено. Мораль: ни одна часть определения не следует из остальных, поэтому в определении независимости в совокупности требуют выполнения всех $2^n - n - 1$ равенств.

Почему это важно

В машинном обучении это различие бьёт по рукам буквально каждый раз, когда речь заходит об ансамблях. Ты построил три модели, проверил попарные корреляции ошибок — все около нуля, ошибки моделей попарно независимы. Ты радостно считаешь надёжность ансамбля как произведение и получаешь красивую цифру. А в проде ансамбль падает целиком, потому что все три модели одновременно ошибаются на определённом типе объектов — «трёхцветной грани» твоих данных: редком, но существующем сегменте, на котором все модели ломаются вместе. Попарные корреляции этого не показывали.

Тот же механизм объясняет провал моделей риска перед кризисом 2008 года: дефолты по ипотечным кредитам действительно были почти независимы попарно в спокойное время, и модели, построенные на попарных корреляциях, показывали ничтожную вероятность массового дефолта. Но существовал общий скрытый фактор — состояние рынка недвижимости, — который при срабатывании валил всех разом. Попарная независимость в норме, катастрофическая зависимость в хвосте.

Типовые схемы: «хотя бы один», серия испытаний, надёжность системы

Теперь соберём весь инструментарий в три готовых шаблона, которые покрывают, наверное, 80% практических задач на эти теоремы.

Схема 1: «хотя бы один» из $n$ независимых

Событие $A$ — «произошло хотя бы одно из $A_1, \dots, A_n$» с вероятностями $p_1, \dots, p_n$, независимых в совокупности.

$$P(A) = 1 - (1-p_1)(1-p_2)\cdots(1-p_n).$$

Если все $p_i = p$: $P(A) = 1 - (1-p)^n$.

Обратная задача (сколько нужно попыток) решается логарифмированием:

$$n \geq \frac{\ln(1 - P_{\text{нужная}})}{\ln(1-p)}.$$

Дробное $n$ округляем вверх, потому что неравенство должно выполниться.

Схема 2: серия независимых испытаний

Если испытание повторяется $n$ раз независимо и в каждом успех имеет вероятность $p$, то:

  • «все $n$ успешны»: $p^n$;
  • «ни одного успеха»: $(1-p)^n$;
  • «хотя бы один успех»: $1 - (1-p)^n$;
  • «хотя бы одна неудача»: $1 - p^n$;
  • «ровно $k$ успехов»: $C_n^k p^k (1-p)^{n-k}$ — это формула Бернулли, ей будет посвящён урок 233, но выводится она ровно из наших двух теорем: вероятность одной конкретной последовательности с $k$ успехами равна $p^k(1-p)^{n-k}$ (теорема умножения), а таких последовательностей $C_n^k$ штук, и они попарно несовместны (теорема сложения).

Схема 3: надёжность системы

Это самая инженерно полезная схема. Система состоит из элементов, каждый работает независимо с известной вероятностью безотказной работы $p_i$.

Последовательное соединение (система работает, только если работают ВСЕ элементы):

$$P_{\text{посл}} = p_1 \cdot p_2 \cdots p_n.$$

Это теорема умножения. Ключевое свойство: надёжность последовательной цепи ниже надёжности самого слабого элемента. Десять элементов по $0{,}99$ дают систему с надёжностью $0{,}99^{10} \approx 0{,}904$ — почти 10% отказов, хотя каждый элемент почти идеален.

Параллельное соединение / резервирование (система работает, если работает ХОТЯ БЫ ОДИН элемент):

$$P_{\text{пар}} = 1 - (1-p_1)(1-p_2)\cdots(1-p_n).$$

Это схема «хотя бы один». Ключевое свойство: надёжность параллельного блока выше надёжности самого сильного элемента. Три элемента по $0{,}9$ дают $1 - 0{,}1^3 = 0{,}999$.

Смешанные схемы разбираются рекурсивно: сначала сворачиваешь параллельные блоки в один «эквивалентный элемент» с посчитанной надёжностью, потом перемножаешь всю последовательную цепь.

Примеры с разбором

Пример 1 (простой). Микросервисы.

Запрос проходит через три микросервиса подряд. Доступность каждого — $0{,}99$. Какова доступность всей цепочки? Сколько «девяток» потеряно?

Последовательное соединение:

$$P = 0{,}99^3 = 0{,}970299 \approx 0{,}9703.$$

Каждый сервис имел «две девятки» ($99\%$), а цепочка даёт $97{,}03\%$ — это уже меньше полутора девяток. В год это $0{,}0297 \cdot 365 \cdot 24 \approx 260$ часов недоступности вместо $87{,}6$ часов у одного сервиса.

Ответ: $\approx 0{,}9703$.

Пример 2 (средний). Смешанная схема.

Система состоит из двух блоков, соединённых последовательно. Первый блок — два дублирующих сервера, каждый работает с вероятностью $0{,}9$, блок работает, если работает хотя бы один сервер. Второй блок — один балансировщик с надёжностью $0{,}95$. Найти надёжность системы.

Разберём по шагам.

Шаг 1. Сворачиваем параллельный блок. Оба сервера откажут с вероятностью $0{,}1 \cdot 0{,}1 = 0{,}01$. Значит блок работает с вероятностью $1 - 0{,}01 = 0{,}99$.

Шаг 2. Соединяем последовательно с балансировщиком:

$$P = 0{,}99 \cdot 0{,}95 = 0{,}9405.$$

Ответ: $0{,}9405$.

Заметь важное: несмотря на то, что дублирование подняло первый блок с $0{,}9$ до $0{,}99$, общая надёжность упёрлась в одиночный балансировщик $0{,}95$ и не может её превысить. Классическая ловушка проектирования: дублируешь то, что и так надёжно, а узкое место остаётся нерезервированным. Первым делом всегда резервируй самый слабый элемент последовательной цепи.

Пример 3 (сложный). Ансамбль по большинству голосов.

Три независимые модели классифицируют объект, каждая даёт правильный ответ с вероятностью $p = 0{,}8$. Итоговый ответ определяется большинством голосов (не менее двух из трёх). Какова вероятность правильного ответа ансамбля?

Ансамбль прав, если правы ровно две модели или все три. Разложим на несовместные события и применим обе теоремы.

Ровно две правы: выбрать, какая ошиблась, можно $C_3^2 = 3$ способами; вероятность каждого варианта по теореме умножения $p^2(1-p) = 0{,}64 \cdot 0{,}2 = 0{,}128$. Варианты несовместны, складываем:

$$3 \cdot 0{,}128 = 0{,}384.$$

Все три правы: $p^3 = 0{,}512$.

Складываем несовместные случаи:

$$P = 0{,}384 + 0{,}512 = 0{,}896.$$

Ответ: $0{,}896$.

Проверим смысл: одна модель даёт $0{,}8$, ансамбль из трёх — $0{,}896$. Ошибка упала с 20% до 10,4%, почти вдвое, при том что модели ничем не лучше исходной. Это и есть математическая суть бэггинга и random forest: агрегирование независимых слабых решений даёт сильное решение.

Но подчеркну критическое условие: независимость. Если модели обучены на одних и тех же данных, одной архитектурой, с одними и теми же признаками, их ошибки коррелированы, и никакого выигрыша не будет. В предельном случае полностью одинаковых моделей ансамбль из трёх даст те же $0{,}8$, что и одна. Вся техника бэггинга (обучение на разных бутстрэп-подвыборках) и случайных подпространств (случайный поднабор признаков в каждом дереве) существует ровно ради одного — искусственно создать независимость между моделями, чтобы теорема умножения заработала в нашу пользу.

Почему это важно

Схема надёжности — это язык, на котором говорят SRE-инженеры и архитекторы. Когда в SLA пишут «доступность 99,9%», за этим стоит расчёт последовательно-параллельной схемы. Когда в ML-системе ставят три реплики модели за балансировщиком, это параллельное соединение. Когда в inference-пайплайне стоят препроцессинг → модель → постпроцессинг → запись в БД — это последовательное соединение, и его надёжность равна произведению, то есть заведомо ниже самого слабого звена. Умение за пять секунд прикинуть, во что превратится $0{,}999^{20}$ (примерно $0{,}98$), отличает инженера, который понимает свою систему, от инженера, который надеется на лучшее.

Где это живёт в машинном обучении

Соберём отдельно ML-приложения, которые прямо вырастают из двух теорем этого урока. Это не «дополнительное чтение» — это то, ради чего теоремы стоит знать.

Наивный байесовский классификатор

Задача классификации: по признакам $x_1, \dots, x_k$ определить класс $C$. Идея байесовского подхода — оценить $P(C \mid x_1, \dots, x_k)$ и выбрать класс с максимальной вероятностью. Но чтобы её посчитать, нужна вероятность $P(x_1, \dots, x_k \mid C)$ — совместное распределение всех признаков внутри класса. И вот тут возникает катастрофа размерности: если каждый признак бинарный, то для $k$ признаков нужно оценить $2^k$ чисел. При $k = 30$ это миллиард параметров, которые невозможно оценить ни на каких данных.

Наивное предположение спасает: считаем признаки независимыми при условии класса. Тогда по теореме умножения для независимых событий:

$$P(x_1, x_2, \dots, x_k \mid C) = P(x_1 \mid C)\cdot P(x_2 \mid C)\cdots P(x_k \mid C).$$

Вместо $2^k$ параметров — всего $k$ на класс. Модель обучается на крошечных данных, работает мгновенно и десятилетиями остаётся рабочим бейзлайном для классификации текстов и спам-фильтрации.

Предположение при этом почти всегда ложное. В тексте слова «нейронная» и «сеть» встречаются вместе куда чаще, чем предсказывает произведение их частот. В медицинских данных «повышенное давление» и «избыточный вес» связаны. Но классификатор всё равно работает — потому что для выбора класса важно не точное значение вероятности, а то, у какого класса она больше, а порядок часто сохраняется даже при кривых абсолютных значениях. Подробный разбор — в уроке 315; пока запомни, что слово «наивный» в названии — это буквально указание на то, что теорема умножения применена там, где для неё нет оснований.

Функция правдоподобия и переход к логарифмам

Мы уже разобрали это выше, но сформулируем как отдельный факт, потому что он того стоит. Предположение i.i.d. (независимые одинаково распределённые наблюдения) + теорема умножения дают

$$L(\theta) = \prod_{i=1}^{n} p(x_i \mid \theta),$$

а логарифм превращает произведение в сумму:

$$\ell(\theta) = \sum_{i=1}^{n} \ln p(x_i \mid \theta).$$

Три следствия, все практические:

  • Численная устойчивость. Произведение $n$ чисел меньше единицы уходит в машинный ноль уже при $n$ порядка сотен. Сумма логарифмов — нет. Отсюда log_softmax вместо log(softmax(...)), отсюда трюк log-sum-exp, отсюда все «логарифмические» варианты функций в библиотеках.
  • Аддитивность. Сумма по объектам разбивается на минибатчи, а значит правдоподобие можно оптимизировать стохастическим градиентным спуском. Произведение так не разбить.
  • Независимость — это допущение, а не факт. Если объекты в выборке зависимы (временные ряды, повторные измерения одного пациента, посты одного пользователя), произведение перестаёт быть правильным правдоподобием, а модель начинает переоценивать свою уверенность. Отсюда правило «сплит по пользователям, а не по строкам» при формировании train/test — иначе зависимые объекты попадут и туда, и туда, и оценка качества будет завышенной.

Вероятность коллизии при хешировании

Пусть у хеш-таблицы $m$ корзин и хеш-функция раскидывает ключи равномерно и независимо. Вставляем $n$ различных ключей. Какова вероятность, что случится хотя бы одна коллизия?

Через дополнение: считаем вероятность, что все ключи попали в разные корзины. Первый ключ — куда угодно ($m/m$), второй должен избежать одной занятой корзины ($(m-1)/m$), третий — двух ($(m-2)/m$), и так далее. По цепному правилу:

$$P(\text{нет коллизий}) = \frac{m}{m}\cdot\frac{m-1}{m}\cdots\frac{m-n+1}{m} = \prod_{i=1}^{n-1}\left(1 - \frac{i}{m}\right).$$$$P(\text{хотя бы одна коллизия}) = 1 - \prod_{i=1}^{n-1}\left(1 - \frac{i}{m}\right).$$

Используя $1 - x \approx e^{-x}$ при малых $x$, получаем оценку:

$$P(\text{нет коллизий}) \approx \exp\left(-\frac{n(n-1)}{2m}\right) \approx e^{-n^2/(2m)}.$$

Отсюда знаменитый «парадокс дней рождения»: коллизия становится вероятнее, чем её отсутствие, уже при

$$n \approx \sqrt{2m\ln 2} \approx 1{,}177\sqrt{m}.$$

Для $m = 365$ дней в году это $n \approx 22{,}5$, то есть в группе из 23 человек шанс совпадения дней рождения превышает половину. Для хеш-таблицы на миллион корзин — уже около 1178 ключей. Для 64-битного хеша ($m = 2^{64}$) — около $5{,}1$ миллиарда значений: именно поэтому 64-битные хеши считаются небезопасными для дедупликации больших датасетов, а берут 128-битные и длиннее. Кстати, это же рассуждение — основа атаки «дней рождения» на криптографические хеш-функции: стойкость $n$-битного хеша к коллизиям не $2^n$, а всего $2^{n/2}$.

Надёжность и мониторинг ML-систем

И последнее приложение, которое приходит с опытом эксплуатации. Каждый компонент ML-системы имеет вероятность отказа: сбор фичей, фичестор, сама модель, постобработка. Соединены они последовательно, значит надёжности перемножаются. Если ты хочешь SLA $99{,}9\%$ на всю цепочку из пяти компонентов, каждый должен иметь надёжность не хуже $0{,}999^{1/5} \approx 0{,}9998$ — то есть на порядок лучше целевого показателя. Это фундаментальный факт, а не следствие плохой инженерии: последовательное соединение всегда деградирует, и единственный способ его победить — резервирование, то есть параллельные схемы там, где это возможно.

Практика: 30 заданий

Базовые (задания 1-10)

Задание 1: Бросают игральную кость. Найди вероятность события «выпало чётное число или число, кратное трём».

Задание 2: В ящике 30 деталей: 12 первого сорта, 10 второго и 8 третьего. Наугад берут одну деталь. Найди вероятность того, что она первого или второго сорта.

Задание 3: Из колоды в 36 карт наугад вынимают одну. Найди вероятность того, что это туз или карта пиковой масти.

Задание 4: Известно, что $P(A) = 0{,}4$, $P(B) = 0{,}35$, $P(A\cap B) = 0{,}15$. Найди: (а) $P(A\cup B)$; (б) вероятность того, что не произойдёт ни одно из событий.

Задание 5: Проводится 3 независимых испытания, в каждом успех наступает с вероятностью $0{,}2$. Найди вероятность того, что успех наступит хотя бы один раз.

Задание 6: Даны $P(A) = 0{,}5$ и $P(B) = 0{,}4$. Определи, независимы ли события, если: (а) $P(A\cap B) = 0{,}2$; (б) $P(A\cap B) = 0{,}25$; (в) $A$ и $B$ несовместны.

Задание 7: Два стрелка независимо друг от друга стреляют по мишени. Первый попадает с вероятностью $0{,}8$, второй — с вероятностью $0{,}7$. Найди вероятность того, что: (а) попадут оба; (б) попадёт хотя бы один; (в) попадёт ровно один.

Задание 8: Классификатор ошибается на отдельном объекте с вероятностью $0{,}03$ независимо от других объектов. Найди вероятность того, что на двух случайно взятых объектах он ошибётся хотя бы раз.

Задание 9: В наборе 10 объектов, из них у 3 есть пропуски в данных. Наугад выбирают 2 объекта подряд без возврата. Найди вероятность того, что оба объекта содержат пропуски.

Задание 10: Два сервиса работают независимо, доступность каждого $0{,}99$. Найди доступность системы, если: (а) сервисы соединены последовательно (система работает, только когда работают оба); (б) сервисы дублируют друг друга (система работает, когда работает хотя бы один).

Средние (задания 11-20)

Задание 11: Даны три события с вероятностями $P(A) = 0{,}4$, $P(B) = 0{,}5$, $P(C) = 0{,}3$, попарные пересечения $P(A\cap B) = 0{,}2$, $P(A\cap C) = 0{,}1$, $P(B\cap C) = 0{,}15$, тройное пересечение $P(A\cap B\cap C) = 0{,}05$. Найди вероятность того, что произойдёт хотя бы одно из трёх событий.

Задание 12: Три независимых события имеют вероятности $0{,}4$, $0{,}5$ и $0{,}3$. Найди вероятность того, что: (а) не произойдёт ни одно; (б) произойдёт хотя бы одно; (в) произойдёт ровно одно.

Задание 13: Модель ошибается на объекте с вероятностью $0{,}02$ независимо от других объектов. Пользователю показывается батч из 32 объектов. Найди вероятность того, что в батче есть хотя бы одна ошибка.

Задание 14: Модель ошибается на объекте с вероятностью $0{,}01$. При каком минимальном размере выборки $n$ вероятность того, что модель ошибётся хотя бы раз, станет не меньше $0{,}99$?

Задание 15: Система состоит из двух последовательных блоков. Первый блок — два дублирующих элемента с надёжностью $0{,}9$ каждый (блок работает, если работает хотя бы один элемент). Второй блок — один элемент с надёжностью $0{,}95$. Все элементы независимы. Найди надёжность системы.

Задание 16: Известно, что $P(A) = 0{,}6$ и $P(A\cap B) = 0{,}24$. Найди условную вероятность $P(B\mid A)$. При каком значении $P(B)$ события окажутся независимыми?

Задание 17: В выборке 20 объектов, из них 5 относятся к положительному классу. Наугад берут 3 объекта без возврата. Найди вероятность того, что: (а) все три объекта отрицательные; (б) среди них есть хотя бы один положительный.

Задание 18: Хеш-таблица имеет 1000 корзин, хеш-функция раскидывает ключи равномерно и независимо. В таблицу вставляют 3 различных ключа. Найди вероятность того, что произойдёт хотя бы одна коллизия.

Задание 19: Модель бинарной классификации выдала для пяти независимых наблюдений вероятности правильных ответов $0{,}9$; $0{,}8$; $0{,}95$; $0{,}7$; $0{,}85$. Найди правдоподобие выборки (произведение вероятностей) и логарифмическое правдоподобие.

Задание 20: Из колоды в 36 карт последовательно без возврата вынимают две карты. Найди вероятность того, что: (а) обе карты пиковой масти; (б) хотя бы одна карта пиковой масти.

Продвинутые (задания 21-30)

Задание 21: (Тетраэдр Бернштейна.) Правильный тетраэдр имеет три грани, окрашенные соответственно в красный, синий и зелёный цвет, а четвёртая грань окрашена во все три цвета сразу. Тетраэдр подбрасывают. Событие $A$ — «выпавшая грань содержит красный», $B$ — «содержит синий», $C$ — «содержит зелёный». Проверь попарную независимость и независимость в совокупности.

Задание 22: Бросают две симметричные монеты. $A$ — «на первой монете орёл», $B$ — «на второй монете орёл», $C$ — «на обеих монетах выпало одинаково». Докажи, что эти события попарно независимы, но не независимы в совокупности.

Задание 23: (Задача о совпадениях.) Четыре письма случайным образом раскладывают по четырём подписанным конвертам, по одному письму в конверт. Найди вероятность того, что хотя бы одно письмо попадёт в свой конверт.

Задание 24: Известно только, что $P(A) = 0{,}7$ и $P(B) = 0{,}6$. В каких границах может лежать $P(A\cap B)$? А $P(A\cup B)$?

Задание 25: Три независимые модели классифицируют объект, каждая даёт верный ответ с вероятностью $0{,}8$. Итоговый ответ выбирается по большинству голосов. Найди вероятность верного ответа ансамбля. Насколько снизилась вероятность ошибки по сравнению с одной моделью?

Задание 26: Четыре независимых детектора аномалий срабатывают на аномальном объекте с вероятностями $0{,}5$; $0{,}6$; $0{,}7$; $0{,}8$. (а) Найди вероятность того, что аномалию заметит хотя бы один детектор. (б) Сколько нужно независимых детекторов с вероятностью срабатывания $0{,}5$ каждый, чтобы вероятность обнаружения была не ниже $0{,}99$?

Задание 27: Хеш-функция раскидывает ключи равномерно по $m = 1{\,}000{\,}000$ корзинам. Оцени, при каком количестве ключей $n$ вероятность хотя бы одной коллизии превысит $0{,}5$.

Задание 28: ML-пайплайн состоит из трёх последовательных этапов. Загрузка данных успешна с вероятностью $0{,}9$. Предобработка успешна с вероятностью $0{,}85$ при условии успешной загрузки. Обучение успешно с вероятностью $0{,}8$ при условии успеха обоих предыдущих этапов. Найди: (а) вероятность полного успеха; (б) вероятность падения именно на этапе обучения; (в) распределение вероятностей по всем возможным исходам прогона.

Задание 29: Докажи, что если события $A$ и $B$ независимы, то независимы и события $\bar{A}$ и $\bar{B}$. Проиллюстрируй на числах: $P(A) = 0{,}4$, $P(B) = 0{,}25$.

Задание 30: Запрос к внешнему API падает с вероятностью $0{,}05$ независимо от других попыток. Клиент делает до 3 попыток подряд. (а) Найди вероятность того, что запрос в итоге выполнится. (б) За смену обрабатывается 200 таких запросов независимо друг от друга. Найди вероятность того, что хотя бы один запрос провалит все три попытки.

Частые ошибки

❌ Ошибка 1: складывать вероятности совместных событий

Неправильно: «Пропуск в возрасте у 12% строк, пропуск в доходе у 20% строк, значит хотя бы один пропуск у $12\% + 20\% = 32\%$ строк».

Правильно: $P(A\cup B) = P(A) + P(B) - P(A\cap B)$. Если обе колонки пусты у $4{,}5\%$ строк, то ответ $0{,}12 + 0{,}2 - 0{,}045 = 0{,}275$, то есть $27{,}5\%$.

💡 Почему важно: простое сложение всегда даёт завышенную оценку (это неравенство Буля). В аналитике так рождается «раздутый охват» рекламных кампаний, а в инженерных расчётах — избыточно пессимистичные оценки отказов. Складывать напрямую можно только тогда, когда события физически не могут произойти вместе.

❌ Ошибка 2: путать несовместность и независимость

Неправильно: «События несовместны, значит они друг на друга не влияют, значит независимы, значит $P(A\cap B) = P(A)P(B)$».

Правильно: несовместность означает $P(A\cap B) = 0$, а независимость — $P(A\cap B) = P(A)P(B)$. Если обе вероятности ненулевые, эти условия несовместимы друг с другом: несовместные события всегда зависимы.

💡 Почему важно: это самая частая концептуальная ошибка в теме. Проверь себя на очевидном примере: выпадение «1» и выпадение «2» на одной кости — несовместные события. Но если ты знаешь, что выпала единица, то вероятность двойки не $1/6$, а ноль. Влияние максимальное, никакой независимости.

❌ Ошибка 3: считать «хотя бы один» умножением вероятности на количество

Неправильно: «Вероятность ошибки $0{,}02$, объектов 32, значит вероятность ошибки в батче $32\cdot 0{,}02 = 0{,}64$». Или ещё хуже — «объектов 100, значит $100\cdot 0{,}02 = 2$», то есть вероятность больше единицы.

Правильно: $P = 1 - (1-p)^n = 1 - 0{,}98^{32}\approx 0{,}476$.

💡 Почему важно: линейная оценка $np$ работает только при очень малых $np$ (грубо, при $np < 0{,}1$ ошибка меньше 5%). Дальше она безбожно завышает, а при $np > 1$ выдаёт бессмысленные «вероятности» больше единицы. Правильная формула никогда не выходит за единицу — она к ней асимптотически стремится.

❌ Ошибка 4: считать попарную независимость достаточной для перемножения всех вероятностей

Неправильно: «Проверил корреляции ошибок трёх моделей — все попарно нулевые, значит вероятность одновременной ошибки трёх моделей равна $0{,}2^3 = 0{,}008$».

Правильно: для перемножения $n$ вероятностей нужна независимость в совокупности, а не попарная. Контрпример с тетраэдром Бернштейна показывает, что все попарные равенства могут выполняться, а тройное — нет.

💡 Почему важно: это ошибка стоимостью в миллиарды. Модели оценки ипотечных рисков перед 2008 годом опирались на попарные корреляции дефолтов и получали ничтожную вероятность массового дефолта. Общий скрытый фактор (состояние рынка) валил всех разом. В ML тот же эффект убивает ансамбли: попарно некоррелированные модели могут дружно ошибаться на одном специфическом сегменте данных.

❌ Ошибка 5: применять формулу для независимых событий при выборе без возврата

Неправильно: «В выборке 20 объектов, 5 положительных. Вероятность вытянуть три отрицательных подряд равна $(15/20)^3 = 0{,}4219$».

Правильно: при выборе без возврата события зависимы, нужно цепное правило: $\dfrac{15}{20}\cdot\dfrac{14}{19}\cdot\dfrac{13}{18} \approx 0{,}3991$.

💡 Почему важно: разница мала при выборке из большой совокупности и велика при выборке из маленькой. Практическое правило: если объём выборки меньше 5% от совокупности, можно смело считать события независимыми — погрешность будет пренебрежимой. Если больше — обязательно учитывай зависимость. Кстати, ровно поэтому в статистике есть поправка на конечную совокупность.

❌ Ошибка 6: перемножать вероятности вместо суммирования логарифмов в коде

Неправильно: likelihood = np.prod(probs) для выборки из десятков тысяч объектов.

Правильно: log_likelihood = np.sum(np.log(probs)).

💡 Почему важно: при $n = 10^5$ и типичных $p\approx 0{,}9$ произведение имеет порядок $10^{-4576}$, что float64 представить не может — получишь ровно ноль, а затем -inf или nan при логарифмировании. Сумма логарифмов вычисляется без переполнения. Это не микрооптимизация, а вопрос работоспособности кода вообще. По той же причине в библиотеках существуют log_softmax, logsumexp и log_prob — они делают ту же работу в логарифмическом пространстве.

Главное запомнить

✅ Теорема сложения для несовместных событий: $P(A\cup B) = P(A) + P(B)$, если $A\cap B = \varnothing$. Для попарно несовместных $A_1,\dots,A_n$ вероятности просто складываются.

✅ Общая теорема сложения: $P(A\cup B) = P(A) + P(B) - P(A\cap B)$. Пересечение вычитается ровно один раз, потому что при сложении $P(A)+P(B)$ оно было посчитано дважды.

✅ Формула включений-исключений для трёх событий: плюс одиночные, минус попарные, плюс тройное. Знаки чередуются, чтобы каждая точка была посчитана ровно один раз.

✅ Неравенство Буля: $P(A_1\cup\dots\cup A_n)\leq P(A_1)+\dots+P(A_n)$ — простое сложение всегда даёт оценку сверху, и это законная граница, а не ошибка.

✅ Противоположное событие: $P(\bar A) = 1 - P(A)$. Любое «хотя бы один» считай через «ни одного» — это главный вычислительный приём темы.

✅ Формула «хотя бы один»: $P = 1 - (1-p)^n$ для $n$ независимых испытаний с одинаковой вероятностью $p$. При $n\to\infty$ она стремится к единице для любого $p > 0$.

✅ Определение независимости: $P(A\cap B) = P(A)P(B)$. Это арифметический критерий, а не философское «не влияют».

✅ Независимость ≠ несовместность. Несовместные события с ненулевыми вероятностями всегда зависимы: наступление одного полностью исключает другое.

✅ Теорема умножения: $P(A\cap B) = P(A)P(B\mid A)$ — верна всегда; $P(A\cap B) = P(A)P(B)$ — только для независимых. Цепное правило $P(A_1\cap\dots\cap A_n) = P(A_1)P(A_2\mid A_1)\cdots$ работает без каких-либо предположений.

✅ Попарная независимость не влечёт независимость в совокупности (тетраэдр Бернштейна, две монеты). Для перемножения всех $n$ вероятностей нужна именно независимость в совокупности.

✅ Надёжность систем: последовательное соединение — произведение (всегда хуже слабейшего элемента), параллельное резервирование — $1-\prod(1-p_i)$ (всегда лучше сильнейшего). Резервируй самое слабое звено.

✅ Логарифм превращает умножение в сложение — отсюда логарифмическое правдоподобие, кросс-энтропия и вся численная устойчивость обучения моделей.

Связь с другими темами курса

Что было раньше: урок 226 дал язык событий (пространство $\Omega$, объединение, пересечение, противоположное событие) — без него формулы этого урока были бы просто набором символов. Уроки 227 и 228 научили считать вероятность одного события: классическое определение $P(A) = m/n$ и геометрическую вероятность через отношение мер. В этом уроке мы впервые начали строить из событий конструкции, и именно поэтому аналогия «вероятность ведёт себя как площадь» из геометрической вероятности так хорошо здесь работает.

Что дальше: следующий урок 230 полностью посвящён условной вероятности — мы ввели её здесь только как рабочий инструмент для теоремы умножения, а там разберём подробно: интуицию сужения пространства, свойства, парадоксы (включая знаменитый парадокс Монти Холла) и связь с зависимостью признаков. Урок 231 — формула полной вероятности: если разбить пространство на несовместные гипотезы, теоремы сложения и умножения комбинируются в мощный инструмент. Урок 232 — формула Байеса, из которой вырастает весь байесовский подход в ML. Урок 233 — схема Бернулли: формула $C_n^k p^k(1-p)^{n-k}$ выводится ровно из наших двух теорем, и мы уже видели её частные случаи в заданиях про ансамбли. А в уроке 315 нас ждёт наивный байесовский классификатор — прямое приложение теоремы умножения там, где независимости на самом деле нет.

Где это применяется в жизни и в ML/данных:

🤖 В машинном обучении: функция правдоподобия как произведение вероятностей независимых наблюдений и переход к логарифмам; наивный байесовский классификатор; расчёт надёжности ансамблей и обоснование бэггинга; вероятность хотя бы одной ошибки на батче; предположение i.i.d. и его нарушения при сплите данных.

📊 В анализе данных: пересечения аудиторий и честный охват рекламных кампаний; проблема множественных сравнений и поправка Бонферрони (вероятность найти хотя бы один ложноположительный результат при переборе гипотез — это ровно $1-(1-\alpha)^m$); согласованность таблиц сопряжённости.

💻 В программировании: вероятность коллизии хешей и парадокс дней рождения; выбор длины хеша для дедупликации; расчёт SLA распределённых систем; надёжность ретраев и очередей.

🏥 В медицине и страховании: вероятность хотя бы одного побочного эффекта при комбинации препаратов; расчёт совокупного риска портфеля полисов; оценка чувствительности каскада диагностических тестов.

🎰 В теории игр и азартных играх: та самая исходная задача Кардано про шестёрку за несколько бросков; расчёт шансов в покере; оценка «вероятности разорения» при длинной серии ставок.

Интересные факты

💡 Ошибка Кардано стоила ему денег. Джероламо Кардано, врач и математик XVI века, зарабатывал игрой в кости и первым попытался посчитать вероятность выбросить хотя бы одну шестёрку за $n$ бросков. Его первый ответ был $n/6$ — простое сложение. По этой логике за 6 бросков шестёрка гарантирована, а за 12 бросков вероятность равна двум, что абсурдно. Правильный ответ $1-(5/6)^n$ даёт за 6 бросков всего $0{,}665$, а не единицу. Между этими двумя числами — целое состояние, проигранное на длинной дистанции.

💡 Задача де Мере, с которой началась теория вероятностей. Шевалье де Мере, французский аристократ и игрок, заметил расхождение: ставить на «хотя бы одна шестёрка за 4 броска одной кости» выгодно ($1-(5/6)^4 = 0{,}5177$, чуть больше половины), а на «хотя бы одна пара шестёрок за 24 броска двух костей» — уже невыгодно ($1-(35/36)^{24} = 0{,}4914$, чуть меньше половины). Разница всего в 2,6 процентных пункта, но де Мере заметил её эмпирически, играя тысячи партий. Именно с этого вопроса началась переписка Паскаля и Ферма 1654 года, положившая начало теории вероятностей.

💡 Парадокс дней рождения ломает интуицию у всех. В группе из 23 человек вероятность совпадения дней рождения превышает $50\%$, а в группе из 70 человек — превышает $99{,}9\%$. Люди систематически недооценивают ответ, потому что мысленно считают «сколько человек совпадёт со мной», а надо считать пары: в группе из 23 человек пар не 22, а $C_{23}^2 = 253$. Тот же счёт пар лежит в основе «атаки дней рождения» на криптографические хеши: чтобы найти коллизию в $n$-битном хеше, нужно перебрать не $2^n$ значений, а всего $2^{n/2}$ — именно поэтому MD5 (128 бит) считается сломанным при $2^{64}$ операциях.

💡 Задача о совпадениях сходится к $1 - 1/e$. Если случайно разложить $n$ писем по $n$ подписанным конвертам, вероятность того, что хотя бы одно попадёт по адресу, при росте $n$ не стремится ни к нулю, ни к единице. Она сходится к $1 - e^{-1}\approx 0{,}6321$, причём сходимость невероятно быстрая: уже при $n = 6$ ответ отличается от предельного меньше чем на $0{,}0002$. Число $e$ выскакивает здесь буквально из знакопеременного ряда формулы включений-исключений, который совпадает с разложением $e^{-1}$.

💡 «Наивный» классификатор побеждает при заведомо ложных предположениях. Наивный Байес предполагает независимость признаков, которой в реальных данных практически никогда нет. Тем не менее в задачах классификации текстов он десятилетиями остаётся сильным бейзлайном и иногда обгоняет куда более сложные модели на малых выборках. Причина в том, что для выбора класса важны не абсолютные значения вероятностей (они у наивного Байеса чудовищно искажены и почти всегда близки к 0 или 1), а лишь их порядок — а порядок оказывается на удивление устойчивым к нарушению независимости.

Лайфхаки и полезные трюки

1. Услышал «хотя бы» — сразу пиши единицу минус

Это рефлекс, который надо выработать. «Хотя бы один», «хотя бы раз», «не менее одного», «встретится где-нибудь», «сработает какой-нибудь» — всё это переводится в $1 - P(\text{ни одного})$. Прямой счёт через перебор случаев почти всегда длиннее и почти всегда приводит к ошибке в комбинаторике.

2. Для независимых событий объединение считай через дополнение, а не через формулу сложения

Вместо $P(A) + P(B) - P(A)P(B)$ пиши $1 - (1-P(A))(1-P(B))$. Формулы эквивалентны, но вторая короче, легче обобщается на $n$ событий и не даёт ошибиться со знаком перед пересечением. Проверь на числах: $P(A)=0{,}4$, $P(B)=0{,}4$ дают $1 - 0{,}6\cdot 0{,}6 = 0{,}64$ против $0{,}4+0{,}4-0{,}16=0{,}64$ — тот же ответ, вдвое меньше арифметики.

3. Считай в уме через $e^{-np}$

При малом $p$ вероятность «хотя бы одного» из $n$ независимых испытаний примерно равна $1 - e^{-np}$. Держи в голове три опорные точки: $np = 1 \Rightarrow \approx 63\%$, $np = 3 \Rightarrow \approx 95\%$, $np = 5 \Rightarrow \approx 99\%$. Этого хватает, чтобы за пять секунд прикинуть, реалистична ли оценка, которую тебе показывает коллега в отчёте.

4. Проверяй расчёт разбиением на непересекающиеся куски

Для двух событий это четыре куска: «только $A$», «только $B$», «оба», «ни одного». Для трёх — восемь. Посчитай каждый, убедись, что все неотрицательны и сумма равна единице. Этот приём ловит и арифметические ошибки, и логически несогласованные исходные данные, которые иначе выглядят вполне правдоподобно.

5. Правило 5% для выбора без возврата

Если выборка составляет меньше 5% от генеральной совокупности, разницей между выбором с возвратом и без возврата можно пренебречь и считать события независимыми. Ошибка будет в пределах долей процента. Если больше 5% — обязательно считай через цепное правило с меняющимися знаменателями.

6. Никогда не перемножай вероятности в коде — суммируй логарифмы

Как только количество множителей переваливает за несколько десятков, произведение начинает терять точность, а за пару сотен — уходит в машинный ноль. Пиши np.sum(np.log(p)) вместо np.prod(p), используй scipy.special.logsumexp для сложения в логарифмическом пространстве и log_softmax вместо log(softmax(x)). Это не педантизм — это разница между работающим кодом и nan в логах обучения.

7. Первым делом резервируй самое слабое звено

В последовательной цепи надёжность равна произведению, и общий результат всегда ниже надёжности самого слабого элемента. Дублирование сильного элемента почти ничего не даёт: в примере с блоками ($0{,}9$ дублированный и $0{,}95$ одиночный) результат $0{,}9405$ упирается в нерезервированный $0{,}95$. Всегда считай, какой элемент ограничивает систему, и вкладывайся именно в него.

Заключение

Две теоремы. Сложение отвечает на вопрос «или», умножение — на вопрос «и». Всё остальное в этом уроке — следствия, частные случаи и приёмы применения. И этого набора хватает, чтобы посчитать вероятность ошибки на батче, надёжность продакшен-системы, шанс коллизии в хеш-таблице и выигрыш от ансамбля моделей.

Но главное, что стоит унести из урока, — это не формулы, а два изменённых рефлекса. Первый: услышав «хотя бы один», ты больше не начинаешь перебирать случаи, а сразу считаешь дополнение. Второй: увидев произведение вероятностей, ты автоматически спрашиваешь себя — а точно ли события независимы, и независимы ли они в совокупности, а не только попарно? Первый рефлекс экономит время. Второй спасает от ошибок, которые в реальных системах стоят дорого — от развалившегося ансамбля до недооценённого системного риска.

Дальше будет только интереснее. В следующем уроке мы разберём условную вероятность по-настоящему — со всеми её парадоксами и с той самой интуицией «сужения пространства», которую здесь пришлось дать в сжатом виде. Потом придёт формула полной вероятности, потом Байес — и вот тогда сложится полная картина того, как машина учится обновлять свои убеждения при поступлении новых данных. А фундамент этой картины ты только что заложил. Двигаемся дальше! 🚀

Понял тему? Закрепи в боте! 🚀

Попрактикуйся на задачах и получи персональные рекомендации от AI

💪 Начать тренировку
💬 Есть вопрос? Спроси бота!