= Min-entropy
{title2=$H_\infty(X)$}
{wiki}
For a <discrete random variable> $X$ with a finite or countable <alphabet> and <probability mass function> $p_x=\mathbb P(X=x)$, define $p_{\max}=\max_xp_x$. Its <min-entropy>, using base-two <logarithms>, is
$$
H_\infty(X)=-\log_2p_{\max}
=\min_{x:p_x>0}(-\log_2p_x).
$$
The unit is the <bit>. This is the smallest <information content> of any possible outcome: it records the easiest outcome to predict, whereas <Shannon entropy> averages <information content> over all outcomes. A normalized countable <probability mass function> has an attained positive maximum, so $H_\infty(X)$ is finite even when <Shannon entropy> is infinite. Outcomes of zero <probability> cannot minimize the surprise and are omitted from the minimum; including extra impossible symbols changes neither quantity.https://www.cs.cornell.edu/courses/cs6830/2009fa/lecnotes.pdf[Pass and shelat, A Course in Cryptography, Section 8.3.2, Definition 148.1]{ref}
Suppose someone knows the <probability mass function> but receives no observation correlated with $X$, and must name exactly one outcome. Naming $x$ succeeds with <probability> $p_x$, so naming a most likely outcome is optimal:
$$
p_{\mathrm{guess}}(X)=\max_x\mathbb P(X=x)=2^{-H_\infty(X)}.
$$
Tied maxima give equally good guesses. Randomizing independently among guesses cannot improve success: if the guess has <probability mass function> $q_x$, its success <probability> is $\sum_xq_xp_x\leq p_{\max}\sum_xq_x=p_{\max}$. This is the simplest instance of <maximum a posteriori decoding>. The identity gives <min-entropy> an operational meaning: $H_\infty(X)\geq k$ <bits> means every single guess succeeds with <probability> at most $2^{-k}$, under these information assumptions.https://arxiv.org/html/0807.1338[König, Renner and Schaffner, The operational meaning of min- and max-entropy, Section I.3.1, equation (18) and the no-side-information case]{ref}
For an exact analytical example on symbols $A,B,C,D,E$, compare the two <probability mass functions>
$$
u=(1/4,1/4,1/4,1/4,0),\qquad b=(1/2,1/8,1/8,1/8,1/8).
$$
Under $u$, each possible outcome has <information content> $2$ <bits>; under $b$, $A$ has <information content> $1$ <bit> and each other outcome has $3$ <bits>. Consequently their <Shannon entropies> agree exactly,
$$
H(u)=4\frac14\cdot2=2,\qquad H(b)=\frac12\cdot1+4\frac18\cdot3=2,
$$
but $H_\infty(u)=2$ and $H_\infty(b)=1$ <bits>. A best single guess therefore succeeds with <probability> $1/4$ under $u$ and $1/2$ under $b$. The same average surprise can hide a factor of two in immediate predictability. The zero entry in $u$ contributes zero to <Shannon entropy>, using $0\log_2 0=0$.
\Image[/min-entropy-guessing-equal-average.png]
{title=Two exact probability models have the same average surprise but different best single guesses}
For the <discrete uniform distribution> on $m$ possible outcomes, $H_\infty=\log_2m$ <bits> and the best single guess succeeds with <probability> $1/m$. A certain outcome has $H_\infty=0$ and success <probability> one. Thus <min-entropy> is useful when a common outcome could defeat an attempt to make outputs unpredictable, even if rare alternatives raise <Shannon entropy>.
For <cryptography>, this unconditional calculation alone does not certify security: an observer might know $X$ already. If a report $Y=X$ reveals a uniform four-outcome source, its unconditional <min-entropy> remains $2$ <bits> but guessing after the report succeeds with <probability> one. For finite classical reports, the appropriate success calculation uses <conditional probabilities> and <maximum a posteriori decoding>:
$$
p_{\mathrm{guess}}(X\mid Y)=\sum_{y:p_Y(y)>0}p_Y(y)\max_x\mathbb P(X=x\mid Y=y).
$$
The <conditional entropy> $H(X\mid Y)$ instead averages remaining surprise. A security argument must specify the observer's information and the protocol's required guarantee; neither unconditional <min-entropy> nor <Shannon entropy> supplies those assumptions.
Back to article page
