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

בתורת ההסתברות, משפט ברירת זמן העצירה (באנגלית: 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}$

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

ראו גם

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