איגודיות

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

הגדרה

בהינתן שרשרת מרקוב שמרחב המצבים שלה ניתן לחלוקה על ידי תתי קבוצות זרות המסומנות ב t_i, כך שמתקבלת החלוקה $\scriptstyle {T=\{t_{1},t_{2},\ldots \}}$ של מצבי השרשרת, השרשרת תיקרא ניתנת לאיגוד ביחס לחלוקה T אם ורק אם

$\forall t_{i},t_{j}\in T,\forall n,n'\in t_{i}:\sum _{m\in t_{j}}q(n,m)=\sum _{m\in t_{j}}q(n',m),$

כאשר $q(i,j)$ היא ההסתברות לעבור ממצב $i$ למצב $j$.

כלומר, עבור כל שני מצבים מאוגדים $t_{i}$ ו-$t_{j}$ (כולל האפשרות $i=j$), סכום ההסתברויות של המעברים מכל מצב מקורי בודד שהתאגד ל-$t_{i}$ אל כל המצבים שהתאגדו ל-$t_{j}$ זהה.

דוגמאות

בהינתן מטריצת הסתברויות המעברים

$P={\begin{pmatrix}{\frac {1}{2}}&{\frac {3}{8}}&{\frac {1}{16}}&{\frac {1}{16}}\\{\frac {7}{16}}&{\frac {7}{16}}&0&{\frac {1}{8}}\\{\frac {1}{16}}&0&{\frac {1}{2}}&{\frac {7}{16}}\\0&{\frac {1}{16}}&{\frac {3}{8}}&{\frac {9}{16}}\end{pmatrix}}$

נבחין שמצבי המטריצה ניתנים לאיגוד על ידי החלוקה $\scriptstyle {T=\{(1,2),(3,4)\}}$ אז נגדיר מטריצה חדשה P_t שתיקרא המטריצה המאוגדת של P על t:

$P_{t}={\begin{pmatrix}{\frac {7}{8}}&{\frac {1}{8}}\\{\frac {1}{16}}&{\frac {15}{16}}\end{pmatrix}}$

הסבר:

החלוקה $\scriptstyle {T=\{(1,2),(3,4)\}}$ מאגדת את המצבים 1 ו-2 יחד ואת המצבים 3 ו-4 יחד. ההסתברות לעבור ממצב מספר 1 לעצמו היא ${\frac {1}{2}}$ ולמצב 2 היא ${\frac {3}{8}}$, ובסה"כ ${\frac {7}{8}}$. שתי ההסתברויות למעברים ממצב 2 למצב 1 וממצב 2 לעצמו הן ${\frac {7}{16}}$ ובסה"כ ${\frac {7}{8}}$ .

מכיוון ששני סכומי ההסתברויות שווים זה לזה, ההסתברות למעבר מהמצב שאוגד מהמצבים 1 ו-2 לעצמו תהיה ${\frac {7}{8}}$.

ההסתברות לעבור ממצב מספר 3 לעצמו היא ${\frac {1}{2}}$ ולמצב 4 היא ${\frac {7}{16}}$, ובסה"כ ${\frac {15}{16}}$. ההסתברות לעבור ממצב מספר 4 לעצמו היא ${\frac {9}{16}}$ ולמצב 3 היא ${\frac {3}{8}}$, ובסה"כ ${\frac {15}{16}}$.

מכיוון ששני סכומי ההסתברויות שווים זה לזה, ההסתברות למעבר מהמצב שאוגד מהמצבים 3 ו-4 לעצמו תהיה ${\frac {15}{16}}$.

ההסתברות לעבור ממצב מספר 1 למצב מספר 3 או למצב מספר 4 היא ${\frac {1}{16}}+{\frac {1}{16}}={\frac {1}{8}}$. ההסתברות לעבור ממצב מספר 2 למצב מספר 3 או למצב מספר 4 היא $0+{\frac {1}{8}}={\frac {1}{8}}$.

מכיוון שההסתברויות למעברים מהמצבים 1 ו-2 שאוגדו יחד אל מצבים 3 ו-4 שאוגדו יחד זהות, ההסתברות למעבר מהמצב שאוגד מהמצבים 1 ו-2 למצב שאוגד מהמצבים 3 ו-4 תהיה ${\frac {1}{8}}$.

ההסתברות לעבור ממצב מספר 3 למצב מספר 1 או למצב מספר 2 היא ${\frac {1}{16}}+0={\frac {1}{16}}$. ההסתברות לעבור ממצב מספר 4 למצב מספר 1 או למצב מספר 2 היא $0+{\frac {1}{16}}={\frac {1}{16}}$.

מכיוון שההסתברויות למעברים מהמצבים 3 ו-4 שאוגדו יחד אל מצבים 1 ו-2 שאוגדו יחד זהות, ההסתברות למעבר מהמצב שאוגד מהמצבים 3 ו-4 למצב שאוגד מהמצבים 1 ו-2 תהיה ${\frac {1}{16}}$.