Definición de entropía de colisión

Question

La entropía de colisión se define como la entropía Renyi para el caso $ \ alfa= 2 $ . Está dado por

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

Tome dos variables aleatorias $ x $ y $ x '$ que sigue la misma distribución de probabilidad. La probabilidad de una colisión es luego simplemente $ p _ {\ rm colch}=sum_ {i= 1} ^ {n} p_ {i} ^ {2} $ . Entonces esperaría que decimos que la entropía de colisión es solo $ h (p_ {\ rm coll}) $ i.e.

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

Esto está en analogía con la entropía binaria, pero con la probabilidad se reemplaza con la probabilidad de una colisión.

¿Cuál es la motivación detrás de elegir $ (1) $ ¡Para ser la definición de entropía de colisión?

Answer 1

Cuando $ x $ se distribuye uniformemente sobre un dominio de tamaño $ n $ , luego la entropía de Shannon, la entropía de colisión y la entropía MIN son todos iguales a $ \ log n $ .En cierto sentido, todos estos parámetros miden la cantidad de incertidumbre en $ x $ .

En contraste, su definición propuesta siempre está entre $ 0 $ y $ 1 $ , tendiendo a cero como $ x $ se vuelve más impredecible.Esto es bastante diferente de otras nociones de entropía, en las que cero significa predecible .