Shannon Entropia a Min-Entropy

Question

In molti giornali ho letto che è ben noto che l'entropia di Shannon di una variabile casuale può essere convertito in min-entropia (fino a piccola distanza statistica) prendendo copie indipendenti della variabile. Qualcuno può spiegare a me che cosa esattamente significa questo?

Answer 1

Questa è una conseguenza della asintotica proprietà equipartizione (AEP), che è una forma della legge dei grandi numeri . L'AEP afferma che se una variabile casuale ha (binario) entropia $ H $ e si prende n $ copie di esso, allora la maggior parte dei punti di dati hanno probabilità circa $ di 2 ^ $ {- NH} $. Questo è vero solo per il maggior numero di punti di dati, che è la fonte della piccola distanza statistica che si parla.

A titolo di esempio, si consideri un $ p $ moneta -biased. Se gettate $ n $ monete con pregiudizi $ p $, quindi molto probabilmente si otterrà approssimativamente $ pn $ teste, ognuna delle quali eventi ha probabilità più o meno $$ p ^ {pn} (1-p) ^ {(1-p) n} = 2 ^ {- NH (p)}. $$