随机概率选择

本文关键字：选择 概率 随机 | 更新日期: 2023-09-27 18:04:28

假设我有10个奖品要给100个人。每个人都有机会，一次一个。因此，如果第一个人没有赢得奖品，概率就会上升，99人中有10人，所以1……另外，所有10个奖项都必须取消。

如果最后还有奖品，那个人有1/1的机会得到奖品，那么最好的方式是什么?

我是这样想的:

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

我想知道是否有更好或更直接的方法来做这件事。我知道这看起来很简单，但这个简单的任务是应用程序一个非常重要的方面的一部分，它必须是正确的。

澄清:为什么我想做这样的事情:

在现实中存在无限数量的玩家，每个玩家都有X或Y的获胜概率，例如10/100 = 10%。但是如果我把它留给随机数生成器，那么在100个玩家中就有可能只有9个会赢，或者最坏的情况是11个。在我的应用中，我必须确保每100个玩家中不超过且不少于10个玩家获胜。

随机概率选择

每个人都应该有平等的获胜机会吗?在这种情况下，为什么不随机选择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);
}

我又考虑了一下这个问题，得出了以下结论。我们可以给第一个人一个公平的获胜机会，然后如果剩下的奖励公平地分配给其他人(不管他是赢还是输)，那么整个事情就是公平的。当然，这远不是正式的证明，所以请随时纠正我。下面应该给出一个公平的系统:

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分配给他们，并且概率(k-n)/k， n奖。平均起来是(n*(n-1))/k + (n*(k-n))/k = n*(k-1)/k，这是他们公平的奖金份额。
  3. 我们使用相同的方法在k-1人中分配n-1或n奖金。Q.E.D.

这将使您的行为迫使获胜者的概率在人数减少时趋近于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--;
}

最公平的方法是生成一个从1到100的随机数!/(90 !* 10!))(因为这是获奖者的可能组合的数量)，并使用它来颁发奖品。

然而，使用该数字的倍数更容易，例如获奖者的排列数量，即(100!/90)。一种方法是填充一个包含100个整数的数组，但每次都从数组中删除获胜的整数(将其与最后一个非获胜整数交换是实现这一目标的最简单方法)。

你的算法有效地要求100的随机性!虽然我相信它仍然是非常公平的，但它的效率要低得多。

相关文章：