העשרה: שרשראות מרקוב (Markov Chains)

מוטיבציה

שרשראות מרקוב הן הבסיס המתמטי לאלגוריתם PageRank. הבנה שלהן מסבירה למה PageRank עובד, לא רק איך.

מהי שרשרת מרקוב?

מצבים (States)

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

דוגמה: מזג אוויר — {שמש, גשם, עננים}

מעברים (Transitions)

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

תכונת מרקוב (Markov Property)

העתיד תלוי רק בהווה, לא בעבר.

כלומר: ההסתברות לעבור למצב הבא תלויה רק במצב הנוכחי, לא בסדרת המצבים שהובילה אליו.

$P(X_{n+1} = j \mid X_n = i, X_{n-1}, \ldots, X_0) = P(X_{n+1} = j \mid X_n = i)$

אינטואיציה: כמו משחק לוח — אכפת לך רק איפה אתה עכשיו, לא איך הגעת לשם.

מטריצת מעבר (Transition Matrix)

הגדרה

מטריצה $T$ כאשר $T[i][j]$ = ההסתברות לעבור ממצב $i$ למצב $j$.

תכונה חשובה

כל שורה סכומה 1 — ממצב כלשהו חייבים לעבור לאיזשהו מצב (כולל להישאר).

דוגמה: מזג אוויר

         שמש   גשם   עננים
שמש    [ 0.7   0.1   0.2  ]
גשם    [ 0.2   0.4   0.4  ]
עננים  [ 0.3   0.3   0.4  ]

קריאה: אם היום שמש, מחר יהיה שמש בהסתברות 0.7, גשם 0.1, עננים 0.2.

ייצוג בפייתון

# מטריצת מעבר כרשימת רשימות
T = [[0.7, 0.1, 0.2],
     [0.2, 0.4, 0.4],
     [0.3, 0.3, 0.4]]

# T[i][j] = P(עובר ל-j | נמצא ב-i)
# שורה 0 = מהלכי מצב "שמש"
# סכום כל שורה = 1.0

הקשר לגרפים

שרשרת מרקוב = גרף מכוון ממושקל:

• צמתים = מצבים
• קשתות = מעברים אפשריים
• משקלות = הסתברויות מעבר

     0.7
  ┌──────┐
  ↓      │
 שמש ──0.1──→ גשם
  │              │
  0.2          0.4
  ↓              ↓
 עננים ←──0.4──┘

קשר ל-PageRank

באלגוריתם PageRank, הגרף הוא האינטרנט:

• צמתים = דפי אינטרנט
• קשתות = קישורים בין דפים
• הסתברות מעבר = $\frac{1}{\text{מספר קישורים יוצאים}}$

הליכה אקראית (Random Walk)

מהי?

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

סימולציה

import random

def random_walk(T, steps, start=0):
    """הליכה אקראית על שרשרת מרקוב"""
    state = start
    path = [state]

    for _ in range(steps):
        # בוחרים מצב הבא לפי הסתברויות השורה
        probs = T[state]
        state = random.choices(range(len(probs)), weights=probs)[0]
        path.append(state)

    return path

T = [[0.7, 0.1, 0.2],
     [0.2, 0.4, 0.4],
     [0.3, 0.3, 0.4]]

walk = random_walk(T, 20, start=0)
print(walk)  # [0, 0, 2, 1, 2, 0, 0, 0, 2, ...]

ספירת ביקורים

def visit_counts(T, steps, start=0):
    """סופר כמה פעמים ביקרנו בכל מצב"""
    n = len(T)
    counts = [0] * n
    state = start

    for _ in range(steps):
        probs = T[state]
        state = random.choices(range(n), weights=probs)[0]
        counts[state] += 1

    # נרמול לפרופורציות
    return [c / steps for c in counts]

props = visit_counts(T, 1_000_000)
print(props)  # [~0.47, ~0.22, ~0.31]

זה בדיוק מה ש-PageRank עושה! הפרופורציות הן ה-"דירוג" של כל מצב.

התפלגות סטציונרית (Stationary Distribution)

מהי?

וקטור הסתברויות $\pi$ שמקיים:

$\pi \cdot T = \pi$

כלומר: אם ההתפלגות היא $\pi$, אחרי עוד צעד היא נשארת $\pi$.

אינטואיציה

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

הקשר ל-PageRank

וקטור ה-PageRank הוא ההתפלגות הסטציונרית של שרשרת המרקוב שמתאימה לגרף האינטרנט.

דף עם PageRank גבוה = מצב שהגולש האקראי מבקר בו הרבה.

ארגודיות (Ergodicity)

מתי מובטחת התכנסות?

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

שני תנאים

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

✓ אי-פריק:           ✗ פריק (לא מקושר):
A → B → C → A         A → B    C → D
                       (לא ניתן להגיע מ-A ל-C)

2. א-מחזוריות (Aperiodic): אין מחזור קבוע בחזרה למצב.

✓ א-מחזורי:           ✗ מחזורי (מחזור 2):
A → B                  A → B → A → B → ...
A → A (יכול להישאר)   (תמיד חוזר אחרי 2 צעדים)

ארגודי = אי-פריק + א-מחזורי

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

למה PageRank צריך Damping?

בעיה 1: Dead Ends (מבוי סתום)

A → B → C (C אין לו קישורים יוצאים)

הגולש נתקע ב-C. השרשרת לא אי-פריקה.

בעיה 2: Spider Traps (מלכודות)

A → B → A → B → ...  (לולאה שלא יוצאים ממנה)

הגולש נכלא בתת-קבוצה. השרשרת לא אי-פריקה.

הפתרון: Damping + Teleportation

בהסתברות $1-p$ הגולש קופץ לדף אקראי (כולל כל הדפים בגרף).

$\text{מעבר} = \begin{cases} \text{עוקב אחרי קישור} & \text{בהסתברות } p \\ \text{טלפורטציה לדף אקראי} & \text{בהסתברות } 1-p \end{cases}$

למה זה עובד?

• מכל מצב אפשר להגיע לכל מצב (דרך טלפורטציה) → אי-פריקות
• יש סיכוי להישאר (לטלפורט לעצמך) → א-מחזוריות
• ביחד = ארגודיות → מובטחת התכנסות!

סיכום נקודות חשובות

• תכונת מרקוב: העתיד תלוי רק בהווה
• מטריצת מעבר: שורות סכומן 1, $T[i][j]$ = הסתברות $i \to j$
• הליכה אקראית: סימולציה של שרשרת מרקוב = בדיוק מה ש-PageRank עושה
• התפלגות סטציונרית: $\pi T = \pi$ — מתייצבת אחרי מספיק צעדים
• ארגודיות = אי-פריקות + א-מחזוריות → מבטיחה התכנסות
• Damping הופך כל גרף לארגודי (פותר dead ends ומלכודות)
• PageRank = שיעורי ביקור בהתפלגות הסטציונרית

קישורים נוספים

• יישום: pagerank.md - האלגוריתם שמשתמש בשרשראות מרקוב
• רקע: probability_random.md - הסתברות וספריית random