Откуда берётся случайность: генератор, зерно и честное тасование

Если ты объяснишь, что такое зерно и почему обычный генератор не годится для ключей, покажешь перекос остатка от деления и напишешь тасование Фишера-Йетса - листай до «Теперь сам».

Как думаешь, честно ли такое тасование

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

Ответь себе до чтения: все ли порядки после этого равновероятны? Каждый элемент куда-то переехал, случайность использована щедро. Ответ - нет, и это видно без единого запуска: для трёх элементов у программы 3 · 3 · 3 = 27 равновозможных путей, а перестановок шесть. Двадцать семь на шесть не делится.

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

Книга со случайными числами. До компьютеров такие печатали: открой на любой странице и читай подряд. Числа в ней настоящие случайные, но сама книга неизменна: кто открыл её на той же странице, прочтёт то же самое.

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

Механизм: состояние, зерно и два способа всё испортить

Генератор псевдослучайных чисел хранит состояние и на каждый запрос делает одно и то же: вычисляет новое состояние из старого и выдаёт число. Зерно - начальное состояние.

Простейший пример - линейный конгруэнтный генератор: x = (a · x + c) mod m.

a = 5, c = 3, m = 16, зерно 7:    6 1 8 11 10 5 12 15 14 9 0 3 2 13 4 7 | 6 1 …
a = 4, c = 2, m = 16, зерно 7:    14 10 10 10 10 10 …

Первая строка обходит все 16 значений и возвращается к началу: состояний всего 16, значит и последовательность повторяется не позже чем через 16 шагов. Вторая застревает на втором шаге: параметры подобраны неудачно. Длина цикла генератора - его период. В Python модуль random использует генератор «вихрь Мерсенна» с состоянием в 19 937 бит и периодом 2¹⁹⁹³⁷ − 1; в тренажёре стоит он же, поэтому числа совпадают.

Что из этого следует. Одно зерно - одна последовательность: опыт можно повторить бит в бит, и это полезно. Без зерна генератор засевается от часов и системного шума, и запуски различаются. А по нескольким сотням выданных чисел состояние вихря Мерсенна вычисляется полностью: каждое выданное число - обратимо преобразованное слово состояния, а слов всего 624. После этого все будущие числа известны. Для ключей, токенов и паролей нужен криптографически стойкий генератор, у которого состояние по выходу не восстановить; в Python это модуль secrets.

Первый способ испортить: остаток от деления. Нужно число от 0 до 2, есть три случайных бита - число от 0 до 7. Остаток от деления на 3 раскладывает восемь значений по трём корзинам: 0, 3, 6 дают ноль, 1, 4, 7 - единицу, 2, 5 - двойку. Двойка выпадает в 2/8 случаев вместо 1/3. Восемь на три не делится, и поделить поровну нельзя никак.

Лекарство - отбор: взять столько битов, сколько нужно для записи n − 1, и если число получилось не меньше n, выбросить его и взять новое. Каждое оставшееся значение равновероятно. Так устроены random.randrange и random.randint.

Второй способ: тасование с лишними путями. Алгоритм, делающий k независимых равновероятных выборов из n вариантов, имеет nᵏ равновозможных путей. Чтобы все n! перестановок были равновероятны, пути должны делиться между ними поровну, то есть nᵏ должно делиться на n!. Для n ≥ 3 это невозможно: в n! входит множитель n − 1, у которого с n нет общих делителей.

Тасование Фишера-Йетса делает выборы разного размера: для последнего места - из n вариантов, для предпоследнего - из n − 1, и так далее. Путей n · (n − 1) · … · 2 = n!, и каждый ведёт к своей перестановке.

для i от n − 1 вниз до 1:
    j = случайное целое от 0 до i включительно
    поменять a[i] и a[j]

Правило

Псевдослучайная последовательность полностью определяется зерном. Для воспроизводимости зерно задают, для секретов берут криптографически стойкий генератор. Число от 0 до n − 1 получают отбором, а не остатком от деления. Список тасуют алгоритмом Фишера-Йетса: a[i] меняют с a[j], где j случайно от 0 до i; путей у него ровно n!. Вариант, где j случайно от 0 до n − 1 при каждом i, даёт неравномерное распределение при любом n ≥ 3.

Разбор: генератор в две строки и перекос остатка

def posledovatelnost(a, c, m, x, skolko):
    spisok = []
    for i in range(skolko):
        x = (a * x + c) % m
        spisok.append(x)
    return spisok

print(posledovatelnost(5, 3, 16, 7, 18))
print(posledovatelnost(4, 2, 16, 7, 8))
print(posledovatelnost(5, 3, 16, 7, 6) == posledovatelnost(5, 3, 16, 7, 6))

[6, 1, 8, 11, 10, 5, 12, 15, 14, 9, 0, 3, 2, 13, 4, 7, 6, 1]
[14, 10, 10, 10, 10, 10, 10, 10]
True

Третья строка - про воспроизводимость: одно и то же зерно дало один и тот же список. Посмотри на младший бит первой последовательности: чётное, нечётное, чётное, нечётное. У такого генератора с модулем-степенью двойки младшие биты повторяются с коротким периодом, и брать от его чисел остаток по малому модулю нельзя вдвойне.

Теперь перекос остатка. Первая часть программы перебирает все восемь трёхбитных чисел, вторая делает 24 000 случайных выборов двумя способами.

import random

ostatki = [0, 0, 0]
for chislo in range(8):
    ostatki[chislo % 3] = ostatki[chislo % 3] + 1
print(ostatki)

def bez_perekosa(n, bitov):
    while True:
        r = random.getrandbits(bitov)
        if r < n:
            return r

random.seed(32)
s_ostatkom = [0, 0, 0]
s_otborom = [0, 0, 0]
for i in range(24000):
    k = random.getrandbits(3) % 3
    s_ostatkom[k] = s_ostatkom[k] + 1
    k = bez_perekosa(3, 2)
    s_otborom[k] = s_otborom[k] + 1
print(s_ostatkom, s_otborom)

[3, 3, 2]
[8974, 9084, 5942] [8036, 7965, 7999]

С остатком двойка выпала 5942 раза из 24 000 вместо восьми тысяч - на четверть реже. С отбором все три значения около восьми тысяч. Функция bez_perekosa берёт два бита, число от 0 до 3, и выбрасывает тройку; это алгоритм Лас-Вегас: ответ всегда честный, а число попыток случайно, в среднем 4/3.

На 32-битных числах перекос остатка мал, пока n мало, и поэтому годами остаётся незамеченным. При n в три миллиарда он уже грубый: случайных чисел 2³² ≈ 4,3 миллиарда, и нижние 1,3 миллиарда значений получаются из двух исходных чисел каждое, а остальные - из одного, то есть выпадают вдвое реже.

Разбор: 27 путей на 6 перестановок

Перебор всех путей двух тасований для списка [1, 2, 3]. Перестановка записана трёхзначным числом. Первый блок - наивное тасование: на каждом из трёх шагов элемент меняют со случайным из трёх. Второй - Фишера-Йетса: последний элемент меняют со случайным из трёх, средний - со случайным из двух.

def nomer(a):
    return a[0] * 100 + a[1] * 10 + a[2]

naivnoe = {}
for i0 in range(3):
    for i1 in range(3):
        for i2 in range(3):
            a = [1, 2, 3]
            vybor = [i0, i1, i2]
            for i in range(3):
                j = vybor[i]
                t = a[i]
                a[i] = a[j]
                a[j] = t
            naivnoe[nomer(a)] = naivnoe.get(nomer(a), 0) + 1

fisher = {}
for j2 in range(3):
    for j1 in range(2):
        a = [1, 2, 3]
        t = a[2]
        a[2] = a[j2]
        a[j2] = t
        t = a[1]
        a[1] = a[j1]
        a[j1] = t
        fisher[nomer(a)] = fisher.get(nomer(a), 0) + 1

for k in sorted(naivnoe):
    print(k, naivnoe[k], fisher[k])

123 4 1
132 5 1
213 5 1
231 5 1
312 4 1
321 4 1

Наивное тасование выдаёт порядки 132, 213 и 231 в пяти случаях из 27, остальные - в четырёх: разница в четверть. У Фишера-Йетса на каждую перестановку ровно один путь из шести.

Граница честного тасования - сам генератор. Перестановок 52 карт 52! ≈ 8 · 10⁶⁷, это число из 226 битов. Генератор, засеянный 32-битным зерном, способен выдать не больше 2³² разных последовательностей, то есть около четырёх миллиардов раскладов из 8 · 10⁶⁷. Алгоритм тасования при этом безупречен; мало случайности на входе. У вихря Мерсенна состояния хватает на все перестановки списков до 2080 элементов.

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

Зерно из времени. В 1999 году в одном покерном сервисе колоду тасовали генератором, засеянным числом миллисекунд с полуночи. Таких значений 86,4 миллиона; зная примерное время на сервере и свои карты, расклад всего стола перебирали за секунды. Там же использовалось и наивное тасование.

Сортировка со случайным сравнением. «Отсортируй, а сравнение пусть возвращает случайный ответ» - распространённый способ перемешать список одной строкой. Распределение получается неравномерным и зависит от алгоритма сортировки. В 2010 году из-за этого окно выбора браузера, которое Windows показывала пользователям в Европе, ставило одни браузеры на первые места заметно чаще других.

random для токенов. Ссылка для сброса пароля, построенная на обычном генераторе, предсказуема для того, кто получил несколько предыдущих ссылок.

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

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

Воспроизводимость. Тест, упавший на случайных данных, бесполезен, если данные не повторить. Поэтому зерно печатают в журнал при каждом запуске случайного теста и позволяют задать его снаружи. Все программы этого раздела начинаются с random.seed(…) по той же причине: число в уроке должно получаться и у тебя.

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

Выбор генератора - вопрос о противнике. Если противника нет - моделирование, тесты, алгоритмы, - быстрый обычный генератор годится. Если случайное число что-то защищает, противник есть, и генератор обязан быть стойким.

Теперь сам

1. Генератор x = (3x + 1) mod 8 запущен с зерна 0. Выпиши числа до первого повтора. Чему равен период?
2. Из случайного числа от 0 до 9 получают число от 0 до 3 остатком от деления на 4. С какой вероятностью выпадет ноль и с какой - тройка?
3. Сколько равновозможных путей у наивного тасования четырёх элементов и почему оно не может быть равномерным?
4. В тасовании Фишера-Йетса написали j = random.randint(0, i - 1) вместо random.randint(0, i). Может ли после такого тасования элемент остаться на своём месте?
5. Тест со случайными данными упал один раз из двадцати запусков. Что нужно было сделать заранее, чтобы найти причину?