有谁听说过"Proof. Markov"这个数学定理吗?
在 < <introduction to Agorithms> > 关于hash的部分,最后的universial hash 的证明部分用到了 "Proof. Markov’s inequality "
says that for any nonnegative random variable X, we have Pr{X ≥ t} ≤ E[X]/t.Applying this inequality with t = 1, we findthat the probability of 1 or more collisions isat most 1/2.
我想它的意思是这样一个数学定理:对于任意的非负数X 都有
Pr{X ≥ t} ≤ E[X]/t,这里Pr是probillity的意思,也就是概率的意思.我没有找到关于t的定义.有谁见过这个定理,可以证明一下吗?
[解决办法]
设X的概率密度函数为f(x),那么E{x}=I[0~+inf,xf(x)dx] (这里用I表示积分号,积分限为从0到+inf就是正无穷大,积分项为xf(x)dx, 因为X非负所以积分限小于零的部分为0); Pr(X> =t)=I[t~+inf,f(x)dx],则:
左式 <=右式 <=== I[t~+inf,f(x)dx] <=I[0~+inf,xf(x)dx]/t
<=== t*I[t~+inf,f(x)dx] <=I[0~+inf,xf(x)dx];
<=== t*(1-I[0~t, f(x)dx]) <=I[0~+inf,xf(x)dx];
<=== t <=t*(I[0~t, f(x)dx]+ I[0~+inf, xf(x)dx/t]);
因为上面不等式右边第二个积分I[0~+inf, xf(x)dx/t]> =I[t~+inf, xf(x)dx/t]> =I[t~+inf, f(x)dx],所以右边括号内这两个积分之和大于等于I[0~+inf, f(x)dx]=1, 所以上面的不等式得证,由此可倒推回定理结论.
[解决办法]
如果楼主学过概率的话，相信楼主听说过切比雪夫（chebyshey)不等式吧？
这个定理是切比雪夫不等式的推广，叫马尔科夫（markov)不等式。其证明方法与chebyshev不等式类似。只需要令chebyshev不等式中的数学期望为0，并且不等放缩时不用平方，而直接采用绝对值放缩，很容易得到。表达式中的E[X］是随机变量X的数学期望，t只是一个任意正实数。
