Как работает взвешенный случайный выбор

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

Коротко

• Вероятность = вес варианта, делённый на общий вес.
• Кумулятивные веса превращают варианты в сегменты интервала от 0 до 1.
• Безопасное случайное число выбирает точку, а соответствующий сегмент — победителя.
• Выбор без возвращения удаляет победителя и пересчитывает оставшиеся веса.
• Честность проверяется сравнением наблюдаемых и ожидаемых частот на длинной серии.

Обычная и взвешенная случайность

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

• в игре обычная добыча должна выпадать часто, а редкая — редко;
• в розыгрыше у участников разное количество билетов;
• в A/B-тесте 80% пользователей идёт в контрольную группу, 20% — в новую;
• учителю нужно, чтобы сложные вопросы появлялись чаще простых.

Взвешенная случайность — всё ещё случайность. Отличается только заданное распределение вероятностей.

Веса — не проценты

Вес варианта — это не вероятность сам по себе, а относительное число. Чтобы получить вероятность, разделите вес на сумму всех весов.

Пример:

• A, вес 1;
• B, вес 2;
• C, вес 7.

Общий вес равен 10, поэтому вероятности — 10%, 20% и 70%. Если сделать 100 выборов, C выиграет примерно 70 раз. Если сделать 10, результат может быть 4, 6 или даже 0. На коротких сериях шум велик; веса описывают ожидание на длинной дистанции.

Кумулятивное распределение

Кумулятивное распределение превращает веса в сегменты интервала от 0 до 1:

• A занимает 0,00–0,10;
• B — 0,10–0,30;
• C — 0,30–1,00.

Ширина каждого сегмента равна вероятности варианта. Сегменты не пересекаются и вместе покрывают весь интервал.

Поэтому для выбора не нужно отдельное случайное число для каждого варианта: достаточно весов и их суммы.

Обратное преобразование

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

1. Посчитайте общий вес.
2. Возьмите случайное значение между 0 и общим весом.
3. Идите по вариантам, добавляя каждый вес к накопленной сумме.
4. Остановитесь на первом варианте, чья кумулятивная сумма больше или равна случайному значению.

Этот вариант и есть победитель. Если значение попало в сегмент A, выигрывает A; если в C — C.

Алгоритм занимает O(n) времени на выбор, где n — количество вариантов. Он прост, корректен и более чем достаточно быстр для страницы с десятками вариантов.

С возвращением и без возвращения

С возвращением каждый выбор независим. Один и тот же вариант может выиграть несколько раз. Это подходит, если каждый розыгрыш должен использовать исходные вероятности.

Без возвращения выбранный вариант удаляется из пула. Оставшиеся веса пересчитываются перед следующим шагом. Если A удалён, общий вес уменьшается, поэтому B и C получают большую долю следующего выбора.

Без возвращения — это не перемешивание. Не все перестановки равновероятны: варианты с большими весами чаще оказываются раньше.

Alias method для больших объёмов

Для миллионов выборов или очень больших списков есть более быстрый метод — alias method. Он один раз строит таблицу и затем отвечает на каждый выбор за константное время.

Он полезен в играх и симуляциях с огромным количеством выборов. Для браузерного инструмента с небольшим списком кумулятивное обратное преобразование проще и вполне достаточно.

Частые ошибки

Веса легко задать неправильно. Смотрите на эти ошибки:

• Принимать вес 70 за 70%, когда другие веса не равны нулю. Это 70% только если остальные веса в сумме дают 30 или меньше.
• Разрешать нулевые или отрицательные веса. Нулевой вариант не выиграет никогда, отрицательный делает распределение бессмысленным.
• Использовать Math.random() для розыгрыша, где важна непредсказуемость.
• Неправильно преобразовывать случайные значения в сегменты.
• Оценивать честность по десяти-двадцати розыгрышам. Маленькая выборка может сильно отличаться от ожидаемого распределения.

Ещё одна ошибка — путать взвешенный выбор с перемешиванием. Если нужны все перестановки равновероятно, перемешивайте список. Если нужен взвешенный первый выбор, используйте взвешенный розыгрыш.

Как проверить взвешенный выбор

Сравните ожидаемые и наблюдаемые частоты. Для весов 1, 2 и 7 ожидаемые вероятности — 10%, 20% и 70%. На тысячах выборов наблюдаемые доли должны приближаться к этим числам.

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

Для публичного взвешенного розыгрыша запишите варианты, веса и результат. Это позволит проверить процесс даже без публикации кода.

Как это реализовано на сайте

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

Всё работает локально в браузере. Ваши варианты, веса и результаты не отправляются на сервер.

Итог

Взвешенная случайность меняет вероятности, а не источник случайности. Нормализуйте веса, возьмите безопасное случайное число и выберите соответствующий кумулятивный сегмент. Так получаются честные неравные вероятности для таблиц добычи, розыгрышей, A/B-тестов и учебных активностей.