S*********g
发帖数: 5298 | 1 x_i=(1/2)^d_i
\sum{x_i}=1
I=d1*(1/2)^d1+d2*(1/2)^d2+...+dn*(1/2)^dn
=-\sum{x_i log(x_i)} (Log is based on 2)
0= | H****h
发帖数: 1037 | 2 f is concave if f(r*x+(1-r)*y)>=r*f(x)
+(1-r)*f(y) for 0
f"<=0, then f is concave. If f is concave,
by induction, (f(x1)+f(x2)+...+f(xn))/n
<=f((x1+x2+...+xn)/n). So I/n<=f(1/n)
=-log(1/n)/n=log(n)/n, and I<=log(n). | S*********g
发帖数: 5298 | 3 This is strict.
Actually, it is a theorem in information theorem.
I is just the entropy of the {1,2,3,4,...,n}.
It is -E(log x) if you explain x_i as possibility of i.
Use the Jenson's inequality, E(f(x))>=f(Ex) if f is convex.
You will get that the entropy reaches the maximum when {i} is
uniformaly distributed, say x_i=1/n.
The maximun value is log(n)
Notice -Log is convex.
Then,
E log(1/[nx]) <= log(E(1/[nx]))<= log(1)=0
-E(log(x))<=E(log(n))=log(n). |
|
