שרשרת מרקוב

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

שרשרת מרקוב לתיאור מזג האוויר

שרשרת מרקוב היא מודל הסתברותי המשמש בדרך-כלל לתיאור התפתחות של תהליכים כסדרה של מצבים.

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

בתור דוגמה ננסה לתאר מודל פשטני של מזג האוויר כשרשרת מרקוב. נניח שאנו מעוניינים לתאר את מזג האוויר במשך שבוע, כסדרה של 7 מצבים (מצב לכל יום): בהיר, מעונן או גשום. על מנת להפוך תיאור זה למודל הסתברותי, עלינו להגדיר התפלגות על מרחב הסדרות, כלומר להתאים הסתברות להתרחשותה של כל סדרה של 7 מצבים. למשל, ייתכן שהמודל שלנו יתאים לסדרה

"גשום, גשום, מעונן, בהיר, בהיר, בהיר, בהיר"

הסתברות 0.01, ולסדרה הקבועה

"גשום, גשום, ... גשום"

הסתברות 0.2, וכך הלאה.

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

תוכן עניינים

1 הגדרה מדויקת וחישוב ההתפלגות
2 דוגמאות לשרשראות מרקוב
- 2.1 המקרה הקלאסי
- 2.2 שרשרת מרקוב הפוכה
  - 2.2.1 דוגמה לתהליך לא מרקובי
3 הערות שוליים
4 קישורים חיצוניים

[עריכה] הגדרה מדויקת וחישוב ההתפלגות

שרשרת מרקוב היא תהליך סטוכסטי, כלומר סדרה של משתנים מקריים $X_0,X_1,X_2,\ldots$ המקיימת את תכונת מרקוב: ההתפלגות של המשתנה המקרי ה- n+1-י בהינתן המשתנים שקדמו לו, שווה להתפלגותו בהינתן המשתנה ה- n-י בלבד:

$\Pr(X_{n+1}=j|X_0=i_0, X_1=i_1,\ldots, X_n=i_n) = \Pr(X_{n+1}=j|X_n=i_n)\,$

במאמר זה נתמקד במקרה שהמשתנים המקריים מקבלים ערכים בקבוצה $\{1,2,\ldots,N\}$ , ואז ניתן לחשוב על הערך של השרשרת כהילוך מקרי על קבוצה סופית כלשהי של מצבים.

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

1. מספר המצבים $N$ ,

2. וקטור ההתפלגות ההתחלתית, כלומר ההתפלגות של $\ X_0$ , שנסמנה ב- $\vec q_0$ כאשר $(\vec q_0)_j=\Pr(X_0=j)$

3. סדרה של מטריצות NxN, שנסמנן $P_1,P_2,\ldots$ , המגדירות את הסתברויות המעבר, כך ש: $[P_t]_{ij}=\Pr(X_t=i|X_{t-1}=j)$ ,

ההסתברות לראות סדרה סופית כלשהי של מצבים, $i_0,i_1,\ldots,i_L$ נתונה על-ידי: $q_{i_0} \prod_{t=1}^{L} [P_t]_{i_ti_{t-1}}$

באופן דומה ניתן לחשב את ההסתברות לכל מאורע במרחב הסדרות (האינסופיות).

ההתפלגות של המשתנה $X k$ נתונה על-ידי הווקטור $\vec q_k = (\prod_{t=1}^kP_t)\ \vec q_0$

[עריכה] דוגמאות לשרשראות מרקוב

[עריכה] המקרה הקלאסי

במקרה הפשוט ביותר, שרשרת מרקוב מתוארת לפי שלושת הפרמטרים המוגדרים בסעיף הקודם. למשל בתרשים מתוארת השרשרת עם הפרמטרים הבאים:

$\vec q_0 = \begin{bmatrix} 1/3 \\ 1/3 \\ 1/3\end{bmatrix}$ ו- $P_t = \begin{bmatrix} 0.3& 0.1 & 0 \\ 0.5 & 0.45 & 0.3 \\ 0.2&0.45&0.7\end{bmatrix}$ לכל t.

באופן כללי, הסתברויות המעבר יכולות להשתנות עם הזמן.

[עריכה] שרשרת מרקוב הפוכה

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

האם תהליך כזה ^[1] יכול לקיים את תכונת מרקוב? (חשוב לשים לב, שהתכונה עדיין בוחנת את ההסתברויות למצב בכל יום בהינתן המצב ביום שלפניו. הגדרת התכונה "לא מודעת" לכך שבחרנו להפוך את סדר ההגרלה).

מתברר שהתשובה היא חיובית. יתר-על-כן, ניתן להגדיר וקטור התפלגות למצב מזג האוויר ביום שבת, והסתברויות מעבר "אחורה בזמן" כך שההתפלגות המתקבלת תהיה זהה לזו שבדוגמה מהסעיף הקודם ^[2]. בפרט, היא בוודאי תקיים את תכונת מרקוב. למעשה, ניתן להראות בעזרת חוק בייס, שכל תהליך "מרקובי הפוך" כזה יקיים את תכונת מרקוב, בתנאי שההסתברות להיות בכל מצב לא מתאפסת בשום זמן, כלומר אם $\forall {t,j} \Pr(X_t=j) \neq 0$ .

[עריכה] דוגמה לתהליך לא מרקובי

נניח שמזג האוויר בשבוע הראשון מוגרל כך שסדרת המצבים

"גשום, גשום, גשום ... גשום"

מופיעה בהסתברות 0.5, בעוד ששאר האפשרויות לסדרת מצבי מזג האוויר בשבוע הראשון מוגרלות בהסתברות שווה (כלומר, בהסתברות $\ 0.5/(3^7-1)$ כל אחת). לאחר יום שבת, מזג האוויר מוגרל כמו בדוגמה הקודמת - כל פעם על סמך היום הקודם.

השוויון המופיע בהגדרת תכונת מרקוב אומנם מתקיים ביום שני בשבוע הראשון (ובאופן טריוויאלי גם ביום ראשון, ובכל הימים שלאחר השבוע הראשון), אך מיום שלישי ועד ליום שבת בשבוע הראשון הוא מופר. למשל, ההסתברות שיום שבת יהיה גשום בהינתן שיום שישי היה גשום היא $\ 5/6$ . בעוד שההסתברות לכך שיום שבת יהיה גשום בהינתן שמיום ראשון ועד יום שישי היה גשום, היא $\ 2188/2190$ , שזה יותר מ- 99.9%.

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

[עריכה] הערות שוליים

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