再问一道Amazon的面经题。。。

给你一个integer的stream,在stream结束的时候随机等概率返回其中一个元素。
这个是我在面经里摘下来的，信息就这么多啦，
为什么这么多非主流的题。。。

这是online sampling的特殊情形。
当面对stream中第 i 个item时，以 1/i 的概率把当前选择的元素替换成item i。
概率分析: item i 被选到当且仅当 item i 在 step i 的时候被选中，并且再也没有被替换掉。item i 在 step i 被选中的概率是 1/i；之后每一步（step j）没有被替换的概率是 1-1/j， i+1<= j <=n，n 是 stream 中 item 的个数。所以同时满足的概率是
1/i * [1 - 1/(i+1)] * [1 - 1/(i+2)] * ... * [1 - 1/n] = 1/i * i/(i+1) * (i+1)/(i+2) * ... * (n-1)/n = 1/n.

这个问题可以扩展到更一般的权重: item i 的权重是 w_i。
令 w = \sum_{i=1}^n w_i 代表所有权重的和。那么以概率 w_i/w 的概率选到 item i 的方法也类似：
当面对stream中第 i 个item时，以 w_i/s_i 的概率把当前选择的元素替换成item i，这里 s_i = \sum_{k=1}^i w_k 是前 i 个 item 的权重的和。
概率分析: item i 被选到当且仅当 item i 在 step i 的时候被选中，并且再也没有被替换掉。item i 在 step i 被选中的概率是 w_i/s_i；之后每一步（step j）没有被替换的概率是 1-w_j/s_j， i+1<= j <=n，n 是 stream 中 item 的个数。所以同时满足的概率是
w_i/s_i * [1 - w_{i+1}/s_{i+1}] * [1 - w_{i+2}/s_{i+2}] * ... * [1 - w_n/s_n] = w_i/s_i * s_i/s_{i+1} * s_{i+1}/s_{i+2} * ... * s_{n-1}/s_n = w_i/s_n = w_i/w。
这里 s_{j+1} = s_j + w_{j+1}，以及 s_n = w。

蓄水池抽样，挺经典的 lz搜一下就ok了

wmtws9dsj 发表于 2015-3-12 10:55
蓄水池抽样，挺经典的 lz搜一下就ok了

好的好的，谢谢啦，关键字就是蓄水池抽样？