הילוך מקרי

הילוך מקרי (מכונה גם "הילוך שיכור") הוא סוג של תהליך סטוכסטי, המתאר תנועה אקראית לאורך זמן בדיד או רציף. הילוך מקרי הוצג לראשונה על ידי קרל פירסון בשנת 1905.^[1]

לדוגמה, המצב הכספי של מהמר המהמר הימורים רבים בזה אחר זה ניתן למידול כהילוך מקרי. באופן כללי, הילוכים מקריים משמשים בתחומים רבים: אקולוגיה, כלכלה, פסיכולוגיה, מדעי המחשב, פיזיקה, כימיה וביולוגיה.^[2]^[3]^[4]^[5]^[6]^[7]^[8]^[9]

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

הגדרה

הילוך מקרי בזמן בדיד

תהא $\left\{X_{i}\right\}_{i=1}^{\infty }$ סדרה של משתנים מקריים, בלתי תלויים ושווי-התפלגות. לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \in \mathbb{N}} נגדיר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_n = X_1+X_2+...+X_n} . אז סדרת המשתנים המקריים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{S_n\right\}_{n=1}^{\infty}} היא הילוך מקרי בזמן בדיד.

הילוך מקרי בזמן רציף

יהי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X(0)} משתנה מקרי כלשהו. עבור כל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle t > 0} נגדיר

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X(t) = \sum_{i=1}^{N(t)} \Delta x_i}

כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{ \Delta x_i \right\}_{i=1}^{\infty}} סדרה של משתנים מקריים בלתי-תלויים ושווי-התפלגות המייצגים את ה"קפיצות", ו $N(t)$ הוא מספר הצעדים בקטע הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(0,t\right)} , כלומר מספר הצעדים שהתרחשו עד לזמן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle t} .

משפחת המשתנים המקריים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{ X(t) \right\}_{t \ge 0}} היא הילוך מקרי בזמן רציף. באופן מדויק יותר, הילוך מקרי רציף בו הקפיצות בלתי-תלויות, מכונה ספרבילי. ישנה גם הגדרה להילוך מקרי בזמן רציף שאינו ספרבילי דווקא.

נשים לב כי פונקציית הצפיפות של ההילוך בזמן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle t'} עבור ערך הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x'} כלשהו, היא סכום על כל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N \in \mathbb{N}} , של האפשרות לקבל ב- $N$ צעדים את הערך הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x'} , בהינתן שהתבצעו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} צעדים אחרי זמן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle t'} . כלומר, מתקבלת הנוסחה

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{P}\left(x',t'\right) = \sum_{N=0}^{\infty} \mathbb{P}\left(\text{occured } N \text{ jumps after time } t' \right) \cdot \mathbb{P}\left(x' \mid \text{after } N \text{ jumps}\right) }

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

הילוך מקרי בסריג

מודל פופולרי הוא של הילוך מקרי על סריג, בו בכל שלב הסמן קופץ לאתר אחר בהתאמה להתפלגות מסוימת. במקרה של הילוך מקרי פשוט, הסמן יכול לנוע רק אל אתרים שכנים על פני הסריג. במקרה פשוט של הילוך מקרי סימטרי על סריג בו מספר השכנים של כל קודקוד סופי, ההסתברות זהה עבור קפיצה לכל אחד מהשכנים. כלומר, בכל קודקוד, הצעד הבא מפולג אחיד על פני הקודקודים השכנים. הדוגמה היסודית ביותר היא של הילוך מקרי על הסריג השלם ה-d-ממדי (המכונה לעיתים סריג על קובייתי) הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb Z ^ d} .^[10]

הילוך מקרי על סריג חד-ממדי

דוגמה יסודית היא הילוך מקרי על ציר המספרים השלמים (הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb Z} ), אשר מתחילה ב-0 ובכל שלב נעה 1+ או 1- בהסתברות שווה.

ניתן לתאר הילוך זה באופן הבא: סמן ממוקם על ציר המספרים השלמים בנקודה $0$ ומטבע הוגן מוטל. אם המטבע נוחת על עץ, הסמן מועבר לנקודה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1} , ואם על פלי, הסמן מועבר לנקודה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle -1} . לאחר חמש הטלות, הסמן יכול להיות באחת מבין הנקודות 1, 1-, 3, 3-, 5, או 5-. למשל לאחר חמש הטלות של שלוש עץ ושני פלי (הסדר לא משנה), הסמן יסיים בערך 1. בפירוט, ישנן עשר דרכים לנחיתה על 1 (על ידי הטלת שלוש פעמים עץ ושני פעמים פלי), עשר דרכים לנחיתה על 1- (על ידי הטלת שלוש פעמים עץ ושתי פעמים פלי), חמש דרכים לנחיתה על 3 (על ידי הטלת ארבע פעמים עץ ופעם אחת פלי), חמש דרכים לנחיתה על 3- (על ידי הטלת ארבע פעמים פלי ופעם אחת עץ), דרך אחת של נחיתה על 5 (על ידי הטלת חמש פעמים עץ) ודרך אחת של נחיתה על 5- (על ידי הטלת חמש פעמים פלי). ראו איור להלן להמחשה של התוצאות האפשריות של 5 הטלות.

כדי להגדיר הילוך זה באופן פורמלי, נתבונן בסדרת משתנים מקריים בלתי תלויים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Z_1, Z_2,\dots } , כאשר כל משתנה הוא בעל ערך של 1 או 1- בהסתברות שווה, ונקבע כי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_0 = 0\,\!} ו- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_n =\sum_{j=1}^nZ_j } . הסדרה $\{S_{n}\}_{n}\,\!$ נקראת הילוך מקרי על הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb Z} . התוחלת של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_n\,\!} ( הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E(S_n)\,\!} ) היא אפס. כלומר, הממוצע של כל הטלות המטבע שואף לאפס כגידול במספר הטלות. זה נובע מתכונת האדיטיביות של התוחלת:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E(S_n)=\sum_{j=1}^n E(Z_j)=0.}

חישוב דומה הנעזר בחוסר התלות של המשתנים המקריים והעובדה ש הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E(Z_n^2)=1} מראה כי:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E(S_n^2)=\sum_{i=1}^n \sum_{j=1}^n E(Z_j Z_i)=n}

מה שמרמז כי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E(|S_n|)\,\!} , מרחק ההזזות הצפוי לאחר n צעדים, צריך להיות מסדר גודל של ${\sqrt {n}}$ . למעשה:^[11]

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lim_{n\to\infty} \frac{E(|S_n|)}{\sqrt n}= \sqrt{\frac {2}{\pi}}}

תוצאה זו מראה כי דיפוזיה אינה יעילה לערבוב, בגלל הדרך שבה השורש הריבועי מתנהג עבור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} גדול.

נשאלת השאלה "כמה פעמים ההילוך המקרי יחזור לנקודת ההתחלה לו נאפשר לו להימשך לנצח?". הילוך מקרי פשוט ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb Z} יחצה כל נקודה מספר אינסופי של פעמים בהסתברות 1. לתוצאה זו ישנם שמות רבים: "תופעה חוצת רמות", "הישנות" או "חורבן המהמר". הסיבה לשם האחרון היא כדלקמן: מהמר עם כמות סופית של כסף בסופו של דבר יפסיד בעת שישחק משחק הוגן כנגד "הבית", לצורך העניין עם כמות אינסופית של כסף. הכסף של המהמר יבצע הילוך מקרי שבשלב מסוים יגיע לאפס ויסיים את המשחק.

אם a ו-b הם שלמים וחיוביים, אזי המספר הצפוי של צעדים עד שהילוך מקרי פשוט חד-ממדי המתחיל ב-0 יגיע לנקודה b או a- הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a\cdot b} . ההסתברות שהילוך מקרי זה יגיע ל-b לפני a- היא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{a}{(a+b)}} , טיעון שיכול למשל לנבוע מהעובדה שהילוך מקרי פשוט הוא מרטינגל.

חלק מהתוצאות שהוזכרו לעיל ניתן להסיק ממאפייני משולש פסקל. מספר ההליכות השונות בעלי n צעדים בהם כל צעד הוא אורך אחד, ימינה או שמאלה, הוא 2ⁿ. עבור הילוך מקרי פשוט, כל אחת מההליכות האלו סבירה באותה מידה. על מנת ש- S_n יהיה שווה למספר k הכרחי ומספיק עבורנו שמספר הפעמים אשר יתבצע צעד ימינה יעלה על אלה ששמאלה ב- k פעמים. מספר ההליכות אשר מקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_n=k} שווה למספר הדרכים של בחירת n + k)/2) אלמנטים מתוך n, כלומר :הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \choose (n+k)/2} .כדי שהביטוי הנ"ל יהיה שונה מאפס, יש צורך שיתקיים כי n + k יהיה מספר זוגי. לכן, ההסתברות ש $S_{n}=k$ שווה להפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{-n}{n\choose (n+k)/2}} . על ידי ייצוג ערכים של משולש פסקל במונחים של עצרת ושימוש בנוסחת סטירלינג, אפשרי לקבל אומדנים טובים להסתברויות הבאות לערכים גדולים של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} .

אם המרחב מוגבל רק למספרים הטבעיים +הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb Z} , מספר הדרכים שבהן הילוך מקרי ינחת על כל מספר נתון בחמש הטלות יכול להיות מוצג כ־{0,5,0,4,0,1}.

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

k	−5	−4	−3	−2	−1	0	1	2	3	4	5
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle P[S_0=k]}						1
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2P[S_1=k]}					1		1
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^2P[S_2=k]}				1		2		1
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^3P[S_3=k]}			1		3		3		1
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^4P[S_4=k]}		1		4		6		4		1
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^5P[S_5=k]}	1		5		10		10		5		1

משפט הגבול המרכזי ו-law of the iterated logarithm מתארים היבטים חשובים של התנהגות של הילוך מקרי פשוט ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb Z} . בפרט, משפט הגבול המרכזי טוען כי כאשר n גדל, ההסתברות (פרופורציונלי למספרים בכל שורה) מתקרבת להתפלגות נורמלית.

כהכללה ישירה, אחד יכול לשקול הילוך מקרי על סריג גבישי. למעשה זה אפשרי לקיים את משפט הגבול המרכזי ומשפט הסטייה הגדול בהגדרה זו.^[12]^[13]

שרשרת מרקוב

הילוך מקרי חד-ממדי הוא גם מודל של שרשרת מרקוב, אשר מרחב המצבים שלה ניתן על ידי השלמים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i=0,\pm 1,\pm 2,\dots .} עבור מספר כלשהו p אשר מקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,0 < p < 1} , הסתברויות המעבר (ההסתברות של P_i,j לעבור ממצב i למצב j) נתון בתור: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,P_{i,i+1}=p=1-P_{i,i-1}} .

בממדים גבוהים יותר

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

האם השיכור יחזור לביתו מהבר? זו מקבילה בשני ממדים של הבעיה שדנו בה לעיל. במקרה של הילוך מקרי 2-ממדי, התשובה היא כמעט בוודאות כן. אבל עבור 3 ממדים או גבוהים יותר, ההסתברות של חזרה למקור יורדת ככל שגדל מספר הממדים. בשלושה ממדים, ההסתברות יורדת לכ-34%. ^[14]

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

היחס לתהליך וינר

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

תהליך וינר הוא גבול הסקאלה של הילוך מקרי בממד 1. זה אומר שאם לוקחים הילוך מקרי עם צעדים קטנים מאוד, מתקבל קירוב לתהליך וינר (ופחות מדויק, לתנועה בראונית). לייתר דיוק, אם גודל הצעד הוא ε, צריך לבצע הילוך באורך L/ε² לעורך וינר משוער של L . ככל שגודל הצעד נוטה ל-0 (ומספר הצעדים גדל באופן יחסי) הילוך מקרי מתכנס לתהליך וינר. באופן פורמלי, אם B הוא המרחב של כל הנתיבים באורך L עם הטופולוגיה המרבית, ואם M הוא המרחב של המדידה מעל B עם טופולוגיה הנורמה, אז ההתכנסות היא במרחב M . באופן דומה, תהליך וינר בכמה ממדים הוא גבול קנה המידה של הילוך מקרי באותו מספר הממדים.

הילוך מקרי הוא פרקטל בדיד (פונקציה עם ממדים שלמים; 1,2,...), אבל מסלול תהליך וינר הוא פרקטל אמיתי, ויש קשר בין שניהם. לדוגמה, ביצוע צעדים מהילוך מקרי עד אשר המסלול עושה מעגל ברדיוס r·l (כאשר l הוא אורך הצעד). המספר הממוצע של צעדים אשר הוא מבצע הוא r². עובדה זו היא גרסה דיסקרטית של העובדה שתהליך וינר הוא פרקטל של ממד האוסדורף.

בשני ממדים, המספר הממוצע של הנקודות אשר לאותו ההילוך יש על השפה של מסלולו הוא r^4/3. זה מתאים לעובדה שהגבול של המסלול בתהליך וינר הוא פרקטל של ממד 4/3, עובדה שחזה בנואה מנדלברוט בעזרת שימוש בסימולציות אבל הוכח רק בשנת 2000 על ידי ג'ורג לורל, עודד שרם, וונדלין ורנר.^[15]

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

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

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma^2 = \frac{t}{\delta t}\,\varepsilon^2}

כאשר t הוא הזמן שחלף מאז תחילת ההילוך המקרי, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \varepsilon} הוא גודל הצעד של ההילוך המקרי, והפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \delta t} הוא הזמן שחלף בין שני שלבים רצופים.

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

בשלושה ממדים, השונות המקבילה לפונקציית גרין של משוואת דיפוזיה היא:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma^2 = 6\,D\,t}

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle D = \frac{\varepsilon^2}{6 \delta t}}

נשים לב כי בשני הביטויים של השונות מעל מתאימים להתפלגות הקשורה לווקטור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vec R} המקשר את שני קצוות של ההילוך המקרי, בתלת ממד. השונות הקשורה לכל רכיב הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle R_x} , הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle R_y} or הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle R_z} היא רק שליש מערך זה (עדיין בתלת ממד). לכן עבור דו-ממד:^[16]

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle D = \frac{\varepsilon^2}{4 \delta t}}

ועבור חד-ממד:^[17]

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle D = \frac{\varepsilon^2}{2 \delta t}}

הילוך מקרי גאוסיאני

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

כאן, גודל הצעד היא ההתפלגות נורמלית מצטברת ההפוכה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Phi^{-1}(z,\mu,\sigma)} כאשר 0 ≤ z ≤ 1 הוא מספר אקראי מפוזר באופן אחיד, וμ וσ הם הסטיות הממוצעת והסטנדרטיות של ההתפלגות הנורמלית, בהתאמה.

אם μ אינו אפס, ההילוך המקרי ישתנה בצורה ליניארית. אם v_s הוא הערך ההתחלתי של ההילוך המקרי, הערך הצפוי לאחר n צעדים יהיו v_s + nμ.

למקרה המיוחד שבו μ שווה לאפס, אחרי n צעדים, התפלגות ההסתברות של מרחק ההזזה ניתנת על ידי N(0, nσ²), שכאשר N() הוא הסימון בהתפלגות הנורמלית, n הוא מספר הצעדים, וσ הוא משתנה של ההתפלגות הנורמלית המצטברת ההפוכה כמו שניתן לעיל.

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{i=0}^n {X_i}=Z}

אבל יש לנו את התפלגות עבור הסכום של שני משתנים בלתי תלויים אשר מתפלגים נורמלית, Z = X + Y, והוא ניתן על ידי:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N(\mu_X=\mu_Y,\sigma^2_X+\sigma^2_Y)}

במקרה שלנו, μ_X = μ_Y = 0 ו σ²_X = σ²_Y = σ² נקבל:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N(0, 2\sigma^2)}

ולכן עבור n צעדים יש לנו:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Z \sim N(0, n\sigma^2)}

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sqrt{E|S_n^2|} = \sigma \sqrt{n}.}

אבל להילוך מקרי גאוסיאני, זה רק סטיית התקן של ההתפלגות של מרחק ההזזה לאחר n צעדים. לפיכך, אם μ שווה לאפס, ומאחר ושורש ממוצע ריבועים (RMS) מרחק ההזזה הוא סטיית תקן אחת, יש הסתברות 68.27% שהמרחק ההזזה rms אחרי n צעדים ייפלו בין ± σהפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sqrt{n}} . כמו כן, יש הסתברות של 50% שהמרחק ההזזה לאחר n צעדים ייפלו בין הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \pm 0.6745\sigma\sqrt{n}} .

דיפוזיה אנומלית

במערכות בעלות חוסר סדר כגון פרקטלים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma^2} לא יכולה להיות פרופורציונלית להפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle t} אלא להפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle t^{2 / d_w}} . המעריך הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle d_w } נקרא מעריך הדיפוזיה האנומלית ויכול להיות גדול יותר או קטן יותר מ-2. ^[18] דיפוזיה אנומלית יכולה גם לבוא לידי ביטוי כ-σ_r² ~ Dt^α כאשר α הוא פרמטר אנומליה.

מספר אתרים שונים

מספר האתרים השונים אשר ביקר בהם מהלך בודד הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S(t)} נחקר בהרחבה עבור סריג מממדים 2 ו-3, כמו כן עבור פרקטלים.^[19]^[20] כמות זו שימושית לניתוח של בעיות של מילכוד ותגובות קינטית. כמו כן כמות זו קשורה גם לצפיפות הרטט של המצבים ,^[21]^[22] תהליכי תגובה דיפוזיונית ^[23] והתפשטות של אוכלוסיות באקולוגיה.^[24] ההכללה של הבעיה הזו למספר האתרים השונים בהם ביקרו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} הילוכים, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_N(t)} , לאחרונה נלמדה עבור d ממדים בסריג אוקלידי.^[25] מספר האתרים השונים בהם ביקרו N הולכים אקראיים לא קשור בצורה פשוטה למספר האתרים השונים אשר ביקר בהם כל אחד מההולכים.

וריאציות של הילוכים מקריים

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

הילוך מקרי בגרפים

הילוך מקרי באורך K על גרף אינסופי G עם שורש 0 היא תהליך סטוכסטי עם משתנים מקריים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_1,X_2,\dots,X_k} כך ש הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_1=0} ו- ${X_{i+1}}$ הוא קודקוד הנבחר באופן אקראי מהשכנים של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_i } .

לאחר מכן המספר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_{v,w,k}(G)} הוא ההסתברות שהילוך באורך k המתחילה מv' מסתיימת בW.

בפרט, אם G הוא גרף עם שורש 0 , הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_{0,0,k}} היא ההסתברות שלאחר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle k } צעדים ההילוך המקרי יחזור ל0.

נניח כעת שהעיר שלנו היא כבר לא רשת ריבוע מושלמת. כאשר השיכור שלנו מגיע לצומת מסוימת הוא בוחר בין הכבישים הזמינים השונים בהסתברות שווה. לכן, אם יש לצומת שבע יציאות השיכור יבחר בכל אחת עם הסתברות של שביעית. זהו הילוך מקרי בגרף. האם השיכור שלנו יגיע לביתו? מתברר שבתנאים לא כל כך קשים, התשובה היא עדיין כן. לדוגמה, אם באורכים של כל אבני הם בין a ו b (כאשר a ו b הם כל שני מספרים חיוביים סופיים), אז השיכור כמעט בוודאות יגיע לביתו. נשים לב שאין הנחה שהגרף הוא גרף מישורי, כלומר העיר עשויה להכיל מנהרות וגשרים. דרך אחת להוכיח תוצאה זו היא באמצעות הקשר לרשתות חשמל. ניקח מפה של העיר ונמקם נגד אחד של 0 אוהם בכל אזור. עכשיו נמדוד את "ההתנגדות בין נקודה ואינסוף". במילים אחרות, נבחר מספר R וניקח את כל הנקודות ברשת החשמל עם מרחק גדול יותר מ-R מהנקודה שלנו ונחבר בניהם. זוהי עכשיו רשת חשמל סופית ואנו יכולים למדוד את ההתנגדות מהנקודה שבחרנו לנקודות המקושרות אם ניקח את R עד אינסוף. המגבלה נקראת "ההתנגדות בין נקודה ואינסוף". מתברר שהנ"ל הוא אמיתי (ניתן למצוא הוכחה יסודית בספרו של דויל וסנל - Doyle and Snell):

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

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

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

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

החל בשנת 1980, מחקר רב הושקע בחיבור תכונות של הגרף להילוכים מקריים. בנוסף לחיבור לרשת החשמל שתואר לעיל, יש קשרים חשובים לאי-שוויון איזופרימטרי, אי-שוויון פונקציונלי כגון סובולב (סובולב אי שוויון) ופואנקרה (אי שוויון פואנקרה^[26]) והמאפיינים של הפתרונות של המשוואה לפלס. חלק משמעותי של מחקר זה התמקד בגרף קיילי.^[27] לדוגמה, ההוכחה דייב באייר ו פרסי דיאקוניס כי 7 ערבובי ריפל שאפל^[28] מספיקים כדי לערבב חפיסת הקלפים היא תוצאה על הילוך מקרי על חבורת הסימטריות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_n} , ההוכחה משתמשת במבנה הקבוצה באופן מהותי. במקרים רבים תוצאות בדידות אלה נגזרות מהיריעה וחבורת לי.

הילוך מקרי עם אינטראקציה עצמית

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

הילוך תוך כדי הימנעות עצמית.^[29] הילוך מקרי תוך הימנעות עצמית באורך n בZ^d היא נתיב בן n צעדים אקראיים המתחיל בראשית, עושה מעברים רק בין אתרים סמוכים בZ^d, לא מבקר באותו אתר פעמיים, ונבחר באופן אחיד בין כל השבילים הללו. בשני ממדים, בשל המילכוד העצמי, המרחק של הימנעות עצמית אופיינית הוא מאוד קצר,^[30] ואילו בממד גבוה יותר הוא גדל מעבר לכל גבול. מודל זה לעיתים קרובות נעשה שימוש בפיזיקת פולימרים (מאז 1960).
הילוך מקרי מוחק לולאה (Gregory Lawler).^[31]^[32]
הילוך מקרי מחוזק (Robin Pemantle 2007).^[33]

הילוך מקרי ארוך טווח עם קורלציה

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

רשומות פעימות הלב^[34]
רצפי DNA ללא קידוד^[35]
סדרת זמן התנודתיות של מניות^[36]
רשומות טמפרטורה ברחבי העולם^[37]

דוגמאות להילוכים מקריים

דיפוזיה כהילוך מקרי

נניח כי חלקיק מוכנס למערכת חד-ממדית, כך שברגע t=0 הוא נמצא ב-x=0. כל חלקיק בתורו עושה צעד ימינה או שמאלה, כאשר אורך הצעד הוא δ, ובכל צעד החלקיק יכול לצעוד ימינה בהסתברות 1/2 או שמאלה בהסתברות 1/2. נסמן ב- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_i(n)} את מקומו של החלקיק ה-i לאחר n צעדים (שימו לב ש-x יכול להיות גם שלילי, אם החלקיק עשה יותר צעדים שמאלה מאשר ימינה.)

אם נחזור על הניסוי עם עוד חלקיקים, N בסה"כ. מה נוכל לומר על ההתפלגות של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x(n)} של החלקיקי השונים?

ראשית, לכל חלקיק בנפרד ברור כי מיקומו אחרי הצעד ה-n יהיה במרחק δ+ או δ– ממיקומו אחרי הצעד ה-(n-1), כלומר:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\textstyle x(n)=x(n-1)\pm\delta} .

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \langle x(n)\rangle=\frac{1}{N}\sum_{i=1}^{N}x_i(n)=\sum_{i=1}^{N}x_i(n-1)\pm \delta=\langle x(n-1)\rangle}

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \langle x(n)\rangle=0}

אך מה לגבי הממוצע של ריבוע המרחק מהראשית? שוב נבדוק את הקשר בין המצב אחרי הצעד ה-n למצב אחרי הצעד ה-(n-1):

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_i^2(n)=(x_i^2(n-1)\pm\delta)^2=x_i^2(n-1)\pm 2x(n-1)\delta+\delta^2}

לכן בממוצע:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \langle x^2(n)\rangle=\sum_{i=1}^{N}x_i^2(n)=(x_i(n-1)\pm \delta)^2=2=\langle x^2(n-1)\rangle \pm \langle 2x(n-1)\delta \rangle + \langle \delta^2 \rangle}

ניתן לראות כי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \langle 2x(n-1)\delta \rangle=0} מטעמי סימטריה, אולם כעת האיבר השלישי באגף השמאלי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \langle \delta^2 \rangle} אינו 0. ולכן נקבל:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \langle x^2(n)\rangle=\langle x^2(n-1)\rangle + \langle \delta^2 \rangle}

הממוצע של המרחק בריבוע מהמרכז גדל בכל צעד ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \delta^2} . מאחר שאחרי אפס צעדים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \langle x^2(0)\rangle=0} , נוכל לקבל כי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \langle x^2(n)\rangle=n\delta^2} .

המסקנה הזו מעניינת מאוד: בערך מוחלט, המרחק הממוצע מהראשית שחלקיק מגיע אליו ב-n צעדים הוא:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \langle |x|\rangle=\sqrt{\langle x^2(n)\rangle}=\sqrt{n}\delta}

מעניין לראות כי חלקיק שעושה n צעדים שכולם באותו כיוון היה מגיע למרחק n·δ מהראשית. משמעות הדבר שהיעילות של הילוך מקרי בהרחקת חלקיקים מהראשית מדוכאת פי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\textstyle \sqrt{n}} יחסית לתנועה חופשית.

הילוך מקרי בכלכלה

נבדק במקור על ידי מוריס קנדל (Maurice Kendall) בשנת 1953, התאוריה קובעת כי תנודות במחיר המניה אינן תלויות זה בזה להן את אותה התפלגות הסתברות, אבל על פני תקופה של זמן, המחירים ישמרו על מגמת עלייה. כלומר, התייחסות של הילוך מקרי למחירי מניות, אומרת כי הסיכוי של המחיר העתידי של המניה לעלות זהה לסיכוי שלה לרדת.

השערת ההילוך המקרי

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

את המושג ניתן לייחס לברוקר הצרפתי ז'ול ראגנלוט (Jules Regnault) שפרסם ספר בשנת 1863, ולאחר מכן למתמטיקאי הצרפתי לואיס באכליאר (Louis Bachelier) דוקטורנט אשר עבודתו שכותרתה "התאוריה של ספקולציה"^[38] (1900) כללה כמה תובנות ופרשנות ראויות לציון. אותם הרעיונות פותחו מאוחר יותר על ידי בית הספר סלואן MIT של פרופסור פול קוטנר (Paul Cootner) בספר 1964 הוא "התווים אקראיים של מחירי שוק המניות".^[39] המונח הפך לפופולרי בעקבות הספר, "הילוך מקרי בוול סטריט", 1973 על ידי ברטון מלכיאל (Burton Malkiel), פרופסור לכלכלה באוניברסיטת פרינסטון,^[40] והיה בשימוש קודם לכן במאמר של יוג'ין פאמה ( Eugene Fama) ב-1965 "הילוך מקרי במחירי שוק המניות", שהיה גרסה פחות טכנית של תזת הדוקטורט. התאוריה שמחירי המניות נעים באופן אקראי הוצעה קודם לכן על ידי מוריס קנדל (Maurice Kendall) במאמר ב-1953, "ניתוח של כלכלת סדרת הזמן, חלק 1: מחירים".^[41]

הילוך מקרי בביולוגיה

שגיאה ביצירת תמונה ממוזערת:

הילוך מקרי של בקטריה

מידול תנועה ביולוגית

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

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

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

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

תנועה של בעלי חיים ומיקרו-אורגניזמים כהילוך מקרי

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

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

לאבלי ודלקוויסט (1975) השתמש במודל של הילוך מקרי כדי לתאר את התנועה של חיידק Escherichia כאשר אין כיוון מועדף והראה כיצד להפיק מקדם הדיפוזיה לשטף של חיידקים. הם דנו גם בכמה אמצעים סטטיסטיים בתפוצה רחבה כאשר יש כיוון מועדף, אבל לא קשר את זה למודל הילוך מקרי לתנועה של תאים בודדים. הילוכים מקריים עם קורלציה כבר היו בשימוש על ידי הול (1977) כאשר לומד את התנועה של אמבה,^[42] Kareiva & Shigesada מודל פרפרי כרוב המטילים ביצים או בחיפוש לאתרי צוף, ועוד רבים אחרים. Bovet & Benhamou הגדירו עד מודל סימולציה של הילוך מקרי עם קורלציה והציעו פיתולים כאמצעי המרחבי של המסלול שאינו תלוי באורך הדגימה שהוטל. לאחרונה, באיירס (2000) השתמש בסימולציות של הילוכים מקריים מתואמים ללמוד פיזור חיפושיות קליפה ביערות, ובאיירס (2001) משתמש באותו מודל הסימולציה למצוא קורלציה בין שורש ממוצע הריבועים ומרחק פיזור.

שימושים