2
$\begingroup$

The collision entropy is defined as the Renyi entropy for the case $\alpha = 2$. It is given by

$$\mathrm{H}_{2}(X)=-\log \sum_{i=1}^{n} p_{i}^{2} \tag{1}$$

Take two random variables $X$ and $X'$ which follow the same probability distribution. The probability of a collision is then simply $P_{\rm coll} = \sum_{i=1}^{n} p_{i}^{2}$. I would then expect that we say the collision entropy is just $H(P_{\rm coll})$ i.e.

$$-\left(\sum_{i=1}^{n} p_{i}^{2}\right)\log\left(\sum_{i=1}^{n} p_{i}^{2}\right) - \left(1 -\sum_{i=1}^{n} p_{i}^{2}\right)\log\left(1-\sum_{i=1}^{n} p_{i}^{2}\right)$$

This is in analogy with the binary entropy but with the probability replaced with the probability of a collision.

What is the motivation behind choosing $(1)$ to be the definition of collision entropy?

$\endgroup$
1
  • $\begingroup$ When the distribution is uniform, all Renyi entropies are the same. In contrast, your proposal is always between 0 and 1. $\endgroup$ – Yuval Filmus Feb 12 '20 at 15:01
1
$\begingroup$

When $X$ is distributed uniformly over a domain of size $n$, then Shannon entropy, collision entropy and min-entropy are all equal to $\log n$. In a sense, all of these parameters measure the amount of uncertainty in $X$.

In contrast, your proposed definition is always between $0$ and $1$, tending to zero as $X$ gets more unpredictable. This is quite different from other notions of entropy, in which zero stands for predictable.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.