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

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

## הגדרה
### המקרה הכללי
נניח כי \mathcal{A}=\{A_1, A_2, \ldots, A_n\} היא קבוצה סופית של מאורעות במרחב מדגם \Omega, שהסתברות כל אחד מהם קטנה מ-1. אנו מעוניינים לדעת מה ההסתברות ש**אף אחד** מהמאורעות הנ"ל לא מתקיים, כלומר, נניח שהמאורעות הם "רעים" ונשאל מה ההסתברות של המאורע ה"טוב", \Pr[\overline{A_1}\wedge \overline{A_2}\wedge \cdots \wedge \overline{A_n}]. ידוע שאם המאורעות ה"רעים" בלתי תלויים, המאורע הטוב מתקיים בהסתברות חיובית ממש:
  \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]).
למת המקומיות מרחיבה את העיקרון לעיל ומראה שגם כאשר המאורעות הרעים **תלויים זה בזה** בצורה חלשה,  ההסתברות של המאורע הטוב תהיה חיובית ממש אם מתקיימים תנאי הלמה. 

באופן מדויק, נסמן ב-\Gamma(A_i) את קבוצת כל המאורעות התלויים ב-A_i. הלמה קובעת כי אם קיימת פונקציה x: \mathcal{A} \to (0,1) הממפה לכל מאורע "רע" מספר בין 0 ל-1,  ומתקיים, לכל מאורע A_i,
\Pr[A_i] \le x(A_i)\prod_{B \in \Gamma (A_i)}(1-x(B)),
אזי הסתברות המאורע הטוב חסומה על ידי
 \Pr[\overline{A_1}\wedge \overline{A_2}\wedge \cdots \wedge \overline{A_n}]  \ge \prod_{i=1}^n (1-x(A_i)).

### המקרה הסימטרי
אם הסתברותו של כל מאורע A_i חסומה על ידי p, וכל אחד מהמאורעות תלוי לכל היותר ב-d מאורעות אחרים, ומתקיים 
e(d+1)p \le 1
אזי המאורע הטוב מתקיים בהסתברות חיובית ממש: \Pr[\overline{A_1}\wedge\cdots\wedge\overline{A_n}] >0

כאשר e הוא בסיס הלוגריתם הטבעי, e\approx 2.178.
הוכחת מקרה זה מתקבלת על ידי הפונקציה x(A_i)=\frac{1}{d+1}. על-מנת לקיים את תנאי הלמה נדרש כי 
\Pr[A_i]=p \le \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 \le \frac{1}{d+1} e^{-1}
או במילים אחרות, e(d+1)p \le 1. ניתן להראות שמספיק לדרוש  edp \le 1.

## דוגמה
נראה בעזרת הלמה, כי לבעיית הספיקות עבור נוסחת k-SAT יש תמיד השמה מספקת, אם כל משתנה מופיע ב T=\frac{2^k}{4k} פסוקיות לכל היותר. תהי \varphi נוסחת k-SAT עם המשתנים הבוליאניים x_1, x_2, \ldots, x_n. כלומר הנוסחה היא מהצורה
 \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  
כאשר כל אחד מהאברים y_{i_j} הוא אחד המשתנים x_t או ההופכי \overline{x_t}, כאשר  1\le t \le n.

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

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

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

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

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

## הערות שוליים

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