Случайный выбор вероятности

Question

Скажем, у меня есть 10 призов, чтобы дать 100 человек.Каждый человек получает выстрел, по одному за раз.Так что, если первый человек не сможет выиграть приз, вероятность возрастет, 10 из 99, и так один ... Также все 10 призов ДОЛЖНЫ быть разыграны.

Как лучше написать это так, чтобы к концу, если еще оставался приз, у этого человека был шанс 1 к 1 получить приз ...

Что я думал так:

int playersLeft = 100
int winners = 0

while (winners < 10)
    winners += (random.Next(playersLeft--)<(10-winners)) ? 1 : 0;

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

На самом деле существует неограниченное количество игроков, каждый из которых имеет вероятность выигрыша X в Y, скажем, 10/100 = 10%.Однако, если я оставлю это генератору случайных чисел, есть вероятность, что из 100 игроков только 9 выиграют или, что хуже всего, 11. В моем приложении я должен убедиться, что не более и не менее 10 игроков на каждые 100 будутвыиграть.

Answer 1

Должен ли каждый человек иметь равные шансы на победу? В таком случае, почему бы просто не выбрать случайным образом 10 различных чисел 1-100, а затем сделать вид, что они делают это по порядку?

var winners = new HashSet<int>();
while(winners.Count < 10)
{
  var number = random.Next(100);
  if(!winners.Contains(number)) winners.Add(number);
}

for(i = 0; i < 100; i++)
{
  if(winners.Contains(i)) Console.WriteLine("{0} won!!!", i);
  else Console.WriteLine("{0} didn't win, sorry...", i);
}

Answer 2

Я подумал еще об этом и придумал следующее.Мы можем дать первому парню шанс на победу, а затем, если остальные награды будут справедливо распределены между остальными людьми (независимо от того, выиграет он или проиграет), все будет честно.Конечно, это далеко не формальное доказательство, поэтому не стесняйтесь поправлять меня.Следующее должно дать честную систему:

int prizes = 10;
for(int i = 100; i >= 1; i++)
{
  var result = random.Next(people);
  if(result < prizes)
  {
     Console.WriteLine("{0} won", i);
     prizes--;
  }
}

Редактировать: Доказательство этого работает:

1. Первый человек тривиально имеет n / k шанс на победу ( n - количество призов, k - количество человек.
2. Предположим, что мы справедливо распределим оставшиеся призы среди остальных людей. В этом случаеони будут иметь с вероятностью n / k , n-1 выигрышей, распределенных между ними и с вероятностью (kn) / k , n призы, что в среднем составляет (n * (n-1)) / k + (n * (kn)) / k = n * (k-1) / k , что составляет их справедливую долю
3. Мы используем один и тот же метод для распределения n-1 или n призов среди k-1 человек. QED

Answer 3

Это даст вам возможность заставить победителя перейти к 1,0, когда количество людей сокращается. Однако, как отметил @obrok, вероятность того, что человек выиграет приз, зависит от его ранга в списке из 100 человек.

Это фактически тот же алгоритм, который используется для выбора подмножества "N выбирать K". http://mcherm.com/permalinks/1/a-random-selection-algorithm

int prizes = 10;
int people = 100;

while ( prizes > 0 ) {
   double probOfWin = (double) prizes / people; 
   if ( random.NextDouble() <= probOfWin ) {
      prizes--;
   }
   people--;
}

Answer 4

Совершенно справедливый способ сделать это - сгенерировать случайное число от 1 до (100! / (90! * 10!)) (Так как это количество возможных комбинаций призеров) и использовать его для присуждения призов.

Однако проще использовать несколько кратных этого числа, например, количество перестановок призеров, которое равно (100! / 90!). Один из способов сделать это состоит в том, чтобы заполнить массив из 100 целых чисел, но каждый раз удалять из него выигрышное целое число (поменять его последним не выигрышным целым числом - это самый простой способ добиться этого).

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