有n种事件 发生概率都为1/n 问 平均需要多少次 才能使得每种事件都至少发生m次？

jjkkt

有n种事件 发生概率都为1/n 问 平均需要多少次 才能使得每种事件都至少发生m次？

kastin

题目叙述不清，n种事件独立否？如果不独立，那么给出相应的关系。“平均需要多少次”——是n件事的试验次数之和，还是什么？

jjkkt

kastin 发表于 2016-11-4 10:58
题目叙述不清，n种事件独立否？如果不独立，那么给出相应的关系。“平均需要多少次”——是n件事的试验次数 ...

从1到n n个正整数中 每次等概率随机取一个
问 要使得每个数字都被取出过至少m次 需要的次数的期望

kastin

先明确一点，抽取到某个数字的随机事件服从几何分布，而几何分布的期望是概率的倒数。

假设已经抽了1次，一定能保证某个数字（标记为 `a_1`）被取到。
那么再抽多少次就能保证第二个数字 `a_2` 至少取到一次呢？显然，剩下的某个数字被取到的概率为 `\frac{n-1}{n}`，那么平均还需要 `\frac{n}{n-1}` 次就能取到剩余的某个数字，标记为 `a_2`.
类似地，除去 `a_1,a_2` 两个数字之外某个数字被取到的概率为 `\frac{n-2}{n}`，故平均还需要 `\frac{n}{n-2}` 次.
……
于是要保证所有数字至少出现1次的期望即为上述期望次数之和$$1+\frac{n}{n-1}+\frac{n}{n-2}+\cdots+\frac{n}{1}=nH_n$$其中 `H_n` 为调和数。

如果把上述过程称之为“一轮”，那么进行 `m` 轮之后，就能保证每个数字至少被取出过 `m` 次。这是因为，每一轮都是独立的（期望可相加）。于是可知楼主的答案应该是`mnH_n`，量级为 `O(mn\ln n)`.

如果上述问题进行推广，改成每次抽取 `k` 个不同的数字，问使得每个数字至少被取出过 `m` 次所需次数的期望。这个问题就更有趣了。

kastin

同样的方法，对于推广后的问题结果是$$\frac{1}{k}\left[\left(\frac{n}{n}+\frac{n-1}{n-1}+\cdots+\frac{n-k+1}{n-k+1}\right)+\left(\frac{n}{n-k}+\frac{n-1}{n-k-1}+\cdots+\frac{n-k+1}{n-2k+1}\right)+\left(\frac{n}{n-2k}+\frac{n-1}{n-2k-1}+\cdots+\frac{n-k+1}{n-3k+1}\right)+\cdots\right]m$$

hujunhua

俺还是没懂楼主的问题。取若干次时某个数字被取到的期望为 1 次，并不意味它就至少能取到 1 次呀。
期望不是现实，用至少合适吗？就算期望有10000次，也不能保证至少能实现一次。

BeerRabbit

与《互斥单掉落收集》相关的两个计算问题.zip (5.39 KB, 下载次数: 0)

2016-11-8 16:05 上传

点击文件名下载附件

jjkkt

kastin 发表于 2016-11-5 13:25
先明确一点，抽取到某个数字的随机事件服从几何分布，而几何分布的期望是概率的倒数。

假设已经抽了1次 ...

何来每轮这个说法？
前5次为11111和12345 对面后面的算法的概率分布明显不同