一些关于概率的题目

---------------------------------------------------------------------------

以等概率从一个序列中选取一个元素

这个问题可能有如下几种提法：
1) 在链表中等概率选取一个元素。
2) 从一个不知道大小的数据流中以等概率选取一个元素。
3) 无限长序列随机采样。
4) ...

解法：
示例代码如下：

nmatch = 0;
for (p = list; p != NULL; p = p->next)
{
if (rand() % ++nmatch == 0)
{
selected = p;
}
}

return selected;

证明：
对第 k 个节点（从 k=1 开始计数，最大为链表长度 n)
它被选中的情况是 selected = p; 被执行，并且后面的所有节点都不执行这一句
因此其概率为
1 1 1 1 1
- * (1- ---) * (1- ---) * ... * (1- -) = -
k k+1 k+2 n n

---------------------------------------------------------------------------