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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

למת המקומיות של לובאס (באנגלית: Lovász Local Lemma) היא למה בתורת ההסתברות אשר פותחה בשנת 1975 על ידי לסלו לובאס ופול ארדש.‏[1] מטרת הלמה להרחיב טענה הסתברותית על משתנים בלתי תלויים למקרה בו המשתנים תלויים באופן "חלש" אחד בשני. הלמה מראה, שאם קיימים מאורעות שהסתברות כל אחד מהם קטנה מ-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.‏[2]

דוגמה[עריכת קוד מקור | עריכה]

נראה בעזרת הלמה, כי לבעיית הספיקות עבור נוסחאת 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}<1 אזי המאורע הטוב בעל הסתברות חיובית ממש. במילים אחרות, אם T<\frac{2^k}{4k} מתקיימים תנאי הלמה, ואז בהכרח קיימת השמה עבורה כל הפסוקיות מסתפקות.

חשיבות ותוצאות נוספות[עריכת קוד מקור | עריכה]

בשנת 2009 הראה מוזֶר (R. Moser) דרך קונסטרוקטיבית (אלגוריתם אקראי) למצוא נקודה \omega\in \Omega במרחב המדגם, כך שאף אחד המאורעות ה"רעים" A_iאינו מתקיים. תוחלת זמן הריצה של האלגוריתם נתון על ידי \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.