Definizione dell'entropia di collisione

Question

L'entropia di collisione è definita come entropia Renyi per il caso $ \ alfa= 2 $ . È dato da

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

Prendi due variabili casuali $ x $ e $ x '$ che seguono la stessa distribuzione della probabilità. La probabilità di una collisione è quindi semplicemente $ p _ {\ rm coll}=sum_ {i= 1} ^ {n} p_ {i} ^ {2} $ . Mi aspetterei quindi che diciamo che l'entropia di collisione è solo $ h (p _ {\ rm coll}) $ I.e.

$$ - \ sinistra (\ suum_ {i= 1} ^ {n} p_ {i} ^ {2} \ Destra) \ log \ sinistra (\ sum_ {i= 1} ^ {n} p_ {i}} {2} \ destra) - \ sinistra (1 - \ sum_ {i= 1} ^ {n} p_ {i} ^ {2} \ Destra) \ log \ sinistra (1- \ sum_ {i= 1} ^ {n} p_ {i} ^ {2} \ destra) $$

Questo è in analogia con l'entropia binaria ma con la probabilità sostituita con la probabilità di una collisione.

Qual è la motivazione dietro la scelta di $ (1) $ per essere la definizione di entropia di collisione?

Answer 1

quando $ x $ è distribuito uniformemente su un dominio della dimensione $ n $ , quindi entropia shannon, Entropia di collisione e min-entropia sono tutti uguali a $ \ log n $ .In un certo senso, tutti questi parametri misurano la quantità di incertezza in $ x $ .

In contrasto, la tua definizione proposta è sempre tra $ 0 $ e $ 1 $ , tendendo a zero come $ x $ diventa più imprevedibile.Questo è molto diverso da altre nozioni di entropia, in cui zero stand per prevedibile .