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

'''למת המקומיות של לובאס''' (באנגלית: '''Lovász Local Lemma''') היא [[למה (מתמטיקה)|למה]] ב[[תורת ההסתברות]] אשר פותחה בשנת 1975 על ידי [[לסלו לובאס]] ו[[פול ארדש]].{{הערה|שם=LTR-המאמר|Paul Erdős, László Lovász. [http://www.cs.elte.hu/~lovasz/scans/LocalLem.pdf 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.}} מטרת הלמה להרחיב טענה הסתברותית על משתנים בלתי תלויים למקרה בו המשתנים תלויים באופן "חלש" אחד בשני. הלמה מראה, שאם קיימים [[מאורע]]ות שהסתברות כל אחד מהם קטנה מ-1, אזי ההסתברות שאף אחד מהם לא מתקיים היא חיובית ממש, אפילו אם המאורעות עצמם [[תלות (סטטיסטיקה)|תלויים]], אך מקיימים את תנאי הלמה. הלמה בעלת חשיבות רבה ב[[מתמטיקה]] ו[[מדעי המחשב]], למשל עבור הוכחות קיום ב[[השיטה ההסתברותית|שיטה ההסתברותית]].

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

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

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

כאשר [[e (קבוע מתמטי)|e]] הוא בסיס [[לוגריתם טבעי|הלוגריתם הטבעי]], <math>e\approx 2.178</math>.
הוכחת מקרה זה מתקבלת על ידי הפונקציה <math>x(A_i)=\frac{1}{d+1}</math>. על-מנת לקיים את תנאי הלמה נדרש כי 
<math display="block">\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}</math>
או במילים אחרות, <math>e(d+1)p \le 1</math>. ניתן להראות שמספיק לדרוש <math> edp \le 1</math>.{{הערה|שם=LTR-שרר|Shearer, J. On a problem of spencer. Combinatorica 5(3):241-245, 1985, http://dx.doi.org/10.1007/BF02579368.}}

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

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

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

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

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

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

==הערות שוליים==
{{הערות שוליים|יישור=שמאל}}

[[קטגוריה:משפטים בתורת ההסתברות|מקומיות של לובאס]]
[[קטגוריה:למות|מקומיות]]