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

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

 אי-שוויון גיבס 
תהיינה  ו  התפלגויות הסתברות בדידות. אזי



השוויון בין האגפים מתקיים אם ורק אם  לכל . במילים אחרות, האנטרופיה של התפלגות  קטנה או שווה לאנטרופיה הצולבת שלו עם כל התפלגות אחרת .

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



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

נסמן ב  את קבוצת כל ערכי  שעבורם pi אינו אפס. מכיוון ש  עבור כל x > 0, עם שוויון אם ורק אם x=1, מקבלים



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

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

  ,

או לחלופין

  .

ניתן להרחיב את שני הסכומים לכל . כלומר כולל , כאשר זוכרים כי הביטוי  שואף ל-0 בגבול ש  שואף ל-0, ו  שואף ל  כאשר  שואף ל-0. לסיכום מתקבל



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

שני תנאים אלה יתקיימו אם ורק אם  עֲבוּר , כלומר ההתפלגויות ו  זהות.

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

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


כאשר אי-השוויון הראשון נובע מאי-השוויון של ינסן. השוויון האחרון נובע מכך ש  היא התפלגות הסתברות, ולכן  .

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

  .

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



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

קטגוריה:הוכחות
גיבס
קטגוריה:תורת הקודים
קטגוריה:תורת האינפורמציה