שרשראות מרקוב הן כלי שימושי ביותר לתיאור תהליכים במגוון תחומים, כגון: תורת המשחקים, פיזיקה, עיבוד אותות וניתוח שפות טבעיות. נראה שהמתמטיקאי הרוסי אנדריי מרקוב, שחקר אותן לראשונה בתחילת המאה ה-20 ושעל שמו הן קרויות, התעניין בהן בשל הערך העיוני שלהן לתורת ההסתברות - הן איפשרו לו להכליל את משפט הגבול המרכזי למשתנים תלויים.
כדוגמה, ניתן לתאר דגם פשטני של מזג האוויר כשרשרת מרקוב. בניית הדגם יוצאת מהפשטה על פיה מזג האוויר מתואר במשך שבוע כסדרה של 7 מצבים (מצב לכל יום): בהיר, מעונן או גשום. על מנת להפוך תיאור זה למודל הסתברותי, יש להגדיר התפלגות במרחב הסדרות, כלומר להתאים הסתברות להתרחשותה של כל סדרה של 7 מצבים. מודל זה, למשל יכול להתאים לסדרה:
"גשום, גשום, מעונן, בהיר, בהיר, בהיר, בהיר"
הסתברות 0.01, ולסדרה הקבועה
"גשום, גשום, ... גשום"
הסתברות 0.2, וכך הלאה.
היסטוריה.
אנדריי מרקוב חקר שרשראות מרקוב בתחילת המאה ה-20. מרקוב התעניין בחקירת הרחבות של רצפים אקראיים בלתי תלויים. למרקוב הייתה מוטיבציה לחקור תחום זה בעקבות ויכוח עם פאבל נקראסוב שטען שאי-תלות היא תנאי הכרחי עבור החוק החלש של המספרים הגדולים.
במאמר הראשון שלו על שרשראות מרקוב, שפורסם ב-1906, מרקוב הראה שתחת תנאים מסוימים, הממוצעים של תוצאות השרשרת יתכנסו לווקטור ערכים, ועל ידי כך הוכח החוק החלש של המספרים הגדולים ללא הנחת אי-תלות, שנתפסה באותה העת כתנאי להוכחה.
ב-1912 חקר אנרי פואנקרה שרשראות מרקוב על קבוצות סופיות במטרה לחקור ערבוב קלפים. שימושים מוקדמים נוספים בשרשראות מרקוב כוללים מודל דיפוזיה, שהוצג על ידי פול וטטיאנה אהרנפסט ב-1907 ותהליך מסתעף, שהוצג על ידי פרנסיס גולטון והנרי ויליאם ווטסון ב-1873, לפני מחקרו של מרקוב. לאחר עבודתם של ווטסון וגאלטון, התגלה שהתהליכים המסתעפים שהם חקרו נחקרו כשלושה עשורים קודם לכן בצורה בלתי תלויה על ידי אירנה-ז'ול ביינאמה.
דגם מרקובי ומערכת מרקובית.
דגם מוגדר כדגם מרקובי ומערכת מוגדרת כמערכת מרקובית אם כל המידע בהווה, היכול לשמש לניבוי המצבים העתידיים, מתמצה במצב הנוכחי. משמעותו של תנאי זה, היא שאין צורך לזכור את מצבי העבר, שכן מידע זה לא יועיל בניבוי העתיד.
אינטואיטיבית, מודל מרקובי מתאר מערכת "חסרת זיכרון": מערכת שבה אין השפעות עקיפות של מצבים קודמים בסדרה, על מצבים עתידיים (השפעות "עקיפות" הן השפעות שאינן באות לידי ביטוי במצב הנוכחי).
הגדרת שרשרת מרקוב וחישוב ההתפלגות.
תכונת מרקוב.
שרשרת מרקוב היא תהליך סטוכסטי, כלומר סדרה של משתנים מקריים
formula_1
המקיימת את תכונת מרקוב: ההתפלגות של המשתנה המקרי ה- n+1-י בהינתן המשתנים שקדמו לו, שווה להתפלגותו בהינתן המשתנה ה- n-י בלבד:
formula_2
כאשר המשתנים המקריים מקבלים ערכים בקבוצה
formula_3.
שרשרת מרקוב המקיימת את תכונת מרקוב ניתנת לייצוג בעזרת אוטומט הסתברותי.
שרשרת מרקוב מסדר k.
שרשרת מרקוב מסדר k מתארת תהליך סטוכסטי שעבורו ההתפלגות של המשתנה המקרי הn+1-י בהינתן המשתנים שקדמו לו, שווה להתפלגותו בהינתן k המשתנים שקדמו לו:
formula_4
לפי הגדרה זו, תהליך סטוכסטי המקיים את תכונת מרקוב מהווה שרשרת מרקוב מסדר 1.
חישוב הסתברות מאורע במרחב הסדרות הסופיות.
ניתן לייצג את ערך השרשרת כהילוך אקראי בקבוצה סופית של מצבים.
תכונת מרקוב מאפשרת לתאר את התפלגות של סדרת המשתנים בצורה תמציתית.
הוכח כי ניתן להגדיר במלואה כל התפלגות של שרשרת מרקוב על ידי המקדמים הבאים:
1. מספר המצבים
formula_5
2. וקטור ההתפלגות ההתחלתית, כלומר ההתפלגות של
formula_6,
המסומנת ב-
formula_7
כאשר
formula_8
3. סדרה של מטריצות NxN, המסומנות
formula_9,
והמגדירות את הסתברויות המעבר, כך ש:
formula_10,
ההסתברות לקבלת סדרה סופית של מצבים,
formula_11 הנתונה על ידי:
formula_12
חישוב הסתברות מאורע במרחב הסדרות האינסופיות.
חישוב ההסתברות לכל מאורע במרחב הסדרות (האינסופיות), נעשה באופן דומה:
ההתפלגות של המשתנה
formula_13
נתונה על ידי הווקטור
formula_14
תכונות של שרשראות מרקוב.
הומוגניות בזמן.
שרשרת מרקוב נקראת הומוגנית בזמן אם מתקיים ש-formula_15 ללא תלות ב-formula_16. כלומר, כאשר ההסתברות לעבור ממצב למשנהו אינה תלויה בזמן ההגעה אליו.
לדוגמה, אם לאחר התקדמות של formula_17 שלבים בפעולת מערכת מרקובית ההסתברות לעבור ממצב formula_18 למצב formula_19 אינה זהה להסתברות המעבר אם כבר התבצעו 5 שלבים במערכת, השרשרת אינה הומוגנית בזמן.
לעומת זאת אם הסתברויות המעברים של כל המצבים אל שאר המצבים אינן משתנות בהתאם למספר השלבים שעברה המערכת, השרשרת הומוגנית בזמן.
פריקות.
שרשרת מרקוב נקראת אי פריקה אם מכל מצב בשרשרת ניתן להגיע אל כל שאר המצבים.
מצב ארגודי.
מצב formula_20 בשרשרת מרקוב יקרא מצב ארגודי אם לכל מצב formula_21 המקושר ל-formula_20 (כלומר קיים מסלול מ-formula_20 ל-formula_21) אז גם formula_20 מקושר ל-formula_21 (כלומר קיים מסלול מ-formula_21 ל-formula_20)
מחלקה בלתי פריקה.
מחלקה בלתי פריקה של מצבים מקיימת שעבור כל מצב formula_20 במחלקה ועבור כל מצב formula_21 במחלקה המצבים מקושרים וגם עבור כל formula_20 במחלקה ועבור formula_32 שאינו במחלקה אז formula_20 לא מקושר ל-formula_32 (אך ייתכן כי formula_32 מקושר ל-formula_20).
מחלקה בלתי פריקה היא מחלקת שקילות של מצבים ארגודים. שרשרת מרקוב בלתי פריקה מקיימת שכל המצבים בה הם ארגודים.
נשנות.
מצב formula_20 יקרא נשנה אם הסיכוי לחזור אליו מעצמו פעם נוספת הוא 1 כלומר formula_38 כאשר formula_39 מסמל את הסיכוי לחזור למצב הformula_20 לראשונה לאחר formula_32 צעדים. מצב שאינו נשנה יקרא מצב חולף.
נשים לב שמצב שאיננו ארגודי הוא חולף, אך המשפט ההפוך נכון רק עבור שרשראות סופיות. נשים לב שתכונה שקולה לנשנות היא formula_42 כאשר formula_43 מסמל את הסיכוי לחזור למצב הformula_20 לראשונה לאחר formula_32 צעדים.
משתי התכונות הללו ניתן להסיק כי נשנות היא תכונה מחלקתית. כלומר אם מצב formula_20 במחלקה בלתי פריקה הוא נשנה אז כל המצבים במחלקה הזו נשנים.
נשנות חיובית.
מצב formula_20 יקרא נשנה חיובית אם הוא נשנה ובנוסף מתקיים ש-formula_48 תוחלת זמן החזרה של המצב סופית. אחרת אם המצב נשנה ותוחלת זמן החזרה היא אינסופית המצב יקרא מצב נשנה אפס.
נשנות אפס ונשנות חיובית הן תכונות מחלקתיות.
בשרשראות סופיות כל המצבים הנשנים הם נשנים חיובית.
מחזוריות.
עבור מצב formula_20 נתבונן בformula_50 ונתבונן ב-formula_51 המחלק המשותף המקסימלי של האיברים בקבוצה. אם formula_52 נאמר שהמצב formula_20 הוא formula_51 מחזורי. אחרת, אם formula_55 נאמר שהשרשרת לא מחזורית.
נשים לב שמחזוריות היא תכונה מחלקתית אף היא ולכן עבור כל מצב formula_21 הנמצא במחלקה של formula_20 המצב formula_21 הוא formula_51 מחזורי אף הוא.
התפלגות סטציונרית.
עבור מצב נשנה ולא מחזורי formula_20 מתקיים שהגבול formula_61 קיים כאשר formula_62 .
עבור מטריצת מעבר מרקובית formula_63 אשר מצביה אינה מחזוריים מתקיים שעבור התפלגות מצבים formula_64 מתקיים formula_65
כלומר התפלגות מצבים זו היא וקטור עצמי בעל ערך עצמי formula_66 של formula_63 ועל כן נקראת התפלגות סטציונרית.
עבור תהליך מרקובי אי פריק שכל מצביו נשנים חיובית ולא מחזוריים ההתפלגות הסטציונרית היא יחידה ושווה ל-formula_68.
עבור ההתפלגות הסטציונרית מתקיים כי עבור כל מצב formula_20 מתקיים כי formula_70
כאשר השרשרת היא לא מחזורית ובלתי פריקה, התפלגות המצבים תשאף להתפלגות הסטציונרית, ללא תלות בוקטור התפלגות המצבים ההתחלתי.
תנאי האיזון המפורט.
תנאי האיזון המפורט דורש תנאי חזק יותר על ההתפלגות הסטציונרית formula_71. כאשר תנאי זה מתקיים השרשרת תקרא שרשרת מרקוב הפיכה.
דוגמאות לשרשראות מרקוב.
המקרה הקלאסי.
לעיתים, שרשרת מרקוב מתוארת לפי הסתברויות המעברים בין המצבים בעזרת וקטור המייצג את ההסתברויות להתחיל את המערכת בהתאם לכל מצב, ובעזרת מטריצה המתאימה את ההסתברויות לעבור מהמצב בשורה ה-i (כל שורה מסתכמת ל-1) למצב בטור ה-j. למשל, בתרשים המובא בפתיח הערך מתוארת השרשרת עם וקטור המצבים ההתחלתיים ומטריצת המעברים הבאים:
בהגדרה כללית, הסתברויות המעבר יכולות להשתנות עם הזמן.
שרשרת מרקוב הפיכה.
לעיתים, תהליכים שלכאורה אינם מרקוביים מקיימים את תכונת מרקוב.
לדוגמה, מערכת כזו היא מערכת מזג אוויר אשר מנתחים אותה על ידי בניית דגם של מצביה לאחור בזמן. במקום להגריל את מצב מזג האוויר ביום הראשון ולאחר מכן ביום השני, מגרילים את מצב מזג האוויר בדגם, ליום האחרון, ולאחריו לאחור, ליום שקדם לו. כל יום, על סמך הנתונים ביום שלאחריו על פי הסתברויות-מעבר שנקבעו מראש. תהליך בניית דגם מסוג זה יכול לקיים את תכונת מרקוב.
יתר-על-כן, ניתן להגדיר וקטור התפלגות למצב מזג האוויר ביום האחרון וכן הסתברויות מעבר "אחורה בזמן", כך שההתפלגות המתקבלת תהיה זהה לדגם המחושב קדימה. מערכת זו מקיימת את תכונת מרקוב.
בעזרת חוק בייס הוכח שכל תהליך "מרקובי הפיך" מסוג זה מקיים את תכונת מרקוב, בתנאי שההסתברות לכל מצב אינה מתאפסת באף אחת מנקודות הזמן.
formula_74.
דוגמה לתהליך לא מרקובי.
בהנחה שמזג האוויר בשבוע הראשון מוגרל כך שסדרת המצבים
"גשום, גשום, גשום, ..., גשום"