Як працює зважений випадковий вибір

Зважений випадковий вибір – це те, що ви використовуєте, коли варіанти не повинні мати однакову ймовірність. Ваги показують, як часто в середньому кожен варіант має вигравати.

Ключові висновки

• Ймовірність = вага поділена на загальну вагу.
• Кумулятивні ваги перетворюють опції на сегменти інтервалу від 0 до 1.
• Безпечне випадкове значення вибирає точку; виграє відповідний сегмент.
• Зваження без заміни видаляє переможця та повторно нормалізує ваги, що залишилися.
• Перевірте справедливість, порівнюючи спостережувану та очікувану частоти в багатьох розіграшах.

Рівна чи зважена випадковість

Звичайний випадковий вибір розглядає кожен варіант однаково. Це правильно для жеребкування в класі, де кожен учень повинен мати однакові шанси. Але багато реальних рішень є свідомо нерівними:

• Гра вимагає, щоб звичайна здобич з’являлася часто, а рідкісна – рідко.
• Розіграш дає деяким учасникам більше квитків, ніж іншим.
• A/B тест направляє 80% користувачів на контрольний варіант і 20% на новий.
• Учитель хоче, щоб важкі питання з'являлися частіше, ніж легкі.

Зважена випадковість все ще залишається випадковістю. Різниця полягає в тому, що розподіл ймовірностей є навмисним.

Ваги - це ймовірності, а не кількість

Вага опціону сама по собі не є ймовірністю. Це відносне число. Щоб отримати ймовірність, розділіть вагу на суму всіх ваг.

Припустімо, що є такі варіанти:

• А, вага 1.
• B, вага 2.
• С, вага 7.

Загальна вага дорівнює 10, тому ймовірності становлять 10%, 20% і 70%. Якщо ви зіграєте нічию 100 разів, C має виграти приблизно 70 разів. Якщо ви зіграєте внічию лише 10 разів, C може виграти 4, 6 або навіть 0 разів. Маленькі зразки шумлять; ваги описують довгострокове очікування.

Кумулятивний розподіл

Кумулятивний розподіл перетворює ці ваги на сегменти інтервалу від 0 до 1. З тим самим прикладом:

• А покриває від 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 отримають більші частки наступного розіграшу.

Без заміни не тасування. Він не створює кожну перестановку з рівною ймовірністю. Він створює зважений порядок: варіанти з більшою вагою зазвичай з’являються раніше.

Метод псевдоніма для вибору великого обсягу

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

Метод псевдоніма корисний в іграх і симуляціях, які потребують мільйонів вибірок. Для інструмента браузера з невеликим списком сукупна вибірка зворотного перетворення є простішою та цілком адекватною.

Типові помилки

Ваги легко помилитися. Слідкуйте за такими помилками:

• Обробка ваги 70 як 70%, якщо інші ваги не дорівнюють нулю. Це лише 70%, якщо сума інших ваг становить 30 або менше.
• Дозволяє нульові або негативні ваги. Варіанти з нульовою вагою ніколи не можуть виграти. Від’ємні ваги роблять розподіл безглуздим.
• Використання Math.random() для розіграшу, який має бути непередбачуваним.
• Використання упередженого відображення для перетворення випадкових значень на сегменти.
• Оцінюйте справедливість з десяти-двадцяти нічиїх. Невеликі зразки можуть сильно відрізнятися від очікуваного розподілу.

Ще одна поширена помилка - плутати зважування з перетасуванням. Якщо вам потрібна однакова ймовірність кожної перестановки, перетасуйте список. Якщо вам потрібен зважений перший вибір, використовуйте зважене жеребкування.

Як перевірити зважений розіграш

Порівняйте очікувані та спостережувані частоти. З вагами 1, 2 і 7 очікувані ймовірності становлять 10%, 20% і 70%. За тисячами розіграшів спостережувані пропорції повинні наближатися до цих цифр.

Не перетлумачуйте маленьку вибірку. Справедлива нічия може призвести до дивовижної серії. Важливим є те, чи збігаються спостережувані частоти в міру зростання вибірки і чи задокументована реалізація.

Для публічного зваженого розіграшу запишіть варіанти, ваги та результат. Це робить розіграш доступним для аудиту, навіть якщо ви ніколи не опублікуєте код.

Як цей сайт реалізує зважений випадковий вибір

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

Усе працює локально у вашому браузері. Ваші параметри, ваги та результати не завантажуються.

Підсумок

Зважена випадковість змінює ймовірності, а не джерело випадковості. Нормалізуйте ваги, використовуйте безпечне випадкове значення та виберіть відповідний кумулятивний сегмент. Це дає вам справедливі нерівні ймовірності для столів здобичі, розіграшів, A/B-тестів і занять у класі.