Конспект раздела: случайность как инструмент

Одна мысль на весь раздел

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

что покупают                          чем платят                            где в разделе
время, не зависящее от входа          случайным временем                    быстрая сортировка, кукушкина таблица
проверку дешевле вычисления           малой вероятностью пропустить ошибку  Фрейвалдс, тождество многочленов, отпечаток
память меньше данных                  приближённым ответом                  Блум, Моррис, count-min, HyperLogLog, квантили
выборку без знания размера            ничем: ответ точен по распределению   резервуар, ключи u^(1/w)
объект из необозримого множества      ожиданием смешивания                  алгоритм Метрополиса
доказательство существования          ничем: случайность не исполняется     вероятностный метод

Как части связаны

вероятность и независимость ──► матожидание ──► линейность ──► индикаторы ──► «сколько в среднем»
                                    │                              │
                                    │                              ├─► 1,39·n·log₂ n у быстрой сортировки
                                    │                              ├─► E[шум строки count-min] ≤ N/w
                                    │                              └─► E[Z²] = F₂, E[2ᶜ] = n + 1
                                    ▼
                    Марков ──► Чебышёв ──► Чернов и Хёфдинг ──► «как далеко от среднего»
                       │           │              │
                       │           │              ├─► размер выборки ln(2/δ)/(2ε²): опрос, π, квантили
                       │           │              └─► большинство и медиана: ошибка e^(−ck)
                       │           └─► медиана средних: второй момент, оценки сводок
                       └─► обрыв на 2T: Лас-Вегас → Монте-Карло;  count-min: шум ≤ 2N/w с вероятностью 1/2

шары и корзины ──► пустые ячейки e^(−n/m) ──► доля единиц фильтра Блума, малые счёты HyperLogLog
               └─► два выбора ──► кукушкино хеширование ──► кукушкин фильтр

геометрическое распределение 1/p ──► купоны n·Hₙ ──► обход полного графа, тасование по одной карте
                                 └─► повтор до проверенного ответа: Монте-Карло → Лас-Вегас

произведение (1 − 1/i) сокращается ──► Каргер 2/(n(n−1)) ──► резервуар k/n

блуждание по пути: n² ──► 2-SAT за n²;   диффузия √t ──► время смешивания кольца
равновесие потоков ──► стационарное распределение ──► ранжирование страниц ──► Метрополис

Что выбрать

вопрос                                     инструмент                                 цена
есть ли ключ в множестве                   фильтр Блума                               1,44·log₂(1/p) бит на ключ
то же, с удалением                         кукушкин фильтр, фильтр со счётчиками
сколько всего событий, памяти - биты       счётчик Морриса                            σ до 0,7·n
сколько раз был этот ключ                  count-min                                  +2N/w, с вероятностью
какие ключи самые частые                   SpaceSaving, Мисры-Гриса                   N/k,  без случайности
сколько разных                             HyperLogLog                                1,04/√m
медиана, перцентили                        сводка с уплотнением, Гринвальда-Ханны     ε по рангу, память ~1/ε
дальний перцентиль по значению             гистограмма с растущими промежутками       относительная точность
k случайных элементов потока               резервуар                                  k элементов и счётчик
случайные элементы по весам                ключи u^(1/w)                              k пар
случайные пользователи, а не события       хеш идентификатора                         размер выборки случаен
те же ли элементы в двух потоках           отпечаток в случайной точке                n/p
верно ли A·B = C                           Фрейвалдс                                  3n², ошибка 1/2ᵏ
минимальный разрез без потоков             Каргер                                     n²·ln n прогонов
долгое поведение процесса без памяти       уравнения равновесия                       решение системы
выборка из необозримого множества          Метрополис                                 время смешивания

Числа раздела, которые стоит помнить

1/e ≈ 0,368        доля пустых корзин при n шарах в n корзин;  ln 2 ≈ 0,693;  Hₙ ≈ ln n + 0,577
n·Hₙ               купоны: 225 для 50;   2/(n(n−1)) - успех прогона Каргера;   k/n - резервуар
1,39·n·log₂ n      сравнения быстрой сортировки со случайным опорным
18 445             наблюдений для точности 1% с надёжностью 95% - при любом размере совокупности
1/2ᵏ, pᵏ           односторонняя ошибка после k повторов;   e^(−k/8) - медиана k оценок
10 бит на ключ     фильтр Блума с ошибкой около 1%, семь хеш-функций, половина единиц
12 КБ              HyperLogLog на 16 384 ячейки, ошибка 0,81%
50%                порог заполнения кукушкиной таблицы с двумя функциями
n²                 шагов блуждания на путь длины n;   2m(n − 1) - обход любого связного графа
7                  тасований врезкой для 52 карт;   2080 - длина списка, все перестановки которого
                   ещё умещаются в состояние вихря Мерсенна

Границы, общие для всех приёмов

Независимость. Умножение вероятностей, сложение дисперсий, экспоненциальные оценки, усиление повтором - всё это требует независимости: событий, замеров, запусков, хеш-функций. Оценка объединения и линейность ожидания - единственные инструменты раздела, которым она не нужна.

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

Ошибка измеряется в своих единицах. У сводок частот - в долях всего потока, у квантилей - в рангах, у HyperLogLog - в долях ответа. Перевод в другие единицы - редкий ключ, хвост распределения, малое пересечение - обычно показывает, что сводка для этого вопроса не годится.

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

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

Ловушки джокера

Сложил вероятности пересекающихся событий или перемножил зависимые. Обе ошибки дают правдоподобные числа.

Принял ожидаемое число за вероятность, а среднее - за типичное. 0,69 совпадения - не 69% шансов; средние 76 мс - не время типичного запроса.

Посчитал pᵏ для двусторонней ошибки. Большинство из трёх при p = 1/4 - это 15,6%.

Взял остаток от деления и наивное тасование. Число путей должно делиться на число исходов.

Забыл про одинаковые ключи. Монетка не спасает простое разбиение быстрой сортировки.

Проверил в известной заранее точке. Ошибку можно спрятать именно там.

Не пересчитал сводку под выросшие данные. Фильтр Блума перестаёт отсекать молча.

Усреднил перцентили и сложил оценки уникальных. Объединять нужно сводки, а не ответы.

Спросил сводку о том, чего она не видит. Редкий ключ у count-min, p99,9 у выборки, пересечение малых множеств у HyperLogLog.

Поверил цепи, у которой числа перестали меняться. Стабильность - не смешивание.

Распределения, зависимости и малые сводки

Задача	Инструмент	Условие или граница
Воспроизводимый эксперимент	PRNG с зерном	Воспроизводимость не даёт криптостойкости.
Нагрузка ящиков и выпуклая цена	Пуассон и Йенсен	Приближение распределения требует условий; среднее функции отличается от функции среднего.
Зависимые наблюдения	Мартингал и локальная лемма	Азуме нужны ограниченные изменения; лемма Ловаса использует граф зависимостей.
Различные элементы и сходство	KMV и MinHash	Сохраняй предположения о хеше и определение оцениваемой величины.
Потоки и геометрия	AMS, JL, корсеты, спаннеры	Независимость хешей, фиксированный набор точек и целевая функция входят в гарантию.
Сближение цепей и обслуживание	Каплинг и M/M/1	Стационарный M/M/1 требует ρ<1; средняя длина ρ/(1−ρ).

Непрерывные модели и оценивание

Плотность даёт вероятность интервала через площадь; условная плотность получается делением совместной на положительную маргинальную. У равномерных порядковых статистик среднее k-го элемента выборки размера n равно k/(n+1). Экспоненциальное ожидание с интенсивностью λ>0 имеет среднее 1/λ и отсутствие памяти.

Процесс Пуассона связывает счётчик событий с экспоненциальными межприходами. Независимое прореживание и слияние сохраняют модель. Для стационарной очереди проверяй баланс скоростей и нормируемость: решение уравнений без суммы 1 ещё не распределение. Стационар встроенной цепи скачков и доли времени в состояниях могут различаться. Формулы PASTA и Литтла требуют условий своих моделей.

У нормального приближения называй условия и тип сходимости. В совместной нормальной модели нулевая ковариация означает независимость; в общем случае такого вывода нет. Метод максимального правдоподобия выбирает параметры заданного семейства. Точные E/M-шаги EM не уменьшают правдоподобие, но не гарантируют максимум; ограничения дисперсии меняют задачу.

Проверь, что можешь объяснить

Чем алгоритм Лас-Вегас отличается от алгоритма Монте-Карло и как одно превращают в другое? Почему линейность ожидания не требует независимости, а граница Чернова требует? Откуда берётся размер выборки и почему в нём нет размера совокупности? Почему минимум в count-min, гармоническое среднее в HyperLogLog и медиана в оценке второго момента - это три разных ответа на один вопрос «как собрать несколько ненадёжных оценок»? Что общего у доказательств для алгоритма Каргера и резервуарной выборки? Почему блуждание решает формулы с двумя литералами и не решает с тремя? Что правило Метрополиса обещает и о чём молчит?