שרשרת מרקוב

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

שרשרת מרקובאנגלית: Markov Chain) היא מודל הסתברותי המשמש בדרך-כלל לתיאור התפתחות של תהליכים כסדרה של מצבים.

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

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

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

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

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

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

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

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

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

ראו גם[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

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

קישורים חיצוניים[עריכת קוד מקור | עריכה]