3

Say I have 10 prizes to give to 100 people. Each person gets a shot, one at a time. So if the first person fails to win a prize, the probability goes up, 10 in 99, and so one... Also all 10 prizes MUST go.

What would be the best way to write this in such a way that by the end if there is still a prize left, that person would have a 1 in 1 chance to get a prize...

What I was thinking like this:

int playersLeft = 100
int winners = 0

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

I wanted to know if there was a better or more straight forward way to do it. I know it seems simple but this simple task is part of a very important aspect of the app and it must be right.

TO CLARIFY: Why I want to do something like this:

In reality there is an unlimited number of players, each with an X in Y probability to win, say 10/100 = 10%. However if I leave it to the random number generator, there is a chance that in 100 players, only 9 would win, or worst, 11. In my app, I must assure that no more and no less than 10 players for every 100 will win.

4
  • You do realise that if you do it like this there will be better and worse moments to join the game? Aug 5, 2011 at 9:09
  • @obrok - Yes, I know. But any other way, I have to manipulate it depending on the case. For instance, if no prices have been won, force a winner every X amount of players or if all prices have been won, especify that there can be no more winners for the duration of the game. Which is why I want to spread out winner for the entire game evenly. Say if there are 1000 players, make sure the first 100 have = chance than the last 100. As opposed to giving all prices by the 900th person, so the last 100 have 0 chance of winnig. I dont know if I make myself clear.
    – AJC
    Aug 5, 2011 at 14:16
  • And it's not possible to just wait until 100 players arrive and the distributed prizes, is it? Aug 5, 2011 at 14:37
  • Nop... winners can claim their prize at any time and they must be selected winner or looser as soon as they finish playing.
    – AJC
    Aug 5, 2011 at 14:48

4 Answers 4

3

Should every person have equal chances of winning? In that case why not just select randomly 10 distinct numbers 1-100 and then pretend to do it in order?

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);
}
1
  • For simplification I put it in a while loop. However the selection will be made throughout a long period of time and this approach would require me to save the pre-selection on a database, which I would rather not... but thanks... However you are right, with my approach, not all players get te same chance to win.
    – AJC
    Aug 4, 2011 at 22:31
2

I have thought about this some more and have come up with the following. We can give the first guy a fair shot at winning and then if the rest of the rewards are distributed fairly among the rest of the people (no matter if he wins or loses) the whole thing will be fair. Of course that's far from formal proof, so feel free to correct me. The following should give a fair system:

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

Edit: Proof this works:

  1. The first person trivially has n/k chance of winning (n being the number of prizes, k being the number of people.
  2. Let's assume we distribute the remaining prizes fairly among the rest of the people. In that case they will have with probability n/k, n-1 prizes distributed between them and with probability (k-n)/k, n prizes. That adds up to (n*(n-1))/k + (n*(k-n))/k = n*(k-1)/k on average which is their fair share of the prizes.
  3. We use the same method to either distribute n-1 or n prizes among the k-1 people. Q.E.D.
1
  • I assume people = i... Yes this is more like what I am looking for, thank you.
    – AJC
    Aug 4, 2011 at 22:48
1

This will give you the behavior of forcing the probability of a winner to go to 1.0 as the number of people shrinks. However, as @obrok pointed out, the probability of a person winning a prize depends on their rank in the list of 100 people.

This is actually the same algorithm that is used for "N choose K" subset selection. 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--;
}
2
  • Yeah, this is pretty much the same as what I propposed... I was just trying to keep probabilities equal for all, but at the same time making sure a precise number of prizes where won... Thanks...
    – AJC
    Aug 5, 2011 at 14:09
  • 1
    Actually, I should have been more precise. The marginal probabilities of each person winning are the same, but the conditional probability of a win given the previous winners is not uniform, i.e. let x[n] by the nth person and k be the number of prizes and N the total number of people. For this selection algorithm, p(x[n] = WINNER) = k/N, but p(x[n] = WINNER | x[0], ..., x[n-1]) = (k - #winners thus far) / (N - n)
    – Lucas
    Aug 5, 2011 at 17:00
0

The perfectly fair way to do is to generate a random number from 1 to (100! / (90! * 10!)) (since this is the number of possible combinations of prizewinners) and use that to award the prizes.

However it's easier to use some multiple of that number, such as the number of permutations of prizewinners, which is (100! / 90!). One way of doing this is to populate an array of 100 integers but remove the winning integer from the array each time (swapping it with the last non-winning integer is the easiest way to achieve this).

Your algorithm effectively requires randomness of 100! so it is much less efficient, although I believe it is still perfectly fair.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.