Линейность математического ожидания — это фундаментальный принцип теории вероятностей, который позволяет упростить решение сложных задач в комбинаторике, не прибегая к прямому подсчёту всех возможных исходов. Лекция от MIT OpenCourseWare демонстрирует, как этот инструмент помогает находить средние значения и доказывать существование объектов с заданными свойствами через вероятностный метод.
📈 Принцип линейности математического ожидания 0:27
Математическое ожидание обладает свойством линейности: если у нас есть набор случайных величин $X_1, X_2, \dots, X_n$ и константы $c_1, c_2, \dots, c_n$, то ожидание их линейной комбинации равно сумме ожиданий этих величин, умноженных на соответствующие константы.
Математически это выражается так: $$E\left[\sum_{i=1}^n c_i X_i\right] = \sum_{i=1}^n c_i E[X_i]$$
Важно помнить, что это правило работает только для суммы. Для произведения случайных величин равенство обычно не выполняется, за исключением случаев, когда величины независимы или не коррелируют друг с другом.
🔀 Среднее количество неподвижных точек перестановки 1:49
Рассмотрим задачу: каково среднее количество неподвижных точек в случайной перестановке чисел от $1$ до $n$? Неподвижная точка — это число, которое при перестановке отображается само на себя.
Попытка подсчитать количество перестановок с $0, 1, 2$ и более неподвижными точками напрямую может быть крайне сложной. Вместо этого применяется метод индикаторных случайных величин:
- Введем случайную величину $X_i$, которая равна $1$, если элемент $i$ является неподвижной точкой, и $0$ в противном случае.
- Вероятность того, что конкретный элемент $i$ при случайной перестановке останется на месте, составляет $1/n$.
- Общее число неподвижных точек $X$ равно сумме всех индикаторов: $X = X_1 + X_2 + \dots + X_n$.
- Согласно линейности ожидания: $E[X] = E[X_1] + E[X_2] + \dots + E[X_n]$.
- Поскольку каждое $E[X_i] = 1/n$, сумма $n$ таких слагаемых дает в точности $1$.
Таким образом, среднее число неподвижных точек в случайной перестановке всегда равно единице, независимо от размера $n$.
🏆 Гамильтоновы пути в случайных турнирах 5:23
Более сложная задача касается теории графов, а именно понятия турнира. Турнир — это ориентированный граф, в котором между каждой парой вершин есть ровно одно ребро. Гамильтонов путь — это путь, проходящий через каждую вершину графа ровно один раз.
Существует теорема: для любого $n$ существует турнир на $n$ вершинах, содержащий не менее $n! \cdot 2^{-(n-1)}$ гамильтоновых путей.
Доказательство через вероятностный метод 8:45
Вместо явной конструкции (которая была бы крайне трудной) используется вероятностный подход:
- Рассмотрим случайный турнир, где направление каждого из $n(n-1)/2$ ребер определяется подбрасыванием честной монеты.
- Любая из $n!$ возможных перестановок вершин образует потенциальный путь.
- Для того чтобы этот путь стал гамильтоновым (все ребра ориентированы по ходу пути), необходимо, чтобы все $n-1$ ребер «выпали» в нужном направлении.
- Вероятность этого события для каждой конкретной перестановки составляет $2^{-(n-1)}$.
- По линейности ожиданий, среднее количество таких путей равно $n! \cdot 2^{-(n-1)}$.
Так как среднее количество путей равно этому числу, логически должен существовать хотя бы один конкретный случай (турнир), где количество таких путей как минимум не меньше среднего. Это элегантное доказательство позволяет избежать сложного перебора вариантов.
