הצגת המקור של הדף "משפט ברירת זמן העצירה"

{{סימון מתמטי}}

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

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

==זמן עצירה==

{{ערך מורחב|זמן עצירה}}

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

<math display="block">F_n = \sigma \left( M_1,...,M_n \right) \subset \mathcal{F}</math>

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

==נוסח המשפט==

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

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

===הוכחה===

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

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

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

==שימוש==

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

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

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

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

<math display="block">\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)</math>

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

<math display="block">\mathbb{P} \left( \tau_0 < \tau_k \right) = \frac{1}{k}</math>

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

<math display="block">\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}</math>

ולכן בהכרח <math>\mathbb{P} \left( \tau_0 < \infty \right) = 1</math>, כלומר ההילוך נשנה.

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

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