In probability theory or information theory, the min-entropy of a discrete random event x with possible states (or outcomes) 1... n and corresponding probabilities p₁... p_n is

$H\_infty(X)\; =\; min\_\{i=1\}^n\; (-log\; p\_i)\; =\; -(max\_i\; log\; p\_i)\; =\; -log\; max\_i\; p\_i$

The base of the logarithm is just a scaling constant; for a result in bits, use a base-2 logarithm. Thus, a distribution has a min-entropy of at least b bits if no possible state has a probability greater than 2^-b.

The min-entropy is always less than or equal to the Shannon entropy; it is equal when all the probabilities p_i are equal. min-entropy is important in the theory of randomness extractors.

The notation $H\_infty(X)$ derives from a parameterized family of Shannon-like entropy measures, Rényi entropy,

$H\_k(X)\; =\; -log\; sqrt[k-1]\{begin\{matrix\}sum\_i\; (p\_i)^kend\{matrix\}\}$

k=1 is Shannon entropy. As k is increased, more weight is given to the larger probabilities, and in the limit as k→∞, only the largest p_i has any effect on the result.

See also

• Rényi entropy
• Leftover hash-lemma, Extractor

References