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

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

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

## זמן עצירה

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

F_n = \sigma \left( M_1,...,M_n \right) \subset \mathcal{F}

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

## נוסח המשפט

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

בתנאי שמתקיים לפחות אחד משלושת התנאים הבאים:
# קיים קבוע C \in \mathbb{R} שעבורו \tau \leq C בהסתברות 1.
# \tau  בהסתברות 1, וגם קיים קבוע C \in \mathbb{R} שעבורו \left| M_n \right| \leq C בהסתברות 1 לכל n \leq \tau.
# \mathbf{E} \left[ \tau \right] , וגם קיים קבוע C \in \mathbb{R} שעבורו \left| M_{n+1} - M_n \right|  בהסתברות 1 לכל n \leq \tau.

### הוכחה

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

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

נשתמש בטענות אלה כדי להוכיח את המשפט עבור שלושת התנאים:
# נשים לב כי בהתקיים תנאי 1, אז בהסתברות 1 X_C = M_{\min (\tau, C)} = M_{\tau}, ולכן נובע מהטענות שהזכרנו כי \mathbf{E} [ M_{\tau} ] = \mathbf{E} [ X_C ] = \mathbf{E} [X_0 ] = \mathbf{E} [M_0].
# נשים לב כי בהתקיים תנאי 2, אז בהסתברות 1 \lim_{n \to \infty} M_{\min(\tau, n)} = M_{\tau}. לכן ממשפט ההתכנסות החסומה נובע כי, \mathbf{E}[M_0] = \mathbf{E}[M_{\min(\tau, n)}] \to \mathbf{E}[M_{\tau}] \text{ as } n \to \infty
# נשים לב כי בהתקיים תנאי 3, אז בהסתברות 1 מתקיים לכל n \in \mathbb{N}, \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 ולכן בפרט, \left| X_{\min(\tau, n)} \right| \leq \left| X_0 \right| + \min(\tau, n) \cdot C \leq \left| X_0 \right| + \tau \cdot C נשים לב כי צד ימין של אי השוויון הוא משתנה מקרי בעל תוחלת, ולכן ממשפט ההתכנסות הנשלטת נובע כי, \mathbf{E}[M_0] = \mathbf{E}[M_{\min(\tau, n)}] \to \mathbf{E}[M_{\tau}] \text{ as } n \to \infty

## שימוש

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

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

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

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

\mathbf{E} \left[ S_\tau \right] = 0\cdot \mathbb{P} \left( \tau_0 \leq \tau_k\right) + k\cdot \mathbb{P}\left( \tau_k 

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

\mathbb{P} \left( \tau_0 

מכאן נובע כי לכל k>0,

\mathbb{P} \left( \tau_0 

ולכן בהכרח \mathbb{P} \left( \tau_0 , כלומר ההילוך נשנה.

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

קטגוריה:משפטים בתורת ההסתברות
קטגוריה:תהליכים סטוכסטיים