Индикаторы: ожидаемое число без распределения

Если ты разложишь счётчик на индикаторы, выведешь ожидаемое число обновлений максимума и объяснишь, почему ожидаемое число совпадений - не вероятность совпадения, - листай до «Теперь сам».

Как думаешь, сколько раз обновится максимум

Программа ищет наибольшее число в массиве из 1000 разных чисел, стоящих в случайном порядке. Она идёт слева направо и каждый раз, когда встречает число больше всех предыдущих, записывает его в переменную.

Прежде чем читать дальше, оцени, сколько раз в среднем произойдёт запись: около 500, около 30 или меньше десяти? Ответ - 7,49. Чтобы получить его напрямую, пришлось бы найти вероятность ровно одной записи, ровно двух, ровно трёх и так до тысячи. Через индикаторы он считается в одну строку.

На что это похоже

Учёт посещаемости. Нужно узнать, сколько человек в среднем приходит на занятие. Можно выписать все возможные составы группы с их вероятностями - их 2³⁰ для тридцати человек. А можно завести на каждого студента одну клеточку: пришёл - единица, не пришёл - ноль. Число пришедших - сумма клеточек. Среднее число пришедших - сумма средних по клеточкам, а среднее одной клеточки - это просто доля занятий, на которые этот студент ходит.

Друзья могут ходить парами, перед сессией приходят все разом - клеточки зависимы как угодно. На сумму средних это не влияет.

Механизм: счётчик как сумма нулей и единиц

Индикатор события A - случайная величина I, равная 1 на исходах, где A случилось, и 0 на остальных. Её ожидание по определению:

E[I] = 1 · P(A) + 0 · (1 − P(A)) = P(A)

Умножение на ноль стирает всё, кроме вероятности события. В этом весь смысл приёма: ожидание индикатора не нужно вычислять, оно уже известно, как только известна вероятность.

Теперь пусть X считает, сколько из событий A₁, …, Aₙ случилось. Тогда X = I₁ + I₂ + … + Iₙ, и по линейности

E[X] = E[I₁] + … + E[Iₙ] = P(A₁) + … + P(Aₙ)

Работа по шагам:

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

Пример, который решается в уме. В гардеробе n человек получают свои куртки в случайном порядке: каждая из n! раздач равновозможна (n! = 1 · 2 · … · n - число способов раздать n курток n людям). Сколько человек в среднем получат свою куртку? Событие Aᵢ - «человек i получил свою». Его куртка с равной вероятностью досталась любому из n, поэтому P(Aᵢ) = 1/n. Сумма: n · 1/n = 1. В среднем ровно один человек, сколько бы их ни было - пять или пять миллионов. События зависимы: если все, кроме одного, получили свои куртки, последний тоже получит свою. Линейность этого не замечает.

Правило

Ожидание индикатора равно вероятности события: E[I] = P(A). Если величина X считает, сколько из событий A₁, …, Aₙ случилось, то E[X] = P(A₁) + … + P(Aₙ) - при любой зависимости между событиями. Вероятность того, что случилось хотя бы одно, не больше этого числа: P(X ≥ 1) ≤ E[X].

Разбор: обновления максимума

Событие Aᵢ - «число на месте i больше всех предыдущих». Среди первых i чисел наибольшее с равной вероятностью стоит на любом из i мест: порядок случаен, и ни одно место не лучше другого. На последнем, i-м, оно стоит с вероятностью 1/i. Значит

E[обновлений] = 1/1 + 1/2 + 1/3 + … + 1/n = Hₙ

Это гармоническое число из раздела про суммы: Hₙ ≈ ln n + 0,577, где ln - натуральный логарифм, по основанию e ≈ 2,718. Добавка 0,577 - постоянная, к которой стремится разность Hₙ − ln n; для тысячи ln 1000 = 6,91, и вместе с ней получается 7,49. Логарифм появился, потому что вероятность нового максимума убывает как 1/i, а сумма таких долей растёт как логарифм: на каждом удвоении длины массива прибавляется примерно одна и та же величина, около 0,69.

Проверка бросками: 60 случайных перестановок чисел от 0 до 999. random.shuffle(a) перемешивает список на месте, все порядки равновозможны. Числа неотрицательны, поэтому начальное значение −1 меньше любого из них; для произвольных чисел начинать нужно с первого элемента.

import random

def rekordov(a):
    luchshij = -1
    skolko = 0
    for x in a:
        if x > luchshij:
            luchshij = x
            skolko = skolko + 1
    return skolko

random.seed(11)
n = 1000
opytov = 60
a = list(range(n))
vsego = 0
for opyt in range(opytov):
    random.shuffle(a)
    vsego = vsego + rekordov(a)

garmonicheskoe = 0
for i in range(1, n + 1):
    garmonicheskoe = garmonicheskoe + 1 / i
print(round(vsego / opytov, 2), round(garmonicheskoe, 2))

7.72 7.49

В опыте 7,72, по формуле 7,49. Шестьдесят повторов дают среднее с разбросом в несколько десятых; к самому числу 7,49 оно подошло бы на тысячах повторов.

Из этого следует практический вывод про цикл поиска максимума: сравнений в нём всегда одно на элемент, а присваиваний в среднем Hₙ. Ветка «нашёл новый максимум» почти никогда не выполняется, и её цена на случайных данных не важна. На отсортированном по возрастанию массиве она выполняется n раз: ожидание посчитано по случайному порядку и про худший вход ничего не говорит.

Разбор: инверсии, и чем ожидаемое число отличается от вероятности

Инверсия - пара мест i < j, на которых числа стоят в неправильном порядке: a[i] > a[j]. Сортировка вставками делает ровно столько сдвигов, сколько в массиве инверсий, - это было в разделе про сортировки. Сколько их в случайной перестановке?

Событие для пары мест (i, j) - «эта пара инверсия». Два разных числа на двух местах стоят в одном из двух порядков с равной вероятностью: 1/2. Пар мест n(n − 1) / 2. Ожидаемое число инверсий - n(n − 1) / 4.

import random

def inversij(a):
    k = 0
    for i in range(len(a)):
        for j in range(i + 1, len(a)):
            if a[i] > a[j]:
                k = k + 1
    return k

random.seed(8)
n = 40
opytov = 50
a = list(range(n))
vsego = 0
for opyt in range(opytov):
    random.shuffle(a)
    vsego = vsego + inversij(a)
print(round(vsego / opytov, 1), n * (n - 1) / 4)

389.7 390.0

Отсюда «сортировка вставками на случайном входе делает около n² / 4 сдвигов» - вдвое меньше худшего случая, но всё ещё квадрат.

Теперь граница приёма. В группе 23 человека. Пар людей 23 · 22 / 2 = 253, каждая пара совпадает по дню рождения с вероятностью 1/365. Ожидаемое число совпавших пар - 253 / 365 ≈ 0,69. А вероятность, что совпала хотя бы одна пара, - 0,507, это известный парадокс дней рождения.

Числа разные, и разница принципиальна. Ожидаемое число пар усредняет и те группы, где совпали сразу три человека и пар получилось три. Вероятность считает такую группу один раз. Индикаторы дают первое число; второе они дают только как оценку сверху: величина, равная нулю или не меньше единицы, в среднем не меньше вероятности того, что она ненулевая. Отсюда P(X ≥ 1) ≤ E[X]: 0,507 ≤ 0,69. Когда ожидаемое число плохих событий намного меньше единицы, оценка становится точной и рабочей: «ожидаемое число коллизий 0,001» означает «коллизия случится не чаще одного раза на тысячу».

Что ломается без этого

Попытка найти распределение. Вероятность ровно трёх обновлений максимума в массиве из тысячи чисел выражается громоздкой суммой. Тот, кто начинает с неё, до ответа обычно не доходит. Вопрос «сколько в среднем» не требует знать, как часто бывает каждое значение.

Ожидаемое число вместо вероятности. «Ожидается 0,69 совпадения, значит вероятность совпадения 69%» - ошибка из прошлого разбора. При ожидаемом числе 5 вероятность никак не 500%.

Вероятность одного события без симметрии. 1/i для нового максимума получено из того, что порядок случаен. Если данные приходят почти отсортированными по возрастанию, каждое новое число - максимум с вероятностью, близкой к единице, и сумма близка к n, а не к ln n.

Индикаторы для разброса. Сумма вероятностей даёт среднее и ничего не говорит о том, насколько от него отклоняются значения. Для разброса зависимость между событиями уже важна.

Зачем это в работе

Почти каждая оценка «в среднем» для рандомизированного алгоритма получена этим приёмом. Быстрая сортировка со случайным опорным: событие - «элементы i и j сравнивались», сумма по парам даёт 1,39 · n · log₂ n сравнений; это разобрано через две главы. Хеш-таблица: событие - «ключ j попал в ту же ячейку, что и искомый», сумма даёт ожидаемую длину цепочки. Список с пропусками: событие - «узел поднялся на этаж k».

В проектировании систем то же рассуждение отвечает на вопросы про нагрузку. Сто тысяч ключей разложены по ста узлам кеша случайно, один узел выключили - сколько ключей в среднем потеряется? Событие для ключа - «лежал на выключенном узле», вероятность 1/100, ответ - тысяча, без единого слова о том, как именно ключи распределены.

Теперь сам

1. Монету бросают 100 раз. Через индикаторы найди ожидаемое число орлов.
2. В массив из 365 ячеек случайно и независимо кладут 50 ключей. Чему равно ожидаемое число пар ключей, попавших в одну ячейку?
3. Случайная перестановка чисел от 1 до n. Место i (не крайнее) - «пик», если число на нём больше обоих соседей. Чему равно ожидаемое число пиков?
4. В гардеробе 200 человек. Чему равно ожидаемое число людей, получивших чужую куртку?
5. Ожидаемое число ошибок при передаче блока - 0,002. Что можно сказать о вероятности, что блок передан с ошибкой?