Как выбрать одно из значений с определенной вероятностью?

#python #алгоритм #случайные_числа #теория_вероятностей

Пример. Катя получила 10 баллов, а Коля — 20 баллов.
Значит в одном случае из трех победит Катя, а в двух из трех — Коля.

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

Какой формулой это расчитывается (Нужна универсальная формула для любого числа участников
лотереи)?

P.S. Язык Python.
    

Ответы

Ответ 1

Примем за условие:


  Игрок 1 - вероятность выигрыша 10
  Игрок 2 - вероятность выигрыша 20


В простом случае, нам надо сложить все вероятности выигрыша вместе (то есть 10 +
20 в примере) и потом сгенерировать случайное число в диапазон от 0 до суммы вероятностей
(до 30). Далее, от получившегося случайного числа, отнимать вероятности выигрыша по
очереди (например, идем сверху вниз), и как только разность станет меньше 0 - вы нашли
искомого Игрока (победителя).

Итак, пример:

10 + 20 = 30 // сумма вероятностей
Random(30) = 26.67 // случайное число
26.67 - 10 = 16.67 // вычитаем вероятность 1 игрока
16.67 - 20 = -3.33 // вычитаем вероятность 2 игрока
// Результат стал меньше 0. Значит 2-й игрок - искомый победитель




В английской среде алгоритм имеет название "Roulette wheel selection" (и часто используется
в генетических алгоритмах). Такое название дано в связи с тем, что можно представить
все вероятности как сектора рулеточного колеса (на рисунке они приведены к процентам
от суммы), и случайным образом выбирать положение на колесе, определяя тем самым "выигравший"
сектор.


Ответ 2

В Питоне уже есть готовая функция, чтобы выбрать победителя в соответствии с весами:

>>> import random
>>> random.choices(['Катя', 'Коля'], weights=[10, 20])
['Коля']  # пример возможного вывода


Можно проверить, что Kоля выбирается в ~2/3 случаев, а Катя в ~1/3 в среднем:

>>> from collections import Counter
>>> Counter(random.choices(['Катя', 'Коля'], weights=[10, 20])[0]
...         for _ in range(100000))
Counter({'Коля': 66715, 'Катя': 33285})


Для случая, только двух участников, легко самостоятельно реализовать выбор:

>>> 'Катя' if random.random() < 1/3 else 'Коля'
'Коля'


Похожие результаты:

>>> Counter('Катя' if random.random() < 1/3 else 'Коля'
...         for _ in range(100000))
Counter({'Коля': 66617, 'Катя': 33383})


Чтобы сложнее было победителя предсказать, можно secrets модуль использовать:

>>> import secrets
>>> 'Катя' if secrets.randbelow(30) < 10 else 'Коля'
'Коля'


randbelow() может вернуть 30 возможных значений [0, 30), при этом для 10 выпавших
значений [0, 10) выбирается Катя (1/3 vs. 2/3 разделение).

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