שרשרת מרקוב

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

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

תוכן עניינים

1 מבוא
2 הגדרה מדויקת וחישוב ההתפלגות
3 דוגמאות לשרשראות מרקוב
4 הערות
5 קישורים חיצוניים

[עריכה] מבוא

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

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

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

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

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

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

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

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

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

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

שרשרת מרקוב היא תהליך סטוכסטי, כלומר סדרה של משתנים מקריים $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$ כל אחת). לאחר יום שבת, מזג האויר מוגרל כמו בדוגמה הקודמת - כל פעם על סמך היום הקודם.

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

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

[עריכה] הערות

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