Re: A question on Shannon entropy

From: M. Boreale (
Date: 07/06/04

Date: 6 Jul 2004 04:19:51 -0700 (David Wagner) wrote in message news:<cccahn$4ss$>...
> 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).
> 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.

Many thanks for these references.

 - Michele