Re: A question on Shannon entropy

From: David Wagner (daw_at_taverner.cs.berkeley.edu)
Date: 07/05/04 

Date: Mon, 5 Jul 2004 19:35:19 +0000 (UTC)

M. Boreale wrote:
>Is there any result relating Shannon entropy to collision probability?

Sounds like you want to relate Shannon entropy to Renyi entropy
of order 2.

>I.e., to be more precise, suppose:
>- X is a discrete r.v. with prob. distribution p1,...,pN;
>- IC(X) is the probability of collision for X, Sum_i pi^2 (i.e. the
>probability of getting twice the same outcome in two independent
>experiments);
>- H(X) is Shannon entropy of X, -Sum_i pi*log(pi);

Yup. The Renyi entropy of order 2, usually written H_2(X),
is - lg IC(X).
http://www.cs.berkeley.edu/~daw/my-posts/entropy-measures

Cachin's thesis includes a proof that H(X) >= H_2(X). When X
is close to the uniform distribution on N items, then both are
close to lg N. See the above URL for a pointer.