Gibbs ojämlikhet

Josiah Willard Gibbs

Inom informationsteorin är Gibbs ojämlikhet ett uttalande om informationsentropin för en diskret sannolikhetsfördelning . Flera andra gränser för entropin av sannolikhetsfördelningar härleds från Gibbs ojämlikhet, inklusive Fanos ojämlikhet . Den presenterades först av J. Willard Gibbs på 1800-talet.

Gibbs ojämlikhet

Anta att

P=\{p_{1},\ldots ,p_{n}\}

är en diskret sannolikhetsfördelning . Sedan för någon annan sannolikhetsfördelning

Q=\{q_{1},\ldots ,q_{n}\}

Följande olikhet mellan positiva storheter (eftersom p _i och q _i är mellan noll och ett) gäller:

-\sum _{i=1}^{n}p_{i}\log p_{i }\leq -\sum _{i=1}^{n}p_{i}\log q_{i}

med jämlikhet om och bara om

p_{i}=q_{i}

för allt jag . Med ord, informationsentropin för en distribution P är mindre än eller lika med dess korsentropi med någon annan distribution Q.

Skillnaden mellan de två kvantiteterna är Kullback–Leibler-divergensen eller relativ entropi, så olikheten kan också skrivas:

D_{\mathrm {KL} }(P\|Q)\equiv \sum _{i= 1}^{n}p_{i}\log {\frac {p_{i}}{q_{i}}}\geq 0.

Observera att användningen av bas-2- logaritmer är valfri och gör att man kan referera till kvantiteten på varje sida av ojämlikheten som en "genomsnittlig överraskning " mätt i bitar .

Bevis

För enkelhetens skull bevisar vi påståendet med den naturliga logaritmen ( $ln$ ). Därför att

\log _{b}a={\frac {\ln a}{\ln b}},

den speciella logaritmbasen $b > 1$ som vi väljer skalar endast förhållandet med faktorn $1 / ln b$ .

Låt $I$ beteckna mängden av alla $i$ för vilka p _i inte är noll. Sedan, eftersom $\ln x\leq x-1$ för alla x > 0 , med likhet om och endast om x=1 , har vi:

-\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\höger)

=-\summa _{i\in I}q_{i}+ \sum _{i\in I}p_{i}=-\sum _{i\in I}q_{i}+1\geq 0

Den sista olikheten är en konsekvens av att del _{pi och q i} är _av en en sannolikhetsfördelning. Specifikt är summan av alla värden som inte är noll pi _{1. Vissa} qi _. som inte är noll kan dock ha exkluderats eftersom valet av index är betingat av att inte är noll Därför kan summan av q _i vara mindre än 1.

har vi över indexuppsättningen ${\displaystyle I} :$

-\sum _{i\in I}p_{i}\ln {\frac {q_{i}}{p_{i}}}\ geq 0

,

eller motsvarande

-\sum _{i\in I}p_{i}\ln q_{i}\geq -\ summa _{i\in I}p_{i}\ln p_{i}

.

Båda summorna kan utökas till alla $i=1,\ldots ,n$ , dvs inklusive $p_{i}=0$ , genom att komma ihåg att uttrycket $p\ln p$ tenderar till 0 som $p$ tenderar till 0, och $(-\ln q)$ tenderar att $\infty$ eftersom $q$ tenderar till 0. Vi kommer fram till

-\sum _{i=1}^{n}p_{i}\ln q_{i }\geq -\sum _{i=1}^{n}p_{i}\ln p_{i}

För att jämlikheten ska bestå kräver vi

${\frac {q_{i}}{p_{i}}}=1$ för alla $i\in I$ så att likheten $\ln {\frac {q_{i}}{p_{i}}}={\frac {q_{i}}{p_{i}}}-1$ håller ,
och $\sum _{i\in I}q_{i}=1$ vilket betyder $q_{i}=0$ om $i\notin I$ , det vill säga $q_{i}=0$ om $p_{i}=0$ .

Detta kan hända om och endast om $p_{i}=q_{i}$ för $i=1,\ldots ,n$ .

Alternativa bevis

Resultatet kan alternativt bevisas med Jensens olikhet , logsummans olikhet , eller det faktum att Kullback-Leibler-divergensen är en form av Bregman-divergens . Nedan ger vi ett bevis baserat på Jensens ojämlikhet:

Eftersom log är en konkav funktion har vi följande: