Выбор через random_u64() % n неравномерен: что предлагает автор

Austin Seipp в блоге разбирает распространённый приём: чтобы выбрать случайный объект из набора, берут большое случайное число random_u64() и сводят его к числу вариантов остатком от деления (например, r % 10). Автор признаётся, что сам так делал в молодости, в частности на C, где в стандартной библиотеке нет ничего, кроме rand(), и на Haskell. Но у решения есть скрытая проблема: остаток от деления не сохраняет равномерное распределение исходной функции, и вероятности выбора оказываются не такими, как мы интуитивно ждём.

Проблему автор показывает на простом примере. Берём целое число от 0 до 9 (каждое выпадает с шансом 10%) и по остатку от деления выбираем один из трёх объектов. Входы {0, 3, 6, 9} дают объект №1, {1, 4, 7} дают №2, {2, 5, 8} дают №3. Выходит, что объект №1 выбирается в 40% случаев вместо задуманных 33%, а №2 и №3, только в 30%. Правильное поведение даёт функция random_between(l, h), в которой каждое число от l до h включительно выбирается с вероятностью 1/((h-l)+1), но она устроена сложнее. По мнению автора, проблема двойная: плохо давать в API только равномерную функцию (тем более что её самый полезный вариант легко реализовать неверно) и вообще мыслить не в той предметной области.

Первое предложение автора: вместо низкоуровневого random_u64() по умолчанию использовать random_choice(), функцию, которая принимает набор дискретных вариантов и вероятность каждого. Распределение приходится прописывать самому, и перекос вроде «40%?!» сразу бросается в глаза. Функции random_u64() и random_between() при этом, по его словам, всё равно должны существовать.

Второе: вероятности, которые в сумме дают ровно 1.0, неудобны из-за неустойчивости вычислений с плавающей точкой и необходимости пересчитывать масштаб. Автор предлагает относительные целочисленные веса: распределение 0,4/0,3/0,3 записывается как (4, 3, 3), вес варианта, его доля от суммы. Так, по его словам, делает большинство стандартных библиотек, например в Python. Реализовать такой выбор проще, если есть random_between(l, h): для весов 15 + 12 + 3 = 30 достаточно взять random_between(0, 29); значения 0-14 дают первый вариант, 15-26, второй, 27-29, третий.

Третья часть, теоретическая. Автор напоминает, что мы работаем не с числами, а со случайными величинами, и нелинейные операции не сохраняют их математическое ожидание: E[f(X)] не всегда равно f(E[X]). Мы думаем, что сохраняем свойство значения x = random_u64(), а на самом деле пытаемся сохранить свойства самой функции random_u64().

Наконец, практический случай. Команда автора, клиент платформы Antithesis, которая ищет ошибки, случайно прогоняя важные пути в коде; автор описывает её как детерминированный фаззер (программу для поиска ошибок случайными входными данными) для целой операционной системы. Покрытие кода служит ориентиром: путь, который фаззер не нашёл, не протестирован. В примере с загрузкой блоба (фрагмента данных) заданы веса: малый 88, средний 4, большой 4, очень большой 4, то есть при тесте примерно 7/8 загрузок малые и примерно 1/8 крупные трёх размеров. Автор отмечает, что возможность менять такие числа очень полезна для исследования пространства состояний, а набор вариантов можно расширять по условиям (например, через choice.push()), чтобы направлять поиск. Недавно, пересмотрев код, связанный с Antithesis, команда заменила все вкравшиеся вызовы random_u64() на взвешенный random_choice(), потому что на практике нужен был только дискретный взвешенный выбор, и ввела мораторий на новые вызовы random_u64() до особого распоряжения. Урок автор решил не оставлять в сообщении коммита, потому что сам постоянно его забывает.

Ключевые факты

• Выбор объекта через random_u64() % n не сохраняет равномерность: в примере с числами 0, 9 и тремя объектами первый выбирается в 40% случаев вместо 33%, второй и третий, в 30%.
• Правильная равномерная функция random_between(l, h) даёт каждому числу шанс 1/((h-l)+1), но реализовать её сложнее.
• Автор предлагает по умолчанию использовать random_choice() с явным распределением, а лучше с относительными целочисленными весами вроде (4, 3, 3), как делает большинство стандартных библиотек, например в Python.
• Пример из тестирования: веса 88/4/4/4 для размеров блоба дают при тесте примерно 7/8 малых загрузок и примерно 1/8 крупных.
• Команда автора, клиент Antithesis, заменила все свои вызовы random_u64() на взвешенный выбор и ввела мораторий на новые вызовы.

Почему это важно

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

Кому это важно

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

Как это применить

Перед тем как написать выбор через остаток от деления, спросите себя, нельзя ли записать нужное распределение напрямую. Для равномерного выбора в диапазоне нужна корректная функция random_between(l, h). Для остальных случаев автор советует список пар «вариант и целочисленный вес», например [(Blue, 10), (Red, 5)], и выбор числа в интервале по сумме весов. Можно по аналогии с командой автора запретить новые вызовы низкоуровневого random_u64(), оставив взвешенный выбор как основной инструмент.

Можно ли доверять

Это личный блог-пост Austin Seipp с авторскими оценками («я думаю», «по моему мнению»), а не исследование. Арифметика в игрушечном примере проверяется на пальцах: из 10 входов 4 попадают в первый вариант и по 3 во второй и третий. Размер смещения для настоящего u64 при остатке от деления на 10 в тексте не приведён; пример показывает принцип. Результаты замены в коде команды (тесты, найденные ошибки, покрытие) не измерялись и не приводятся.

Риски и подводные камни

Автор сам указывает, что вероятности с суммой 1.0 страдают от неточностей плавающей запятой, поэтому для практики предпочтительнее целочисленные веса. Взвешенный выбор требует корректной random_between(l, h), которую, по словам автора, легко реализовать неверно. Если менять набор вариантов по ходу работы (пример с choice.push()), веса придётся перебалансировать, хотя автор допускает структуру кода, где этого можно избежать. Совет про мораторий, решение конкретной команды, а не универсальное правило.

«Иными словами, вы должны сами прописать распределение вероятностей.»

— Austin Seipp, «When random is not actually random enough»