c******a
发帖数: 6 | 1 Let S=\sum_{i=1}^n S_i be a sum of n independent random variables each
attaining values +1 and -1 with equal probability. Let P(n, d)=Pr[S>d].
Prove that for d<=n/C,
P(n,d)>=(1/C) * exp(-d^2/Cn)
where C is a suitable constant. |
v********e
发帖数: 1058 | 2 chernoff bound
【在 c******a 的大作中提到】
: Let S=\sum_{i=1}^n S_i be a sum of n independent random variables each
: attaining values +1 and -1 with equal probability. Let P(n, d)=Pr[S>d].
: Prove that for d<=n/C,
: P(n,d)>=(1/C) * exp(-d^2/Cn)
: where C is a suitable constant.
|
c******a
发帖数: 6 | 3 chernoff bound是<=
这个问题就是为了show chernoff bound是tight的啊。
【在 v********e 的大作中提到】
: chernoff bound
|
v********e
发帖数: 1058 | 4 不好意思，看错了。
那看不懂这题了……取n=2, C = 2, d = n/C = 1, 则P(S > d) = 1/4, 而(1/C) * exp
(-d^2/Cn) = 1/2 * e^(-1/4) > 1/4.
试了几个别的数，原题都不成立。我大概没看懂题……
【在 c******a 的大作中提到】
: chernoff bound是<=
: 这个问题就是为了show chernoff bound是tight的啊。
|
d*********a
发帖数: 255 | 5 楼主说的是存在一个常数C，不是说对所有的常数，你这样试常数没有意义
exp
【在 v********e 的大作中提到】
: 不好意思，看错了。
: 那看不懂这题了……取n=2, C = 2, d = n/C = 1, 则P(S > d) = 1/4, 而(1/C) * exp
: (-d^2/Cn) = 1/2 * e^(-1/4) > 1/4.
: 试了几个别的数，原题都不成立。我大概没看懂题……
|
v********e
发帖数: 1058 | 6 原题说的是合适的常数，不是“存在一个常数”
C趋于无穷时不等式右面趋于0，左面趋于接近1/2的数，随便取个充分大的C就成立了。
有这么trivial么
【在 d*********a 的大作中提到】
: 楼主说的是存在一个常数C，不是说对所有的常数，你这样试常数没有意义
:
: exp
|
d*********a
发帖数: 255 | 7 就是这样的trivial
【在 v********e 的大作中提到】
: 原题说的是合适的常数，不是“存在一个常数”
: C趋于无穷时不等式右面趋于0，左面趋于接近1/2的数，随便取个充分大的C就成立了。
: 有这么trivial么
|
c******a
发帖数: 6 | 8 不trivial啊。
右边趋向于0没错，但是左边趋向于1/2的速度与n有关啊。你要证明这个“充分大”的C
是一个常数，与n无关的啊。
【在 d*********a 的大作中提到】
: 就是这样的trivial
|
d*********a
发帖数: 255 | 9 把n固定
的C
【在 c******a 的大作中提到】
: 不trivial啊。
: 右边趋向于0没错，但是左边趋向于1/2的速度与n有关啊。你要证明这个“充分大”的C
: 是一个常数，与n无关的啊。
|
