Вероятность и статистика · объяснение и практика
Почему остаток случайного числа не всегда даёт равномерный выбор
Проверяем равномерность остатков конечного случайного источника подсчётом прообразов. Убираем лишний хвост и доказываем равные шансы результата после повторного выбора.

В теме Случайные процессы и имитация: углубление · Учебная карта
Главная мысль
Если X равномерно выбирается из целых 0,…,M−1, остаток X по модулю m равномерен только при делимости M на m. Здесь предполагаются положительные целые M и m, причём m≤M. Для исправления сохраняют первые m⌊M/m⌋ исходов, отбрасывают оставшийся хвост и после отказа заново независимо выбирают X. У каждого остатка тогда одинаковое число прообразов.
Равные входные шансы могут объединиться неравномерно
Возьмём источник из десяти равновероятных чисел от нуля до девяти и хотим получить четыре результата. Остаток ноль приходит от нуля, четырёх и восьми; остаток один — от единицы, пяти и девяти. Для остатков два и три есть только по два исходных числа. Вероятности получаются 3/10, 3/10, 2/10 и 2/10. Операция остатка корректна арифметически, но не сохраняет нужную равномерность.
Разделим M на m: M=qm+r, где 0≤r<m. Для первых r остатков имеется q+1 прообразов, для остальных — q. Когда r=0, все группы равны. При положительном остатке некоторые результаты получают лишний шанс. Увеличение количества опытов не устраняет этот перекос: наблюдаемые доли будут стабилизироваться около неравных вероятностей. Это систематическое свойство преобразования, а не случайная неудачная короткая серия.
Убираем целиком неполный блок
Пусть L=qm. Принимаем исходное X только при X<L, после чего возвращаем X mod m. Каждый допустимый остаток имеет ровно q принятых прообразов, а всего принятых чисел L. Условная вероятность каждого результата равна q/L=1/m. После отказа нужен новый независимый выбор из исходного полного диапазона. Замена хвоста одним удобным значением снова создала бы лишнюю вероятность.
Доля принимаемых предложений равна L/M. Среднее число попыток до одного принятия равно M/L при независимых повторах. Это оценка среднего расхода, а не гарантированная граница времени выполнения. Вариант m>M данным правилом не поддерживается: q=0 и принимать нечего. Чтобы получить больше равновероятных исходов, сначала нужно построить более широкий источник, например из нескольких независимых разрядов.
Пример
Источник равномерен на 0,…,13. Нужны пять равновероятных значений. Как устроить отбор?
M=14, m=5, q=2, L=10. Принимаем 0,…,9 и берём остаток по модулю 5; значения 10,…,13 требуют нового выбора. Каждый результат имеет два прообраза. Принятие равно 10/14=5/7, средний расход — 7/5 попытки.
Источник и преобразование проверяются отдельно
Доказательство предполагает действительно равномерный исходный диапазон. Если сами входные числа смещены, одинаковое количество прообразов ещё не гарантирует равную сумму их вероятностей. Также повторное использование одного отклонённого числа вместо новой попытки может изменить условный закон или вообще зациклить процедуру. В алгоритме явно разделяют генерацию, проверку допустимости и преобразование принятого значения.
Библиотечная функция выбора целого из диапазона обычно предпочтительнее самостоятельного деления случайного дробного числа: её контракт специально описывает равномерный выбор. Но равномерность одного результата не означает непредсказуемость и не делает учебный генератор пригодным для секретных ключей. Здесь рассматривается конечная вероятностная модель и распределение значений. Безопасность источника и зависимости между последовательными вызовами требуют самостоятельных условий.
От чтения к действию
А теперь — вы
Частые вопросы
Почему нельзя остатки хвоста просто заменить нулём?
Ноль получит все перенесённые вероятности и станет встречаться чаще. Для равномерности хвост отклоняют, затем выбирают заново.
Если M кратно m, отбрасывание нужно?
Нет. У всех остатков уже по M/m прообразов, поэтому прямой остаток равномерен при равномерном X.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Как отбор под огибающей создаёт нужное распределение
Как огибающая и независимая равномерная проверка меняют закон принятой точки, почему неподходящую константу нельзя исправить обрезанием вероятности.
Открыть темуКогда порядок выбранных предметов не создаёт новый вариант
Считаем группы без должностей и порядка, объясняем деление на перестановки внутри выбранной группы и отличаем сочетания от упорядоченного выбора.
Открыть тему