AMS: частотные моменты, независимость знаков и гарантии ошибки

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

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

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

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

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

Механизм: вторые и четвёртые произведения

У знака sᵢ значения плюс и минус один равновероятны. Раскрывая Z², получаем сумму fᵢ² и смешанные произведения fᵢfⱼsᵢsⱼ. Их ожидания нулевые при попарной независимости и нулевых средних. Поэтому E[Z²]=F₂.

Для разброса нужно E[Z⁴]. В разложении появляются произведения четырёх знаков. Если четыре различных знака независимы, ненулевыми остаются только члены с чётными кратностями индексов. Получается E[Z⁴]=Σfᵢ⁴+6Σᵢ<ⱼfᵢ²fⱼ²≤3F₂², значит Var(Z²)≤2F₂². Попарной независимости для этого шага недостаточно.

Среднее r независимых оценок имеет дисперсию не больше 2F₂²/r. По Чебышёву вероятность относительной ошибки больше ε не превосходит 2/(rε²). Выбрав r≥8/ε², делаем вероятность плохой группы не больше четверти. Медиана нечётного числа независимых групп неверна только если плохих больше половины; число групп порядка log(1/δ) даёт нужное усиление.

Это вероятностная гарантия для фиксированного потока, не зависящего от скрытых случайных знаков. Адаптивный противник, видящий сводку и подбирающий последующие обновления, требует другого анализа.

Правило

Укажи порядок независимости хеша и независимость повторов. Правильное ожидание не заменяет границу дисперсии. Обновление (i,Δ) прибавляет Δ·sᵢ; одинаковые хеши позволяют складывать сводки отдельных частей потока.

Разбор: полный перебор всех знаков

from itertools import product
from fractions import Fraction


def moments(frequencies):
    values = []
    for signs in product((-1, 1), repeat=len(frequencies)):
        z = sum(f * s for f, s in zip(frequencies, signs))
        values.append(z*z)
    mean = Fraction(sum(values), len(values))
    variance = sum((x-mean)**2 for x in values) / len(values)
    return mean, variance


frequencies = [3, 2, 1]
f2 = sum(x*x for x in frequencies)
mean, variance = moments(frequencies)
assert mean == f2
assert variance <= 2 * f2*f2
print("F2:", f2, "среднее:", mean, "дисперсия:", variance)
values = []
for a, b, c in product((-1, 1), repeat=3):
    d = a*b*c
    z = a+b+c+d
    values.append(z*z)
mean = Fraction(sum(values), len(values))
variance = sum((x-mean)**2 for x in values) / len(values)
print("Зависимые четыре знака:", mean, variance)
print("Ошибочная граница 2*F2^2:", 2*4**2)
left = [3, 0, 1]
right = [0, 2, 0]
for signs in product((-1, 1), repeat=3):
    z1 = sum(f*s for f, s in zip(left, signs))
    z2 = sum(f*s for f, s in zip(right, signs))
    z = sum(f*s for f, s in zip(frequencies, signs))
    assert z1+z2 == z
print("Слияние проверено для всех знаков")
print("Копий при epsilon=1/2:", 32)

F2: 14 среднее: 14 дисперсия: 196
Зависимые четыре знака: 4 48
Ошибочная граница 2*F2^2: 32
Слияние проверено для всех знаков
Копий при epsilon=1/2: 32

На трёх ключах можно перебрать все наборы знаков и получить точное ожидание без статистической погрешности. Код также проверяет сливаемость: одна и та же таблица знаков на двух узлах даёт счётчик, сумма которого равна счётчику объединённого потока. С разными таблицами эта линейность для одного запроса теряется.

Разбор: четыре знака с зависимостью

Возьми три независимых честных знака и четвёртый, равный их произведению. Любые три из четырёх независимы, но произведение всех четырёх всегда единица. Для частот, равных единице, ожидание квадрата остаётся четырём, а дисперсия достигает 48, нарушая стандартную границу 2F₂²=32. Именно четвёртые смешанные члены объясняют, почему красивого доказательства среднего недостаточно.

В потоке с удалениями частоты могут стать отрицательными, но квадратная оценка по-прежнему оценивает Σfᵢ². Момент первого порядка через модули уже не равен алгебраической сумме обновлений. Не смешивай модели положительного потока и потока с подписанными обновлениями.

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

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

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

Нужно оценить концентрацию событий по пользователям и сливать статистику потоков без передачи словаря частот. F₂ позволяет заметить, что нагрузка концентрируется на небольшой группе ключей. При выборе размера сводки формулы переводят требуемую относительную точность и вероятность ошибки в число счётчиков, а не в произвольное «возьмём побольше».

Теперь сам

При ε=1/2 сколько независимых копий достаточно в одной группе по условию r≥8/ε²? Почему одна группа ещё не даёт произвольно малую вероятность ошибки?