Gibbsa neegalaĵ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}, \dots, p_{n}}

diskreta probablodistribuo. Tiam por ĉiu la alia diskreta probablodistribuo

Q = {q_{1}, \dots, 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-Leibler aŭ relativa entropio, tiel la neegalaĵo povas ankaŭ esti skribita kiel

K L (p, q) \geq 0

Pruvo

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 p_i 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} (\frac{q_{i}}{p_{i}} - 1) \\ = & - \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:

$\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.
$\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 Jensen aŭ logaritma suma neegalaĵo.

Korolario

La entropio de P estas barita per:

H (p_{1}, \dots, p_{n}) \leq \log n

La pruvo estas bagatela - simple meti $q_{i} = 1 / n$ por ĉiuj i.

Vidu ankaŭ

Gibbsa neegalaĵo

Pruvo

Korolario

Vidu ankaŭ

Navigada menuo

Serĉi