o*******w
发帖数: 349 | 1 直觉上很显然，怎么证明呢?
n
SUM i*Pr(i) is bounded by O(n^a) where a < 1
i
Pr(0), Pr(1), Pr(2), ... 是一个概率密度
大致有∶
因为 Pr(i) can be bounded by O(1/i^c) where c > 1 否则 SUM Pr(i) > 1（怎么证?）; e.g.
n
SUM 1/i = O(ln n)
1
只需考虑 SUM 1/i^(c-1) c<2 的情况, i.e. 1< c <2。则
n
SUM i*Pr(i) < SUM i*(1/i^c)
1
= SUM 1/i^(c-1) = O(n/n^(c-1))
= O(n^(2-c)) = O(n^a) where a = 2-c < 1 | B****n
发帖数: 11290 | 2 This seems wrong. Consider the Pr(i)=c/(i*log(i)^2) i>=2, where c is a
constant which makes Pr(i) become a probability distribution.
Then the sum can not be bounded by O(n^a), where a<1
证?）; e.g.
【在 o*******w 的大作中提到】
: 直觉上很显然，怎么证明呢?
: n
: SUM i*Pr(i) is bounded by O(n^a) where a < 1
: i
: Pr(0), Pr(1), Pr(2), ... 是一个概率密度
: 大致有∶
: 因为 Pr(i) can be bounded by O(1/i^c) where c > 1 否则 SUM Pr(i) > 1（怎么证?）; e.g.
: n
: SUM 1/i = O(ln n)
: 1
| o*******w
发帖数: 349 | 3 感谢指教！
看来我只能得到
SUM i*Pr(i) = o(n) 了？
可能连这个结果都不一定 | Q***5
发帖数: 994 | 4 This can be proved:
For any epsilon >0, there exists K, such that \sum_K^\infty i*P(i)<\epsilon
Let N big enough, such that K/N<\epsilon.
Now, for any n>N,
\sum_1^n i*P(i)/n <= (\sum_1^(K-1) K*P(i)+ n*\sum_K^n P(i))/n
epsilon< 2*\epsilon
【在 o*******w 的大作中提到】
: 感谢指教！
: 看来我只能得到
: SUM i*Pr(i) = o(n) 了？
: 可能连这个结果都不一定
| o*******w
发帖数: 349 | |
|
