Shannon-Entropie zu Min-Entropie

7

In vielen Artikeln habe ich gelesen, dass es bekannt ist, dass die Shannon-Entropie einer Zufallsvariablen durch unabhängige Kopien der Variablen in Min-Entropie (bis zu einem kleinen statistischen Abstand) umgewandelt werden kann. Kann mir jemand erklären, was genau das bedeutet?

sh0t
quelle

Antworten:

6

Dies ist eine Folge der asymptotischen Äquipartitionseigenschaft (AEP), die eine Form des Gesetzes der großen Zahlen ist. Der AEP gibt an, dass eine Zufallsvariable eine (binäre) Entropie aufweistH und du nimmst n Kopien davon, dann haben die meisten Datenpunkte ungefähr eine Wahrscheinlichkeit 2nH. Dies gilt nur für die meisten Datenpunkte, die die Quelle der von Ihnen erwähnten kleinen statistischen Entfernung sind.

Betrachten Sie als Beispiel a p-voreingenommene Münze. Wenn du wirfstn Münzen mit Voreingenommenheit p, dann werden Sie höchstwahrscheinlich grob bekommen pn Köpfe, von denen jedes Ereignis ungefähr eine Wahrscheinlichkeit hat

ppn(1p)(1p)n=2nh(p).
Yuval Filmus
quelle