Re: A question on Shannon entropy
From: Jean-Luc Cooke (jlcooke_at_engsoc.org)
Date: 07/05/04
- Next message: Peter Fairbrother: "Re: public key crypto"
- Previous message: Jean-Luc Cooke: "Re: Riemann Hypothesis and P vs NP"
- In reply to: M. Boreale: "A question on Shannon entropy"
- Next in thread: David Wagner: "Re: A question on Shannon entropy"
- Reply: David Wagner: "Re: A question on Shannon entropy"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: 5 Jul 2004 14:33:38 GMT
Well,
You could to it the long way:
- alphabet X
- H(X) entropy of alphabet X
- L(X) number of elements in alphabet X
Assume:
- each symbol in X has probability of appearing equal to H(X)
Compute:
- The collision probability for N outcomes.
Birthday example:
P = Prod_{n=1..k} { ((L(X)-n)/L(X)) }
And just plug in what you're missing.
JLC
M. Boreale <boreale@dsi.unifi.it> wrote:
> Hello,
> I'm an outsider (though well informed) of cryptography, so apologies
> in advance if this turn out to be a trivial question.
> Is there any result relating Shannon entropy to collision probability?
> 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);
> My question is if there is any theorem relating IC(X) to H(X).
> The (obviuous) intuition is that the higher IC(X), the lower H(X).
> E.g., for X a constant (IC(X)=1) then H(X)=0, while when X has a
> uniform distribution, IC(X) reaches its minimum (1/N) and H(X) its
> maximum (-log(N)). Does this generalize to arbitrary X, and how?
> I'm asking this because, when the distribution of X is unknown, it is
> apparently simpler to estimate IC(X) (by, say, measuring the fraction
> of collisions over repeated experiments on X) than H(X).
> Many thanks
> - Michele
--
- Next message: Peter Fairbrother: "Re: public key crypto"
- Previous message: Jean-Luc Cooke: "Re: Riemann Hypothesis and P vs NP"
- In reply to: M. Boreale: "A question on Shannon entropy"
- Next in thread: David Wagner: "Re: A question on Shannon entropy"
- Reply: David Wagner: "Re: A question on Shannon entropy"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
