隨機概率選擇

說我有10個獎給100人。每個人每次都有一個鏡頭。所以如果第一個人沒有贏得獎品，那麼概率就會上升，99年有10個，所以有一個......所有10個獎項都必須去。隨機概率選擇

什麼會以這樣的方式來寫這篇文章，通過是否存在仍留有一個獎結束後，這個人將有一個1 1機會獲得獎品的最佳途徑......

什麼我是這樣想的：

int playersLeft = 100 
int winners = 0 

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

我想知道是否有更好或更直接的方法來做到這一點。我知道這似乎很簡單，但這個簡單的任務是應用程序非常重要的一部分，它必須是正確的。

澄清：爲什麼我想要做這樣的事情：

在現實中的玩家數量不限，每個Y中概率X取勝，說10/100 = 10％。然而，如果我將它留給隨機數生成器，那麼在100名玩家中，只有9人會獲勝，或者最差的是11人。在我的應用程序中，我必須保證每100人中不會有不少於10人贏得。

來源

2011-08-04 AJC

你知道嗎，如果你這樣做，會有更好更糟的時刻加入遊戲？ –

@obrok - 是的，我知道。但任何其他方式，我必須根據情況操作它。例如，如果沒有贏得價格，則每X個玩家強制一個贏家，或者如果所有價格都已贏取，則應指定在遊戲期間不能再有贏家。這就是爲什麼我想要均勻分攤整個比賽的勝利者。假設有1000名玩家，確保前100名有機會比過去100名有所提高。與900名玩家提供所有價格相反，所以最後100名玩家有機會獲得0名玩家。我不知道我是否清楚自己。 – AJC

不可能等到100名玩家到達並分發獎品，是嗎？ –

我已經想到了這一些，並已經想出了以下內容。我們可以讓第一個人贏得一個公平的勝利，然後如果其餘的獎勵在其他人中公平分配（不管他是贏還是輸），整個事情就會公平。當然這遠不是正式的證明，所以請隨時糾正我。下面應該給一個公平的制度：

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

編輯：證明這個作品：

第一人稱平凡具有N/K勝算（ñ作爲獎品的數量， k是人數
我們假設我們剩下的獎金公平地分配給其餘的人，在這種情況下，他們的概率爲n/k,n-1在它們之間分配的獎品以概率（k-n）/ k,n n獎品。平均而言，這是他們公平的份額份額，總計爲（n *（n-1））/ k +（n *（k-n））/ k = n *（k-1）/ k。
我們用同樣的方法將K-1人與人之間要麼分配N-1或ñ獎品。證明完畢

來源

2011-08-04 22:42:50

我假設人=我...是的，這更像是我在找什麼，謝謝。 – AJC

當然，非常感謝...... – AJC

每個人都應該有平等的獲勝機會嗎？那麼爲什麼不只是隨機選擇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); 
}

來源

2011-08-04 22:21:28

爲了簡化，我把它放在while循環中。然而，選擇將在很長一段時間內進行，這種方法將要求我將預選保存在數據庫上，我不想......但是，謝謝......但是，您說得對，用我的方法，並非所有的玩家都有同樣的機會贏得勝利。 – AJC

完全公平的做法是產生一個從1到（100！/（90！* 10！））的隨機數（因爲這是獲獎者可能組合的數量）並用它來獎勵獎品。

但是，使用該數字的某個倍數比較容易，例如獲獎者的排列數（100！/ 90！）。這樣做的一種方法是填充一個由100個整數組成的數組，但每次都從數組中移除獲勝的整數（與最後一個非獲勝整數交換是實現此目的的最簡單方法）。

你的算法有效地需要100的隨機性！所以它效率低得多，儘管我相信它仍然是完全公平的。

來源

2011-08-04 22:47:10 Neil

這會給你一個行爲，迫使獲勝者的概率隨着人數的縮減而降至1.0。然而，正如@布羅克所指出的，一個人獲獎的可能性取決於他們在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--; 
}

來源

2011-08-05 03:48:24 Lucas

是的，這與我提出的幾乎相同......我只是想保持所有人的概率相同，但同時確保獲得準確數量的獎品...謝謝... – AJC

其實，我應該更精確。每個人獲勝的*邊際*概率是相同的，但給定先前獲勝者的*條件*概率是不統一的，即讓x [n]爲第n個人，k爲獎項的數量，N爲總人數。對於這種選擇算法，p（x [n] = WINNER）= k/N，但是p（x [n] = WINNER | x [0]，...，x [n-1]）=（k - ＃獲勝者）/（N - n） – Lucas

隨機概率選擇

回答

相關問題