19השיטה ההסתברותית, המשך: ניסוי אחיד ל-MAXCUT, חסם 7/8 ל-3ESAT, ובעיית הקבוצה השלטת

בקצרה

• מוכיחים מחדש שבכל גרף $G=(V,E)$ קיים חתך בגודל $\ge \frac{|E|}{2}$, אבל בניסוי אקראי אחר: במקום להטיל מטבע לכל קודקוד, מגרילים קבוצה $U$ באופן אחיד מתוך $2^V$. כל הניתוח זהה חוץ מצעד אחד — חישוב $\Pr[I_e=1]$ — שהופך מחישוב אי-תלות לחישוב ספירה קומבינטורית.
• מוכיחים שלכל נוסחת 3E-CNF (בדיוק שלושה ליטרלים ממשתנים שונים בכל הסגר) עם $m$ הסגרים קיימת השמה המספקת לפחות $\frac{7}{8}m$ הסגרים. זהו החסם הטוב ביותר האפשרי מבחינה חישובית: לפי משפט ה-PCP, להבדיל בין $\frac78$ לבין $\frac78+\varepsilon$ זו בעיה NP-קשה.
• מגדירים את בעיית הקבוצה השלטת $\mathrm{DS}$ ומוכיחים שהיא NP-שלמה, באמצעות הרדוקציה $\mathrm{VC} \le_p \mathrm{DS}$: לכל קשת $xy$ מוסיפים קודקוד חדש $v_{xy}$ ומחברים אותו ל-$x$ ול-$y$.
• מוכיחים טענת קיום מהכיוון ההפוך: בכל גרף בעל דרגה מינימלית $d$ קיימת קבוצה שלטת קטנה — בגודל לכל היותר $\frac{\ln(d+1)+1}{d+1}\cdot|V|$. כאן משתמשים ב-$\Pr[X \le \mathbb{E}[X]]>0$ במקום ב-$\Pr[X \ge \mathbb{E}[X]]>0$.
• הניסוי שם הוא דו-שלבי: שלב אקראי (כל קודקוד נכנס בהסתברות $p$ בנפרד) ואחריו שלב דטרמיניסטי מתקן שדואג שהקבוצה תהיה שלטת בוודאות. זהו התבנית "הגרל ואז תקן", ומחירה מתבטא בתוחלת ולא בנכונות.
• ערך ההסתברות $p=\frac{\ln(d+1)}{d+1}$ אינו קסם: הוא המינימום של הפונקציה $f(p)=p+e^{-p(d+1)}$, ואת הגזירה עושים בשיעור.
• מוטיב מרכזי לכל השיעור: השיטה ההסתברותית היא טיעון ממוצע, לא אלגוריתם. אין בה שום ניסיון למצוא את האובייקט; היא רק אומרת שמשהו שטוב לפחות כמו הממוצע חייב להתקיים.

רקע ותלויות

מהו חתך (שיעור 10, שיעור 18). בהינתן גרף $G=(V,E)$ וקבוצה $U \subseteq V$, החתך המושרה על ידי $U$ הוא $(U,\bar{U}) \;=\; \{\, e \in E \;:\; |e \cap U| = 1 \,\},$ כלומר קבוצת הקשתות שקצה אחד שלהן ב-$U$ והקצה השני מחוץ ל-$U$. גודל החתך הוא $|(U,\bar U)|$. $\mathrm{MAXCUT}$ היא בעיית מציאת חתך מקסימלי; היא NP-קשה (שיעור 10, דרך $\mathrm{3NAE}\le_p\mathrm{MAXCUT}$).

כיסוי בקודקודים (שיעור 10). $U\subseteq V$ היא כיסוי בקודקודים אם $\forall e\in E:\ e\cap U \ne \emptyset$. השפה: $\mathrm{VC} = \bigl\{\, \langle G,k\rangle \;:\; G \text{ graph},\ k\in\mathbb{N},\ \exists U \subseteq V \text{ a vertex cover},\ |U|\le k \,\bigr\}.$ בשיעור 10 הוכח ש-$\mathrm{VC}$ היא NP-שלמה. זו נקודת המוצא של הרדוקציה כאן.

כיוון הרדוקציה. הסימון $A \le_p B$ אומר: קיים אלגוריתם פולינומי שממיר קלט של $A$ לקלט של $B$ תוך שימור התשובה. במילים — $B$ היא הבעיה הקשה יותר; פתרון ל-$B$ נותן פתרון ל-$A$. לכן כדי להוכיח ש-$\mathrm{DS}$ קשה, נראה $\mathrm{VC} \le_p \mathrm{DS}$ ולא להפך. (בדיבור מחליפים את הכיוון הזה כל הזמן; שווה לעצור ולוודא.)

שתי הטענות שמניעות את השיטה ההסתברותית (שיעור 18, משפט 9). יהי $(\Omega,\Pr)$ מרחב הסתברות סופי.

1. אם $A \subseteq \Omega$ מאורע ו-$\Pr[A]>0$, אז $A \ne \emptyset$.
2. אם $X$ משתנה מקרי בעל תוחלת, אז $\Pr\bigl[X \ge \mathbb{E}[X]\bigr] > 0$.

בשיעור הזה נזדקק גם לגרסה המשלימה של (2), שנוכיח בהמשך (למה 1): $\Pr\bigl[X \le \mathbb{E}[X]\bigr] > 0$.

המשמעות — וזו הנקודה שחוזרת בכל השיעור. הצמד (1)+(2) אומר: אם בניתי ניסוי אקראי על אוסף אובייקטים והראיתי שהתוחלת של מדד האיכות היא $c$, אז קיים אובייקט שאיכותו לפחות $c$. זהו טיעון ממוצע: לא ייתכן שכל האיברים נמצאים מתחת לממוצע. ההוכחה אינה מצביעה על האובייקט, אינה מייצרת אותו, ואינה אלגוריתם — האקראיות היא כלי הוכחה בלבד, והטענה שמוכיחים היא טענה קומבינטורית טהורה שאין בה זכר להסתברות.

לינאריות התוחלת (הסתברות, וחזרה בשיעור 18). לכל משתנים מקריים $X_1,\dots,X_k$ בעלי תוחלת, $\mathbb{E}\Bigl[\sum_{i=1}^{k} X_i\Bigr] \;=\; \sum_{i=1}^{k}\mathbb{E}[X_i],$ בלי שום הנחה על אי-תלות. זהו הכלי היחיד שנחיל על כל המשתנים ביחד; כל השאר נעשה למשתנה בודד. זו בדיוק הסיבה שנשתמש בתוחלת ולא בשונות — שונות דורשת חישוב קובריאנציות ותקרוס כאן.

אינדיקטור. לכל מאורע $A$, המשתנה $I_A$ שמקבל $1$ אם $A$ קרה ו-$0$ אחרת מקיים $\mathbb{E}[I_A]=\Pr[A]$.

מ-$\mathrm{3SAT}$ ל"בדיוק שלושה" (שיעור 8). בשיעור 8 ראינו רדוקציה מ-$\mathrm{SAT}$ ל-$\mathrm{3SAT}$, ובדרך גם את הטכניקה שממירה הסגר קצר מדי להסגרים באורך בדיוק $3$. את זה נניח כאן: אנחנו מתחילים ישירות מנוסחאות שבהן כל הסגר מכיל בדיוק שלושה ליטרלים ממשתנים שונים.

הגדרות

הגדרה 1: נוסחת 3E-CNF, והבעיה $\mathrm{MAX\text{-}3ESAT}$

נוסחה בוליאנית $\varphi$ היא בצורת 3E-CNF (בהקלטה: "3 exact SAT") אם היא בצורת 3CNF ובנוסף בכל הסגר שלה יש בדיוק שלושה ליטרלים משלושה משתנים שונים.

השפה/הבעיה בגרסת האופטימיזציה:

קלט: נוסחה $\varphi$ בצורת 3E-CNF. מטרה: למצוא השמה $v$ המספקת מספר רב ביותר של הסגרים ב-$\varphi$.

זו גרסת האופטימיזציה של $\mathrm{SAT}$: לא שואלים "כן/לא — האם ניתן לספק את הכול", אלא מבקשים למקסם.

למה נדרשת ההקפדה הזו. שתי הדרישות אינן קישוט. "בדיוק שלושה" (ולא "לכל היותר שלושה") נחוצה כדי שההסתברות שהסגר אינו מסופק תהיה בדיוק $\frac18$ ולא יותר; "משתנים שונים" נחוצה כדי שנוכל לפרק הסתברות של חיתוך למכפלה. בלי שתיהן החישוב בהמשך פשוט לא עובד. בהקלטה ([00:17:37]) הוסבר שאם אנחנו מדברים על אלגוריתמים אפשר לעבור לצורה הזו על ידי רדוקציה, אבל את הקלט עצמו צריך להביא לצורה הזו במפורש.

דוגמה. $\varphi = (x_1\vee x_2\vee x_3)\wedge(\neg x_1 \vee x_2 \vee x_4)$ היא 3E-CNF: שני הסגרים, בכל אחד שלושה ליטרלים משלושה משתנים שונים. שימו לב ש-$x_1$ ו-$x_2$ חוזרים בין הסגרים — זה מותר לגמרי ([00:21:24]).

אי-דוגמה. $(x_1 \vee x_1 \vee x_2)$ אינה חוקית — שני ליטרלים מאותו משתנה בתוך אותו הסגר. גם $(x_1\vee x_2)$ אינה חוקית — שני ליטרלים בלבד.

הגדרה 2: קבוצה שלטת (Dominating Set)

יהי $G=(V,E)$ גרף. קבוצת קודקודים $U \subseteq V$ תיקרא קבוצה שלטת (dominating set) אם $\forall x \in V:\quad x \in U \ \ \vee\ \ \exists y\in U \text{ such that } xy \in E .$

במילים: כל קודקוד בגרף הוא או בתוך הקבוצה, או שכן מיידי של מישהו בקבוצה. שימו לב שמדובר בשכנות ישירה, לא בקיום מסלול ([00:51:24]).

אינטואיציה ומוטיבציה ([00:53:01]). נניח שאני רוצה לשלם למשפיענים ברשת כדי להפיץ מסר. אני רוצה קבוצה שכל אחד ברשת או שילמתי לו, או שהוא מחובר ישירות למישהו ששילמתי לו — וכמה שיותר קטנה, כי משלמים לכל אחד. אותו דבר במיקום רמזורים בצמתים, שלטי פרסומת, או תחנות שירות. זו בדיוק קבוצה שלטת מינימלית.

ההבדל מכיסוי בקודקודים ([01:03:06]). ההגדרות דומות מאוד, אבל מסתכלות מכיוונים שונים: בכיסוי בקודקודים המטרה היא לגעת בכל קשת; בקבוצה שלטת המטרה היא לכסות כל קודקוד. בקבוצה שלטת אני לא חייב לגעת בכל קשת.

דוגמה. במסלול $a - b - c$, הקבוצה $U=\{b\}$ שלטת: $b\in U$, ו-$a,c$ שכנים של $b$.

אי-דוגמה. באותו גרף, $U'=\{a\}$ אינה שלטת: $c \notin U'$ ו-$c$ אינו שכן של $a$.

הגדרה 3: הבעיה $\mathrm{DS}$

קלט: גרף $G=(V,E)$ ומספר $k \in \mathbb{N}$. שאלה: האם קיימת ב-$G$ קבוצה שלטת בגודל לכל היותר $k$?

השפה: $\mathrm{DS} = \bigl\{\, \langle G,k\rangle \;:\; \exists U \subseteq V \text{ dominating in } G,\ |U| \le k \,\bigr\}.$

"לכל היותר" מול "בדיוק" ([00:51:57]). כאן ההבחנה אינה משנה: אם $U$ שלטת ו-$U \subseteq U' \subseteq V$, אז $U'$ שלטת גם היא (התנאי הוא קיומי ולא נהרס בהוספה). לכן קיום קבוצה שלטת בגודל $\le k$ שקול לקיום קבוצה שלטת בגודל בדיוק $k$, כל עוד $k \le |V|$. (לעומת זאת ב-$\mathrm{VC}$, מסיבה דומה, גם שם אין הבדל.)

הגדרה 4: דרגה מינימלית

לגרף $G=(V,E)$ נסמן $d \;=\; \min_{v \in V} \deg(v),$ כלומר הדרגה המינימלית בגרף. זו הדרגה שתופיע בטענת הקיום של הקבוצה השלטת. שימו לב לכיוון: מכיוון שנרצה לחסום מלמעלה ביטוי מהצורה $(1-p)^{\deg(v)+1}$, ומכיוון ש-$0<1-p<1$, חסם מלמעלה מתקבל מחזקה נמוכה יותר — כלומר מ-$\deg(v) \ge d$. לכן דווקא הדרגה המינימלית היא הפרמטר הנכון כאן, ולא המקסימלית.

משפטים והוכחות

משפט 1: בכל גרף קיים חתך בגודל $\ge \frac{|E|}{2}$ — הוכחה שנייה, בניסוי אחיד

טענה. יהי $G=(V,E)$ גרף. אז קיימת קבוצה $U \subseteq V$ שהחתך $(U,\bar U)$ שהיא משרה מכיל לפחות $\frac{|E|}{2}$ קשתות.

מה חדש כאן. את הטענה עצמה כבר הוכחנו בשיעור 18 (משפט 10) בניסוי שבו לכל קודקוד מטילים מטבע הוגן בנפרד ובאופן בלתי תלוי. הטענה אינה משתנה ואינה משתפרת. מה שמשתנה הוא הניסוי, ולכן גם צעד אחד בהוכחה. המרצה הציג את זה מפורשות כתרגיל בשיטה ([00:02:45]): "תחשבו על הדבר הטבעי ביותר לעשות — אם אני רוצה להגיד קיימת קבוצה, מה האלגוריתם האקראי הכי פשוט שאתם יכולים לדמיין? תבחר קבוצה, באופן אחיד ואקראי." זהו האלגוריתם הקצר ביותר האפשרי; מחירו הוא שהניתוח דורש ספירה.

הניסוי. בהינתן הגרף $G$ (שהוא קבוע ואינו מוגרל), נבחר קבוצה $U \subseteq V$ באופן אחיד ואקראי מתוך כל תת-הקבוצות של $V$.

מרחב המדגם. מרחב המדגם הוא $\Omega \;=\; 2^{V} \;=\; \{\, U : U \subseteq V \,\},$ כלומר קבוצת כל תתי-הקבוצות של $V$, ו-$|\Omega| = 2^{|V|}$. ההתפלגות היא אחידה: $\Pr[\{U\}]=2^{-|V|}$ לכל $U\subseteq V$.

הערה על סימון ([00:03:50]). בכיתה נאמר בטעות ש-$|\Omega|=2$; הובהר מיד ש-$\Omega$ עצמו הוא $2^V$ — אובייקט, קבוצת קבוצות — ואילו $2^{|V|}$ הוא מספר, גודלו. שני דברים שונים לחלוטין שהסימון הדומה מבלבל ביניהם.

מעל מה ההסתברות. כל ההסתברויות והתוחלות להלן הן מעל בחירת $U$ — כלומר מעל מטבעות האלגוריתם — עבור הגרף $G$ הקבוע. אין כאן שום הגרלה של גרף.

המשתנים המקריים. נסמן ב-$X$ את גודל החתך, $X: 2^V \to \mathbb{R}, \qquad X(U) = \bigl|(U,\bar U)\bigr| ,$ ולכל $e\in E$ נסמן ב-$I_e$ את האינדיקטור לכך ש-$e$ בחתך, $I_e : 2^V \to \{0,1\}, \qquad I_e(U) = \begin{cases}1 & |e\cap U|=1\\ 0 & \text{otherwise}\end{cases}$ ואז, כשוויון בין פונקציות, $X \;=\; \sum_{e\in E} I_e .$

חישוב התוחלת. מלינאריות התוחלת, $\mathbb{E}[X] \;=\; \sum_{e\in E}\mathbb{E}[I_e].$ תהי $e = xy \in E$ (ומכיוון שהגרף פשוט, $x \ne y$). אז $\mathbb{E}[I_e] \;=\; \Pr[I_e=1] \;=\; \Pr\bigl[(x\in U \wedge y\notin U)\ \vee\ (x\notin U \wedge y\in U)\bigr].$ שני המאורעות זרים (לא ייתכן ש-$x\in U$ וגם $x\notin U$), ולכן מאדיטיביות סופית: $= \Pr[x\in U \wedge y\notin U] \;+\; \Pr[x\notin U \wedge y\in U].$

וכאן — ורק כאן — ההוכחה נפרדת מזו של שיעור 18. אי אפשר לכתוב $\tfrac12\cdot\tfrac12$, כי לא הגדרנו מאורע פר קודקוד ולא הנחנו אי-תלות בין קודקודים; אנחנו מגרילים קבוצה אחת ([00:07:49]). מה שכן יש לנו זה שההתפלגות אחידה, ובהתפלגות אחידה ההסתברות היא "רצוי חלקי סך הכול": $\Pr[x\in U \wedge y\notin U] \;=\; \frac{\bigl|\{\, U\subseteq V \;:\; x\in U \wedge y\notin U \,\}\bigr|}{2^{|V|}},$ ובאותו אופן עבור המחובר השני. נותר לספור את המונה.

הספירה, במלואה. נסמן $\mathcal{A} \;=\; \{\, U \subseteq V \;:\; x \in U,\ y \notin U \,\}, \qquad \mathcal{B} \;=\; 2^{\,V\setminus\{x,y\}} .$ נגדיר $\Phi:\mathcal{A}\to\mathcal{B}$ על ידי $\Phi(U) = U \setminus \{x\}$. הפונקציה מוגדרת היטב: אם $U \in \mathcal{A}$ אז $y \notin U$ ולכן $U\setminus\{x\} \subseteq V\setminus\{x,y\}$. היא חד-חד-ערכית ועל, כי יש לה הופכית מפורשת $\Psi:\mathcal{B}\to\mathcal{A}$, $\Psi(W) = W\cup\{x\}$ — ואכן $\Psi(W)\in\mathcal{A}$ (מכיל את $x$, אינו מכיל את $y$), וכן $\Phi(\Psi(W))=W$ ו-$\Psi(\Phi(U))=U$ לכל $U\in\mathcal{A}$ (השוויון האחרון תקף כי $x\in U$). לכן $|\mathcal{A}| \;=\; |\mathcal{B}| \;=\; 2^{|V|-2},$ שם השוויון האחרון הוא הנוסחה הבסיסית $|2^{A}| = 2^{|A|}$ עבור $A = V\setminus\{x,y\}$, שגודלה $|V|-2$ (כי $x\ne y$).

הערה: בהרצאה הצעד הזה נאמר במילה אחת — "זה כמו לבחור תת-קבוצה של $V\setminus\{x,y\}$" — והפירוט הועלה רק אחרי שאלה מהכיתה ([00:09:41]). הפירוט הוא הפונקציה ההפיכה שלמעלה. הטכניקה הכללית ([00:16:12]): כדי לספור קבוצה, מוצאים התאמה חד-חד-ערכית ועל לקבוצה שיש עבורה נוסחה מוכרת.

מסימטריה מלאה (החלפת התפקידים של $x$ ו-$y$) גם $\bigl|\{U : x\notin U,\ y\in U\}\bigr| = 2^{|V|-2}$. לכן $\mathbb{E}[I_e] \;=\; \frac{2^{|V|-2}}{2^{|V|}} \;+\; \frac{2^{|V|-2}}{2^{|V|}} \;=\; \frac14+\frac14 \;=\; \frac12 ,$ ומכאן $\mathbb{E}[X] \;=\; \sum_{e\in E}\frac12 \;=\; \frac{|E|}{2}.$

מתוחלת לקיום. לפי טענה (2) של השיטה ההסתברותית, $\Pr\bigl[X \ge \tfrac{|E|}{2}\bigr] > 0$, כלומר $\Pr\left(\left\{\, U\subseteq V \;:\; X(U) \ge \tfrac{|E|}{2} \,\right\}\right) > 0,$ ולפי טענה (1) הקבוצה הזו אינה ריקה. כלומר קיימת $U\subseteq V$ שהחתך שהיא משרה מכיל לפחות $\frac{|E|}{2}$ קשתות. $\blacksquare$

מדוע זה טיעון ממוצע ולא אלגוריתם. מה שהראינו הוא שהערך הממוצע של $X$ על פני כל $2^{|V|}$ הקבוצות הוא $\frac{|E|}{2}$. לא ייתכן שכל האיברים בממוצע קטנים ממש מהממוצע, ולכן מישהו לפחות משיג אותו. ההוכחה אינה מצביעה על אף $U$ קונקרטית, ואינה נותנת שיטה למצוא אחת. (למצוא כזו אפשר — ראו את החיפוש המקומי בשיעור 13 ואת האלגוריתם החמדן בשיעור 14 — אבל זה סיפור אחר לגמרי.)

מלכודת ([00:13:31], [00:14:37]). שאלה מהכיתה: "למה לא פשוט מכפילים את ההסתברויות?" התשובה: אי-תלות היא משהו שצריך להוכיח או להניח, לא משהו שנובע מכך שהדגימה אחידה. במקרה הזה זה אמנם נכון — החישוב שביצענו למעשה מוכיח ש-$\Pr[x\in U \wedge y\notin U]=\tfrac14 = \tfrac12\cdot\tfrac12$ — אבל זה מסקנה של החישוב ולא קלט שלו. שאלה נוספת ערבבה בין "זרים" לבין "בלתי תלויים"; אלה מושגים שונים לחלוטין, ולמעשה מנוגדים: שני מאורעות זרים בעלי הסתברות חיובית הם בהכרח תלויים.

משפט 2: בכל נוסחת 3E-CNF קיימת השמה המספקת $\ge \frac78$ מההסגרים

טענה. תהי $\varphi$ נוסחה בצורת 3E-CNF עם $m$ הסגרים. אז קיימת השמה $v$ המספקת לפחות $\frac{7}{8}m$ מההסגרים של $\varphi$.

הניסוי. נסמן את משתני $\varphi$ ב-$x_1,\dots,x_n$. נגדיר השמה אקראית $v$ כך: לכל $1\le i\le n$, באופן בלתי תלוי בשאר, $\Pr[v(x_i)=1]=\tfrac12, \qquad \Pr[v(x_i)=0]=\tfrac12 .$

מרחב המדגם ומעל מה ההסתברות. מרחב המדגם הוא קבוצת כל ההשמות $\Omega=\{0,1\}^{\{x_1,\dots,x_n\}}$, $|\Omega|=2^n$. הנוסחה $\varphi$ קבועה — היא הקלט; היא אינה מוגרלת. כל ההסתברויות והתוחלות הן מעל בחירת ההשמה, כלומר מעל מטבעות האלגוריתם.

המשתנים המקריים. נסמן ב-$X$ את מספר ההסגרים המסופקים: $X : \Omega \to \mathbb{R}, \qquad X(v) = \bigl|\{\, C \text{ a clause of } \varphi \;:\; v \text{ satisfies } C \,\}\bigr| .$ לכל הסגר $C$ של $\varphi$ נסמן ב-$I_C$ את האינדיקטור למאורע "$v$ מספקת את $C$". שימו לב: $I_C$ היא פונקציה של $v$ בלבד; $C$ אינו קלט שלה אלא חלק מהמבנה שלה ([00:27:32]). אז $X \;=\; \sum_{C \in \varphi} I_C,$

ולכן מלינאריות התוחלת

$\mathbb{E}[X]=\sum_{C\in\varphi}\mathbb{E}[I_C].$

חישוב $\mathbb{E}[I_C]$. יהי $C$ הסגר של $\varphi$. לפי ההגדרה קיימים שלושה ליטרלים $\ell_1,\ell_2,\ell_3$ ממשתנים שונים כך ש-$C=\ell_1\vee\ell_2\vee\ell_3$. נחשב דווקא את ההסתברות המשלימה, כי היא זו שיש לה תיאור פשוט: $\Pr[I_C=0] \;=\; \Pr\bigl[v \text{ does not satisfy } C\bigr] \;=\; \Pr\bigl[v(\ell_1)=0 \ \wedge\ v(\ell_2)=0\ \wedge\ v(\ell_3)=0\bigr],$ כי דיסיונקציה אינה מסופקת אם ורק אם כל הליטרלים שלה מקבלים $0$.

כאן נכנסת אי-התלות. שלושת הליטרלים באים משלושה משתנים שונים, ולכן שלושת המאורעות $\{v(\ell_j)=0\}$ נקבעים על ידי שלושה מטבעות שונים ובלתי תלויים, ולכן: $= \Pr[v(\ell_1)=0]\cdot\Pr[v(\ell_2)=0]\cdot\Pr[v(\ell_3)=0].$ לכל ליטרל בודד $\ell$: אם $\ell = x_i$ אז $\Pr[v(\ell)=0]=\Pr[v(x_i)=0]=\tfrac12$; ואם $\ell=\neg x_i$ אז $\Pr[v(\ell)=0]=\Pr[v(x_i)=1]=\tfrac12$. בשני המקרים $\tfrac12$. לכן $\Pr[I_C=0] \;=\; \tfrac12\cdot\tfrac12\cdot\tfrac12 \;=\; \tfrac18,$

ולכן

$\mathbb{E}[I_C]=\Pr[I_C=1] \;=\; 1-\tfrac18 \;=\; \tfrac78 .$

האינטואיציה מאחורי ה-$\frac18$ ([00:20:50]). להסגר עם שלושה ליטרלים ממשתנים שונים יש $2^3=8$ דרכים להשים ערכי אמת לליטרלים שלו, ובדיוק אחת מהן מכשילה אותו — זו שנותנת $0$ לשלושתם. משם ה-$8$ וגם ה-$3$: $8=2^3$, והמעריך הוא מספר הליטרלים בהסגר.

סיום. נסמן ב-$m$ את מספר ההסגרים ב-$\varphi$. אז $\mathbb{E}[X] \;=\; \sum_{C\in\varphi}\mathbb{E}[I_C] \;=\; \sum_{C\in\varphi}\frac78 \;=\; \frac78 m .$ לפי טענה (2), $\Pr\bigl[X\ge\tfrac78 m\bigr]>0$, ולפי טענה (1) המאורע הזה אינו ריק. כלומר קיימת השמה $v$ המספקת לפחות $\frac78 m$ הסגרים. $\blacksquare$

השאלה החשובה של השיעור ([00:34:28]). סטודנט הצביע על כך שהאינדיקטורים $I_C$ תלויים זה בזה — הסגרים שונים חולקים משתנים, ולכן ההסתברות שאחד מסופק בהחלט משפיעה על ההסתברות שהשני מסופק. זו הבחנה נכונה לגמרי, והתשובה היא שזה לא משנה: לינאריות התוחלת אינה דורשת דבר מהמשתנים המקריים מלבד קיום התוחלת. ברגע שעברנו מ-$\mathbb{E}\bigl[\sum_C I_C\bigr]$ ל-$\sum_C \mathbb{E}[I_C]$, כל תוחלת מחושבת בנפרד ואין יותר אינטראקציה. אילו היינו רוצים שונות — היינו נתקעים, כי היינו צריכים את כל הקובריאנציות. וגם: אילו היינו שואלים "מה ההסתברות שההשמה מספקת בדיוק כך וכך הסגרים", החישוב היה נורא בגלל אותן תלויות. התוחלת היא מדד "חלש" ולכן מתירני, וזו בדיוק הסיבה שהיא עובדת פה.

למה 1: $\Pr\bigl[X \le \mathbb{E}[X]\bigr] > 0$

טענה. יהי $(\Omega,\Pr)$ מרחב הסתברות סופי ויהי $X$ משתנה מקרי עליו. אז $\Pr\bigl[X\le\mathbb{E}[X]\bigr]>0$.

הוכחה. נסמן $\mu=\mathbb{E}[X]$ ונניח בשלילה $\Pr[X\le\mu]=0$. אז לכל $\omega\in\Omega$ עם $\Pr[\{\omega\}]>0$ מתקיים $X(\omega)>\mu$. לכן $\mu \;=\; \sum_{\omega\in\Omega}\Pr[\{\omega\}]\,X(\omega) \;=\; \sum_{\omega:\,\Pr[\{\omega\}]>0}\Pr[\{\omega\}]\,X(\omega) \;>\; \sum_{\omega:\,\Pr[\{\omega\}]>0}\Pr[\{\omega\}]\cdot\mu \;=\; \mu,$ כאשר האי-שוויון חד מפני שהסכום אינו ריק (סכום ההסתברויות הוא $1>0$), והשוויון האחרון כי $\sum_\omega \Pr[\{\omega\}]=\Pr[\Omega]=1$. קיבלנו $\mu>\mu$ — סתירה. $\blacksquare$

האינטואיציה ([01:34:49]). תחשבו על ממוצע: לא ייתכן שכל האיברים גדולים ממש מהממוצע, וגם לא ייתכן שכולם קטנים ממנו ממש. מישהו חייב להיות מעליו או שווה לו, ומישהו חייב להיות מתחתיו או שווה לו. זו כל התובנה. בשיעור 18 השתמשנו בכיוון ה-$\ge$ כי רצינו חתך גדול; במשפט 5 נשתמש בכיוון ה-$\le$ כי נרצה קבוצה שלטת קטנה.

משפט 3: $\mathrm{DS}\in\mathrm{NP}$

טענה. $\mathrm{DS}\in\mathrm{NP}$.

הוכחה (מוודא דטרמיניסטי). נגדיר מוודא $M$ שמקבל קלט $\langle G,k\rangle$ ותעודה $\langle U\rangle$ שהיא קידוד של תת-קבוצה של $V$. $M$ פועל כך:

1. בודק ש-$U\subseteq V$ וש-$|U|\le k$. זמן $O(|V|)$.
2. לכל $x\in V$ בודק אם $x\in U$; אם לא, עובר על רשימת השכנים של $x$ ובודק אם קיים $y\in U$ עם $xy\in E$. אם עבור איזשהו $x$ שני הבדיקות נכשלו — דוחה.
3. אם כל הקודקודים עברו — מקבל.

נכונות. לפי הגדרה 2, $U$ שלטת אם ורק אם כל $x\in V$ עובר את הבדיקה בשלב 2. לכן $M$ מקבל את $\langle G,k\rangle,\langle U\rangle$ אם ורק אם $U$ היא קבוצה שלטת בגודל $\le k$; כלומר קיימת תעודה מתקבלת אם ורק אם $\langle G,k\rangle\in\mathrm{DS}$.

חשבון סיבוכיות. אורך התעודה הוא $O(|V|\log|V|)$ ביטים — פולינומי בגודל הקלט. שלב 2 עולה $O(|V|+|E|)$ בייצוג רשימות שכנויות (או $O(|V|^2)$ במטריצת שכנויות). סך הכול פולינומי. $\blacksquare$

הערה ([00:54:33]). ניתן להראות שייכות ל-$\mathrm{NP}$ גם על ידי מכונה אי-דטרמיניסטית שמנחשת את $U$ ואז בודקת. המרצה העדיף את הניסוח עם המוודא הדטרמיניסטי — "אני מרגיש יותר בשליטה" — ושתי הדרכים תקפות באותה מידה.

משפט 4: $\mathrm{VC}\le_p\mathrm{DS}$, ולכן $\mathrm{DS}$ היא NP-שלמה

טענה. $\mathrm{VC}\le_p\mathrm{DS}$. מכיוון ש-$\mathrm{VC}$ היא NP-קשה (שיעור 10), נובע ש-$\mathrm{DS}$ NP-קשה; ביחד עם משפט 3, $\mathrm{DS}$ היא NP-שלמה.

למה דווקא $\mathrm{VC}$ ([00:56:07]). כי היא "מריחה דומה" — שתי הבעיות מבקשות קבוצת קודקודים קטנה שמכסה משהו. הדמיון הזה הוא בדיוק מה שמאפשר רדוקציה קצרה, וההבדל ביניהן הוא בדיוק מה שהרדוקציה צריכה לגשר עליו.

הרדוקציה (האלגוריתם $R$).

קלט: גרף $G=(V,E)$ ומספר $k\in\mathbb{N}$ — כלומר קלט של $\mathrm{VC}$.

1. לכל קשת $xy\in E$: 1.1. הוסף קודקוד חדש $v_{xy}$ וחבר אותו בקשת ל-$x$ ובקשת ל-$y$.
2. הסר מהגרף המתקבל את כל הקודקודים המבודדים, והחזר את הגרף המתקבל $\hat G=(\hat V,\hat E)$ יחד עם אותו $k$.

חשבון זמן הריצה ([00:58:56]). הלולאה בשלב 1 רצה $|E|$ פעמים; בכל איטרציה מוסיפים קודקוד אחד ושתי קשתות — פעולה בזמן קבוע (או $O(\log)$ בייצוג סביר). זיהוי הקודקודים המבודדים בשלב 2 הוא מעבר יחיד על רשימות השכנויות, $O(|V|+|E|)$. סך הכול $O(|V|+|E|)$, ובוודאי פולינומי בגודל הקלט. הגרף המוחזר מקיים $|\hat V| \le |V|+|E|$ ו-$|\hat E| \le 3|E|$, כלומר גם הפלט פולינומי — מה שנחוץ, כי אחרת אי אפשר היה לכתוב אותו בזמן פולינומי.

האלגוריתם מחזיר אינסטנס תקין. הקלט הוא זוג $\langle$גרף, מספר$\rangle$ והפלט הוא זוג $\langle$גרף, מספר$\rangle$ — כלומר קלט חוקי של $\mathrm{DS}$.

למה בכלל צריך את שלב 2 ([01:11:49]). קודקוד מבודד ב-$G$ אינו נוגע באף קשת, ולכן לעולם אינו דרוש לכיסוי בקודקודים: אם $U$ כיסוי, גם $U$ ללא קודקודים מבודדים הוא כיסוי. לעומת זאת בקבוצה שלטת קודקוד מבודד חייב להיכנס לקבוצה — אין לו שכן שיכסה אותו. בלי שלב 2 היינו מחייבים את $\mathrm{DS}$ להוסיף קודקודים שאין להם שום מקבילה בצד $\mathrm{VC}$, וזה היה מקלקל את שמירת התשובה. מכיוון שהסרת קודקודים מבודדים אינה משנה את התשובה של $\mathrm{VC}$ (הקשתות לא השתנו), מותר לנו להניח מעתה ש-$G$ נטול קודקודים מבודדים.

נסמן מעתה: $G=(V,E)$ הוא הגרף לאחר הסרת הקודקודים המבודדים, $\hat G=(\hat V,\hat E)$ הגרף שמחזיר האלגוריתם. שימו לב לתכונה המבנית שנשתמש בה שוב ושוב: לכל קודקוד חדש $v_{xy}\in \hat V\setminus V$ יש בדיוק שני שכנים ב-$\hat G$, והם $x$ ו-$y$, ושניהם ב-$V$.

כיוון א': אם $\langle G,k\rangle\in\mathrm{VC}$ אז $\langle \hat G,k\rangle\in\mathrm{DS}$.

נניח $\langle G,k\rangle\in\mathrm{VC}$. אז קיימת $U\subseteq V$ כך ש-$\forall e\in E:\ e\cap U\ne\emptyset$, וכן $|U|\le k$.

נתבונן באותה $U$ בדיוק, כתת-קבוצה של $\hat V$ (חוקי, כי $V\subseteq\hat V$). נראה שהיא שלטת ב-$\hat G$. יהי $x\in\hat V$; נניח $x\notin U$ (אם $x\in U$ אין מה להוכיח — זו טענת "או", ולהוכחתה מספיק להראות שאם צד אחד לא מתקיים אז השני מתקיים).

מקרה 1: $x\in V$. מכיוון ש-$G$ נטול קודקודים מבודדים, קיים $y\in V$ עם $xy\in E$. $U$ כיסוי בקודקודים, ולכן $xy\cap U\ne\emptyset$, כלומר $x\in U$ או $y\in U$. הנחנו $x\notin U$, ולכן $y\in U$. וכן $xy\in E\subseteq\hat E$. אז ל-$x$ יש שכן ב-$U$.

מקרה 2: $x\notin V$. אז $x$ הוא קודקוד שנוצר בשלב 1, כלומר קיימים $a,b\in V$ עם $ab\in E$ ו-$x=v_{ab}$. $U$ כיסוי בקודקודים, ולכן $a\in U$ או $b\in U$. מהבנייה $ax\in\hat E$ וגם $bx\in\hat E$. לכן בכל מקרה קיים $y\in\{a,b\}\cap U$, ו-$xy\in\hat E$ — כלומר ל-$x$ יש שכן ב-$U$.

בשני המקרים $x\in U$ או שקיים לו שכן ב-$U$; לכן $U$ שלטת ב-$\hat G$. וגודלה $|U|\le k$ לא השתנה. לכן $\langle\hat G,k\rangle\in\mathrm{DS}$.

כיוון ב': אם $\langle\hat G,k\rangle\in\mathrm{DS}$ אז $\langle G,k\rangle\in\mathrm{VC}$.

נניח שקיימת $\hat U\subseteq\hat V$ שלטת ב-$\hat G$ עם $|\hat U|\le k$.

כאן אי אפשר לקחת את $\hat U$ כמו שהיא ([01:18:11]) — היא אולי מכילה קודקודים חדשים, ולכן אפילו אינה מוכלת ב-$V$, ולכן ודאי אינה כיסוי בקודקודים של $G$. נבנה ממנה קבוצה $U\subseteq V$:

לכל $x\in\hat U$:

• אם $x\in V$ — נכניס את $x$ ל-$U$.
• אם $x\notin V$ — נכניס ל-$U$ אחד משכניו (לפי כלל שרירותי קבוע, למשל "הראשון לפי סדר הקידוד"; הבחירה אינה משנה).

$U$ מוכלת ב-$V$. לכל $x\in\hat U\setminus V$ שני שכניו הם קודקודים של $V$, ולכן הקודקוד שהכנסנו הוא ב-$V$. ובמקרה הראשון הכנסנו $x\in V$ עצמו.

חשבון הגודל. לכל איבר של $\hat U$ הכנסנו ל-$U$ לכל היותר איבר אחד, ולכן $|U|\le|\hat U|\le k$. (ייתכן שהכנסנו את אותו קודקוד פעמיים — למשל אם $v_{ab}$ ו-$v_{ac}$ שניהם ב-$\hat U$ ובשניהם נבחר $a$ — ואז $|U|$ קטן ממש; זה רק לטובתנו, כי אנחנו רוצים חסם עליון.)

$U$ היא כיסוי בקודקודים של $G$. תהי $xy\in E$ ונניח $x\notin U$; נראה $y\in U$.

ראשית, $x\notin U$ יחד עם $x\in V$ גורר $x\notin\hat U$ (אילו היה $x\in\hat U$, הרי $x\in V$, והבנייה הייתה מכניסה אותו ל-$U$).

כעת נתבונן בקודקוד $v_{xy}\in\hat V$ — הוא קיים, כי $xy\in E$ ולכן שלב 1 יצר אותו. $\hat U$ שלטת ב-$\hat G$, ולכן $v_{xy}\in\hat U$ או שקיים שכן של $v_{xy}$ ב-$\hat U$.

מקרה 1: $v_{xy}\in\hat U$. אז בבניית $U$ הכנסנו אחד משכניו — כלומר את $x$ או את $y$. מכיוון ש-$x\notin U$, בהכרח הכנסנו את $y$, ולכן $y\in U$.

מקרה 2: קיים שכן של $v_{xy}$ ב-$\hat U$. שכניו של $v_{xy}$ הם בדיוק $x$ ו-$y$, ושניהם ב-$V$. מכיוון ש-$x\notin\hat U$, בהכרח $y\in\hat U$; ומכיוון ש-$y\in V$, הבנייה הכניסה את $y$ עצמו ל-$U$, כלומר $y\in U$.

בשני המקרים $y\in U$, ולכן $xy\cap U\ne\emptyset$. מכיוון ש-$xy$ הייתה קשת שרירותית, $U$ היא כיסוי בקודקודים של $G$ בגודל $\le k$, ולכן $\langle G,k\rangle\in\mathrm{VC}$.

סיכום. $R$ רץ בזמן פולינומי ומקיים $\langle G,k\rangle\in\mathrm{VC}\iff R(\langle G,k\rangle)\in\mathrm{DS}$. לכן $\mathrm{VC}\le_p\mathrm{DS}$, ומכיוון ש-$\mathrm{VC}$ NP-קשה גם $\mathrm{DS}$ NP-קשה. יחד עם משפט 3, $\mathrm{DS}$ היא NP-שלמה. $\blacksquare$

מה עושה הקודקוד $v_{xy}$, בשורה אחת ([01:26:46]). הוא כופה על אחד מבין $x,y$ להיות בפנים. זו כל הרדוקציה: תרגום הדרישה "כל קשת נגועה" לדרישה "כל קודקוד נשלט", על ידי הפיכת כל קשת לקודקוד שדורש שליטה.

מלכודת: רדוקציה אינה פותרת ([00:59:59]). רדוקציה לעולם אינה מוצאת פתרון. היא מקבלת אינסטנס ומחזירה אינסטנס. האלגוריתם $R$ אינו יודע מהו $U$ ואינו יודע מהו $\hat U$ — אלה מופיעים רק בהוכחת הנכונות, שבה מותר לנו להניח שקיים פתרון ולבנות ממנו פתרון לצד השני. אותו דבר בדיוק קרה ברדוקציה $\mathrm{SAT}\le_p\mathrm{3SAT}$ בשיעור 8: האלגוריתם שיחק רק עם ההסגרים; ההשמות הופיעו רק בהוכחה ([01:29:32]).

משפט 5: בכל גרף בעל דרגה מינימלית $d$ קיימת קבוצה שלטת בגודל $\le\frac{\ln(d+1)+1}{d+1}|V|$

טענה. יהי $G=(V,E)$ גרף ותהי $d$ הדרגה המינימלית בו. אז קיימת ב-$G$ קבוצה שלטת בגודל לכל היותר $\frac{\ln(d+1)+1}{d+1}\cdot|V| .$

למה זה שונה מקודם. עד עכשיו הוכחנו קיום של אובייקט גדול (חתך גדול, הרבה הסגרים מסופקים). כאן אנחנו רוצים אובייקט קטן, ולכן נשתמש ב-$\Pr[X\le\mathbb{E}[X]]>0$ (למה 1) במקום ב-$\Pr[X\ge\mathbb{E}[X]]>0$.

למה לא לבחור קבוצה אחידה ([01:35:52]). אם נגריל $U$ אחידה מתוך $2^V$ — כמו במשפט 1 — אז כל קודקוד נכנס בהסתברות $\tfrac12$ ולכן $\mathbb{E}[|U|]=\tfrac{|V|}{2}$, שזה גרוע לחלוטין: אנחנו רוצים קבוצה קטנה. לכן נשתמש בהסתברות $p$ קטנה מ-$\tfrac12$, ונקבע אותה אחר כך.

הניסוי (אלגוריתם דו-שלבי). נסמן $p \;=\; \frac{\ln(d+1)}{d+1}\ \in (0,1) ,$ ונתחיל מ-$U=\emptyset$.

שלב 1 (אקראי). לכל קודקוד $v\in V$, באופן בלתי תלוי בכל השאר, נכניס את $v$ ל-$U$ בהסתברות $p$. שלב 2 (דטרמיניסטי, מתקן). לכל $x\in V$: אם $x$ וכל שכניו אינם ב-$U$ — נכניס את $x$ ל-$U$.

מרחב המדגם ומעל מה ההסתברות. מרחב המדגם הוא $\Omega=\{0,1\}^{V}$ — תוצאות $|V|$ המטבעות של שלב 1 — עם ההתפלגות שבה כל קואורדינטה היא $1$ בהסתברות $p$ בנפרד ובאופן בלתי תלוי. הגרף $G$ הוא קבוע; אין כאן הגרלת גרפים. כל התוחלות מעל מטבעות שלב 1.

נכונות בוודאות. הקבוצה $U$ שמתקבלת בסוף שלב 2 היא בהכרח קבוצה שלטת — לא בהסתברות כלשהי, אלא תמיד. הנימוק: יהי $x\in V$ ונניח בסוף התהליך ש-$x\notin U$. אז בפרט $x$ לא הוכנס בשלב 2, כלומר לא התקיים התנאי "$x$ וכל שכניו אינם ב-$U$" בזמן הבדיקה, כלומר ל-$x$ יש שכן שנכנס ב-$U$ (או ש-$x$ עצמו נכנס — בסתירה להנחה). לכן כל קודקוד הוא ב-$U$ או בעל שכן ב-$U$ ([01:42:52]).

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

פירוק הגודל. נסמן ב-$X$ את מספר הקודקודים שנכנסו ל-$U$ בשלב 1, וב-$Y$ את מספר הקודקודים שנכנסו בשלב 2. שני השלבים מכניסים קודקודים זרים (שלב 2 מכניס רק קודקודים שאינם ב-$U$), ולכן $|U| \;=\; X + Y .$

למה $Y$ עדיין אקראי, למרות ששלב 2 דטרמיניסטי ([01:44:00]). שלב 2 אינו מטיל מטבעות, אבל הקלט שלו אקראי: אילו קודקודים הוא צריך להוסיף תלוי לחלוטין במה שקרה בשלב 1. זהו מצב שכיח — חלק דטרמיניסטי של אלגוריתם שפועל על קלט אקראי, ולכן פלטו משתנה מקרי.

חישוב $\mathbb{E}[X]$. לכל $v\in V$ נסמן ב-$I_v$ את האינדיקטור למאורע "$v$ הוכנס ל-$U$ בשלב 1". אז $X=\sum_{v\in V}I_v$, ומלינאריות התוחלת $\mathbb{E}[X] \;=\; \sum_{v\in V}\mathbb{E}[I_v] \;=\; \sum_{v\in V}\Pr[I_v=1] \;=\; \sum_{v\in V} p \;=\; p\,|V| \;=\; \frac{\ln(d+1)}{d+1}\,|V| .$ (כאן, למרות שהמטבעות בלתי תלויים, לא השתמשנו באי-תלות כלל — לינאריות התוחלת לא דורשת אותה. אי-התלות תיכנס לראשונה בחישוב $\mathbb{E}[Y]$.)

חישוב $\mathbb{E}[Y]$. לכל $v\in V$ נסמן ב-$J_v$ את האינדיקטור למאורע "$v$ הוכנס ל-$U$ בשלב 2". אז $Y=\sum_{v\in V}J_v$ ומלינאריות התוחלת $\mathbb{E}[Y]=\sum_{v\in V}\mathbb{E}[J_v]$.

יהי $v\in V$. לפי הגדרת שלב 2, $J_v=1$ אם ורק אם לא $v$ ולא אף אחד משכניו נכנסו ל-$U$ בשלב 1. אלה $\deg(v)+1$ מטבעות שונים ובלתי תלויים (המטבע של $v$ ומטבעות $\deg(v)$ שכניו), וכל אחד מהם צריך להיכשל, כלומר לצאת "לא נכנס", בהסתברות $1-p$ כל אחד. לכן — וכאן, לראשונה, נכנסת אי-התלות בין הקודקודים — $\mathbb{E}[J_v] \;=\; \Pr[J_v=1] \;=\; (1-p)^{\deg(v)+1} .$

כעת נחסום מלמעלה בשלושה צעדים: $(1-p)^{\deg(v)+1} \;\overset{(a)}{\le}\; (1-p)^{d+1} \;\overset{(b)}{\le}\; \bigl(e^{-p}\bigr)^{d+1} \;=\; e^{-p(d+1)} \;\overset{(c)}{=}\; \frac{1}{d+1} .$

• (a) מכיוון ש-$d$ היא הדרגה המינימלית, מתקיים $\deg(v)\ge d$ ולכן $\deg(v)+1\ge d+1$; ומכיוון ש-$0<1-p<1$, העלאה בחזקה גדולה יותר רק מקטינה. (זו בדיוק הסיבה שהפרמטר הוא הדרגה המינימלית ולא המקסימלית.)
• (b) מאי-השוויון הסטנדרטי $1+x\le e^{x}$ לכל $x\in\mathbb{R}$, עם $x=-p$: $1-p\le e^{-p}$. שני האגפים חיוביים, ולכן מותר להעלות בחזקה חיובית ולשמור על הכיוון.
• (c) הצבת $p=\frac{\ln(d+1)}{d+1}$ נותנת $p(d+1)=\ln(d+1)$, ולכן $e^{-p(d+1)}=e^{-\ln(d+1)}=\frac{1}{d+1}$.

לכן $\mathbb{E}[Y] \;=\; \sum_{v\in V}\mathbb{E}[J_v] \;\le\; \sum_{v\in V}\frac{1}{d+1} \;=\; \frac{|V|}{d+1} .$

חיבור. מלינאריות התוחלת (גם $X$ ו-$Y$ תלויים זה בזה בצורה חזקה — ושוב, לא אכפת לנו): $\mathbb{E}\bigl[|U|\bigr] \;=\; \mathbb{E}[X]+\mathbb{E}[Y] \;\le\; \frac{\ln(d+1)}{d+1}|V| \;+\; \frac{1}{d+1}|V| \;=\; \frac{\ln(d+1)+1}{d+1}\,|V| .$

מתוחלת לקיום. נסמן $c=\frac{\ln(d+1)+1}{d+1}|V|$. לפי למה 1, $\Pr\bigl[\,|U|\le\mathbb{E}[|U|]\,\bigr]>0$, ומכיוון ש-$\mathbb{E}[|U|]\le c$ גם $\Pr\bigl[\,|U|\le c\,\bigr]>0$. לפי טענה (1) המאורע הזה אינו ריק, כלומר קיימת תוצאה של המטבעות שעבורה הקבוצה המתקבלת מקיימת $|U|\le c$. ומכיוון שהקבוצה המתקבלת היא תמיד שלטת (הראינו לעיל), זוהי קבוצה שלטת בגודל $\le c$. $\blacksquare$

הערה עדינה על סדר הטיעונים ([01:48:47]). סטודנט שאל למה לא לעצור אחרי שלב 1. התשובה: אחרי שלב 1 יש לי קבוצה קטנה אבל אין לי מושג אם היא שלטת, ולכן לא הוכחתי דבר. אילו הטענה שלי הייתה "לפחות", יכולתי לוותר על התיקון; אבל הטענה היא "לכל היותר", ולכן אני חייב לשלם על הפיכת הקבוצה לשלטת, והתשלום מופיע כתוספת $\mathbb{E}[Y]$.

הערה על כיוון החסמים ([01:53:04]). בחישוב $\mathbb{E}[Y]$ חסמנו מלמעלה. בפועל ייתכן ששלב 2 יכניס פחות קודקודים ממה שהחסם מרשה (למשל, ייתכן שקודקוד שנספר "נחסך" כי שכן שלו נכנס). זה בסדר גמור, כי אנחנו מוכיחים "לכל היותר": חסם עליון על התוחלת נותן קיום של אובייקט קטן לפחות כמוהו.

משפט 6: מאיפה הגיע $p=\frac{\ln(d+1)}{d+1}$

טענה. הערך $p=\frac{\ln(d+1)}{d+1}$ הוא הערך הממזער של החסם שהניתוח לעיל מייצר, כפונקציה של $p$.

הגזירה ([01:56:23]–[02:01:08]). נריץ את אותו ניתוח בדיוק עם $p\in(0,1)$ כללי, בלי להתחייב לערך. שלב 1 נותן $\mathbb{E}[X]=p|V|$, ושלב 2 נותן, באותם צעדים (a)+(b), $\mathbb{E}[Y] \;\le\; e^{-p(d+1)}|V| .$ לכן $\mathbb{E}\bigl[|U|\bigr] \;\le\; \bigl(p + e^{-p(d+1)}\bigr)\cdot|V| .$ $|V|$ הוא קבוע ביחס ל-$p$, ולכן נותר למזער את $f(p) \;=\; p + e^{-p(d+1)} .$ נגזור ונשווה לאפס: $f'(p) \;=\; 1 - (d+1)\,e^{-p(d+1)} \;=\; 0 \quad\Longleftrightarrow\quad e^{-p(d+1)} \;=\; \frac{1}{d+1}.$ ניקח $\ln$ משני האגפים: $-p(d+1) \;=\; \ln\frac{1}{d+1} \;=\; -\ln(d+1) \quad\Longleftrightarrow\quad p \;=\; \frac{\ln(d+1)}{d+1}.$ זו נקודת מינימום, כי הנגזרת השנייה $f''(p) \;=\; (d+1)^2\,e^{-p(d+1)} \;>\; 0$ חיובית לכל $p$ (הפונקציה קמורה). הצבת ה-$p$ הזה ב-$f$ נותנת $f(p) \;=\; \frac{\ln(d+1)}{d+1} + \frac{1}{d+1} \;=\; \frac{\ln(d+1)+1}{d+1},$ שזה בדיוק החסם של משפט 5. $\blacksquare$

מה כן "הגיע מהשמיים" ([02:00:03]). לא ה-$p$ — הוא נגזר. מה שהגיע מבחוץ הוא הסכמה: הרעיון להכניס כל קודקוד בהסתברות כלשהי ואז לתקן. הסכמה הזו סבירה מאוד ("אנחנו עושים את זה הרבה"), ואחרי שקבעו אותה, ה-$p$ האופטימלי הוא תרגיל חדו"א. שימו לב גם להבחנה שנעשתה בדקה האחרונה: $p$ הוא הארגומנט האופטימלי, לא הערך האופטימלי; הערך האופטימלי הוא $f(p)$.

דוגמאות ותרגילים מהשיעור

דוגמה 1: מעקב מלא אחרי הניסוי האחיד של משפט 1

יהי $G$ המסלול $V=\{a,b,c\}$, $E=\{ab,\ bc\}$, כלומר $|V|=3$, $|E|=2$. מרחב המדגם הוא $\Omega=2^V$ ובו $2^3=8$ קבוצות. נחשב את $X(U)$ לכל אחת: