אי-שוויון גיבס

בתורת האינפורמציה, אי-שוויון גיבס הוא טענה על האנטרופיה של התפלגות הסתברות בדידה. חסמים נוספים על האנטרופיה של התפלגויות הסתברות נובעים מאי-שוויון גיבס, כולל אי-שוויון פאנו. אי-השוויון הוצג לראשונה על ידי ג'יי ווילארד גיבס במאה ה-19.

ג'וזיה וילארד גיבס

אי-שוויון גיבס

תהיינה $P=\{p_{1},\ldots ,p_{n}\}$ ו $Q=\{q_{1},\ldots ,q_{n}\}$ התפלגויות הסתברות בדידות. אזי

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

השוויון בין האגפים מתקיים אם ורק אם $p_{i}=q_{i}$ לכל $i=1,\dots n$. במילים אחרות, האנטרופיה של התפלגות $P$ קטנה או שווה לאנטרופיה הצולבת שלו עם כל התפלגות אחרת $Q$.

ההפרש בין שני הגדלים הוא דיברגנץ קולבק-לייבלר (אנטרופיה היחסית), כך שניתן לכתוב את אי השוויון גם כ

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

הוכחה

למען פשטות הסימון, נשתמש בהוכחת הטענה בלוגריתם הטבעי, המסומן על ידי ln.

נסמן ב $I$ את קבוצת כל ערכי $i$ שעבורם p_i אינו אפס. מכיוון ש $\ln x\leq x-1$ עבור כל x > 0, עם שוויון אם ורק אם x=1, מקבלים

$-\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$

אי השוויון האחרון נובעת מכך ש p_i ו- q_i הם ערכים של התפלגות הסתברות, כך שסכום כל הערכים p_i שאינם אפס הוא 1. עם זאת, ייתכן שחלק מה q_i שאינם אפס הושמטו מאחר שבחירת האינדקסים $I$ נקבעת על סמך הדרישה ש p_i אינו אפס. לכן, סכום ה- q_i עשוי להיות קטן מ-1.

עד כה, בהינתן קבוצת האינדקסים $I$, יש לנו:

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

או לחלופין

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

ניתן להרחיב את שני הסכומים לכל $i=1,\ldots ,n$. כלומר כולל $p_{i}=0$, כאשר זוכרים כי הביטוי $p\ln p$ שואף ל-0 בגבול ש $p$ שואף ל-0, ו $(-\ln q)$ שואף ל $\infty$ כאשר $q$ שואף ל-0. לסיכום מתקבל

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

השוויון מתקבל כאשר מתקיימים שני התנאים:

• לכל $i\in I$ ${\frac {q_{i}}{p_{i}}}=1$ כך שמתקבל השוויון $\ln {\frac {q_{i}}{p_{i}}}={\frac {q_{i}}{p_{i}}}-1$ ,
• $\sum _{i\in I}q_{i}=1$ כלומר $q_{i}=0$ אם $i\notin I$. במילים אחרות, $q_{i}=0$ אם $p_{i}=0$.

שני תנאים אלה יתקיימו אם ורק אם $p_{i}=q_{i}$ עֲבוּר $i=1,\ldots ,n$, כלומר ההתפלגויות $P$ו $Q$ זהות.

הוכחה חלופית

ניתן להוכיח את התוצאה באמצעות אי-שוויון ינסן:

מכיוון שהלוגריתם הוא פונקציה קעורה

$\sum _{i}p_{i}\log {\frac {q_{i}}{p_{i}}}\leq \log \sum _{i}p_{i}{\frac {q_{i}}{p_{i}}}=\log \sum _{i}q_{i}=0$

כאשר אי-השוויון הראשון נובע מאי-השוויון של ינסן. השוויון האחרון נובע מכך ש $Q$ היא התפלגות הסתברות, ולכן $\sum q_{i}=1$ .

יתר על כן, מכיוון שהלוגריתם הוא פונקציה קמורה, אז, בהתאם לתנאי השוויון של אי-שוויון ינסן, השוויון מתקבל רק כאשר מתקיימים שני התנאים:

• ${\frac {q_{1}}{p_{1}}}={\frac {q_{2}}{p_{2}}}=\cdots ={\frac {q_{n}}{p_{n}}}$
• $\sum _{i}q_{i}=1$ .

נסמן ב$\sigma$ את היחס בתנאי הראשון לעיל. נתקבל

$1=\sum _{i}q_{i}=\sum _{i}\sigma p_{i}=\sigma$

כלומר $p_{i}=q_{i}$ לכל $i=1,\dots n$. במילים אחרות, השוויון באי-שוויון ינסן מתקבל אם ורק אם ההתפלגויות $P$ו $Q$ זהות.