蓄水池算法的設計和實作

作者: Grey

原文位址：蓄水池算法的設計和實作

假設有一個源源吐出不同球的機器， 隻有裝下10個球的袋子，每一個吐出的球，要麼放入袋子，要麼永遠扔掉,如何做到機器吐出每一個球之後，所有吐出的球都等機率被放進袋子裡

吐出1到10号球，完全入袋, 引入随機函數f(i)，提供一個值i，等機率傳回1-i的一個數字, 當K号球吐出的時候（K>10) ,我們通過以下決策決定是否要入袋

引入随機函數：f(K) , 如果傳回10以内的數，則入袋，如果傳回10以外的數，則扔掉, 即：10/K的機率決定球是否入袋。

第一步中如果決定入袋，那麼袋子中已經存在的球以等機率丢棄一個。

當K為1～10号的時候，根據我們的規則，入袋機率100%，每個球等機率

當K為任意一個大于10的數，我們假設K為927，即：當927這個編号的球吐出來的時候，我們考慮：

A. 1 ～ 10 号球的入袋機率

B. 大于10号小于等于927号球的入袋機率

如果A和B都可以說明等機率

那麼可以推廣到普遍情況都是等機率的。

A情況，927号球到來的時候，我們可以考慮一下5号球的入袋機率是多少？

5号球需要存活到927号球到來，必須滿足：

11号球來的時候，5号球活下來

12号球來的時候，5号球活下來

...

926号球來的時候，5号球活下來

11号球來的時候，5号球怎麼活下來呢？先看一下，11号球到來，5号球如果沒有活下來的機率<code>q</code>，那麼5号球活下來的機率就是 <code>1 - q</code>

首先，根據我們的規則，11号球要以<code>10/11</code>機率被選中入袋，且5号球要以非常倒黴的情況<code>1/10</code>機率被選中要替換，那麼，11号球到來，5号球被替換的機率為：

那麼5号球活下來的機率就是

12号球到來的時候，5号球活下來的機率同理，可以計算出為<code>11/12</code>

13号球到來的時候，5号球活下來的機率同理，可以計算出為<code>12/13</code>

....

927号球到來的時候，5号球活來的機率同理：可以計算出為<code>926/927</code>

是以，5号球活下來的機率為：

同理，1 ～ 10 号球任意一号都可以按照5号球的計算方式計算，機率均為：<code>10/927</code>

A情況是等機率的

再看B情況，我們可以假設一個大于10但是小于927的球，比如，15号球，考慮入袋機率

15号球要在927号球到來的時候，還在袋子中，則需要保證：

15号球在當時被吐出的時候，以<code>10/15</code>機率被選中，且在

16号球到來的時候，15号球活下來，機率根據A的計算邏輯，為<code>15/16</code>

17号球到來的時候，15号球活下來, 同理，為<code>16/17</code>

926号球到來的時候，15号球活下來，機率為<code>925/926</code>

927号球到來的時候，15号球活下來，機率為<code>926/927</code>

是以，927号球到來的時候，15号球活下來的機率是：

同理，任意大于10小于927号球的機率都可以根據15号球的計算邏輯推算出來，均為<code>10/927</code>

A情況和B情況機率都是<code>10/927</code>

是以規則滿足了題目的要求。

算法和資料結構筆記

算法和資料結構體系班-左程雲