n个数字 平均随机抽取多少次能使得每个数字都出现过m次以上？包括m次
n个数字 平均随机抽取多少次能使得每个数字都出现过m次以上？包括m次 这问题我曾经考虑过，有一些初步的结论，但我现在无法添加附件（可能是我IE的问题） 当$m=1$时，次数为$n\cdot H_n$。其中$H_n=\sum_{i=1}^n 1/i$。
$m>1$比较难解。不知道是否有现成的结论。 本帖最后由 BeerRabbit 于 2014-12-9 17:59 编辑
压缩包里的PDF是问题解决方法的分析过程，其实思路很简单，归根结底就是递归，主要还是算法的设计优化。
其中的Collect.m文件是文档内收录的那个。对这个函数我用VB做过一个小小的计算工具。例如这个例子：
MultiCollect.m是后来对一个更复杂一点的模型的实现，这个模型的表述是这样的：
“进入一个房间后，同时开启房间内的N个盒子，每个盒子都独立进行原来简化模型的掉落判定，求各个箱子的各个掉落物品达到一定数目时，进入房间的次数期望。”
不错。
将该算法应用到楼主的问题，
时间复杂度为$O((n+m)^m/((m-1)!))$，
空间复杂度为$O((n+m)^m/(m!))$。
$m$小的时候还能接受，
$m$大了就不行了。
不知道是否有复杂度更低的算法。
页:
[1]