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 |
|
