m********0 发帖数: 2717 | 1 N balls into N boxes randomly
Expectation of number of balls in the box that has most number of balls. | J*****n 发帖数: 4859 | 2
不会做,但顶一下。
你从哪里搞来这个题目的,面试题?
【在 m********0 的大作中提到】 : N balls into N boxes randomly : Expectation of number of balls in the box that has most number of balls.
| a****9 发帖数: 418 | 3 (1+o(1))log n/loglog n with high probability
google "the power of two random choices"
【在 m********0 的大作中提到】 : N balls into N boxes randomly : Expectation of number of balls in the box that has most number of balls.
| J*****n 发帖数: 4859 | 4
.......
Gamma函数都出来了阿。
【在 a****9 的大作中提到】 : (1+o(1))log n/loglog n with high probability : google "the power of two random choices"
| m********0 发帖数: 2717 | 5 So no close form? only extreme?
【在 a****9 的大作中提到】 : (1+o(1))log n/loglog n with high probability : google "the power of two random choices"
| p*****k 发帖数: 318 | 6 this reminds me a problem discussed earlier:
http://www.mitbbs.com/article_t/Quant/31214529.html
follow the c.d.f. approach by chopinor, we want P(max<=i), i.e., at most i balls can be put in each box (with 1<=i<=N). to get the probability, consider the generating function:
N!/N^N*(1+x/1!+x^2/2!...+x^i/i!)^N,
(which is the partial sum of the exponential series)
we want the coefficient of term x^N from the expansion.
so the expectation can be written as (by taking the nth derivatives then settin | m********0 发帖数: 2717 | 7 The answer is simply wrong。
For[n = 1, n < 5, n++,
Print[n + 1 -
Sum[(-1)^j*Binomial[n, j]*Binomial[2 n - 1 - (i + 1)*j, n - 1], {i,
1, n}, {j, 0, n}]]]
I got
2,3,4,5
其实很容易知道你是错的,你的表达式只能是整数,明显期望值是分数,整数的情况只
有1估计。
balls can be put in each box (with 1<=i<=N). to get the # of ways for that
, consider the generating function: (1+x^1+...+x^i)^N, we want the
coefficient of term x^N.
N-1].
【在 p*****k 的大作中提到】 : this reminds me a problem discussed earlier: : http://www.mitbbs.com/article_t/Quant/31214529.html : follow the c.d.f. approach by chopinor, we want P(max<=i), i.e., at most i balls can be put in each box (with 1<=i<=N). to get the probability, consider the generating function: : N!/N^N*(1+x/1!+x^2/2!...+x^i/i!)^N, : (which is the partial sum of the exponential series) : we want the coefficient of term x^N from the expansion. : so the expectation can be written as (by taking the nth derivatives then settin
| u********e 发帖数: 263 | 8 这题也太可怕了。哪儿问的题啊?
【在 J*****n 的大作中提到】 : : ....... : Gamma函数都出来了阿。
| m********0 发帖数: 2717 | 9 恩,当时我拍拍大腿说好简单,induction。
后来试了好几种induction,发现都很可怕。
突然觉得太可怕了,就发过来了。。。
【在 u********e 的大作中提到】 : 这题也太可怕了。哪儿问的题啊?
| m********0 发帖数: 2717 | 10 能具体点吗? total number of ways to get what?
what is tatal(n) ?
you
【在 p*****k 的大作中提到】 : this reminds me a problem discussed earlier: : http://www.mitbbs.com/article_t/Quant/31214529.html : follow the c.d.f. approach by chopinor, we want P(max<=i), i.e., at most i balls can be put in each box (with 1<=i<=N). to get the probability, consider the generating function: : N!/N^N*(1+x/1!+x^2/2!...+x^i/i!)^N, : (which is the partial sum of the exponential series) : we want the coefficient of term x^N from the expansion. : so the expectation can be written as (by taking the nth derivatives then settin
| | | m********0 发帖数: 2717 | 11 我觉得不太像。。。因为2,3,4,5除什么都跟答案不太一样
1, 3/2, 17/9, 17/8,
我就推算了这四个,然后用C++ confirm了一下。
had a typo of the upper limit of j earlier. sorry about that.
【在 p*****k 的大作中提到】 : this reminds me a problem discussed earlier: : http://www.mitbbs.com/article_t/Quant/31214529.html : follow the c.d.f. approach by chopinor, we want P(max<=i), i.e., at most i balls can be put in each box (with 1<=i<=N). to get the probability, consider the generating function: : N!/N^N*(1+x/1!+x^2/2!...+x^i/i!)^N, : (which is the partial sum of the exponential series) : we want the coefficient of term x^N from the expansion. : so the expectation can be written as (by taking the nth derivatives then settin
| u********e 发帖数: 263 | 12 之前有人提到的paper里说答案是 1/Gamma(n) - 3/2 + o(1)
问这题的人难道指望面试的人当场推出来这个答案?
啥职位的面试?
【在 m********0 的大作中提到】 : 恩,当时我拍拍大腿说好简单,induction。 : 后来试了好几种induction,发现都很可怕。 : 突然觉得太可怕了,就发过来了。。。
| m********0 发帖数: 2717 | 13 但是那个paper里面只给了个limit啊。o(1)多没劲
再说1/Gamma(n) - 3/2 不都是负的了?
Gamma(n) 不是(n-1)! 吗?
【在 u********e 的大作中提到】 : 之前有人提到的paper里说答案是 1/Gamma(n) - 3/2 + o(1) : 问这题的人难道指望面试的人当场推出来这个答案? : 啥职位的面试?
| m*******r 发帖数: 98 | 14 I guess the probability of each partition are not identical?
So we can not simply divide by C(2N-1,N-1)?
balls can be put in each box (with 1<=i<=N). to get the # of ways for that
, consider the generating function: (1+x^1+...+x^i)^N, we want the
coefficient of term x^N.
【在 p*****k 的大作中提到】 : this reminds me a problem discussed earlier: : http://www.mitbbs.com/article_t/Quant/31214529.html : follow the c.d.f. approach by chopinor, we want P(max<=i), i.e., at most i balls can be put in each box (with 1<=i<=N). to get the probability, consider the generating function: : N!/N^N*(1+x/1!+x^2/2!...+x^i/i!)^N, : (which is the partial sum of the exponential series) : we want the coefficient of term x^N from the expansion. : so the expectation can be written as (by taking the nth derivatives then settin
| u********e 发帖数: 263 | 15 算是我转述错了。gamma(n)^-1 只说gamma函数的反函数。
【在 m********0 的大作中提到】 : 但是那个paper里面只给了个limit啊。o(1)多没劲 : 再说1/Gamma(n) - 3/2 不都是负的了? : Gamma(n) 不是(n-1)! 吗?
| m********0 发帖数: 2717 | 16 反函数,好奇葩哦。。。
【在 u********e 的大作中提到】 : 算是我转述错了。gamma(n)^-1 只说gamma函数的反函数。
| u********e 发帖数: 263 | 17 这么奇葩你还坚持不透露啥职位啊。。。。或者偷偷发信给我,只是好奇啥地方这么变
态。还是面试官没意识到这到底其
实还挺麻烦的?
【在 m********0 的大作中提到】 : 反函数,好奇葩哦。。。
| p*****k 发帖数: 318 | 18
you are absolutely right! thx.
i have edited the earlier post: a quick fix i can think of is to put in these multi-nomial coefficients. unfortunately it does not yield as nice analytical result any more (well it was ugly before anyway). it does serve a useful purpose as an algorithm to get the exact answer for any N.
【在 m*******r 的大作中提到】 : I guess the probability of each partition are not identical? : So we can not simply divide by C(2N-1,N-1)? : : balls can be put in each box (with 1<=i<=N). to get the # of ways for that : , consider the generating function: (1+x^1+...+x^i)^N, we want the : coefficient of term x^N.
| b***e 发帖数: 1419 | 19 Sum{f(n, n, i) * i}/n^n // i <- [1..n]
where
f(m, n, k) = Sum{C(m, i) * g(i, n, k)} // i <- [1..m]
g(m, n, k) = f(m, n-m, k-1)
Barely better than brute-force, but reduces the complexity to
polynomial (to n).
pcasnik, is your algorithm down to log(n)? | r******r 发帖数: 138 | 20 start from a pattern, move 1 ball each time, then
max number of balls in a box : 1,...,n (n states)
depending on whether n balls and n boxes are exchangeable:
p(k+1,k)= ...
p(k,k)= ...
p(k-1,k)= ...
all other p=0
form transition matrix, take any initial state (e.g. uniform) b/c we know
this is a stationary chain. pi0 * lim(P^n) = stationary distribution, then
calculate expectation.
would this work?
【在 m********0 的大作中提到】 : N balls into N boxes randomly : Expectation of number of balls in the box that has most number of balls.
| p*****k 发帖数: 318 | 21
so what are the initial conditions here for f?
for my approach, i think for any particular i, it's O(i*N) to get the c.d.f.
【在 b***e 的大作中提到】 : Sum{f(n, n, i) * i}/n^n // i <- [1..n] : where : f(m, n, k) = Sum{C(m, i) * g(i, n, k)} // i <- [1..m] : g(m, n, k) = f(m, n-m, k-1) : Barely better than brute-force, but reduces the complexity to : polynomial (to n). : pcasnik, is your algorithm down to log(n)?
| b***e 发帖数: 1419 | 22 f(m, n, k) means to place n ball into m boxes where the largest volume is
exactly k.
g(m, n, k) means to place n ball into m boxes where the largest volume is
exactly k, and there's no empty boxes.
So for g:
g(m, n, k) = 0 if n<0 or k<0
g(m, 0, 0) = 1 |
|