Fano-egyenlőtlenség

Ez az oldal a korábbi SCH wikiről lett áthozva.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor, kérlek, javíts rajta egy rövid szerkesztéssel!

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót.

Bináris entrópiafüggvény

Tekintsünk egy kétértékű valószínűségi változót, amely az egyik értékét $p$ valószínűséggel veszi fel, a másikat így $(1-p)$ valószínűséggel. Ennek a valószínűségi változónak az entrópiáját jelöljük $h(x)$-szel, kifejezése a definíció szerint:

$h(p)=-p\log {p}-(1-p)\log {(1-p)}$.

Fano-egyenlőtlenség

Tegyük fel, hogy az X és Y valószínűségi változók értéküket ugyanabból az M elemű halmazból veszik fel. Ha $P_{e}=\sum \limits _{x}\sum \limits _{y\not =x}p(x,y)$ annak a valószínűsége, hogy $X\not =Y$, akkor $H(X|Y)\leq P_{e}\log(M-1)+h(P_{e}),$ ahol h(x) a bináris entrópiafüggvény.

Megjegyzések

A következők csak néhány gondolat, ami nekem segített megjegyezni a Fano egyenlőtlenséget, még akkor is, ha esetleg baromság. Vizsgán eszetekbe ne jusson utalni rá. :) Ha tényleg nagy baromság, akkor valaki, aki biztos ebben, törölje ki légyszi az egészet, vagy ha nem, akkor ezt a mentegetőzést vegye ki előle, köszi!

A Fano egyenlőtlenség azt mondja, hogy ha a vevő oldal ismeri X és Y eloszlását, valamint Y értékét, akkor ahhoz, hogy X értékét elküldjük a számára, biztos, hogy átlagosan nem lesz több darab bitre szükség, mint a következő:

_Meg kell adnunk, hogy X és Y értéke eltér-e. h(P_e) megadja, hogy átlagosan hány biten tudjuk leírni azt a tényt, hogy X és Y értéke különbözik._

_Ha X nem egyezik meg Y-nal, akkor (M-1) féle értéket vehet fel, amit log(M-1) biten tudunk leírni, de erre csak akkor van szükség, ha P_e valószínűség szerint X és Y értéke eltér. Tehát szükségünk van további P_e*log({M-1}) bitre._

-- Sales - 2006.06.25.