Обучение математике в Массачусетском технологическом институте (MIT) строится не только на сухих формулах, но и на умении понятно доносить логику доказательств. В рамках курса 18.200 «Принципы дискретной прикладной математики» профессора Анкур Моитра и Питер Шор вместе со специалистом по академическому письму Сьюзан Руссберг представляют студентам фундаментальные инструменты математического мышления. Первая лекция курса посвящена знаменитому принципу Дирихле (в англоязычной традиции — принципу голубиных гнезд), который, несмотря на свою очевидность, позволяет решать сложнейшие задачи комбинаторики, теории графов и даже проливать свет на генеалогию человечества.
🎓 Введение в курс 18.200 и искусство доказательства 0:12
Курс 18.200 под названием «Принципы дискретной прикладной математики» ведут два лектора — профессор Анкур Моитра и профессор Питер Шор. На протяжении семестра студентам предстоит познакомиться с теорией вероятностей, комбинаторикой, производящими функциями, теорией чисел, криптографией, а также теорией кодирования, линейным программированием и многими другими прикладными темами.
Однако, по словам Анкура Моитры, ключевая цель курса заключается не просто в передаче фактов, а в обучении тому, как правильно и понятно выражать математические доказательства. Профессор отмечает, что этот навык часто формируется отрывочно в разных дисциплинах, но осознанное размышление над тем, как сделать доказательство понятным для аудитории, критически важно для любого математика.
Моитра проводит прямую аналогию между математикой и программированием:
Хорошие практики написания кода, такие как модульность, разделение на логические блоки и структурирование, работают точно так же и при составлении качественных математических доказательств.
Важную роль в курсе играют практические занятия (семинары), о которых подробнее рассказывает Сьюзан. Данный курс относится к категории CIM (Communication Intensive in the Major) — дисциплин с интенсивным обучением коммуникации внутри специальности. Цель таких занятий — помочь студентам стать эффективными коммуникаторами в математическом сообществе, основываясь на модели исследовательницы Энн Бофорт.
Успешное общение в математике требует экспертизы в нескольких областях, которые будут развиваться на семинарах:
- Математический контент: углубление и закрепление теоретического материала лекций.
- Профессиональные нормы: понимание стандартов написания текстов, которые в математике отличаются, например, от компьютерных наук (Computer Science / Core 6). Студенты узнают, как правильно писать введение к курсовой работе и как специфически математики используют местоимение «мы».
- Процессы создания текстов: работа над черновиками курсовой работы и освоение системы компьютерной верстки LaTeX, которая потребуется уже для первого домашнего задания. Студентам, не знакомым с LaTeX, предлагается обращаться за помощью в часы консультаций.
- Риторические стратегии: методы достижения целей автора. В математике для упрощения сложной логики активно применяется модульность — разбиение текста и вынесение отдельных утверждений в леммы. Также на семинарах изучают правильное структурирование информации внутри предложений и разделов для обеспечения плавности логического потока, а также использование направляющего текста для ведения читателя за мыслью автора.
🧦 Суть принципа Дирихле и носки в ящике 4:38
Анкур Моитра возвращается к лекционной части, чтобы представить одну из самых простых, но удивительно мощных концепций дискретной математики — принцип голубиных гнезд (в русскоязычной математической традиции известный как принцип Дирихле). Моитра признается, что название принципа кажется ему довольно странным, и он не знает его точной этимологии.
Для демонстрации сути принципа лектор предлагает рассмотреть классическую бытовую задачу, с которой многие сталкиваются по утрам. Представьте, что в темном ящике лежат носки пяти разных цветов. Человек пытается вслепую достать подходящую пару. Возникает вопрос: какое минимальное количество носков нужно вытащить из ящика, чтобы гарантировать наличие хотя бы одной пары одинакового цвета, даже если человеку катастрофически не везет?
Один из студентов дает правильный ответ: необходимо достать ровно 6 носков. Логика проста: в худшем случае первые 5 вытащенных носков окажутся пяти разных цветов, но шестой носок неизбежно совпадет по цвету с одним из уже выбранных.
📦 Формальное доказательство и коробка с голубями 6:53
В общем виде принцип формулируется следующим образом: если у нас есть $n$ голубей, которых мы расселяем по $m$ голубятням (гнездам), и при этом количество голубей строго больше количества гнезд ($n > m$), то как минимум в одной голубятне окажется не менее двух голубей.
Профессор делится забавной личной историей из времен, когда он преподавал курс 6.042. Среди преподавателей MIT существовала своеобразная «гонка вооружений» за лучшие наглядные пособия для лекций. Моитра одолжил у коллеги коробку с бутафорскими «мертвыми голубями».
По воспоминаниям профессора, поездка в лифте знаменитого Стата-центра с коробкой, на которой было написано «мертвые голуби», вызвала массу недоуменных и подозрительных взглядов коллег. Ему приходилось объяснять, что это всего лишь реквизит для объяснения математического принципа. Впрочем, как иронично замечает Моитра, один из коллег в лифте спросил, действительно ли эти чучела помогают студентам лучше понять тему, что заставило профессора пересмотреть свои педагогические приоритеты — на самом деле наглядность не сильно прибавила понимания.
В задаче с носками голубями выступают отдельные носки, а гнездами — их цвета. Однако существуют гораздо более тонкие обобщения этого принципа. Например, если голубей значительно больше, чем гнезд, то можно гарантировать, что хотя бы в одном гнезде окажется не менее $\lceil n/m \rceil$ голубей, где $\lceil \cdot \rceil$ обозначает функцию «потолка» — округление до ближайшего большего целого числа.
Несмотря на очевидность утверждения, Моитра демонстрирует, как строго доказать его методом от противного, что служит отличным примером хорошего тона в написании математических текстов. При оформлении доказательства лектор призывает всегда четко обозначать в самом начале, что используется метод от противного, чтобы читатель понимал общий план и структуру рассуждения до того, как погрузится в детали.
Доказательство строится на подсчете количества голубей двумя способами. Предположим, что принцип Дирихле неверен. Пусть $n$ — общее число голубей. Мы можем просуммировать количество голубей по всем гнездам $h$:
$$n = \sum_{h} N_h$$
Здесь $N_h$ — число голубей в конкретном гнезде $h$. Если наше предположение от противного верно и принцип нарушается, то в каждом из $m$ гнезд находится не более одного голубя (то есть $N_h \le 1$). Следовательно, общая сумма не может превышать количество гнезд:
$$n \le m$$
Однако это напрямую противоречит нашему исходному условию, согласно которому количество голубей строго больше количества гнезд ($n > m$). Полученное противоречие доказывает истинность принципа Дирихле. Лектор подчеркивает, что хотя эта схема кажется тривиальной, по такому же шаблону строятся гораздо более сложные математические рассуждения.
🏈 Теория рукопожатий на футбольной вечеринке 12:31
По мнению Анкура Моитры, написание хорошего доказательства часто заключается в поиске правильной абстракции и модели для визуализации проблемы. В качестве иллюстрации он предлагает доказать следующую лемму, которая на первый взгляд никак не связана с принципом Дирихле. Представьте, что вы приходите на вечеринку в честь Супербоула, где помимо вас присутствует еще сколько-то людей — всего $n$ человек. Лемма утверждает, что на любой такой вечеринке всегда найдутся как минимум два человека, которые знают одинаковое количество людей на этой же вечеринке.
Чтобы доказать этот математический факт, Моитра предлагает использовать теорию графов в качестве абстракции. Мы можем представить людей в виде вершин (узлов) графа, а знакомства между ними — в виде ребер, соединяющих эти вершины.
Профессор рисует на доске пример с четырьмя людьми ($n = 4$). Если провести ребра знакомств, в получившемся графе наглядно видно, что две вершины имеют абсолютно одинаковое число исходящих связей. Количество ребер, сходящихся в одной вершине, в математике называется степенью вершины. Таким образом, степень вершины в нашей модели — это число знакомых конкретного человека на вечеринке.
Для применения принципа Дирихле необходимо определить, что является голубями, а что гнездами. Моитра обращается к аудитории, и один из студентов предлагает считать гнездами вершины, а связями — голубей, однако профессор указывает, что это не приведет к успеху. Другой студент формулирует верную догадку: голубями должны быть сами люди (вершины графа), а гнездами — возможные значения степеней этих вершин, поскольку мы ищем совпадение (коллизию) именно по количеству знакомых.
Каждая вершина (человек) отправляется в «гнездо», соответствующее ее степени знакомств. Возможные значения степеней для графа из $n$ вершин лежат в диапазоне целых чисел от $0$ (человек никого не знает) до $n - 1$ (человек знает абсолютно всех остальных).
На первый взгляд кажется, что доказательство окончено, но Моитра указывает на скрытую ловушку. Принцип Дирихле требует, чтобы количество голубей было строго больше количества гнезд. В данном случае у нас есть $n$ людей (голубей) и ровно $n$ возможных вариантов степеней — от $0$ до $n - 1$ включительно (гнезд). При равенстве $n = m$ принцип напрямую не работает.
Здесь требуется изящная математическая идея. Лектор задает вопрос: возможно ли, чтобы в одном и том же графе одновременно существовали вершина со степенью $0$ и вершина со степенью $n - 1$? Студент дает правильный ответ: если на вечеринке есть человек со степенью $n - 1$, это означает, что он соединен ребрами со всеми остальными участниками. Но в таком случае на вечеринке физически не может быть никого, кто не знаком вообще ни с кем (то есть имел бы степень $0$).
Эти два пограничных случая взаимно исключают друг друга. Проведя строгий разбор случаев, мы получаем следующее:
- Случай 1: в графе есть вершина степени $n - 1$. Тогда вершины степени $0$ быть не может. Количество доступных гнезд сокращается до $n - 1$ (числа от $1$ до $n - 1$), а голубей по-прежнему $n$. Принцип Дирихле применим.
- Случай 2: в графе нет вершины степени $n - 1$. Тогда максимальное число доступных гнезд снова равно $n - 1$ (числа от $0$ до $n - 2$), при $n$ голубях. Принцип Дирихле снова работает.
В обоих сценариях количество людей превышает количество возможных степеней знакомств, что гарантирует наличие двух людей с одинаковым числом знакомых.
🔢 Загадка подмножеств и четырехзначных чисел 21:04
Следующий пример применения принципа Дирихле сложнее предыдущих. С точки зрения вычислительной сложности эта задача выглядит крайне трудной, хотя формулируется очень просто.
Предположим, дано 20 любых произвольных четырехзначных положительных чисел, которые мы обозначим как $x_1, x_2, \dots, x_{20}$. Утверждение леммы гласит: среди этих чисел обязательно найдутся два таких непересекающихся непустых подмножества, суммы элементов которых будут абсолютно равны.
Моитра поясняет, что если бы подмножества могли быть пустыми, задача стала бы тривиальной и неинтересной, ведь сумма элементов пустого множества равна нулю, и они очевидно не пересекаются. Требование непустоты гарантирует поиск содержательного, положительного равенства сумм.
Для написания строгого доказательства в первую очередь необходимо ввести удобную математическую нотацию, переведя условие задачи на язык формул. Мы ищем два подмножества индексов $I$ и $J$, являющихся подмножествами множества ${1, 2, \dots, 20}$. Эти подмножества должны удовлетворять трем жестким условиям:
- Они не должны быть пустыми: $I \neq \emptyset$ и $J \neq \emptyset$.
- Они должны быть непересекающимися: $I \cap J = \emptyset$.
- Их суммы должны быть равны: $\sum_{i \in I} x_i = \sum_{j \in J} x_j$.
Разработка такой нотации — важный шаг, которому активно обучают на семинарах, поскольку без нее невозможно проводить дальнейшие алгебраические манипуляции.
Каковы же в этой задаче голуби и гнезда? Голубями в данном случае выступают все возможные непустые подмножества наших 20 чисел. Поскольку у нас 20 исходных чисел, общее количество всех возможных подмножеств вычисляется как $2^{20}$, а за вычетом пустого множества мы получаем ровно $2^{20} - 1$ голубей, что составляет $1\,048\,575$ вариантов. Моитра мимоходом поясняет, что этот подсчет базируется на понятии биекции: каждое подмножество можно представить в виде битовой строки длиной 20 символов, где единица означает включение элемента в подмножество, а ноль — его отсутствие.
Гнездами же будут являться все теоретически возможные значения сумм. Какова верхняя граница ($m$) для такой суммы? Самая большая сумма получится, если сложить все 20 чисел. Так как каждое число является четырехзначным, оно гарантированно меньше $10^4$. Таким образом, максимальная сумма строго меньше, чем $20 \times 10^4 = 200\,000$, что, в свою очередь, намного меньше $10^6$.
Мы имеем более миллиона голубей ($n = 1\,048\,575$) и менее двухсот тысяч гнезд ($m < 200\,000$). Условие $n > m$ выполняется с огромным запасом. На основании принципа Дирихле мы можем утверждать, что существуют два разных подмножества $A$ и $B$ ($A \neq B$), которые дадут одинаковую сумму элементов:
$$\sum_{i \in A} x_i = \sum_{j \in B} x_j$$
Однако на этом этапе доказательство еще не завершено, так как подмножества $A$ и $B$ могут пересекаться, нарушая наше требование о непересекаемости множеств $I$ и $J$. Моитра обращает внимание на педагогическую деталь: он намеренно использовал временные обозначения $A$ и $B$, чтобы оставить простор для маневра и не запутать аудиторию, ведь итоговые множества $I$ и $J$ будут получены путем модификации $A$ и $B$.
Решение проблемы пересечения предлагает один из слушателей: необходимо найти пересечение множеств $A$ и $B$ и просто удалить все общие элементы из обоих подмножеств. Профессор поясняет логику на простом примере: если оба множества содержат элемент $x_1$, мы можем вычесть его из обеих частей уравнения равенства сумм. Равенство от этого не изменится, но элемент $x_1$ исчезнет из обоих множеств, делая их ближе к состоянию непересекаемости.
Формально мы определяем искомые множества через операцию разности множеств:
$$I = A \setminus B$$ $$J = B \setminus A$$
Это означает, что из множества $A$ удаляются все элементы, которые одновременно присутствуют в $B$, и наоборот. Визуально это легко представить с помощью диаграммы Венна в виде двух пересекающихся кругов, где множествами $I$ и $J$ становятся крайние «полумесяцы», очищенные от общей центральной зоны пересечения. Профессор добавляет, что хотя демонстрация промежуточных стадий не является строго обязательной с точки зрения чистой математики, она колоссально важна педагогически, так как показывает читателю реальный путь размышлений исследователя.
Алгебраически это подтверждается разбиением исходной суммы подмножества $A$ на две части: сумму элементов из пересечения $A \cap B$ и сумму элементов из чистого остатка $I$. Аналогично разбивается сумма для подмножества $B$. Поскольку исходные полные суммы были равны, мы можем просто сократить одинаковую сумму пересекающихся элементов из обеих частей уравнения. В результате мы получаем чистые непересекающиеся множества $I$ и $J$ с равными суммами, что и требовалось доказать.
В завершение разбора этой леммы Анкур Моитра делится поразительным фактом: несмотря на то, что мы только что легко доказали само существование таких подмножеств, в мире компьютерных наук неизвестно ни одного быстрого алгоритма для их реального поиска. Если выписать случайные 20 четырехзначных чисел, вам придется практически вручную перебирать колоссальное количество вариантов, чтобы найти совпадение.
Аналогичный пример можно привести с населением стран мира: математически доказано, что существуют группы стран с абсолютно одинаковым суммарным числом жителей, но найти эти группы можно только полным исчерпывающим перебором. Данная вычислительная сложность активно используется в современной криптографии.
📉 Теорема Эрдёша — Секереша о подпоследовательностях 36:50
Профессор Моитра переходит к разбору самого сложного результата лекции — полноценной красивой теоремы из области комбинаторики. Расширенные версии этой задачи будут включены в первые домашние задания студентов для самостоятельной практики.
Теорема (исторически известная как теорема Эрдёша — Секереша) утверждает: в любой произвольной перестановке чисел от $1$ до $n \cdot m + 1$ обязательно существует либо возрастающая подпоследовательность длиной не менее $m + 1$, либо убывающая подпоследовательность длиной не менее $n + 1$. Здесь $n$ и $m$ — произвольные заданные параметры.
Моитра разъясняет терминологию. Под перестановкой понимается любое изменение исходного порядка чисел: мы словно берем упорядоченную колоду карт и тщательно ее перемешиваем, получая случайную последовательность. Подпоследовательность при этом не обязана быть непрерывной — выбранные числа могут стоять в исходной строке на расстоянии друг от друга, но их относительный порядок следования слева направо должен сохраняться.
Для наглядности лектор предлагает разобрать конкретный пример с параметрами $m = n = 3$. В таком случае мы рассматриваем перестановку чисел от $1$ до $3 \cdot 3 + 1 = 10$. Пусть нам дана следующая последовательность чисел:
$$\langle 3, 2, 1, 6, 5, 4, 9, 8, 7, 10 \rangle$$
В этой последовательности можно найти возрастающую подпоследовательность длины 4, состоящую из элементов 3, 6, 9 и 10. Эти элементы не идут подряд, но они строго возрастают. Также здесь есть убывающая подпоследовательность длины 3, например, 3, 2, 1. Данный пример не только иллюстрирует абстрактные определения, но и доказывает, что рамки теоремы «завязаны» очень плотно: мы нашли возрастающую цепочку длины 4 ($m+1$), но не можем построить ничего длиннее, равно как и не можем найти убывающую цепочку длиннее 3 ($n$).
Доказать эту теорему можно с помощью принципа Дирихле, однако стандартные попытки сделать голубями сами позиции или цепочки ни к чему не приведут. Потребуется ввести тонкое определение для отслеживания математического прогресса одновременно по двум направлениям: длине максимальной возрастающей и длине максимальной убывающей цепочки.
Для каждого элемента, стоящего на позиции $s$ в нашей последовательности, мы вводим две вспомогательные переменные:
- $I_s$ — длина самой длинной возрастающей подпоследовательности, заканчивающейся ровно в позиции $s$.
- $D_s$ — длина самой длинной убывающей подпоследовательности, также заканчивающейся в позиции $s$.
Чтобы продемонстрировать работу этих переменных, профессор составляет на доске таблицу для нашего примера. Один из студентов просит уточнить значения для элементов 3 и 6. Моитра подробно объясняет, что для элемента 6, стоящего на четвертой позиции, самая длинная возрастающая цепочка, в ней заканчивающаяся, имеет длину 2 (например, подпоследовательность $\langle 3, 6 \rangle$). При этом самая длинная убывающая подпоследовательность, оканчивающаяся на шестерке, имеет длину всего 1, поскольку все элементы левее шестерки, которые меньше ее, не могут образовать убывающую пару. Фиксация конечной точки $s$ и движение слева направо — это фундамент понимания данного доказательства.
Переходя к доказательству, мы берем две произвольные позиции в последовательности — $s$ и $t$. Без потери общности предположим, что позиция $s$ находится правее позиции $t$, то есть $s > t$. Лектор разбирает два возможных случая соотношения самих элементов, стоящих на этих позициях:
- Случай 1: элемент на позиции $s$ строго больше элемента на позиции $t$ ($x_s > x_t$). В этом случае мы берем лучшую возрастающую подпоследовательность, которая заканчивалась в точке $t$ (ее длина равна $I_t$), и просто приписываем к ней в конец наш элемент $x_s$. Поскольку $x_s > x_t$, цепочка остается строго возрастающей, а ее длина увеличивается на единицу. Соответственно, выполняется неравенство $I_s \ge I_t + 1$.
- Случай 2: элемент на позиции $s$ строго меньше элемента на позиции $t$ ($x_s < x_t$). Применяя зеркальное рассуждение, мы можем взять лучшую убывающую цепочку, заканчивающуюся в точке $t$, и приписать к ней элемент $x_s$. Цепочка останется валидной убывающей подпоследовательностью, а значит, $D_s \ge D_t + 1$.
Важнейший промежуточный вывод: для любых двух разных позиций $s$ и $t$ пары координат $(I_s, D_s)$ и $(I_t, D_t)$ обязаны отличаться, так как либо первая координата у одной пары строго больше, либо вторая.
Теперь соберем все воедино и применим метод от противного. Предположим, что теорема неверна. Это означает, что в нашей перестановке нет возрастающих подпоследовательностей длины $m + 1$ и нет убывающих подпоследовательностей длины $n + 1$. Следовательно, для любой позиции значение $I_s$ может принимать целые значения максимум от $1$ до $m$, а значение $D_s$ — максимум от $1$ до $n$.
Эти пары значений $(I_s, D_s)$ и есть наши гнезда. Общее число возможных различных пар (размерность пространства гнезд) составляет ровно $n \cdot m$.
Голубями же в данном доказательстве выступают сами физические позиции элементов в последовательности. Всего у нас есть $n \cdot m + 1$ элементов, а значит, и столько же позиций-голубей.
Поскольку количество голубей ($n \cdot m + 1$) строго больше количества гнезд ($n \cdot m$), согласно принципу Дирихле, обязаны найтись две разные позиции $s$ и $t$, которые попадут в одно и то же гнездо. Это означает, что их координаты совпадут:
$$(I_s, D_s) = (I_t, D_t)$$
Однако чуть ранее мы строго доказали, что для любых двух различных позиций эти пары обязаны отличаться (одна из координат обязательно будет больше минимум на единицу). Мы зашли в тупик и получили явное противоречие, что полностью опровергает наше предположение от противного и доказывает истинность теоремы Эрдёша — Секереша.
Отвечая на вопрос студента о том, как можно было додуматься до столь неочевидного шага с введением пар прогресса, Моитра соглашается, что математика — штука сложная, и придумать такое с нуля на экзамене никто не требует. Однако эта структура имеет глубокое сходство с методами динамического программирования в алгоритмах. Чтобы узнать характеристики цепочки в текущей точке, нам достаточно знать лишь агрегированные ответы для предыдущих подзадач, не вникая в то, из каких именно элементов они состояли.
🧬 Нелинейность семейного древа человечества 55:06
В качестве финального и самого любимого примера применения принципа Дирихле Анкур Моитра предлагает разобрать тему, которая касается абсолютно каждого человека. Он вызывает добровольца по имени Энтони из Сент-Луиса, увлекающегося кривыми второго порядка. Используя свои математические суперсилы, профессор заявляет Энтони глубоко личный факт: его семейное древо на самом деле вовсе не является деревом в строгом математическом смысле.
Лектор признается, что когда-то давно аналогичный трюк на лекции вызвал сильное смущение у студентки, которая восприняла это как раскрытие реальной тайны ее семьи, поэтому теперь он называет вызываемых студентов «жертвами». Однако смущаться здесь нечего: нелинейность родословной — это непреложный математический факт, верный для любого живущего на Земле человека.
Профессор формулирует лемму: генеалогическое древо любого человека гарантированно содержит предка, чьи родители являлись кровными родственниками. Для доказательства Моитра предлагает опереться на четыре абсолютно неоспоримых биологических и исторических аксиомы:
- У каждого человека есть ровно два биологических родителя.
- Ни один человек в истории не заводил детей в возрасте старше 100 лет.
- Человеческий род существует как минимум 4000 лет.
- Общее число людей, когда-либо живших на Земле за всю ее историю, по оценкам биологов, ограничено сверху числом $10^{12}$ (один триллион человек).
Построим абстрактную модель, аналогичную графу знакомств. Начнем продвигаться от конкретного человека назад в прошлое, воссоздавая сетку позиций его предков. На первом шаге находитесь вы сами, далее идут 2 родителя, затем 4 бабушки и дедушки и так далее.
Учитывая, что человечество существует не менее 4000 лет, а смена поколения происходит максимум раз в 100 лет, мы можем гарантированно проследить родословную вглубь как минимум на 40 поколений.
Количество идеальных «вакантных мест» (позиций) в таком бинарном дереве предков на глубине 40 поколений составит ровно $2^{40}$. Проведем простое математическое сравнение. Нам известно, что $2^{10} = 1024 > 1000 = 10^3$. Возводя это неравенство в четвертую степень, мы получаем:
$$2^{40} > (10^3)^4 = 10^{12}$$
Таким образом, число позиций в генеалогическом древе одного-единственного человека ($2^{40}$) строго превышает верхний предел общего количества людей, когда-либо существовавших в истории планеты ($10^{12}$).
Применяя принцип Дирихле, где «голубями» являются позиции предков в генеалогической схеме, а «гнездами» — реальные уникальные человеческие личности, жившие в прошлом, мы неизбежно получаем коллизию. Как минимум две различные позиции в схеме предков должны быть заняты одним и тем же реальным человеком.
Это математически доказывает, что ветви родословной любого человека в прошлом пересекались, и его семейное древо представляет собой не дерево, а граф с циклами, что подтверждает неизбежность кровного родства среди далеких предков.
🎲 Мотивация к изучению теории вероятностей 1:02:03
Завершая обсуждение принципа Дирихле, профессор Моитра анонсирует переход к следующему крупному блоку лекций, который будет посвящен дискретной теории вероятностей и комбинаторике. Весь дальнейший материал курса так или иначе будет опираться на искусство подсчета.
Профессор выделяет четыре ключевые причины, почему изучение дискретной вероятности критически важно для современных прикладных математиков и специалистов по компьютерным наукам:
- Связь с комбинаторным подсчетом: вероятность позволяет оценивать шансы возникновения определенных математических объектов с заданными свойствами при их случайном выборе.
- Пробабилистический метод: это продвинутый метод, позволяющий доказать существование крайне странных и сложных математических структур, которые иначе невозможно сконструировать явным образом. Мы доказываем, что вероятность встретить такой объект при случайном выборе строго больше нуля, а значит, он точно существует, даже если мы не знаем алгоритма его точного поиска — это очень похоже на наше доказательство существования равных подмножеств сумм.
- Рандомизированные алгоритмы: современные вычислительные методы часто используют случайность. Например, самые быстрые тесты на простоту (определение, является ли гигантское многозначное число простым) фундаментально основаны на генерации случайных чисел, и для их анализа необходим развитый аппарат теории вероятностей.
- Теория кодирования: вероятность лежит в основе моделирования каналов связи с помехами. Она незаменима, например, при проектировании систем передачи данных со спутников на Землю, позволяя создавать алгоритмы надежного исправления ошибок, возникающих из-за шума в пространстве.
Перед окончанием лекции Моитра вводит базовый формализм, который потребуется студентам на следующем занятии. Фундаментом любой вероятностной модели является пространство элементарных исходов, или выборочное пространство. Точки внутри этого пространства представляют собой все возможные уникальные исходы случайного эксперимента. В качестве классического примера рассматривается бросок стандартной игральной кости, где пространство исходов состоит из шести точек (числа от 1 до 6).
Каждому исходу $x$ в пространстве сопоставляется число — его вероятность $p(x)$, удовлетворяющая двумя базовым аксиомам:
- Вероятность любого исхода неотрицательна: $p(x) \ge 0$ для всех $x$.
- Сумма вероятностей всех возможных исходов в пространстве строго равна единице: $\sum p(x) = 1$.
Для честной игральной кости вероятность каждого исхода равна $1/6$. Однако в курсе будут рассматриваться и более экзотические случаи, когда пространство исходов бесконечно. Например, эксперимент по подбрасыванию монеты до тех пор, пока впервые не выпадет орел, теоретически может продолжаться бесконечно долго, но базовые аксиомы вероятности прекрасно работают и в таких условиях.
Важным понятием являются события, которые математически определяются как подмножества пространства исходов. Вероятность составного события рассчитывается как сумма вероятностей всех элементарных исходов, входящих в это подмножество. Пример такого события — выпадение четного числа при броске кости, что соответствует подмножеству ${2, 4, 6}$.
Также Моитра вводит понятие дополнения события, обозначаемое как $\bar{T}$ или $\text{not } T$. Дополнение включает в себя все исходы пространства, которые не входят в исходное событие $T$. Вероятность дополнения вычисляется по очевидной формуле:
$$P(\bar{T}) = 1 - P(T)$$
На следующей лекции, которая состоится в четверг, профессора планируют перейти к разбору условной вероятности, которая крайне контринтуитивна для человеческого восприятия. Будут рассмотрены не только классические головоломки вроде парадокса Монти Холла, но и реальные примеры из медицинской практики, когда практикующие врачи фатально ошибаются в интерпретации результатов анализов из-за неверного понимания условных вероятностей.
