Last modified: 2026-11-12 01:08:55 (PST)
The entropy of a random variable averages its surprisal. Other summaries of its probabilities answer other questions. This page adds the smallest of them, the min-entropy, to the collision entropy.
Definition 1 (Min-entropy) The min-entropy of a discrete random variable \(X\) is the logarithm of the reciprocal of the largest probability that \(X\) takes any one value:
\[{\mathbb{H}_{\infty}\mathopen{}\left(X\right)\mathclose{}} = -\log \max_x {\mathbb{P}\mathopen{}\left(X = x\right)\mathclose{}}.\]
It is the limiting case of the Rényi entropy of order \(\alpha\) (Rényi 1961), which approaches it as \(\alpha \to \infty\).
Example 1 (Min-entropy of a three-valued random variable)
Let \(X\) take three values with probabilities \(1/2\), \(1/4\) and \(1/4\). The R chunk below finds the largest probability and the min-entropy, with base-2 logarithms.
The largest probability is \(0.5\), so the min-entropy is \({\mathbb{H}_{\infty}\mathopen{}\left(X\right)\mathclose{}} = 1\) bit.
Theorem 1 (The min-entropy is at most the collision entropy) Let \(X\) be a discrete random variable. Then the min-entropy is at most the collision entropy:
\[{\mathbb{H}_{\infty}\mathopen{}\left(X\right)\mathclose{}} \le {\mathbb{H}_{2}\mathopen{}\left(X\right)\mathclose{}}.\]
Proof. Let \(p_{\max} = \max_x {\mathbb{P}\mathopen{}\left(X = x\right)\mathclose{}}\). Each probability \({\mathbb{P}\mathopen{}\left(X = x\right)\mathclose{}}\) is at most \(p_{\max}\), so \({\mathbb{P}\mathopen{}\left(X = x\right)\mathclose{}}^2 \le p_{\max} \, {\mathbb{P}\mathopen{}\left(X = x\right)\mathclose{}}\). Sum over the values \(x\):
\[\sum_x {\mathbb{P}\mathopen{}\left(X = x\right)\mathclose{}}^2 \le p_{\max} \sum_x {\mathbb{P}\mathopen{}\left(X = x\right)\mathclose{}}.\]
The probabilities sum to \(1\), so the collision probability is at most \(p_{\max}\):
\[\mathbb{P}(X = X') = \sum_x {\mathbb{P}\mathopen{}\left(X = x\right)\mathclose{}}^2 \le p_{\max}.\]
The function \(-\log\) is decreasing, so taking it of both sides flips the comparison:
\[-\log \mathbb{P}(X = X') \ge -\log p_{\max}.\]
The left side is \({\mathbb{H}_{2}\mathopen{}\left(X\right)\mathclose{}}\) and the right side is \({\mathbb{H}_{\infty}\mathopen{}\left(X\right)\mathclose{}}\).
Example 2 (Three entropies of one random variable)
The R chunk below computes the min-entropy, the collision entropy and the entropy of the random variable of Example 1.
p <- c(1 / 2, 1 / 4, 1 / 4)
min_entropy <- -log2(max(p))
collision_entropy <- -log2(sum(p^2))
shannon_entropy <- -sum(p * log2(p))
c(
min_entropy = min_entropy,
collision_entropy = collision_entropy,
shannon_entropy = shannon_entropy
)
#> min_entropy collision_entropy shannon_entropy
#> 1.000000 1.415037 1.500000The values rise from \(1\) to \(1.415\) to \(1.5\) bits, as Theorem 1 and the collision entropy bound say.
Remark 1 (Min-entropy measures the chance of a single guess). The best single guess at the value of \(X\) is its most probable value, and that guess is right with probability \(2^{-{\mathbb{H}_{\infty}\mathopen{}\left(X\right)\mathclose{}}}\). So a min-entropy of \(k\) bits says that no guess succeeds with probability above \(2^{-k}\). The entropy gives no such guarantee, because it can be large while one value is very likely. That is why min-entropy is the measure of a secret’s unpredictability.