h*********y
发帖数: 49 | 1 Randomly 产生 N(比如N=10000)个小于M(比如M=100)的正数
问，平均其中有多少个不相同的数 |
l*****a
发帖数: 14598 | 2 can u guarantee that NP<1? |
r****o
发帖数: 1950 | 3 我改了一下。
每个数出现的概率是p=1-[(M-1)/M]^N
所以出现k个数的概率是C(M,k)p^k(1-p)^(M-k).
k的期望是 SUM_(k=1..M) k* C(M,k)p^k(1-p)^(M-k).
【在 l*****a 的大作中提到】
: can u guarantee that NP<1?
|
l******x
发帖数: 163 | 4 这个就是coupon collector's problem的变种吧
【在 h*********y 的大作中提到】
: Randomly 产生 N(比如N=10000)个小于M(比如M=100)的正数
: 问，平均其中有多少个不相同的数
|
r****o
发帖数: 1950 | 5 能不能看看我的解法对不对。
【在 l******x 的大作中提到】
: 这个就是coupon collector's problem的变种吧
|
l******x
发帖数: 163 | 6 不好意思不是很明白你的方法。。。
按照coupon collector的解法
设n_i = 从有i-1个不同的数到i个不同的数需要的投掷数
则E[n_i] = M/(M-i+1)
对这个题看看N等于多少个E[n_i]相加吧？
如果N >= M*lnM则平均上来讲M个数全出现了
不知道这样对不对
【在 r****o 的大作中提到】
: 能不能看看我的解法对不对。
|
b******v
发帖数: 1493 | 7 M*[1-(1-1/M)^N]
【在 h*********y 的大作中提到】
: Randomly 产生 N(比如N=10000)个小于M(比如M=100)的正数
: 问，平均其中有多少个不相同的数
|
B*****t
发帖数: 335 | 8 人家题目要求产生“小于”M的正数
【在 b******v 的大作中提到】
: M*[1-(1-1/M)^N]
|
b******v
发帖数: 1493 | 9 哦，没看清题目，那把M换成M-1就行了
【在 B*****t 的大作中提到】
: 人家题目要求产生“小于”M的正数
|
u**s
发帖数: 50 | 10 抛砖引玉，希望能看到更直接或者简单的做法。
"小于M正数" 是指 [1, M] 正整数还是 [1, M-1] 正整数? 当然，这个不重要，结果类
似。
Assume [1, M] integer.
The problem can be reduced to this:
Throw a ball into M bins with equal prob, repeat N times. What's the
expected number of bins having at least one ball?
Use indicator random variable.
X_i : ith bin is not empty.
X: number of bins are not empty
E(X) = E(\sum X_i) = \sum E(X_i) = \sum P(X_i) = M * (1 - (1 - 1/M)^N)
【在 h*********y 的大作中提到】
: Randomly 产生 N(比如N=10000)个小于M(比如M=100)的正数
: 问，平均其中有多少个不相同的数
|
r****o
发帖数: 1950 | 11 我开始跟你的想法一样，
可是后来想复杂了，不过我现在也不知道我的想法到底对不对。
能不能看看我的解法。
【在 b******v 的大作中提到】
: 哦，没看清题目，那把M换成M-1就行了
|
b******v
发帖数: 1493 | 12 我觉得你前面的解法里好像假设了数字1,...,M 是否出现是独立的
但是这是不对的，
例如M=2，P(1不出现) = P(2不出现) = (1/2)^N
但是P(1不出现，并且 2不出现) = 0 != P(1不出现)*P(2不出现)
我的解法是，定义随机变量
X_i = 1 如果数字i出现，
0 otherwise
则E(X_i) = 1-(1-1/M)^N
则不同的数字共有X= sum_{i=1,...,M} X_i
从而E(X) = sum_{i=1,...,M} E(X_i) = M*[1-(1-1/M)^N]
上式中虽然X_i并不互相独立，但是E是线性的，所以没有关系
【在 r****o 的大作中提到】
: 我开始跟你的想法一样，
: 可是后来想复杂了，不过我现在也不知道我的想法到底对不对。
: 能不能看看我的解法。
|
r****o
发帖数: 1950 | 13 呵呵，多谢指正。
【在 b******v 的大作中提到】
: 我觉得你前面的解法里好像假设了数字1,...,M 是否出现是独立的
: 但是这是不对的，
: 例如M=2，P(1不出现) = P(2不出现) = (1/2)^N
: 但是P(1不出现，并且 2不出现) = 0 != P(1不出现)*P(2不出现)
: 我的解法是，定义随机变量
: X_i = 1 如果数字i出现，
: 0 otherwise
: 则E(X_i) = 1-(1-1/M)^N
: 则不同的数字共有X= sum_{i=1,...,M} X_i
: 从而E(X) = sum_{i=1,...,M} E(X_i) = M*[1-(1-1/M)^N]
|
