למת המקומיות של לובאס

למת המקומיות של לובאס (באנגלית: Lovász Local Lemma) היא למה בתורת ההסתברות אשר פותחה בשנת 1975 על ידי לסלו לובאס ופול ארדש.^[1] מטרת הלמה להרחיב טענה הסתברותית על משתנים בלתי תלויים למקרה בו המשתנים תלויים באופן "חלש" אחד בשני. הלמה מראה, שאם קיימים מאורעות שהסתברות כל אחד מהם קטנה מ-1, אזי ההסתברות שאף אחד מהם לא מתקיים היא חיובית ממש, אפילו אם המאורעות עצמם תלויים, אך מקיימים את תנאי הלמה. הלמה בעלת חשיבות רבה במתמטיקה ומדעי המחשב, למשל עבור הוכחות קיום בשיטה ההסתברותית.

הגדרה

המקרה הכללי

נניח כי ${\displaystyle {\mathcal {A}}=\{A_{1},A_{2},\ldots ,A_{n}\}}$ היא קבוצה סופית של מאורעות במרחב מדגם ${\displaystyle \Omega }$, שהסתברות כל אחד מהם קטנה מ-1. אנו מעוניינים לדעת מה ההסתברות שאף אחד מהמאורעות הנ"ל לא מתקיים, כלומר, נניח שהמאורעות הם "רעים" ונשאל מה ההסתברות של המאורע ה"טוב", ${\displaystyle \Pr[{\overline {A_{1}}}\wedge {\overline {A_{2}}}\wedge \cdots \wedge {\overline {A_{n}}}]}$. ידוע שאם המאורעות ה"רעים" בלתי תלויים, המאורע הטוב מתקיים בהסתברות חיובית ממש:

${\displaystyle \Pr[{\overline {A_{1}}}\wedge {\overline {A_{2}}}\wedge \cdots \wedge {\overline {A_{n}}}]=(1-\Pr[A_{1}])(1-\Pr[A_{2}])\cdots (1-\Pr[A_{n}]).}$

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

באופן מדויק, נסמן ב-${\displaystyle \Gamma (A_{i})}$ את קבוצת כל המאורעות התלויים ב-${\displaystyle A_{i}}$. הלמה קובעת כי אם קיימת פונקציה ${\displaystyle x:{\mathcal {A}}\to (0,1)}$ הממפה לכל מאורע "רע" מספר בין 0 ל-1, ומתקיים, לכל מאורע ${\displaystyle A_{i}}$, $${\displaystyle \Pr[A_{i}]\leq x(A_{i})\prod _{B\in \Gamma (A_{i})}(1-x(B)),}$$ אזי הסתברות המאורע הטוב חסומה על ידי $${\displaystyle \Pr[{\overline {A_{1}}}\wedge {\overline {A_{2}}}\wedge \cdots \wedge {\overline {A_{n}}}]\geq \prod _{i=1}^{n}(1-x(A_{i})).}$$

המקרה הסימטרי

אם הסתברותו של כל מאורע ${\displaystyle A_{i}}$ חסומה על ידי p, וכל אחד מהמאורעות תלוי לכל היותר ב-${\displaystyle d}$ מאורעות אחרים, ומתקיים ${\displaystyle e(d+1)p\leq 1}$ אזי המאורע הטוב מתקיים בהסתברות חיובית ממש: ${\displaystyle \Pr[{\overline {A_{1}}}\wedge \cdots \wedge {\overline {A_{n}}}]>0}$

כאשר e הוא בסיס הלוגריתם הטבעי, ${\displaystyle e\approx 2.178}$. הוכחת מקרה זה מתקבלת על ידי הפונקציה ${\displaystyle x(A_{i})={\frac {1}{d+1}}}$. על-מנת לקיים את תנאי הלמה נדרש כי $${\displaystyle \Pr[A_{i}]=p\leq {\frac {1}{d+1}}\prod _{B\in \Gamma (A_{i})}1-{\frac {1}{d+1}}={\frac {1}{d+1}}\left(1-{\frac {1}{d+1}}\right)^{d}\leq {\frac {1}{d+1}}e^{-1}}$$ או במילים אחרות, ${\displaystyle e(d+1)p\leq 1}$. ניתן להראות שמספיק לדרוש ${\displaystyle edp\leq 1}$.^[2]

דוגמה

נראה בעזרת הלמה, כי לבעיית הספיקות עבור נוסחת k-SAT יש תמיד השמה מספקת, אם כל משתנה מופיע ב ${\displaystyle T={\frac {2^{k}}{4k}}}$ פסוקיות לכל היותר. תהי ${\displaystyle \varphi }$ נוסחת k-SAT עם המשתנים הבוליאניים ${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$. כלומר הנוסחה היא מהצורה

${\displaystyle \varphi =(y_{i_{1}}\vee y_{i_{2}}\vee \cdots \vee y_{i_{k}})\wedge (y_{i_{k+1}}\vee \cdots \vee y_{i_{2k}})\wedge \cdots }$

כאשר כל אחד מהאברים ${\displaystyle y_{i_{j}}}$ הוא אחד המשתנים ${\displaystyle x_{t}}$ או ההופכי ${\displaystyle {\overline {x_{t}}}}$, כאשר ${\displaystyle 1\leq t\leq n}$.

נניח שאנחנו בוחרים את המשתנים ${\displaystyle x_{t}}$ באופן אקראי. כל פסוקית מסופקת אלא אם כל ה${\displaystyle y}$ים בעלי הערך 0, כלומר, פרט להסתברות ${\displaystyle 2^{-k}}$. עבור פסוקית מספר ${\displaystyle i}$ נגדיר את המאורע ה"רע" ${\displaystyle A_{i}}$ בו הפסוקית לא מסופקת על ידי ההשמה. כאמור ${\displaystyle \Pr[A_{i}]\leq 2^{-k}}$ לכל ${\displaystyle i}$.

נניח שכל משתנה מופיע לכל היותר ב- ${\displaystyle T}$ פסוקיות, אזי כל פסוקית תלויה לכל היותר ב- ${\displaystyle kT}$ פסוקיות אחרות, והמאורע ${\displaystyle A_{i}}$ תלוי לכל היותר ב- ${\displaystyle kT}$ מאורעות אחרים.

לפי למת המקומיות, אם ${\displaystyle e(kT+1)2^{-k}<1}$ אזי המאורע הטוב בעל הסתברות חיובית ממש. במילים אחרות, אם ${\displaystyle T<{\frac {2^{k}}{4k}}}$ מתקיימים תנאי הלמה, ואז בהכרח קיימת השמה עבורה כל הפסוקיות מסתפקות.

חשיבות ותוצאות נוספות

בשנת 2009 הראה מוזֶר (R. Moser) דרך קונסטרוקטיבית (אלגוריתם אקראי) למצוא נקודה ${\displaystyle \omega \in \Omega }$ במרחב המדגם, כך שאף אחד המאורעות ה"רעים" ${\displaystyle A_{i}}$אינו מתקיים. תוחלת זמן הריצה של האלגוריתם נתון על ידי ${\displaystyle \sum _{i}{\frac {x(A_{i})}{1-x(A_{i})}}}$.

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

הערות שוליים

1. Paul Erdős, László Lovász. Problems and results on 3-chromatic hypergraphs and some related questions, Infinite and Finite Sets (to Paul Erdős on his 60th birthday), Vol II, pages 609-627, 1975.
2. Shearer, J. On a problem of spencer. Combinatorica 5(3):241-245, 1985, http://dx.doi.org/10.1007/BF02579368.