משפט ברירת זמן העצירה

בערך זה נעשה שימוש בסימנים מוסכמים מתחום המתמטיקה. להבהרת הסימנים ראו סימון מתמטי.

בתורת ההסתברות, משפט ברירת זמן העצירה (באנגלית: Optional Stopping Time Theorem) של ג'וזף דוּבּ, מתאר עיקרון יסודי לגבי תוחלת של מרטינגל, בו עצירת המרטינגל קבועה מראש לפי כלל עצירה כלשהו. המשפט קובע שבתנאים מסוימים, כלל העצירה אינו יכול להגדיל את התוחלת.

באופן מוחשי יותר, משפט זה עוסק בתוחלת הרווח של סדרת הימורים, בהם המהמר יכול לעצור בכל שלב לפי כלל שהוא קובע מראש. למשל, המהמר יכול להחליט שהוא יעזוב עם הכסף שבידיו ברגע שהרווח שלו מגיע לסכום כלשהו שנקבע מראש. המשפט סותר כשל מחשבתי רווח, וקובע שאם מהמר נכנס לקזינו עם סכום מסוים, אז תוחלת הרווח שלו תחת כל כלל עצירה - היא בדיוק הסכום אתו הוא נכנס לקזינו. זהו הנימוק המתמטי לכשל הטמון בשיטת ההימורים המכונה "מרטינגל".

זמן עצירה

ערך מורחב – זמן עצירה

יהי ${\displaystyle \left(\Omega ,{\mathcal {F}},\mathbb {P} \right)}$ מרחב הסתברות, ויהי ${\displaystyle \left\{M_{n}\right\}_{n=1}^{\infty }}$ מרטינגל במרחב זה. נגדיר לכל ${\displaystyle n\in \mathbb {N} }$ את התת-סיגמא אלגברה,

$${\displaystyle F_{n}=\sigma \left(M_{1},...,M_{n}\right)\subset {\mathcal {F}}}$$

ונאמר כי משתנה מקרי ${\displaystyle \tau :\Omega \to \mathbb {N} \cup {\infty }}$ הוא זמן עצירה, אם ${\displaystyle \left\{\tau =n\right\}\in F_{n}}$ לכל ${\displaystyle n\in \mathbb {N} }$. כלומר, המאורע ${\displaystyle \left\{\tau =n\right\}}$, נקבע במלואו לפי המידע שבידינו בשלב ה-${\displaystyle n}$.

נוסח המשפט

לכל זמן עצירה ${\displaystyle \tau }$, מתקיים כי ${\displaystyle M_{\tau }}$ הוא משתנה מקרי בהסתברות 1. כמו כן, מתקיים עבור תוחלתו, $${\displaystyle \mathbf {E} \left[M_{\tau }\right]=\mathbf {E} \left[M_{0}\right]}$$

בתנאי שמתקיים לפחות אחד משלושת התנאים הבאים:

1. קיים קבוע ${\displaystyle C\in \mathbb {R} }$ שעבורו ${\displaystyle \tau \leq C}$ בהסתברות 1.
2. ${\displaystyle \tau <\infty }$ בהסתברות 1, וגם קיים קבוע ${\displaystyle C\in \mathbb {R} }$ שעבורו ${\displaystyle \left|M_{n}\right|\leq C}$ בהסתברות 1 לכל ${\displaystyle n\leq \tau }$.
3. ${\displaystyle \mathbf {E} \left[\tau \right]<\infty }$, וגם קיים קבוע ${\displaystyle C\in \mathbb {R} }$ שעבורו ${\displaystyle \left|M_{n+1}-M_{n}\right|<C}$ בהסתברות 1 לכל ${\displaystyle n\leq \tau }$.

הוכחה

טענה: אם ${\displaystyle \left\{M_{n}\right\}_{n=1}^{\infty }}$ מרטינגל, אזי ${\displaystyle \mathbf {E} \left[M_{n}\right]=\mathbf {E} \left[M_{0}\right]}$ לכל ${\displaystyle n\in \mathbb {N} }$.

טענה: יהי ${\displaystyle \left\{M_{n}\right\}_{n=1}^{\infty }}$ מרטינגל ו-${\displaystyle \tau }$ זמן עצירה כלשהו. נגדיר ${\displaystyle X_{n}:=M_{\min(\tau ,n)}}$ לכל ${\displaystyle n\in \mathbb {N} }$. אזי ${\displaystyle \left\{X_{n}\right\}_{n=1}^{\infty }}$ הוא מרטינגל.

נשתמש בטענות אלה כדי להוכיח את המשפט עבור שלושת התנאים:

1. נשים לב כי בהתקיים תנאי 1, אז בהסתברות 1 ${\displaystyle X_{C}=M_{\min(\tau ,C)}=M_{\tau }}$, ולכן נובע מהטענות שהזכרנו כי ${\displaystyle \mathbf {E} [M_{\tau }]=\mathbf {E} [X_{C}]=\mathbf {E} [X_{0}]=\mathbf {E} [M_{0}]}$.
2. נשים לב כי בהתקיים תנאי 2, אז בהסתברות 1 ${\displaystyle \lim _{n\to \infty }M_{\min(\tau ,n)}=M_{\tau }}$. לכן ממשפט ההתכנסות החסומה נובע כי, $${\displaystyle \mathbf {E} [M_{0}]=\mathbf {E} [M_{\min(\tau ,n)}]\to \mathbf {E} [M_{\tau }]{\text{ as }}n\to \infty }$$
3. נשים לב כי בהתקיים תנאי 3, אז בהסתברות 1 מתקיים לכל ${\displaystyle n\in \mathbb {N} }$, $${\displaystyle \left|M_{n}\right|=\left|M_{0}+\sum _{k=1}^{n}\left(M_{k}-M_{k-1}\right)\right|\leq \left|M_{0}\right|+\sum _{k=1}^{n}\left|M_{k}-M_{k-1}\right|\leq \left|M_{0}\right|+n\cdot C}$$ ולכן בפרט, ${\displaystyle \left|X_{\min(\tau ,n)}\right|\leq \left|X_{0}\right|+\min(\tau ,n)\cdot C\leq \left|X_{0}\right|+\tau \cdot C}$ נשים לב כי צד ימין של אי השוויון הוא משתנה מקרי בעל תוחלת, ולכן ממשפט ההתכנסות הנשלטת נובע כי, ${\displaystyle \mathbf {E} [M_{0}]=\mathbf {E} [M_{\min(\tau ,n)}]\to \mathbf {E} [M_{\tau }]{\text{ as }}n\to \infty }$

שימוש

ממשפט זה ניתן להסיק למשל שהילוך מקרי פשוט על ${\displaystyle \mathbb {Z} }$ הוא נשנה, באופן הבא:

נניח כי ההילוך הוא ${\displaystyle \left\{S_{n}\right\}_{n=1}^{\infty }}$ ומתחיל בנקודה ${\displaystyle S_{0}=1}$. נרצה להראות כי בהסתברות ${\displaystyle 1}$ ההילוך יגיע לנקודה ${\displaystyle 0}$ תוך זמן סופי.

לכל ${\displaystyle k\in \mathbb {Z} }$ נגדיר זמן עצירה מתאים לו, על ידי ${\displaystyle \tau _{k}=\inf \left\{n\in \mathbb {N} \mid S_{n}=k\right\}}$. עבור ${\displaystyle k>0}$ שלם כלשהו, נחשב את ההסתברות שההילוך המקרי יפגע ב-${\displaystyle k}$ לפני שיפגע ב-${\displaystyle 0}$. לשם כך נגדיר זמן עצירה חדש ${\displaystyle \tau =\min \left\{\tau _{0},\tau _{k}\right\}}$, ונשים לב כי מהמשפט נובע שמתקיים ${\displaystyle \mathbf {E} \left[S_{\tau }\right]=\mathbf {E} \left[S_{0}\right]=1}$.

מצד שני, על ידי חישוב ישיר של התוחלת,

$${\displaystyle \mathbf {E} \left[S_{\tau }\right]=0\cdot \mathbb {P} \left(\tau _{0}\leq \tau _{k}\right)+k\cdot \mathbb {P} \left(\tau _{k}<\tau _{0}\right)=k\cdot \mathbb {P} \left(\tau _{k}<\tau _{0}\right)}$$

ולכן נובע בסך הכל,

$${\displaystyle \mathbb {P} \left(\tau _{0}<\tau _{k}\right)={\frac {1}{k}}}$$

מכאן נובע כי לכל ${\displaystyle k>0}$,

$${\displaystyle \mathbb {P} \left(\tau _{0}<\infty \right)\geq \mathbb {P} \left(\tau <\infty \right)-\mathbb {P} \left(\tau _{k}<\tau _{0}\right)=1-{\frac {1}{k}}}$$

ולכן בהכרח ${\displaystyle \mathbb {P} \left(\tau _{0}<\infty \right)=1}$, כלומר ההילוך נשנה.

ראו גם

• מרטינגל (תורת ההסתברות)
• מרטינגל (שיטת הימורים)