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

למת המקומיות של לובאס (באנגלית: 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}]\leq 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}}}]\geq \prod _{i=1}^{n}(1-x(A_{i})).$$

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

אם הסתברותו של כל מאורע $A_{i}$ חסומה על ידי p, וכל אחד מהמאורעות תלוי לכל היותר ב-$d$ מאורעות אחרים, ומתקיים $e(d+1)p\leq 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\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}$$

או במילים אחרות, $e(d+1)p\leq 1$. ניתן להראות שמספיק לדרוש $edp\leq 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\leq t\leq n$.

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

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

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

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

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

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