Définition de l'entropie de collision

Question

L'entropie de collision est définie comme l'entropie RENYI pour le cas $ \ alpha= 2 $ . Il est donné par

$$ \ mathrm {h} _ {2} (x)= - \ journal \ sum_ {i= 1} {i {n} p_ {i}} ^ {2}} ^ {2} \ tag {1} $$

Prenez deux variables aléatoires $ x $ et $ x '$ qui suivent la même distribution de probabilité. La probabilité d'une collision est alors simplement $ p _ {\ rm coll}=sum_ {i= 1} ^ {n} p_ {i} ^ {2} $ . J'attendrais alors que nous disions que l'entropie de collision est juste $ h (p {\ \ rm coll}) $ i.e.

$$ - \ Gauche (\ Sum_ {i= 1} ^ {n} p_ {i} ^ {2} \ droite) \ LOG \ GAUCHE (\ SUM_ {I= 1} ^ {n} p_ {i} ^ {2} \ droite) - \ Gauche (1 - \ Sum_ {i= 1} ^ {n} p_ {i} ^ {2} \ droite) \ LOG \ GAUCHE (1- \ sum_ {i= 1} ^ {n} p_ {i} ^ {2} \ droite) $$

Ceci est en analogie avec l'entropie binaire mais avec la probabilité remplacée par la probabilité d'une collision.

Quelle est la motivation derrière le choix $ (1) $ pour être la définition de l'entropie de collision?

Answer 1

quand $ x $ est distribué uniformément sur un domaine de taille $ n $ , puis shannon entropy, entropie de collision et min-entropie sont tous égaux à $ \ journal n $ .En un sens, tous ces paramètres mesurent la quantité d'incertitude dans $ x $ .

En revanche, votre définition proposée est toujours entre 0 $ et 1 $ , tendant à zéro $ x $ est plus imprévisible.Ceci est assez différent des autres notions d'entropie, dans lesquelles zéro signifie prévisible .