Gibbsa neegalaĵo

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo

En informa teorio, gibbsa neegalaĵo estas propozicio pri la matematika entropio de diskreta probablodistribuo. Kelkaj la aliaj baroj, pri la entropio de probablodistribuoj estas derivita de gibbsa neegalaĵo, inkluzivante la neegalaĵon de Fano.

Estu

 P = \{ p_1 , \ldots , p_n \}

diskreta probablodistribuo. Tiam por ĉiu la alia diskreta probablodistribuo

 Q = \{ q_1 , \ldots , q_n \}

jena neegalaĵo veras

 - \sum_{i=1}^n p_i \log_2 p_i \leq - \sum_{i=1}^n p_i \log_2 q_i

kun egaleco se kaj nur se

 p_i = q_i

por ĉiuj i.

La diferenco inter la du kvantoj estas la negativo de la diverĝenco de Kullback-Leiblerrelativa entropio, tiel la neegalaĵo povas ankaŭ esti skribita kiel

 KL(p,q) \geq 0

Pruvo[redakti | redakti fonton]

Pro tio ko

 \log_2 a = \frac{ \ln a }{ \ln 2 }

sufiĉas al pruvi la frazon uzante la naturan logaritmon (ln). Por la natura logaritmo veras

 \ln x \leq x-1

por ĉiuj x kun egaleco se kaj nur se x=1.

Estu I signifi la aro de ĉiuj i por kiu pi estas ne nulo. Tiam


\begin{matrix}
- \sum_{i \in I} p_i \ln \frac{q_i}{p_i} & \geq & - \sum_{i \in I} p_i \left( \frac{q_i}{p_i} - 1 \right) \\
&& \\
& = & - \sum_{i \in I} q_i + \sum_{i \in I} p_i \\
&& \\
& = & - \sum_{i \in I} q_i + 1 \\
&& \\
& \geq & 0
\end{matrix}

Do

 - \sum_{i \in I} p_i \ln q_i \geq - \sum_{i \in I} p_i \ln p_i

kaj tiam bagatele

 - \sum_{i=1}^n p_i \ln q_i \geq - \sum_{i=1}^n p_i \ln p_i

pro ke la dekstra flanko ne kreskas, sed la maldekstra flanko povas kreski aŭ povas resti la sama.

Por egaleco necesas:

  1.  \frac{q_i}{p_i} = 1 por ĉiuj i \in I tiel ke la proksimuma kalkulado \ln \frac{q_i}{p_i} = 1 - \frac{q_i}{p_i} estas akurata.
  2.  \sum_{i \in I} q_i = 1 tiel ke egaleco daŭras al teni inter la antaŭlasta kaj la _ultimate_ linioj de la pruvo.

Ĉi tio povas okazi se kaj nur se

p_i = q_i

por ĉiuj m=1,...,n.

La rezulto povas alternative esti pruvita per neegalaĵo de Jensenlogaritma suma neegalaĵo.

Korolario[redakti | redakti fonton]

La entropio de P estas barita per:

H(p_1, \ldots , p_n) \leq \log n

La pruvo estas bagatela - simple meti q_i = 1/n por ĉiuj i.

Vidu ankaŭ[redakti | redakti fonton]