Min-entropy

Top

Home > Library > Miscellaneous > Wikipedia

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 extractor.

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)^k\end{matrix}}$

k=1 is the 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.

References

This article does not cite any references or sources. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. (July 2008)

This probability-related article is a stub. You can help Wikipedia by expanding it.

This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)

Donate to Wikimedia

Help us answer these

How did min min lights get its name?

What are min min lights?

What is 1hrs 45 mins in mins?

What does min do?

Post a question - any question - to the WikiAnswers community:

Copyrights:

Cite

Wikipedia on Answers.com This article is licensed under the Creative Commons Attribution/Share-Alike License. It uses material from the Wikipedia article Min-entropy. Read