概率選擇從5 2號（從編程珍珠，第二版）

該算法考慮整數0，1，2，...，N-1，以便，並通過適當的隨機測試來選擇每一個。通過訪問整數，我們保證輸出將被排序。

爲了理解選擇標準，讓我們考慮M = 2 的例子，且n = 5。我們應該以2/5的概率選擇第一個整數0;一個程序實現，通過像

if (bigrand() % 5) < 2

我的問題是一個命題，爲什麼選擇的第一個整數的概率是2/5，而不是1/5？不應該從5個數字中隨機選擇一個數字的概率是1/5？

這裏真是莫名其妙。希望有人能在這裏提供一些解釋。

謝謝！

來源

2012-06-19 Qiang Xu

'bigrand（）％5'可以給0，1，2，3，4，和其中2（0和1）是小於2 – nhahtdh

什麼是該算法的目標是什麼？以相等的概率選擇N個數字中的M個？ – dfb

從5個數字中隨機選擇一個數字的概率是不是應該是1/5？

這是一種設計採樣算法的方法，但這種方法的工作方式不同。它依次考慮每個元素，並決定該元素是否是樣本的一部分。這是m = 2和n = 4的決策樹（抑制了確定性決策）。

      take 0? 
       _____yes_____  _____no_____ 
      /        \ 
      /        take 1? 
      take 1?       yes/  \no 
     yes/ \no      /  \ 
     / \      take 2?  {2,3} 
     {0,1} take 2?     yes/ \no 
      yes/ \no    / \ 
      / \    {1,2} {1,3} 
      {0,2} {0,3}

在根部，3/6後代結果包括0，0取概率2/4 = 1/2。如果我們取0，那麼只有1/3結果包括1.如果我們不取0，那麼2/3結果包括1.在每一步，每個決策的概率與相應子樹的結果數量成比例，確保大小爲m的均勻隨機子集。

來源

2012-06-19 04:32:46 rich

這張圖真的很直觀！ –

假設你挑選一對有序。那麼第一個數字就是該對中第一個數字的概率是1/5，同樣，第一個數字是該對中第二個數字的概率是1/5。（這將永遠都在該對第一和第二個數字。）

因此它有2個機會出5爲處於有序對的某個地方。

挑選一個隨機二元集合是相同的採摘的有序對，然後忘記的順序。因此它也有2個出現在無序對中的機會。

來源

2012-06-19 04:37:00 btilly

也看起來像一個有效的推理，謝謝。 –

概率選擇從5 2號（從編程珍珠，第二版）

回答

相關問題