Fano-egyenlőtlenség forrásának megtekintése

{{GlobalTemplate|Infoalap|InfElmTetel34}}


==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 <math>p</math> valószínűséggel veszi fel, a másikat így <math>(1-p)</math> valószínűséggel. Ennek a valószínűségi változónak az entrópiáját jelöljük <math>h(x)</math>-szel, kifejezése a definíció szerint:

<math>h(p)=-p\log{p}-(1-p)\log{(1-p)}</math>.

==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 <math>P_e = \sum\limits_{x} \sum\limits_{y\not= x} p(x,y)</math> annak a valószínűsége, hogy <math>X \not= Y</math>, akkor
<math> H(X|Y) \le P_e \log(M-1) + h(P_e),</math>
ahol h(x) a bináris entrópiafüggvény.

===Bizonyítás===

==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!<BR>

''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._ 


-- [[SzelessZoltanTamas|Sales]] - 2006.06.25.


[[Category:Infoalap]]