Рандомизированные алгоритмы и вероятностный анализ

Есть класс задач, где детерминированное решение либо мучительно сложное, либо мучительно медленное, либо и то и другое — а решение, которое один раз бросает монетку, умещается в двадцать строк и работает быстрее. Проверить, что A · B = C, за O(n²) вместо O(n^2.37). Понять, простое ли 2048-битное число, за миллисекунды. Найти минимальный разрез графа, не строя ни одного потока. Держать сбалансированное дерево, не написав ни одного разбора случаев для перекраски узлов.

Ключевая интуиция во всех этих случаях одна и та же: случайность — это способ убежать от противника. Детерминированный алгоритм — это функция; для любой такой функции можно подобрать вход, на котором она ведёт себя хуже всего, и рано или поздно этот вход придёт — случайно из продакшн-трафика или намеренно от атакующего. Рандомизированный алгоритм — это уже не функция, а распределение над функциями. Противник видит ваш код, но не видит монетку. Он больше не может подобрать «тот самый» плохой вход: плохим для одного набора монеток вход будет хорошим для другого.

Это тонкий, но принципиальный сдвиг. Мы перестаём усреднять по входам (что требует предположений о том, какие входы бывают — а они всегда неверны) и начинаем усреднять по внутренним монеткам алгоритма. Гарантия становится безусловной: «для любого входа матожидание времени равно O(n log n)» — куда более сильное утверждение, чем «для случайного входа».

Статья предполагает, что вы владеете языком асимптотики и инвариантов (Анализ алгоритмов), знаете quicksort (Сортировки) и модульную арифметику (Теория чисел).

1. Таксономия: Las Vegas, Monte Carlo и что между ними

Рандомизированные алгоритмы делятся по тому, что именно становится случайным.

• Las Vegas — случайно время работы, ответ всегда правильный. Алгоритм не врёт; он может только затянуть. Пример: рандомизированный quicksort. Он никогда не вернёт несортированный массив, но с исчезающе малой вероятностью проработает Θ(n²).
• Monte Carlo — время детерминировано (или жёстко ограничено), а ответ может быть неверным с ограниченной вероятностью. Пример: Миллер–Рабин. Он всегда отвечает за фиксированное число раундов, но иногда называет составное число простым.

Monte Carlo дополнительно делят по типу ошибки:

• Односторонняя ошибка (one-sided): «нет» — всегда правда, «да» — с вероятностью ошибки. Или наоборот. Миллер–Рабин: «составное» — доказано; «вероятно простое» — может быть враньём. Bloom filter: «нет в множестве» — правда; «есть» — возможно false positive.
• Двусторонняя ошибка (two-sided): ошибиться можно в обе стороны. Типично для оценок по выборке — «доля дефектных примерно 3 %».

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

Есть простой мост между классами: Las Vegas → Monte Carlo делается тривиально — обрубаем алгоритм по таймауту и отдаём что есть (или «не знаю»). Обратный переход возможен только если ответ можно дёшево проверить: гоняем Monte Carlo в цикле, пока проверка не скажет «верно». Именно поэтому задачи с быстрой верификацией — самый удобный полигон для рандомизации.

2. Инструментарий вероятностного анализа

Почти весь анализ рандомизированных алгоритмов держится на четырёх приёмах. Их стоит знать не как формулы, а как рефлексы.

2.1 Индикаторы и линейность матожидания

Индикаторная величина X_e равна 1, если событие e произошло, и 0 иначе. Её матожидание равно вероятности события: E[X_e] = Pr[e]. Разложив сложную величину в сумму индикаторов, мы получаем право сложить вероятности — потому что

линейность матожидания E[X + Y] = E[X] + E[Y] верна всегда, независимость не требуется.

Это самый недооценённый инструмент во всей дискретной математике. Величины могут быть дико скоррелированы — сумма матожиданий всё равно сойдётся.

Классический пример. Сколько неподвижных точек в случайной перестановке n элементов? Пусть X_i = 1, если π(i) = i. Тогда Pr[X_i = 1] = 1/n, и E[X] = Σ E[X_i] = n · (1/n) = 1. Ровно одна — при любом n. Считать это через распределение числа неподвижных точек было бы упражнением на субфакториалы; через индикаторы это одна строчка.

2.2 Хвостовые границы: Марков, Чебышёв, Чернов

Матожидание само по себе почти ничего не гарантирует. E[T] = n log n совместимо с «в половине случаев работает вечность». Нужны границы на хвост — и они образуют лестницу: чем больше знаешь о величине, тем резче граница.

Практический смысл: как только вашу случайную величину удаётся представить как сумму независимых слагаемых, вы получаете экспоненциальную концентрацию, и слова «в среднем» превращаются в «практически всегда». Это и есть содержание фразы with high probability (w.h.p.) — обычно она означает «с вероятностью не меньше 1 − 1/n^c для константы c на ваш выбор».

2.3 Union bound

Pr[A₁ ∪ A₂ ∪ … ∪ A_k] ≤ Σ Pr[A_i]. Грубо, зато не требует ничего. Типовое применение: хотим, чтобы ни одно из n плохих событий не произошло; показываем, что каждое имеет вероятность ≤ 1/n²; заключаем, что вероятность любого сбоя ≤ 1/n. Так доказывается, например, что максимальная длина цепочки в хеш-таблице с n ключами и n корзинами равна O(log n / log log n) w.h.p.

2.4 Усиление вероятности (probability amplification)

Одиночный запуск с вероятностью успеха p — это редко достаточно. Дальше два рецепта.

Для односторонней ошибки — просто повторяем k раз. Вероятность, что все k раз ошиблись, равна (1−p)^k и падает экспоненциально. Чтобы получить ошибку ε, нужно k = ln(1/ε) / p запусков.

Для двусторонней ошибки повторение с большинством/медианой — «median trick»: запускаем k раз независимо и берём медиану результатов. Если каждый запуск попадает в нужный интервал с вероятностью ≥ 2/3, то медиана промахивается только когда больше половины запусков промахнулись — а это по Чернову e^(−Ω(k)).

Обратите внимание на экономику: цена линейна по k, качество экспоненциально по k. Именно этот обменный курс делает рандомизацию практичной. Сорок раундов Миллера–Рабина стоят сорок возведений в степень, а вероятность ошибки становится меньше вероятности битового сбоя памяти под космическим излучением — то есть ошибка алгоритма перестаёт быть доминирующим риском системы.

3. Las Vegas в чистом виде: quickselect и quicksort

3.1 Рандомизированный quickselect

Задача: найти k-ю порядковую статистику. Детерминированное решение с гарантией O(n) — это median-of-medians, красивый, но с большой константой и неприятный в реализации. Рандомизированная версия — двадцать строк.

import random

def quickselect(items, k, rng=random):
    """k-я порядковая статистика (0-индексация). Ожидаемо O(n), в худшем O(n²).

    Ключ к анализу: опорный элемент выбирается СЛУЧАЙНО, а не по позиции.
    Поэтому гарантия не зависит от того, как устроен вход.
    """
    a = list(items)                       # копия: алгоритм переставляет элементы
    lo, hi = 0, len(a) - 1
    while lo < hi:
        p = rng.randint(lo, hi)           # ← единственный источник случайности
        a[p], a[hi] = a[hi], a[p]
        pivot = a[hi]

        i = lo                            # разбиение Ломуто
        for j in range(lo, hi):
            if a[j] < pivot:
                a[i], a[j] = a[j], a[i]
                i += 1
        a[i], a[hi] = a[hi], a[i]         # опорный на своё место

        if k == i:
            return a[i]
        elif k < i:
            hi = i - 1                    # рекурсия ТОЛЬКО в одну сторону
        else:
            lo = i + 1
    return a[lo]

Анализ. Опорный элемент называем хорошим, если он попал в средние 50 % по рангу — это происходит с вероятностью 1/2. Хороший опорный сокращает отрезок минимум до 3/4 от прежнего. Значит, ожидаемое число разбиений до сокращения размера в 4/3 раза равно 2 (матожидание геометрической величины с p = 1/2). Суммарная ожидаемая работа:

E[T(n)] ≤ 2·(n + 3n/4 + 9n/16 + …) = 2n · 1/(1 − 3/4) = 8n = O(n).

Геометрическая сумма — вот и весь фокус: рекурсия идёт в одну сторону, размеры падают геометрически, а сумма геометрической прогрессии — константа на первое слагаемое. Память: O(1) сверх входа (цикл вместо рекурсии).

3.2 Quicksort через индикаторы: канонический разбор

Для quicksort ожидаемое число сравнений считается совершенно иначе — и этот приём стоит держать в активной памяти, он переиспользуется повсеместно.

Пусть z₁ < z₂ < … < z_n — элементы в отсортированном порядке, а X_ij = 1, если z_i и z_j вообще когда-либо сравнивались. Ключевое наблюдение: z_i и z_j сравниваются тогда и только тогда, когда первый выбранный опорный из отрезка {z_i, …, z_j} — это сам z_i или сам z_j. Если раньше опорным станет что-то между ними, они попадут в разные половины и больше никогда не встретятся.

В отрезке j − i + 1 элементов, любой из них равновероятно окажется первым опорным:

Pr[X_ij = 1] = 2 / (j − i + 1)

E[X] = Σ_i Σ_{j>i} 2/(j−i+1) = Σ_i 2·H_{n−i} ≈ 2n·ln n ≈ 1.39 · n log₂ n

Заметьте: индикаторы X_ij жутко зависимы друг от друга, и это совершенно не мешает — линейность матожидания зависимости не требует. Полный разбор — CLRS, глава 7.4 (https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/).

Более того, по границе Чернова число сравнений концентрируется: Pr[T > c·n log n] падает полиномиально по n. Практический вывод — квадратичное поведение рандомизированного quicksort не «редко», а не встретится никогда за время жизни вселенной на массиве из миллиона элементов.

Типичная ошибка. «Перемешаю массив один раз, а потом возьму средний элемент как опорный» — это тоже корректная рандомизация (shuffle-then-sort) и она эквивалентна по гарантиям. А вот «возьму медиану из трёх элементов на фиксированных позициях» — не рандомизация: противник строит вход-убийцу (см. знаменитый A Killer Adversary for Quicksort Дугласа Макилроя, https://www.cs.dartmouth.edu/~doug/mdmspe.pdf). Разница между этими двумя стратегиями в тексте почти незаметна, а в проде — это разница между O(n log n) и DoS-уязвимостью.

4. Monte Carlo: проверять дешевле, чем вычислять

4.1 Алгоритм Фрейвальдса

Дано три матрицы n × n и вопрос: верно ли, что A · B = C? Перемножить и сравнить — это O(n^2.37) в лучшем известном случае и O(n³) на практике. Фрейвальдс (1977) проверяет за O(n²) за раунд с односторонней ошибкой ≤ 1/2.

Идея: вместо равенства матриц проверяем равенство их действия на случайном векторе r ∈ {0,1}ⁿ. Считаем A·(B·r) и C·r — это три умножения матрицы на вектор, O(n²). Если A·B = C, равенство выполнится всегда. Если нет — по лемме о ненулевом векторе D = AB − C ≠ 0 даёт Dr ≠ 0 с вероятностью ≥ 1/2.

Почему ≥ 1/2: пусть d_ij ≠ 0. Зафиксируем все координаты r, кроме r_j. Тогда (Dr)_i = c + d_ij·r_j, где c — уже фиксировано. Два значения r_j ∈ {0,1} дают два разных значения (Dr)_i, и максимум одно из них равно нулю. Значит, Pr[(Dr)_i = 0] ≤ 1/2 — это принцип отложенного решения (principle of deferred decisions), ещё один рабочий приём: раскрывать случайные биты в удобном порядке.

def matvec(M, v):
    """Умножение матрицы на вектор, O(n²)."""
    return [sum(row[j] * v[j] for j in range(len(v))) for row in M]

def freivalds(A, B, C, rounds=20, rng=random):
    """Проверка A·B == C за O(rounds · n²) с односторонней ошибкой.

    Возвращает False → ТОЧНО не равны (нашли свидетеля).
    Возвращает True  → равны с вероятностью ошибки ≤ 2^(-rounds).
    """
    n = len(C)
    for _ in range(rounds):
        r = [rng.randint(0, 1) for _ in range(n)]
        if matvec(A, matvec(B, r)) != matvec(C, r):
            return False
    return True

20 раундов дают ошибку < 1e-6, 60 раундов — < 1e-18, и всё это остаётся O(n²). Практическое применение — верификация вычислений, отданных наружу: облачному провайдеру, GPU-ядру, недоверенному узлу. Проверка на порядок дешевле пересчёта.

Порядок в этом протоколе критичен: r выбирается после того, как C зафиксирована. Если исполнитель узнает r заранее, он подберёт C, проходящую проверку. Это общее правило всех рандомизированных проверок — и корень требования «не переиспользуй seed» в криптографических протоколах.

4.2 Миллер–Рабин: тест простоты

Рандомизированный тест простоты — единственный алгоритм из этой статьи, который вы гарантированно используете каждый день, даже не зная об этом: каждый TLS-хендшейк с RSA-ключом когда-то опирался на него при генерации ключа.

Тест строится на том, что в поле Z_p при простом p уравнение x² = 1 имеет ровно два корня: ±1. Записываем n − 1 = 2^s · d с нечётным d, берём случайное основание a и смотрим на последовательность a^d, a^(2d), a^(4d), …, a^(n−1) mod n. Для простого n она обязана либо начинаться с 1, либо содержать n − 1 перед первой единицей. Любое нарушение — доказательство составности, и такое a называют свидетелем.

def is_probable_prime(n, k=40, rng=random):
    """Тест Миллера–Рабина. O(k · log³ n) битовых операций.

    'Составное' — доказано. 'Вероятно простое' — ошибка ≤ 4^(-k).
    """
    if n < 2:
        return False
    for p in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37):
        if n % p == 0:
            return n == p                 # быстрый отсев 80 % кандидатов

    d, s = n - 1, 0                       # n − 1 = 2^s · d, d нечётное
    while d % 2 == 0:
        d //= 2
        s += 1

    for _ in range(k):
        a = rng.randrange(2, n - 1)
        x = pow(a, d, n)                  # быстрое возведение по модулю
        if x == 1 or x == n - 1:
            continue                      # раунд пройден
        for _ in range(s - 1):
            x = x * x % n
            if x == n - 1:
                break                     # нашли «правильный» квадратный корень из 1
        else:
            return False                  # a — свидетель составности, ответ точный
    return True

Границы ошибки. Рабин доказал: для составного n доля свидетелей > 3/4, поэтому k раундов дают ошибку ≤ 4^(−k). Это пессимистичная оценка: для случайного нечётного n реальная вероятность на порядки меньше, и в криптобиблиотеках берут k от 20 до 64 в зависимости от разрядности (см. FIPS 186-5, таблицы C.1–C.3, https://csrc.nist.gov/pubs/fips/186-5/final).

Важная ловушка. Существует детерминированный вариант — фиксированный набор оснований {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} даёт точный ответ для всех n < 3.3·10²⁴. Он идеален для олимпиадных задач. Но в криптографии его использовать опасно: если основания известны, злоумышленник может подсунуть специально построенное составное число, проходящее именно эти основания (см. Prime and Prejudice, Albrecht et al., 2018 — https://eprint.iacr.org/2018/749, где авторы построили такие числа для реальных библиотек). Против adversarial-входа нужна именно случайность — ровно та мысль, с которой началась статья.

5. Каргер: минимальный разрез стягиванием

Самый красивый и контринтуитивный алгоритм в этой статье. Задача: в неориентированном мультиграфе найти глобальный минимальный разрез — минимальное число рёбер, удаление которых разбивает граф надвое. Классическое решение — n − 1 запусков max-flow (см. Остовные деревья и потоки). Каргер (1993) предложил вот что: выбрать случайное ребро, склеить его концы, повторить, пока не останется две вершины. Оставшиеся рёбра между ними и есть ответ.

Почему это работает. Зафиксируем какой-то конкретный минимальный разрез C размера k. Если ни одно ребро из C ни разу не было стянуто, алгоритм вернёт ровно C. Каждая вершина имеет степень ≥ k (иначе её одиночный разрез был бы меньше), значит рёбер в графе ≥ nk/2, и вероятность на первом шаге зацепить ребро из C не превышает k / (nk/2) = 2/n. Перемножая по всем n − 2 шагам:

Pr[C выжил] ≥ Π_{i=0}^{n−3} (1 − 2/(n−i)) = 2 / (n(n−1)) ≥ 1/n²

Одна тысячная процента для n = 300? Да. Но 1/n² — это полиномиальная вероятность, а значит Θ(n² ln n) повторений дают успех w.h.p.: (1 − 1/n²)^(n² ln n) ≤ e^(−ln n) = 1/n. Побочное следствие теоремы: у графа не может быть больше n(n−1)/2 различных минимальных разрезов — чисто комбинаторный факт, доказанный вероятностным аргументом. Это классика вероятностного метода Эрдёша.

def karger_min_cut(n, edges, rng=random):
    """Одна попытка алгоритма Каргера. O(n + m·α(n)) на попытку.

    Приём: вместо «выбрать случайное оставшееся ребро» на каждом шаге
    перемешиваем список рёбер один раз и идём по нему. По симметрии это
    в точности эквивалентно, но заметно проще и быстрее.
    """
    parent = list(range(n))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]     # сжатие пути
            x = parent[x]
        return x

    order = list(edges)
    rng.shuffle(order)
    components = n
    for u, v in order:
        if components == 2:
            break
        ru, rv = find(u), find(v)
        if ru != rv:                          # не петля — стягиваем
            parent[ru] = rv
            components -= 1

    return sum(1 for u, v in edges if find(u) != find(v))


def min_cut(n, edges, rng=random):
    """Полный алгоритм: n² ln n попыток → ошибка ≤ 1/n. O(n² m log n) суммарно."""
    import math
    best = len(edges)
    attempts = max(1, int(n * n * math.log(max(n, 2))))
    for _ in range(attempts):
        best = min(best, karger_min_cut(n, edges, rng))
    return best

Каргер–Штейн. Наивная версия стоит O(n⁴ log n) — дороже потоков. Но вероятность испортить разрез мала в начале и велика в конце: сжатие с n до n/√2 вершин сохраняет разрез с вероятностью ≥ 1/2. Отсюда рекурсия: сжать до n/√2 и дважды рекурсивно решить. T(n) = 2T(n/√2) + O(n²) даёт O(n² log n) на попытку и O(n² log³ n) суммарно — конкурентоспособно с лучшими детерминированными решениями. Оригинал: Karger & Stein, A New Approach to the Minimum Cut Problem, JACM 1996 — https://dl.acm.org/doi/10.1145/234533.234534.

6. Рандомизированные структуры данных

Здесь случайность покупает не скорость, а простоту кода. Балансировка красно-чёрного дерева — это разбор десятка случаев, которые почти невозможно написать без ошибки по памяти. Балансировка treap — «сгенерируй случайное число».

6.1 Treap

Treap = tree + heap. Каждый узел хранит ключ (BST-порядок) и случайный приоритет (куча-порядок). Пара этих условий определяет форму дерева однозначно — и она в точности совпадает с формой BST, в которое ключи вставлялись в порядке убывания приоритетов, то есть в случайном порядке. А про случайное BST известно: ожидаемая глубина Θ(log n), и O(log n) w.h.p.

class TreapNode:
    __slots__ = ("key", "prio", "left", "right")

    def __init__(self, key, prio):
        self.key, self.prio = key, prio
        self.left = self.right = None


def split(t, key):
    """Разрезает treap на (< key) и (≥ key). O(глубина) = O(log n) ожидаемо."""
    if t is None:
        return None, None
    if t.key < key:
        left, right = split(t.right, key)
        t.right = left
        return t, right
    left, right = split(t.left, key)
    t.left = right
    return left, t


def merge(a, b):
    """Склеивает два treap, где все ключи a < всех ключей b."""
    if a is None or b is None:
        return a or b
    if a.prio > b.prio:
        a.right = merge(a.right, b)
        return a
    b.left = merge(a, b)
    return b


def insert(t, key, rng=random):
    """Вставка через split/merge — 3 строки вместо разбора случаев поворотов."""
    left, right = split(t, key)
    return merge(merge(left, TreapNode(key, rng.random())), right)

Весь код балансировки — сравнение a.prio > b.prio. Сравните с любой реализацией AVL или красно-чёрного дерева. Цена: гарантия вероятностная, а константа чуть хуже. Выигрыш: split/merge дают бесплатно операции над диапазонами, которые в RB-дереве писать больно.

6.2 Skip list

Та же идея в списочной форме: элемент поднимается на следующий уровень с вероятностью 1/2, пока монетка даёт орла. Ожидаемое число уровней log₂ n, ожидаемое время поиска O(log n). Skip list заметно проще делать lock-free, чем сбалансированное дерево, — поэтому он живёт в ConcurrentSkipListMap в Java, в MemTable RocksDB и LevelDB (https://github.com/facebook/rocksdb/wiki/MemTable) и в Redis Sorted Set.

Оригинал — Pugh, Skip Lists: A Probabilistic Alternative to Balanced Trees, 1990: https://15721.courses.cs.cmu.edu/spring2018/papers/08-oltpindexes1/pugh-skiplists-cacm1990.pdf.

6.3 Универсальное хеширование

Хеш-таблица — самая массовая рандомизированная структура на планете, и большинство программистов не осознаёт, что она рандомизированная. Ключевая теорема: если хеш-функция выбирается случайно из универсального семейства (Pr[h(x) = h(y)] ≤ 1/m для любых различных x, y), то ожидаемая длина цепочки равна 1 + n/m для любого набора ключей.

class UniversalHash:
    """Семейство Картера–Вегмана: h(x) = ((a·x + b) mod p) mod m.

    a, b выбираются случайно ПРИ СОЗДАНИИ таблицы. Гарантия держится
    для любого набора ключей, включая подобранный атакующим.
    """
    def __init__(self, m, rng=random, p=(1 << 61) - 1):
        self.p, self.m = p, m
        self.a = rng.randrange(1, p)
        self.b = rng.randrange(0, p)

    def __call__(self, x):
        return ((self.a * x + self.b) % self.p) % self.m

Без этой рандомизации хеш-таблица уязвима к hash flooding: атакующий шлёт ключи с одинаковым хешем, все операции вырождаются в O(n), сервис ложится. Это не теория — в 2011 году доклад на 28C3 обрушил разом PHP, Python, Ruby, Java и Node (https://www.youtube.com/watch?v=R2Cq3CLI6H8). Ответ индустрии: SipHash со случайным ключом на процесс — сейчас это дефолт в Python (PYTHONHASHSEED), Rust HashMap, Perl, Ruby. Подробнее про хеширование строк — в Строковых алгоритмах.

7. Случайность на потоке: reservoir sampling

Отдельная важная ветка — когда данных больше, чем памяти, а размер потока заранее неизвестен. Reservoir sampling (алгоритм R Виттера) держит равномерную выборку размера k за один проход и O(k) памяти.

def reservoir_sample(stream, k, rng=random):
    """Равномерная выборка k элементов из потока неизвестной длины.

    Инвариант: после обработки i элементов каждый из них лежит
    в резервуаре с вероятностью ровно k/i. Память O(k), время O(n).
    """
    reservoir = []
    for i, item in enumerate(stream):
        if i < k:
            reservoir.append(item)
        else:
            j = rng.randrange(i + 1)       # равномерно из [0, i]
            if j < k:
                reservoir[j] = item        # вытесняем случайного жильца
    return reservoir

Доказательство инварианта по индукции. Элемент i+1 попадает в резервуар с вероятностью k/(i+1) — прямо по коду. Любой ранее попавший элемент выживает с вероятностью (k/i) · (1 − (k/(i+1))·(1/k)) = (k/i) · (i/(i+1)) = k/(i+1). Индукция замкнулась.

Это ровно тот алгоритм, что стоит за сэмплированием трейсов в OpenTelemetry, за ORDER BY RANDOM() LIMIT k в потоковых движках и за выборкой логов в системах наблюдаемости. Продолжение темы — потоковые скетчи (HyperLogLog, Count–Min) — в Потоковых алгоритмах.

8. Откуда брать случайность в проде

Самая частая ошибка инженеров в рандомизированных алгоритмах — не в математике, а в источнике битов.

Правила, которые стоит записать в чек-лист код-ревью:

1. Никогда не используйте Math.random() / random.random() для того, что видит потенциальный противник. Mersenne Twister восстанавливается по 624 подряд идущим выходам целиком. Токен сессии, сгенерированный так, — это не токен.
2. Фиксируйте seed в тестах, но не в проде. Воспроизводимость нужна для отладки рандомизированного алгоритма — иначе баг, всплывший раз в тысячу запусков, не поймать. Стандартный приём: логировать seed при каждом запуске и уметь запуститься с чужим seed.
3. Отдельный генератор на поток исполнения. Глобальный random под многопоточностью — либо гонка, либо контеншен на мьютексе, который убивает производительность. Numpy явно рекомендует default_rng() на воркер с независимыми потоками (https://numpy.org/doc/stable/reference/random/parallel.html).
4. Не переиспользуйте случайные биты между раундами усиления. Все оценки ошибки (4^(−k), 2^(−k)) держатся на независимости запусков. Одно и то же a в двадцати раундах Миллера–Рабина — это один раунд, а не двадцать.
5. Не путайте «случайное» и «неизвестное мне». Время в миллисекундах, PID и MAC-адрес — это низкоэнтропийные предсказуемые величины. Классика провала — генерация ключей с seed = time() (уязвимость Debian OpenSSL, CVE-2008-0166).

9. Дерандомизация: когда монетку можно убрать

Отдельная красивая ветка теории — превращение рандомизированного алгоритма в детерминированный без потери гарантий.

• Метод условных матожиданий. Если E[качество] ≥ X, то существует конкретный набор монеток, дающий ≥ X. Идём по битам решения и на каждом шаге выбираем то значение, которое не ухудшает условное матожидание. Так строится детерминированный 1/2-приближённый MAX-CUT: помещаем вершины в доли по одной, каждую — в ту сторону, где больше пересекающих рёбер.
• Попарная независимость. Многие анализы (в частности, через Чебышёва) требуют не полной независимости, а только попарной. А попарно независимые n величин строятся из O(log n) честно случайных бит — значит, пространство монеток сжимается до полиномиального размера и его можно перебрать целиком.
• Открытый вопрос. Гипотеза P = BPP (всё, решаемое за полиномиальное время с двусторонней ошибкой, решается и детерминированно) считается вероятной, но недоказанной. Impagliazzo и Wigderson показали: она следует из существования достаточно сложных функций (P = BPP if E requires exponential circuits, 1997 — https://dl.acm.org/doi/10.1145/258533.258590).

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

10. Хронология: как рандомизация стала мейнстримом

11. Типичные ошибки

1. Путать «в среднем по входам» и «в среднем по монеткам». Первое — предположение о мире, которое противник нарушит. Второе — гарантия алгоритма. Средний случай детерминированного quicksort и ожидаемое время рандомизированного — это разные утверждения с одинаковой формулой.
2. Считать матожидание и на этом остановиться. E[T] = O(n) без хвостовой границы ничего не говорит о p99. Всегда спрашивайте: концентрируется ли величина?
3. Забыть, что матожидание не переносится через нелинейность. E[1/X] ≠ 1/E[X], E[X·Y] ≠ E[X]·E[Y] без независимости. Линейность — только для суммы.
4. Переиспользовать случайность. Особенно в усилении и в интерактивных проверках, где противник может подстроиться под уже раскрытые биты.
5. Тестировать рандомизированный код без фиксации seed. Флакающие тесты вы получите, а воспроизводимого падения — нет. Логируйте seed, всегда.
6. Игнорировать стоимость генерации. Вызов rng.randint внутри горячего цикла может стоить дороже самого разбиения. В quicksort опорный берут раз на разбиение, а не раз на элемент; в skip list уровень берут из одного случайного слова через подсчёт нулевых бит, а не циклом бросков.
7. Забыть про качество генератора. LCG вида rand() % n даёт заметное смещение и корреляции младших бит — этого достаточно, чтобы «рандомизированный» quicksort перестал быть рандомизированным.

12. Как это применяют на практике

• Базы данных. Оценка кардинальности через сэмплирование таблиц (ANALYZE в PostgreSQL строит статистику по случайной выборке блоков), HyperLogLog для COUNT(DISTINCT) в ClickHouse и Redis, skip list в MemTable RocksDB.
• Сеть и распределённые системы. Randomized exponential backoff в TCP и в клиентах API — чистая рандомизация против синхронизации ретраев (thundering herd). Gossip-протоколы выбирают случайных соседей и достигают консистентности за O(log n) раундов — см. Параллельные и распределённые алгоритмы. Power of Two Random Choices в балансировщиках: выбрать два случайных бэкенда и отдать запрос менее загруженному — максимальная загрузка падает с Θ(log n / log log n) до Θ(log log n) (https://www.eecs.harvard.edu/~michaelm/postscripts/handbook2001.pdf).
• Безопасность. ASLR — рандомизация адресного пространства; рандомизация hash seed в рантаймах; blinding в криптографических реализациях против тайминг-атак.
• Машинное обучение. Инициализация весов, dropout, SGD-шафлинг батчей, random projections и лемма Джонсона–Линденштрауса для снижения размерности, bootstrap для доверительных интервалов — см. курс Машинное обучение.
• Тестирование. Property-based testing (QuickCheck, Hypothesis) и фаззинг — это рандомизированный поиск контрпримеров. Здесь случайность заменяет невозможный исчерпывающий перебор.
• Приближённые решения NP-трудных задач. Randomized rounding LP-релаксации, локальный поиск со случайными рестартами, симулированный отжиг — прямой мост к следующей статье.

13. Мини-итог

Три вещи, которые стоит унести:

1. Случайность — это защита от противника, а не «среднее по больнице». Гарантия берётся по монеткам алгоритма и потому держится на любом входе.
2. Линейность матожидания + индикаторы решают 80 % задач анализа, а границы Чернова превращают «в среднем» в «почти всегда».
3. Односторонняя ошибка дешёвая: её давят повторениями экспоненциально. Поэтому ищите формулировку задачи, где неправильный ответ можно проверить.

Источники

• Motwani R., Raghavan P. Randomized Algorithms, Cambridge University Press, 1995 — канонический учебник, до сих пор непревзойдённый: https://doi.org/10.1017/CBO9780511814075
• Mitzenmacher M., Upfal E. Probability and Computing, 2nd ed., 2017 — самый доступный вход в тему, с сильной главой про границы Чернова: https://www.cambridge.org/core/books/probability-and-computing/
• CLRS, Introduction to Algorithms, 4th ed. — гл. 5 (вероятностный анализ), 7 (quicksort), 9 (порядковые статистики), 11.3 (универсальное хеширование)
• Karger D., Stein C. A New Approach to the Minimum Cut Problem, JACM 1996 — https://dl.acm.org/doi/10.1145/234533.234534
• Pugh W. Skip Lists: A Probabilistic Alternative to Balanced Trees, CACM 1990 — https://15721.courses.cs.cmu.edu/spring2018/papers/08-oltpindexes1/pugh-skiplists-cacm1990.pdf
• Vitter J. Random Sampling with a Reservoir, ACM TOMS 1985 — https://dl.acm.org/doi/10.1145/3147.3165
• Albrecht M. et al. Prime and Prejudice: Primality Testing Under Adversarial Conditions, 2018 — https://eprint.iacr.org/2018/749
• Mitzenmacher M. The Power of Two Random Choices: A Survey of Techniques and Results — https://www.eecs.harvard.edu/~michaelm/postscripts/handbook2001.pdf
• Aumasson J.-P., Bernstein D. SipHash: a fast short-input PRF, 2012 — https://www.aumasson.jp/siphash/siphash.pdf
• NIST FIPS 186-5, приложение C — требования к числу раундов Миллера–Рабина — https://csrc.nist.gov/pubs/fips/186-5/final
• cp-algorithms — компактные реализации теста простоты и treap — https://cp-algorithms.com/algebra/primality_tests.html

Что дальше

Рандомизация даёт быстрый ответ там, где детерминированный путь дорог, — но она не отменяет самой сложности задачи. Есть класс задач, где ни случайность, ни изобретательность пока не спасают: минимальный ответ там ищется экспоненциально долго. Тогда мы меняем цель — соглашаемся на почти оптимальное решение с доказанной гарантией качества, и приёмы из этой статьи (randomized rounding, случайные рестарты, вероятностный метод) становятся основным инструментом.

NP-полнота, приближённые и эвристические алгоритмы