Конспект: Монте-Карло, Лас-Вегас и рандомизированный quicksort

                  ЛАС-ВЕГАС                          МОНТЕ-КАРЛО
случайно          время                              правильность
гарантия          ожидаемое время на любом входе     вероятность ошибки на любом входе
примеры           quicksort, быстрый выбор,          Миллер-Рабин, Фрейвалдс, Каргер,
                  декартово дерево, список с         Рабин-Карп без перепроверки,
                  пропусками, Рабин-Карп с проверкой оценка по выборке

Лас-Вегас → Монте-Карло:  оборвать на 2T          отказ ≤ 1/2;  k попыток - ≤ 1/2ᵏ
Монте-Карло → Лас-Вегас:  повторять до проверки   (запуск + проверка) / p;  нужна дешёвая проверка

ОЦЕНКА ВЫБОРКОЙ:  ошибка ~ 1/√n        π по 40 000 точек: 3,1403, гарантия ±0,027 с надёжностью 95%
редкая цель: доля p с точностью 10% требует порядка 100/p проб

ГЕНЕРАТОР                                      x = (a·x + c) mod m
одно зерно - одна последовательность           5, 3, 16: период 16;   4, 2, 16: застревает на 10
random - вихрь Мерсенна, период 2¹⁹⁹³⁷ − 1      для ключей и токенов - secrets
остаток от деления перекашивает                8 значений mod 3:  3, 3, 2
честно - отбор: взять биты, лишнее выбросить   randrange и randint так и делают

ТАСОВАНИЕ ФИШЕРА-ЙЕТСА                         НАИВНОЕ (j из всех n)
для i от n − 1 вниз до 1:                      путей nⁿ, перестановок n!, не делится
    j = случайное от 0 до i                    n = 3:  27 путей,  порядки получают 4, 5, 5, 5, 4, 4
    поменять a[i] и a[j]
путей n!, каждой перестановке - один           j от 0 до i − 1: только циклы, (n − 1)! штук
32-битное зерно: не больше 2³² раскладов из 52! ≈ 8·10⁶⁷

БЫСТРАЯ СОРТИРОВКА, СЛУЧАЙНЫЙ ОПОРНЫЙ, РАЗНЫЕ ЭЛЕМЕНТЫ
zᵢ и zⱼ сравниваются  ⇔  первым опорным из zᵢ … zⱼ стал zᵢ или zⱼ          P = 2 / (j − i + 1)
E[сравнений] = 2(n + 1)Hₙ − 4n ≈ 1,39 · n · log₂ n            σ ≈ 0,65 · n
n = 500:  формула 4806,  пять запусков 4574 … 5091;  нижняя граница log₂ 500! = 3767
без монетки на отсортированных 250:  31 125 = n(n − 1)/2,  с монеткой ≈ 2063
одинаковые элементы: квадрат и с монеткой → разбиение на три части

ПРОВЕРИТЬ, НЕ ВЫЧИСЛЯЯ                         ЦЕНА        ОШИБКА «РАВНО»
A·B = C ?   сравнить A·(B·r) и C·r,  r из 0/1  3n²         ≤ 1/2 за проверку, ≤ 1/2ᵏ за k
F = G ?     сравнить в случайной точке mod p   d           ≤ d / p,  p простое
ответ «не равно» достоверен всегда; точка и вектор выбираются ПОСЛЕ того, как дан ответ
испорченный элемент c[3][7]: 22 пропуска из 40;  ошибка x³ − x не видна в 0, 1 и −1

АЛГОРИТМ КАРГЕРА
пока вершин больше двух: стянуть равновероятно выбранное ребро
P(данный минимальный разрез уцелел) ≥ (1 − 2/n)(1 − 2/(n−1)) … (1 − 2/3) = 2 / (n(n − 1))
n(n − 1) · ln n прогонов, взять наименьший:  промах ≤ 1/n²
два клубка по 4 вершины: один прогон прав в 16% случаев, чаще всего выдаёт 3 вместо 2
следствие: минимальных разрезов не больше n(n − 1)/2      Каргер-Штайн: O(n² log³ n)

СРЕДНЕЕ КАК ДОВОД
вероятностный метод     E[X] = μ  ⇒  есть объект с X ≥ μ          разрез ≥ m/2 в любом графе
условные ожидания       ставь вершину напротив большинства         тот же m/2 без монеток; 66 из 100
принцип Яо              плохое распределение входов для всех       одна единица из n: (n + 1)/2 проб
                        детерминированных ⇒ предел для всех        и с монетками
                        рандомизированных