Example. Katya got 10 points, and Kolya got 20 points. So in one case out of three Katya will win, and in two out of three - Kohl will win.

It is necessary to randomly select the winner of the lottery, given their probabilities of winning.

What formula is it calculated (Need a universal formula for any number of lottery participants)?

PS Python language.

  • 3
    If a random number from 0 to 30 is greater than 10, then Kolya will win, if not, then Katya. What is the difficulty? - BogdanBida
  • Gentlemen, why are you actually minus? Good question (just wake up wording) - Kromster
  • Most interested in how to do it. - Administrator

2 answers 2

We accept the condition:

Player 1 - probability of winning 10
Player 2 - probability of winning 20

In the simple case, we need to add all the probabilities of winning together (that is, 10 + 20 in the example) and then generate a random number in the range from 0 to the sum of the probabilities (up to 30). Further, from the resulting random number, take the probabilities of winning one by one (for example, we go from top to bottom), and as soon as the difference becomes less than 0 - you have found the desired Player (winner).

So, an example:

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

In the English environment, the algorithm is called "Roulette wheel selection" (and is often used in genetic algorithms). This name is given due to the fact that all the probabilities can be represented as sectors of the roulette wheel (in the figure they are reduced to percentages of the amount), and randomly choose the position on the wheel, thereby determining the "winning" sector.

enter image description here

  • Unclear. If it fell 7.46, then who won? And why? - Enikeyshchik
  • If it fell 7.46, then we subtract 10 and immediately get a negative number, then won the first one. - Kromster
  • Why 10, not 20? And in your example, why do we start with 10, and not with 20? - Enikeyshchik
  • @ Enikeyshchik edited the answer. We start subtracting by turns. In fact, the queue order is not important (we can go from bottom to top), the main thing is that it should be maintained on subsequent calls. - Kromster
  • one
    @MarinaaaniraM if the weights are equal, then it does not matter and the algorithm does not change. - Kromster

In Python, there is already a ready-made function to choose the winner according to the weights:

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

You can check that the Kolya is selected in ~ 2/3 cases, and Katya in ~ 1/3 on average:

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

For the case of only two participants, it is easy to independently implement the choice:

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

Similar results:

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

To make it harder for the winner to predict, you can use the secrets module:

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

randbelow() can return 30 possible values [0, 30) , while for 10 dropped out values [0, 10) Katya is selected (1/3 vs. 2/3 division).

In general, there may be differences in how many random bits are generated and by what algorithm in the examples given. In different situations, different choices may be more appropriate.