Мартингал и Азима: раскрываем случайность по одному шагу

Если умеешь отделить ограниченный скачок прогноза от независимости входов, листай до «Теперь сам».

Как думаешь, можно ли продолжить, когда индикаторы зависимы

Бросаем шары по ящикам и считаем пустые. Индикаторы пустоты связаны: зная, что один ящик пуст, мы узнаём, что все шары попали в другие ящики. Это меняет условные вероятности их пустоты. При этом каждый следующий шар по-прежнему независимо выбирает любой из всех ящиков. Применить неравенство для суммы независимых индикаторов напрямую нельзя. Но сами положения шаров независимы. Будем раскрывать их по одному и следить не за индикаторами, а за прогнозом окончательного числа пустых ящиков.

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

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

Механизм: условное ожидание сглаживает неизвестное

Пусть итог F зависит от независимых входов X₁,...,Xₙ. После раскрытия первых i входов определим Mᵢ = E[F | X₁,...,Xᵢ]. Начало M₀=E[F], конец Mₙ=F. Усреднение следующего прогноза по ещё неизвестному Xᵢ₊₁ возвращает текущий прогноз. Это свойство повторного условного ожидания, которое и даёт мартингал.

Если изменение одной координаты меняет F не больше чем на dᵢ, то возможные условные прогнозы после её раскрытия также лежат в интервале ширины не больше dᵢ. При независимых входах отсюда следует ограничение скачка |Mᵢ-Mᵢ₋₁|≤dᵢ. Азумы уже применима. Используя дополнительно ширину интервала, получают ограниченные разности: P(|F-E[F]|≥t) ≤ 2 exp(-2t²/Σdᵢ²).

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

Правило

Сначала предъяви информацию прошлого, условный прогноз и границу изменения. Лишь затем подставляй параметры в хвостовую оценку. Условие мартингала относится к ожиданию следующего значения, а не к его равенству предыдущему на каждом запуске.

Разбор: прогноз числа единиц

Для восьми независимых честных битов после i раскрытий прогноз суммы равен числу уже видимых единиц плюс (8-i)/2. Раскрытие следующего бита меняет его на половину в любую сторону. Поэтому в Азиме можно взять cᵢ=1/2, хотя изменение окончательной суммы при замене одного бита равно единице.

from itertools import product
from math import exp

N = 8
paths = list(product((0, 1), repeat=N))


def forecasts(bits):
    seen = 0
    values = [N / 2]
    for i, bit in enumerate(bits, 1):
        seen += bit
        values.append(seen + (N - i) / 2)
    return values


sample = (1, 0, 1, 1, 0, 0, 1, 0)
print("Прогнозы:", forecasts(sample))
for bits in paths:
    values = forecasts(bits)
    assert all(abs(b-a) == 0.5 for a, b in zip(values, values[1:]))
for t in (1, 2, 3):
    exact = sum(abs(sum(bits)-N/2) >= t for bits in paths)
    exact /= len(paths)
    azuma = min(1, 2 * exp(-t*t / (2 * N * 0.5**2)))
    differences = min(1, 2 * exp(-2 * t*t / N))
    assert exact <= azuma + 1e-12
    print(t, f"{exact:.6f}", f"{azuma:.6f}",
          f"{differences:.6f}")


def empty(places, boxes):
    return boxes - len(set(places))


for places in product(range(3), repeat=4):
    old = empty(places, 3)
    for i in range(4):
        for replacement in range(3):
            changed = list(places)
            changed[i] = replacement
            assert abs(empty(changed, 3)-old) <= 1
print("Влияние одного шара проверено на всех малых входах")

Прогнозы: [4.0, 4.5, 4.0, 4.5, 5.0, 4.5, 4.0, 4.5, 4.0]
1 0.726562 1.000000 1.000000
2 0.289062 0.735759 0.735759
3 0.070312 0.210798 0.210798
Влияние одного шара проверено на всех малых входах

Код перебирает все 256 равновероятных входов и сравнивает точный хвост с обеими корректными оценками. Они здесь совпадают: Азумы использовала более точную границу скачка половина, а ограниченные разности - ширину влияния один. Совпадение в этом примере не означает взаимозаменяемость предпосылок вообще.

Разбор: число пустых ящиков

Перенеси один шар из ящика a в b. Освобождение a может увеличить число пустых на один, заполнение b уменьшить на один. Если срабатывают оба изменения, они взаимно сокращаются. Поэтому итог меняется не больше чем на один, а не на два. Для m независимо размещённых шаров сумма dᵢ² равна m.

Получаем P(|F-E[F]|≥t) ≤ 2 exp(-2t²/m). При этом E[F]=n(1-1/n)ᵐ вычисляется точно линейностью ожидания. Ни на одном шаге мы не предполагали независимость признаков пустоты разных ящиков. Независимыми должны быть входные размещения шаров.

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

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

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

При анализе случайной структуры итог часто устроен сложно и не раскладывается на независимые части: число конфликтов, занятых узлов или пустых бакетов. Если отдельное решение генератора влияет на итог ограниченно, мартингал позволяет оценить стабильность результата без явного вычисления его полного распределения.

Теперь сам

Функция независимых ста битов меняется не больше чем на два при замене одного бита. Какова сумма dᵢ² для ограниченных разностей? Что нужно доказать, кроме этой арифметики?