שרשרת מרקוב

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

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

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

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

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

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

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

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

היסטוריה

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

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

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

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

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

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

הגדרת שרשרת מרקוב וחישוב ההתפלגות

תכונת מרקוב

שרשרת מרקוב היא תהליך סטוכסטי, כלומר סדרה של משתנים מקריים $X_{0},X_{1},X_{2},\ldots$ המקיימת את תכונת מרקוב: ההתפלגות של המשתנה המקרי ה- n+1-י בהינתן המשתנים שקדמו לו, שווה להתפלגותו בהינתן המשתנה ה- n-י בלבד: $$\Pr(X_{n+1}=j|X_{n}=i_{n})\,=\Pr(X_{n+1}=j|X_{0}=i_{0},X_{1}=i_{1},\ldots ,X_{n}=i_{n})$$

כאשר המשתנים המקריים מקבלים ערכים בקבוצה $\{1,2,\ldots ,N\}$.

שרשרת מרקוב המקיימת את תכונת מרקוב ניתנת לייצוג בעזרת אוטומט הסתברותי.

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

שרשרת מרקוב מסדר k מתארת תהליך סטוכסטי שעבורו ההתפלגות של המשתנה המקרי הn+1-י בהינתן המשתנים שקדמו לו, שווה להתפלגותו בהינתן k המשתנים שקדמו לו: $$\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-k+1}=i_{n-k+1},X_{n-k+2}=i_{n-k+2},\ldots ,X_{n}=i_{n})\,$$

לפי הגדרה זו, תהליך סטוכסטי המקיים את תכונת מרקוב מהווה שרשרת מרקוב מסדר 1.

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

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

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

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

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_{t}i_{t-1}}$

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

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

ההתפלגות של המשתנה $X_{k}$ נתונה על ידי הווקטור ${\vec {q}}_{k}=\left(\prod _{t=1}^{k}P_{t}\right){\vec {q}}_{0}$

תכונות של שרשראות מרקוב

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

שרשרת מרקוב נקראת הומוגנית בזמן אם מתקיים ש-${\textstyle \Pr(X_{n+1}=j|X_{n}=i_{n})\,}$ ללא תלות ב-${\textstyle n}$. כלומר, כאשר ההסתברות לעבור ממצב למשנהו אינה תלויה בזמן ההגעה אליו.

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

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

פריקות

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

מצב ארגודי

מצב $i$ בשרשרת מרקוב יקרא מצב ארגודי אם לכל מצב $j$ המקושר ל-$i$ (כלומר קיים מסלול מ-$i$ ל-$j$) אז גם $i$ מקושר ל-$j$ (כלומר קיים מסלול מ-$j$ ל-$i$)

מחלקה בלתי פריקה

מחלקה בלתי פריקה של מצבים מקיימת שעבור כל מצב $i$ במחלקה ועבור כל מצב $j$ במחלקה המצבים מקושרים וגם עבור כל $i$ במחלקה ועבור $k$ שאינו במחלקה אז $i$ לא מקושר ל-$k$ (אך ייתכן כי $k$ מקושר ל-$i$).

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

נשנות

מצב $i$ יקרא נשנה אם הסיכוי לחזור אליו מעצמו פעם נוספת הוא 1 כלומר $\textstyle \sum _{k=1}^{\infty }\displaystyle f_{i,i}^{(k)}=1$ כאשר $f_{i,i}^{(k)}$ מסמל את הסיכוי לחזור למצב ה$i$ לראשונה לאחר $k$ צעדים. מצב שאינו נשנה יקרא מצב חולף.

נשים לב שמצב שאיננו ארגודי הוא חולף, אך המשפט ההפוך נכון רק עבור שרשראות סופיות. נשים לב שתכונה שקולה לנשנות היא $\textstyle \sum _{k=1}^{\infty }\displaystyle P_{i,i}^{(k)}=\infty$ כאשר $P_{i,i}^{(k)}$ מסמל את הסיכוי לחזור למצב ה$i$ לאחר $k$ צעדים.

משתי התכונות הללו ניתן להסיק כי נשנות היא תכונה מחלקתית. כלומר אם מצב $i$ במחלקה בלתי פריקה הוא נשנה אז כל המצבים במחלקה הזו נשנים.

נשנות חיובית

מצב $i$ יקרא נשנה חיובית אם הוא נשנה ובנוסף מתקיים ש-$E_{i}$ תוחלת זמן החזרה של המצב סופית. אחרת אם המצב נשנה ותוחלת זמן החזרה היא אינסופית המצב יקרא מצב נשנה אפס.

נשנות אפס ונשנות חיובית הן תכונות מחלקתיות.

בשרשראות סופיות כל המצבים הנשנים הם נשנים חיובית.

מחזוריות

עבור מצב $i$ נתבונן ב$\{k\mid P_{ii}^{(k)}>0\}$ ונתבונן ב-$d_{i}$ המחלק המשותף המקסימלי של האיברים בקבוצה. אם $d_{i}\neq 1$ נאמר שהמצב $i$ הוא $d_{i}$ מחזורי. אחרת, אם $d_{i}=1$ נאמר שהשרשרת לא מחזורית.

נשים לב שמחזוריות היא תכונה מחלקתית אף היא ולכן עבור כל מצב $j$ הנמצא במחלקה של $i$ המצב $j$ הוא $d_{i}$ מחזורי אף הוא.

התפלגות סטציונרית

עבור מצב נשנה ולא מחזורי $i$ מתקיים שהגבול $\textstyle \lim _{k\to \infty }\displaystyle P_{i,i}^{(k)}=\pi _{i}$ קיים כאשר $\pi _{i}={\frac {1}{E_{i}}}$ .

עבור מטריצת מעבר מרקובית $M$ אשר מצביה אינה מחזוריים מתקיים שעבור התפלגות מצבים ${\vec {V}}={\begin{pmatrix}\pi _{1}\\\pi _{2}\\\pi _{3}\\\vdots \end{pmatrix}}$ מתקיים $M{\vec {V}}={\vec {V}}$

כלומר התפלגות מצבים זו היא וקטור עצמי בעל ערך עצמי $1$ של $M$ ועל כן נקראת התפלגות סטציונרית.

עבור תהליך מרקובי אי פריק שכל מצביו נשנים חיובית ולא מחזוריים ההתפלגות הסטציונרית היא יחידה ושווה ל-${\vec {V}}$.

עבור ההתפלגות הסטציונרית מתקיים כי עבור כל מצב $i$ מתקיים כי $\pi _{i}=\sum _{j}\displaystyle P_{j,i}\pi _{j}$

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

תנאי האיזון המפורט

תנאי האיזון המפורט דורש תנאי חזק יותר על ההתפלגות הסטציונרית $P_{i,j}\pi _{i}=P_{j,i}\pi _{j}$. כאשר תנאי זה מתקיים השרשרת תקרא שרשרת מרקוב הפיכה.

דוגמאות לשרשראות מרקוב

המקרה הקלאסי

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

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

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

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

לעיתים, תהליכים שלכאורה אינם מרקוביים מקיימים את תכונת מרקוב.

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

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

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

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

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

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

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

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

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

שימושים לשרשראות מרקוב

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

דוגמאות למודלים אשר מהווים שרשראות מרקוב:

בפיזיקה

• מודל ארנפסט:

מודל המתאר את הדיפוזיה של $N$ חלקיקים בין שני מיכלים זהים. המודל מתאר זאת כתהליך לידה ומוות מרקובי בעל $N+1$ מצבים וההנחה שלכל היותר מעבר יחיד מתרחש בכל צעד. הסתברות המעבר מהמצב ה$i$ למצב ה$i+1$ היא $P_{i,i+1}=(N-i)\lambda$ והסתברות המעבר מהמצב ה$i$ למצב ה$i-1$ היא $P_{i,i-1}=i\lambda$ כאשר $\lambda$ הוא קצב החלפת המיכל של חלקיק.

כאשר אנחנו במצב שיווי משקל התהליך הפיך ולכן נדרוש קיום של תנאי האיזון המפורט. כלומר ש$P_{i,j}\pi _{i}=P_{j,i}\pi _{j}$ נקבל ש$P_{i,i+1}\pi _{i}=P_{i+1,i}\pi _{i+1}$ ממשוואה זו נקבל באינדוקציה כי $\pi _{i}={\binom {N}{i}}\pi _{0}$

מכיוון שאנחנו דורשים שהווקטור יתאר התפלגות הסתברות נדרוש כי $\sum _{i=0}^{N}\pi _{i}=1$ על ידי שימוש בנוסחא $2^{n}=\sum _{k=0}^{n}{n \choose k}$ נקבל כי $\pi _{i}=2^{-N}{N \choose i}$. כאשר $\pi _{i}$ ייצג את פרק הזמן היחסי שבו יהיו במיכל $i$ חלקיקים. באופן דומה ניתן להתייחס לכמות הכדורים בכל מיכל כאל טמפרטורת המיכל ובכך לקבל תיאור סטטיסטי של מעבר חום במקום תיאור קלאסי. עקב העובדה שהשרשרת במודל זה הם מחזוריים (בעלי מחזור 2) וקטור ההתפלגות אינו יתכנס להתפלגות הסטציונרית ללא תלות במצב ההתחלתי אלא יבצע תנודות סביבה. למרות זאת בשנת 1947 הוכיח מארק קארק כי עבור מצב התחלתי השונה ממצב שיווי המשקל מתקיים כי האנטרופיה מונוטונית עולה (תאוריית H). ובכך בעצם המודל מהווה הסבר לחוק השני של התרמודינמיקה ופותר את הפרדוקס הנוצר מההפיכות המיקרוסקופית הנובעת מחוקי ניוטון לבין החוק השני של התרמודינמיקה. מודל דומה נוסף הוא מודל ברנולי לפלס המאפשר מהלך ללא מעבר של חלקיקים בין המיכלים ובכך יוצרים שרשרת בלתי פריקה לא מחזורית ובכך מתקיים שוקטור ההתפלגות במודל זה יתכנס לוקטור ההתפלגות הסטציונרית ללא תלות במצב ההתחלתי. גם במודלים הללו האנטרופיה מקסימלית עבור ההתפלגות הסטציונרית והם מהווים הסבר לחוק השני. בנוסף במודלים הללו ניתן להשתמש בקשר $\pi _{i}={\frac {1}{E_{i}}}$ על מנת להראות שתוחלת זמן החזרה למצבים הרחוקים ממצב שיווי משקל במערכות רב חלקיקיות גדולה בהרבה מהזמנים המאפיינים ניסויים ולהסיק מכך שניתן באופן פרקטי להתעלם ממשפט ההישנות של פואנקרה.

• Markov chain Monte Carlo:

Markov chain Monte Carlo או בקצרה MCMC הם סוג של אלגוריתמים המיועדים לדגימת התפלגות הסתברות. על ידי יצירת שרשרת מרקוב בעלת התפלגות סטציונרית השווה לפונקציה ידועה הפרופורציונית להתפלגות ההסתברות ניתן לדגום את ההסתברות עצמה גם אם היא אינה ידועה ובאמצעות הדגימות ניתן לבצע קירוב של התפלגות ההסתברות. בנוסף ניתן להשתמש בדגימות על מנת להעריך גדלים אותם אנו מעוניינים לחשב.

דוגמה לצורך באלגוריתם מסוג זה היא בחישוב התפלגות בולצמן על ידי שימוש באלגוריתם מטרופוליס. ידוע שעבור מערכת קנונית ההסתברות של חלקיק להמצא במצב $i$ נתונה על ידי $p_{i}={\frac {\exp(-E_{i}/k_{B}T)}{Z}}$ - כאשר $Z=\sum _{i}\exp \left({\frac {-E_{i}}{k_{B}T}}\right)$. אם מספר המצבים האפשרים קטן, ניתן למצוא את Z על ידי סכימה ישירה, אך כיוון שמספר המצבים האפשרי גדל אקספוננציאלית כתלות במספר החלקיקים לרוב לא יהיה ניתן לבצע זאת. לעומת זאת ניתן להגדיר שרשרת מרקוב המקיימת $P_{i,j}={min{\biggl (}e^{E(X_{i})-E(X_{j}) \over K_{b}T},1{\biggl )} \over \left\vert N(i)\right\vert }$ עבור $j\in N(i)$ כאשר $N(i)$ היא סביבת המצבים של $i$ אשר ההבדל בין המצבים הוא חלקיק יחיד. בדומה לאלגוריתם מונטה קרלו המצב ה$j$ יבחר באופן אחיד מתוך $N(i)$. לבסוף על מנת שהשרשרת תהיה לא מחזורית נגדיר $P_{i,i}=1-\sum _{j\in N(i)}P_{i,j}$. כעת בזכות העובדה שזוהי שרשרת מרקוב ניתן להבטיח שההתפלגות תשאף להתפלגות הסטציונרית ללא תלות בבחירה ההתחלתית ולכן ניתן לבחור מצב $i$ התחלתי כללי (על מנת לעשות זאת באופן נומרי צריך לספור את מספר הביקורים עבור כל מצב ולחלק במספר הביקורים הכולל בסך כל המצבים). בנוסף ניתן לראות שהתהליך שבחרנו הוא תהליך הפיך שכן תנאי האיזון המפורט מתקיים.

• שרשראות מרקוב בזמן רציף:

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

ראו גם

• תהליך החלטה מרקובי
• מודל מרקוב חבוי
• דגימת גיבס
• תהליך לידה-מוות

קישורים חיצוניים

מדיה וקבצים בנושא שרשרת מרקוב בוויקישיתוף

• תהליכי מרקוב, דף שער בספרייה הלאומית

• אתר הקורס מבוא לתהליכים סטוכסטיים של שלומי רובינשטיין.

• פוסט על שרשראות מרקוב בבלוג "לא מדויק" של גדי אלכסנדרוביץ'
• בעיית המטריות: איך לא להירטב? - יוסי לוי - נסיכת המדעים
• פרק על שרשראות מרקוב בספר הסתברות של האגודה האמריקאית למתמטיקה (באנגלית)
• The World's Largest Matrix Computation (הדירוג של מנוע החיפוש גוגל מבוסס על חישוב ההתפלגות הסטציונרית של הילוך מקרי ברשת, באנגלית)
• שרשרת מרקוב, באתר MathWorld (באנגלית)