c***a
发帖数: 655 | 1 假设有n个人，编号1-n,独立随机的分成k组。（也就是说，每个人自己扔一个k
面的硬币，是哪面就是哪组。）问人数最多的组的人数的期望是多少。 |
D*******a
发帖数: 3688 | 2 k＝n？
【在 c***a 的大作中提到】
: 假设有n个人，编号1-n,独立随机的分成k组。（也就是说，每个人自己扔一个k
: 面的硬币，是哪面就是哪组。）问人数最多的组的人数的期望是多少。
|
c***a
发帖数: 655 | 3 no la.. k
【在 D*******a 的大作中提到】
: k＝n？
|
y***u
发帖数: 101 | 4 好像是 O(n/k * log k)，应该也是tight的，但不太确定。
【在 c***a 的大作中提到】
: 假设有n个人，编号1-n,独立随机的分成k组。（也就是说，每个人自己扔一个k
: 面的硬币，是哪面就是哪组。）问人数最多的组的人数的期望是多少。
|
c***a
发帖数: 655 | 5 能给个reference么？
【在 y***u 的大作中提到】
: 好像是 O(n/k * log k)，应该也是tight的，但不太确定。
|
y***u
发帖数: 101 | 6 从epsilon-net的结果可以导出。不过应该有更直接的方法，好像
Motwani的Randomized Algorithms里面有提到。
另外这些都是high probability results，不过我想跟期望应该差不多。
【在 c***a 的大作中提到】
: 能给个reference么？
|
m****h
发帖数: 261 | 7
There is a way that can find the probability density function. But it is not
in a closed form.
【在 c***a 的大作中提到】
: 假设有n个人，编号1-n,独立随机的分成k组。（也就是说，每个人自己扔一个k
: 面的硬币，是哪面就是哪组。）问人数最多的组的人数的期望是多少。
|
D*******a
发帖数: 3688 | 8 那还不如simulation呢
【在 m****h 的大作中提到】
:
: There is a way that can find the probability density function. But it is not
: in a closed form.
|
|
y***u
发帖数: 101 | 9
刚刚翻了一下这本书,在Section 3.1提到了一些
我上面说的结果不够tight,实际上,对于
k = \Omega(n), E[Max] = O(log n / loglog n)
otherwise E[Max] = O(n/k)
也就是说除非k跟n差不多,否则最多的bin跟别的bin也差不多.
【在 y***u 的大作中提到】
: 从epsilon-net的结果可以导出。不过应该有更直接的方法，好像
: Motwani的Randomized Algorithms里面有提到。
: 另外这些都是high probability results，不过我想跟期望应该差不多。
|
c***a
发帖数: 655 | 10 多谢各位讨论。我想先用simulation看看结果如何.大家看看这样simulate
是不是等价的：
在0~n-1中随机生成k个数：f_1, f_2, ..., f_k (可重复).不失一般性，把
他们按升序排序，然后结果就是
max(f_2-f_1, f_3-f_2, ..., f_k-f_{k-1},f_1+n-f_k)
【在 y***u 的大作中提到】
:
: 刚刚翻了一下这本书,在Section 3.1提到了一些
: 我上面说的结果不够tight,实际上,对于
: k = \Omega(n), E[Max] = O(log n / loglog n)
: otherwise E[Max] = O(n/k)
: 也就是说除非k跟n差不多,否则最多的bin跟别的bin也差不多.
|
|
|
y***u
发帖数: 101 | 11 是
【在 c***a 的大作中提到】
: 多谢各位讨论。我想先用simulation看看结果如何.大家看看这样simulate
: 是不是等价的：
: 在0~n-1中随机生成k个数：f_1, f_2, ..., f_k (可重复).不失一般性，把
: 他们按升序排序，然后结果就是
: max(f_2-f_1, f_3-f_2, ..., f_k-f_{k-1},f_1+n-f_k)
|
g*****y
发帖数: 1120 | 12 难道不能简单想成：
1*(1/k*(1-1/k)^n-1)+2(1/k^2+(1-1/k)^n-2)+...+n(1/k^n) |
s*****e
发帖数: 21415 | 13 simulate一下先。
【在 c***a 的大作中提到】
: 假设有n个人，编号1-n,独立随机的分成k组。（也就是说，每个人自己扔一个k
: 面的硬币，是哪面就是哪组。）问人数最多的组的人数的期望是多少。
|
x*****o
发帖数: 28 | 14 没那么简单吧.必须保证i是最大值,其他(n-i)无法构成一个比i大的数.
【在 g*****y 的大作中提到】
: 难道不能简单想成：
: 1*(1/k*(1-1/k)^n-1)+2(1/k^2+(1-1/k)^n-2)+...+n(1/k^n)
|
s*m
发帖数: 34 | 15 我怎么觉得是n/k+\theta(\sqrt{n})
【在 y***u 的大作中提到】
: 好像是 O(n/k * log k)，应该也是tight的，但不太确定。
|
y***u
发帖数: 101 | 16
当k=\Omega(n)的时候显然不是啊. 不过下面这个结果也不够tight,我后来更正了.
【在 s*m 的大作中提到】
: 我怎么觉得是n/k+\theta(\sqrt{n})
|
s*m
发帖数: 34 | 17 我默认k很小, :)
【在 y***u 的大作中提到】
:
: 当k=\Omega(n)的时候显然不是啊. 不过下面这个结果也不够tight,我后来更正了.
|
