הצגת המקור של הדף "אי-שוויון גיבס"

[[קובץ:Josiah_Willard_Gibbs_-from_MMS-.jpg|ממוזער|267x267 פיקסלים| ג'וזיה וילארד גיבס]]
ב[[תורת האינפורמציה]], '''אי-שוויון גיבס''' הוא טענה על [[אנטרופיה (סטטיסטיקה)|האנטרופיה]] של [[התפלגות|התפלגות הסתברות]] בדידה. חסמים נוספים על האנטרופיה של התפלגויות הסתברות נובעים מאי-שוויון גיבס, כולל [[אי השוויון של פאנו|אי-שוויון פאנו]]. אי-השוויון הוצג לראשונה על ידי [[ג'וסיה וילארד גיבס|ג'יי ווילארד גיבס]] במאה ה-19.

== אי-שוויון גיבס ==
תהיינה <math> P = \{ p_1, \ldots, p_n \} </math> ו <math> Q = \{ q_1, \ldots, q_n \} </math> [[התפלגות|התפלגויות הסתברות]] בדידות. אזי

: <math> - \sum_{i=1}^n p_i \log p_i \leq - \sum_{i=1}^n p_i \log q_i </math>

השוויון בין האגפים מתקיים אם ורק אם <math> p_i = q_i </math> לכל <math>i = 1, \dots n</math>.<ref name="Bremaud2012">{{Cite book|last=Pierre Bremaud|title=An Introduction to Probabilistic Modeling|date=6 December 2012|publisher=Springer Science & Business Media|isbn=978-1-4612-1046-7}}</ref> במילים אחרות, [[אנטרופיה (סטטיסטיקה)|האנטרופיה]] של התפלגות <math>P</math> קטנה או שווה [[אנטרופיה צולבת|לאנטרופיה הצולבת]]{{אנ|cross entropy}} שלו עם כל התפלגות אחרת <math>Q</math>.

ההפרש בין שני הגדלים הוא [[דיברגנץ קולבק-לייבלר]] (אנטרופיה היחסית), כך שניתן לכתוב את אי השוויון גם כ<ref name="MacKay2003">{{Cite book|last=David J. C. MacKay|title=Information Theory, Inference and Learning Algorithms|date=25 September 2003|publisher=Cambridge University Press|isbn=978-0-521-64298-9}}</ref>

: <math> D_{\mathrm{KL}}(P\|Q) \equiv \sum_{i=1}^n p_i \log \frac{p_i}{q_i} \geq 0.</math>

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

נסמן ב <math>I</math> את קבוצת כל ערכי <math>i</math> שעבורם ''p<sub>i</sub>'' אינו אפס. מכיוון ש <math> \ln x \leq x-1 </math> עבור כל ''x > 0'', עם שוויון אם ורק אם ''x=1'', מקבלים

: <math>- \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</math>

אי השוויון האחרון נובעת מכך ש ''p<sub>i</sub>'' ו- ''q<sub>i</sub>'' הם ערכים של התפלגות הסתברות, כך שסכום כל הערכים ''p<sub>i</sub>'' שאינם אפס הוא 1. עם זאת, ייתכן שחלק ''מה'' ''q<sub>i</sub>'' שאינם אפס הושמטו מאחר שבחירת האינדקסים <math>I</math> נקבעת על סמך הדרישה ש ''p<sub>i</sub>'' אינו אפס. לכן, סכום ה- ''q<sub>i</sub>'' עשוי להיות קטן מ-1.

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

: <math> - \sum_{i \in I} p_i \ln \frac{q_i}{p_i} \geq 0 </math> ,

או לחלופין

: <math> - \sum_{i \in I} p_i \ln q_i \geq - \sum_{i \in I} p_i \ln p_i </math> .

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

: <math> - \sum_{i=1}^n p_i \ln q_i \geq - \sum_{i=1}^n p_i \ln p_i </math>

השוויון מתקבל כאשר מתקיימים שני התנאים:
* לכל <math>i \in I </math> <math> \frac{q_i}{p_i} = 1</math> כך שמתקבל השוויון <math>\ln \frac{q_i}{p_i} = \frac{q_i}{p_i} -1 </math> ,
* <math> \sum_{i \in I} q_i = 1</math> כלומר <math>q_i=0</math> אם <math>i\notin I</math>. במילים אחרות, <math>q_i=0</math> אם <math>p_i=0</math>.

שני תנאים אלה יתקיימו אם ורק אם <math>p_i = q_i </math> עֲבוּר <math>i = 1, \ldots, n</math>, כלומר ההתפלגויות <math>P</math>ו <math>Q</math> זהות.

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

מכיוון שה[[לוגריתם]] הוא [[פונקציה קעורה]]
: <math>\sum_i p_i \log\frac{q_i}{p_i} \le \log\sum_i p_i\frac{q_i}{p_i} = \log\sum_i q_i = 0</math>

כאשר אי-השוויון הראשון נובע מאי-השוויון של ינסן. השוויון האחרון נובע מכך ש <math>Q</math> היא התפלגות הסתברות, ולכן <math>\sum q_i = 1</math> .

יתר על כן, מכיוון שהלוגריתם הוא [[פונקציה קמורה]], אז, בהתאם לתנאי השוויון של אי-שוויון ינסן, השוויון מתקבל רק כאשר מתקיימים שני התנאים:
* <math>\frac{q_1}{p_1} = \frac{q_2}{p_2} = \cdots = \frac{q_n}{p_n}</math>
* <math>\sum_i q_i = 1</math> .

נסמן ב<math>\sigma</math> את היחס בתנאי הראשון לעיל. נתקבל

: <math>1 = \sum_i q_i = \sum_i \sigma p_i = \sigma</math>

כלומר <math> p_i = q_i </math> לכל <math>i = 1, \dots n</math>. במילים אחרות, השוויון באי-שוויון ינסן מתקבל [[אם ורק אם]] ההתפלגויות <math>P</math>ו <math>Q</math> זהות.
== הערות שוליים ==
{{הערות שוליים | יישור = שמאל}}

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