Математическое ожидание и линейность ожидания

Математическое ожидание и его линейность — приём, который превращает страшные задачи в сложение простых слагаемых.

Математическое ожидание дискретной случайной величины X — это E[X] = ∑ x · P(X = x), среднее значение по всем исходам с весами-вероятностями.

Зачем это в олимпиадах

Математическое ожидание (матожидание) — это «среднее значение» случайной величины, и оно отвечает на вопросы «сколько в среднем шагов», «какова ожидаемая сумма», «сколько в среднем сравнений сделает алгоритм». А линейность ожидания — едва ли не самый красивый приём всей олимпиадной вероятности: ожидание суммы всегда равно сумме ожиданий, даже если слагаемые зависимы. Это позволяет разбивать монструозную величину на простые индикаторы и складывать их ожидания. Овладев этим, вы будете решать задачи, которые «в лоб» неподъёмны.

Матожидание: интуиция и определение

Бросаем кубик. Какое число выпадет «в среднем»? Каждая грань равновероятна, поэтому E = (1+2+3+4+5+6)/6 = 3.5. Формально E[X] = ∑ x·P(X=x) — взвешенная сумма значений. Матожидание не обязано быть достижимым значением (3.5 на кубике не выпадет) — это центр тяжести распределения.

from fractions import Fraction

# Ожидание для честного кубика
values = range(1, 7)
E = sum(Fraction(x, 6) for x in values)
print(E, float(E))

# Ожидание суммы двух кубиков считается напрямую
from itertools import product
outcomes = list(product(range(1, 7), repeat=2))
E2 = Fraction(sum(a + b for a, b in outcomes), len(outcomes))
print(E2, float(E2))

Вывод:

7/2 3.5
7 7.0

Линейность ожидания

Линейность ожидания: E[X + Y] = E[X] + E[Y] для любых случайных величин — независимость не требуется. Также E[c·X] = c·E[X].

Это свойство кажется скромным, но его сила в том, что оно не требует независимости. Сумму двух кубиков мы только что посчитали перебором 36 исходов — а по линейности это просто E[X₁] + E[X₂] = 3.5 + 3.5 = 7, мгновенно. Магия начинается, когда величину представляют суммой индикаторов — случайных величин, равных 1, если событие произошло, и 0 иначе. Ожидание индикатора равно вероятности события: E[Iᴬ] = P(A). Поэтому ожидание «числа произошедших событий» = сумма их вероятностей.

from fractions import Fraction

# Ожидаемое число шестёрок при 10 бросках кубика.
# X = сумма индикаторов "i-й бросок дал 6". E[I_i] = 1/6.
n = 10
E = sum(Fraction(1, 6) for _ in range(n))    # линейность: складываем ожидания
print(E, float(E))
# даже если бы броски были зависимы, формула E = n * (1/6) осталась бы верной

Вывод:

5/3 1.6666666666666667

Ожидаемое число шестёрок за 10 бросков — 10 · 1/6 = 5/3 ≈ 1.67. Мы не перебирали 6¹⁰ исходов и не учитывали совместные распределения — линейность позволила сложить десять простых ожиданий. Это и есть фирменный приём.

Разбор задачи: ожидаемое число бросков до первой шестёрки

Сколько в среднем бросков нужно, чтобы выпала шестёрка? Пусть E — искомое ожидание. Первый бросок мы делаем всегда. С вероятностью 1/6 сразу успех (закончили за 1 бросок); с вероятностью 5/6 неудача — и мы оказываемся в исходной ситуации, потратив один бросок. Получаем уравнение E = 1 + (5/6)·E, откуда E = 6. Это геометрическое распределение: ожидание числа испытаний до первого успеха с вероятностью p равно 1/p.

from fractions import Fraction
import random

p = Fraction(1, 6)
E_formula = 1 / p
print(E_formula)                  # 6

# Проверка симуляцией Монте-Карло
random.seed(1)
trials = 200000
total = 0
for _ in range(trials):
    count = 0
    while True:
        count += 1
        if random.randint(1, 6) == 6:
            break
    total += count
print(round(total / trials, 3))   # ожидаем ~6

Вывод:

6
6.01

Формула дала ровно 6, симуляция — 6.01. Совпадение подтверждает и вывод уравнения, и общий факт E = 1/p для геометрического распределения. Приём «составить уравнение на ожидание через один шаг» универсален для задач о случайных блужданиях и цепях.

Задача о собирателе купонов

Классика на линейность: в каждом киндере один из n разных вкладышей равновероятно. Сколько в среднем покупок нужно, чтобы собрать все n? Разобьём процесс на этапы: после того как собрано k разных вкладышей, вероятность получить новый — (n−k)/n, значит ожидаемое число покупок до нового вкладыша — n/(n−k). Суммируя по всем этапам, получаем n·(1 + 1/2 + … + 1/n) = n·Hₙ, где Hₙ — гармоническое число.

from fractions import Fraction

def coupon_collector(n):
    H = sum(Fraction(1, k) for k in range(1, n + 1))
    return n * H

for n in (1, 2, 6, 10):
    e = coupon_collector(n)
    print(n, float(e))

Вывод:

1 1.0
2 3.0
6 14.7
10 29.28968253968254

Для шести вкладышей нужно в среднем 14.7 покупок, для десяти — около 29.3. Здесь линейность ожидания снова разбила сложный процесс на сумму простых этапов. Асимптотика n·ln n — почему «последние» вкладыши собираются так долго.

Разбор задачи: ожидание максимума и индикаторный приём

Линейность сияет даже там, где величина не сумма «очевидных» слагаемых. Возьмём ожидание максимума двух кубиков. Прямо — суммировать x·P(max=x), считая распределение. Но есть изящный индикаторный трюк: для неотрицательной целой величины E[X] = ∑_x≥1 P(X ≥ x). Это «вертикальное» суммирование вероятностей хвостов, и оно часто проще «горизонтального». Сравним оба способа.

from fractions import Fraction
from itertools import product

outcomes = list(product(range(1, 7), repeat=2))

# Способ 1: напрямую через распределение максимума
E_direct = Fraction(sum(max(a, b) for a, b in outcomes), len(outcomes))

# Способ 2: E[X] = сумма P(X >= x) по x = 1..6
E_tail = sum(Fraction(sum(1 for a, b in outcomes if max(a, b) >= x),
                      len(outcomes))
             for x in range(1, 7))

print(E_direct, float(E_direct))
print(E_tail, E_direct == E_tail)

Вывод:

161/36 4.472222222222222
161/36 True

Оба способа дали 161/36 ≈ 4.47. Формула «ожидание = сумма вероятностей хвостов» E[X]=∑P(X≥x) — мощный частный случай линейности: мы представили X как сумму индикаторов [X≥1]+[X≥2]+… и сложили их ожидания. Этот приём незаменим в задачах об ожидаемом максимуме, длине, времени, где прямое распределение считать тяжело.

Подводные камни

Линейность не требует независимости — это её главная сила. Не «доказывайте» независимость зря.
Индикаторы — ваш друг. Сводите «число чего-то» к сумме индикаторов: E[I]=P(событие).
Уравнение на ожидание. Для «числа шагов до…» составляйте E = 1 + ∑ P·Eᵢ и решайте.
Точность. Считайте в Fraction, где нужна точность; ответ по модулю — через обратный элемент.

Итог

E[X]=∑ x·P(X=x) — взвешенное среднее значений величины.
Линейность E[X+Y]=E[X]+E[Y] работает всегда, даже при зависимости.
Индикаторы: E[Iᴬ]=P(A) — ключ к «числу произошедших событий».
Ожидание шагов до первого успеха — 1/p; собиратель купонов — n·Hₙ.