Min-entropy

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.

See also

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

References

This probability-related article is a stub. You can help Wikipedia by expanding it.v · Categories: Entropy and information Information theory Probability stubs Wikimedia Foundation. 2010. Игры ⚽ Поможем написать курсовую Karasumi Tomar Look at other dictionaries: Entropy (film) — Infobox Film name = Entropy imdb id = 0156515 producer = Ashok Amritraj director = Phil Joanou writer = Phil Joanou starring = Stephen Dorff Judith Godrèche Kelly Macdonald Lauren Holly Jon Tenney Frank Vincent Paul Guilfoyle Hector Elizondo Bray …   Wikipedia Rényi entropy — In information theory, the Rényi entropy, a generalisation of Shannon entropy, is one of a family of functionals for quantifying the diversity, uncertainty or randomness of a system. It is named after Alfréd Rényi. The Rényi entropy of order α,… …   Wikipedia Leftover hash-lemma — Imagine that you have a secret key X that has n uniform random bits, and you would like to use this secret key to encrypt a message. Unfortunately, you were a bit careless with the key, and know that an adversary was able to learn about t < n… …   Wikipedia Information theory — Not to be confused with Information science. Information theory is a branch of applied mathematics and electrical engineering involving the quantification of information. Information theory was developed by Claude E. Shannon to find fundamental… …   Wikipedia List of mathematics articles (M) — NOTOC M M estimator M group M matrix M separation M set M. C. Escher s legacy M. Riesz extension theorem M/M/1 model Maass wave form Mac Lane s planarity criterion Macaulay brackets Macbeath surface MacCormack method Macdonald polynomial Machin… …   Wikipedia Extractor — This article is about the extractor in mathematics, for other usage of this word see: extractor (firearms). An (N,M,D,K,epsilon) extractor is a bipartite graph with N nodes on the left and M nodes on the right such that each node on the left has… …   Wikipedia Conversion of units — is the conversion between different units of measurement for the same quantity, typically through multiplicative conversion factors. Contents 1 Techniques 1.1 Process 1.2 Multiplication factors …   Wikipedia Principle of minimum energy — The principle of minimum energy is essentially a restatement of the second law of thermodynamics. It states that for a closed system, with constant external parameters and entropy, the internal energy will decrease and approach a minimum value at …   Wikipedia Exponential distribution — Not to be confused with the exponential families of probability distributions. Exponential Probability density function Cumulative distribution function para …   Wikipedia Mutual information — Individual (H(X),H(Y)), joint (H(X,Y)), and conditional entropies for a pair of correlated subsystems X,Y with mutual information I(X; Y). In probability theory and information theory, the mutual information (sometimes known by the archaic term… …   Wikipedia 18+ © Academic, 2000-2024 Contact us: Technical Support, Advertising Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx. Mark and share Search through all dictionaries Translate… Search Internet Share the article and excerpts Direct link … Do a right-click on the link above and select “Copy Link”