שרשרת מרקוב

היסטוריה

אנדריי מרקוב חקר שרשראות מרקוב בתחילת המאה ה-20. מרקוב התעניין בחקירת הרחבות של רצפים אקראיים בלתי תלויים. למרקוב הייתה מוטיבציה לחקור תחום זה בעקבות ויכוח עם פאבל נקראסוב שטען שאי-תלות היא תנאי הכרחי עבור החוק החלש של המספרים הגדולים.
במאמר הראשון שלו על שרשראות מרקוב, שפורסם ב-1906, מרקוב הראה שתחת תנאים מסוימים, הממוצעים של תוצאות השרשרת יתכנסו לווקטור ערכים, ועל ידי כך הוכח החוק החלש של המספרים הגדולים ללא הנחת אי-תלות, שנתפסה באותה העת כתנאי להוכחה.
ב-1912 פואנקרה חקר שרשראות מרקוב על קבוצות סופיות במטרה לחקור ערבוב קלפים. שימושים מוקדמים נוספים בשרשראות מרקוב כוללים מודל דיפוזיה, שהוצג על ידי פול וטטיאנה אהרנפסט ב-1907 ותהליך מסתעף, שהוצג על ידי פרנסיס גאלטון והנרי ויליאם ווטסון ב-1873, לפני מחקרו של מרקוב. לאחר עבודתם של גאלטון וווטסון, התגלה שהתהליכים המסתעפים שהם חקרו נחקרו כשלושה עשורים קודם לכן בצורה בלתי תלויה על ידי אירנה-ז'ול ביינאמה.

דגם מרקובי ומערכת מרקובית

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

תכונת מרקוב

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

שרשרת מרקוב מסדר k

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

חישוב הסתברות מאורע במרחב הסדרות הסופיות

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

כאשר
3. סדרה של מטריצות NxN, המסומנות
,
והמגדירות את הסתברויות המעבר, כך ש:
,
ההסתברות לקבלת סדרה סופית של מצבים,
 הנתונה על ידי:

חישוב הסתברות מאורע במרחב הסדרות האינסופיות

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

נתונה על ידי הווקטור

הומוגניות בזמן

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

פריקות

שרשרת מרקוב נקראת אי פריקה אם מכל מצב בשרשרת ניתן להגיע אל כל שאר המצבים.

שרשרת מרקוב הפיכה

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

דוגמה לתהליך לא מרקובי

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