הילוך מקרי

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

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

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

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

הגדרה

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

תהא $\left\{X_{i}\right\}_{i=1}^{\infty }$ סדרה של משתנים מקריים, בלתי תלויים ושווי-התפלגות. לכל $n\in \mathbb {N}$ נגדיר $S_{n}=X_{1}+X_{2}+...+X_{n}$. אז סדרת המשתנים המקריים $\left\{S_{n}\right\}_{n=1}^{\infty }$ היא הילוך מקרי בזמן בדיד.

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

יהי $X(0)$ משתנה מקרי כלשהו. עבור כל $t>0$ נגדיר

$X(t)=\sum _{i=1}^{N(t)}\Delta x_{i}$

כאשר $\left\{\Delta x_{i}\right\}_{i=1}^{\infty }$ סדרה של משתנים מקריים בלתי-תלויים ושווי-התפלגות המייצגים את ה"קפיצות", ו $N(t)$ הוא מספר הצעדים בקטע $\left(0,t\right)$, כלומר מספר הצעדים שהתרחשו עד לזמן $t$.

משפחת המשתנים המקריים $\left\{X(t)\right\}_{t\geq 0}$ היא הילוך מקרי בזמן רציף. באופן מדויק יותר, הילוך מקרי רציף בו הקפיצות בלתי-תלויות, מכונה ספרבילי. ישנה גם הגדרה להילוך מקרי בזמן רציף שאינו ספרבילי דווקא.

נשים לב כי פונקציית הצפיפות של ההילוך בזמן $t'$ עבור ערך $x'$ כלשהו, היא סכום על כל $N\in \mathbb {N}$, של האפשרות לקבל ב-$N$ צעדים את הערך $x'$, בהינתן שהתבצעו $N$ צעדים אחרי זמן $t'$. כלומר, מתקבלת הנוסחה

$\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-ממדי (המכונה לעיתים סריג על קובייתי) $\mathbb {Z} ^{d}$.

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

דוגמה יסודית היא הילוך מקרי על ציר המספרים השלמים ($\mathbb {Z}$), אשר מתחילה ב-0 ובכל שלב נעה 1+ או 1- בהסתברות שווה.

ניתן לתאר הילוך זה באופן הבא: סמן ממוקם על ציר המספרים השלמים בנקודה $0$ ומטבע הוגן מוטל. אם המטבע נוחת על עץ, הסמן מועבר לנקודה $1$, ואם על פלי, הסמן מועבר לנקודה $-1$. לאחר חמש הטלות, הסמן יכול להיות באחת מבין הנקודות 1, 1-, 3, 3-, 5, או 5-. למשל לאחר חמש הטלות של שלוש עץ ושני פלי (הסדר לא משנה), הסמן יסיים בערך 1. בפירוט, ישנן עשר דרכים לנחיתה על 1 (על ידי הטלת שלוש פעמים עץ ושני פעמים פלי), עשר דרכים לנחיתה על 1- (על ידי הטלת שלוש פעמים עץ ושתי פעמים פלי), חמש דרכים לנחיתה על 3 (על ידי הטלת ארבע פעמים עץ ופעם אחת פלי), חמש דרכים לנחיתה על 3- (על ידי הטלת ארבע פעמים פלי ופעם אחת עץ), דרך אחת של נחיתה על 5 (על ידי הטלת חמש פעמים עץ) ודרך אחת של נחיתה על 5- (על ידי הטלת חמש פעמים פלי). ראו איור להלן להמחשה של התוצאות האפשריות של 5 הטלות.

כל התוצאות האפשריות לאחר 5 הטלות.

הילוך מקרי בשני ממדים (גרסת אנימציה)

הילוך מקרי עם 25 אלף צעדים (גרסת אנימציה)

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

כדי להגדיר הילוך זה באופן פורמלי, נתבונן בסדרת משתנים מקריים בלתי תלויים $Z_{1},Z_{2},\dots$, כאשר כל משתנה הוא בעל ערך של 1 או 1- בהסתברות שווה, ונקבע כי $S_{0}=0\,\!$ ו- $S_{n}=\sum _{j=1}^{n}Z_{j}$. הסדרה $\{S_{n}\}_{n}\,\!$ נקראת הילוך מקרי על $\mathbb {Z}$. התוחלת של $S_{n}\,\!$ ($E(S_{n})\,\!$) היא אפס. כלומר, הממוצע של כל הטלות המטבע שואף לאפס כגידול במספר הטלות. זה נובע מתכונת האדיטיביות של התוחלת: $$E(S_{n})=\sum _{j=1}^{n}E(Z_{j})=0.$$

חישוב דומה הנעזר בחוסר התלות של המשתנים המקריים והעובדה ש $E(Z_{n}^{2})=1$ מראה כי: $$E(S_{n}^{2})=\sum _{i=1}^{n}\sum _{j=1}^{n}E(Z_{j}Z_{i})=n$$

מה שמרמז כי $E(|S_{n}|)\,\!$, מרחק ההזזות הצפוי לאחר n צעדים, צריך להיות מסדר גודל של ${\sqrt {n}}$. למעשה:

$$\lim _{n\to \infty }{\frac {E(|S_{n}|)}{\sqrt {n}}}={\sqrt {\frac {2}{\pi }}}$$

תוצאה זו מראה כי דיפוזיה אינה יעילה לערבוב, בגלל הדרך שבה השורש הריבועי מתנהג עבור $N$ גדול.

נשאלת השאלה "כמה פעמים ההילוך המקרי יחזור לנקודת ההתחלה לו נאפשר לו להימשך לנצח?". הילוך מקרי פשוט ב-$\mathbb {Z}$ יחצה כל נקודה מספר אינסופי של פעמים בהסתברות 1. לתוצאה זו ישנם שמות רבים: "תופעה חוצת רמות", "הישנות" או "חורבן המהמר". הסיבה לשם האחרון היא כדלקמן: מהמר עם כמות סופית של כסף בסופו של דבר יפסיד בעת שישחק משחק הוגן כנגד "הבית", לצורך העניין עם כמות אינסופית של כסף. הכסף של המהמר יבצע הילוך מקרי שבשלב מסוים יגיע לאפס ויסיים את המשחק.

אם a ו-b הם שלמים וחיוביים, אזי המספר הצפוי של צעדים עד שהילוך מקרי פשוט חד-ממדי המתחיל ב-0 יגיע לנקודה b או a- הוא $a\cdot b$. ההסתברות שהילוך מקרי זה יגיע ל-b לפני a- היא ${\frac {a}{(a+b)}}$, טיעון שיכול למשל לנבוע מהעובדה שהילוך מקרי פשוט הוא מרטינגל.

חלק מהתוצאות שהוזכרו לעיל ניתן להסיק ממאפייני משולש פסקל. מספר ההליכות השונות בעלי n צעדים בהם כל צעד הוא אורך אחד, ימינה או שמאלה, הוא 2ⁿ. עבור הילוך מקרי פשוט, כל אחת מההליכות האלו סבירה באותה מידה. על מנת ש- S_n יהיה שווה למספר k הכרחי ומספיק עבורנו שמספר הפעמים אשר יתבצע צעד ימינה יעלה על אלה ששמאלה ב-k פעמים. מספר ההליכות אשר מקיים $S_{n}=k$ שווה למספר הדרכים של בחירת n + k)/2) אלמנטים מתוך n, כלומר :$n \choose (n+k)/2$.כדי שהביטוי הנ"ל יהיה שונה מאפס, יש צורך שיתקיים כי n + k יהיה מספר זוגי. לכן, ההסתברות ש $S_{n}=k$ שווה ל$2^{-n}{n \choose (n+k)/2}$. על ידי ייצוג ערכים של משולש פסקל במונחים של עצרת ושימוש בנוסחת סטירלינג, אפשרי לקבל אומדנים טובים להסתברויות הבאות לערכים גדולים של $n$.

אם המרחב מוגבל רק למספרים הטבעיים +$\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
$P[S_{0}=k]$						1
$2P[S_{1}=k]$					1		1
$2^{2}P[S_{2}=k]$				1		2		1
$2^{3}P[S_{3}=k]$			1		3		3		1
$2^{4}P[S_{4}=k]$		1		4		6		4		1
$2^{5}P[S_{5}=k]$	1		5		10		10		5		1

משפט הגבול המרכזי ו-law of the iterated logarithm מתארים היבטים חשובים של התנהגות של הילוך מקרי פשוט ב-$\mathbb {Z}$. בפרט, משפט הגבול המרכזי טוען כי כאשר n גדל, ההסתברות (פרופורציונלי למספרים בכל שורה) מתקרבת להתפלגות נורמלית.

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

שרשרת מרקוב

הילוך מקרי חד-ממדי הוא גם מודל של שרשרת מרקוב, אשר מרחב המצבים שלה ניתן על ידי השלמים $i=0,\pm 1,\pm 2,\dots .$ עבור מספר כלשהו p אשר מקיים $\,0<p<1$, הסתברויות המעבר (ההסתברות של P_i,j לעבור ממצב i למצב j) נתון בתור: $\,P_{i,i+1}=p=1-P_{i,i-1}$.

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

שלושה צעדים של הילוך מקרי בשלושה ממדים

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

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

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

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

סימולצית צעדים אשר בקירוב מתארת את תהליך וינר בשני ממדים

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

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

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

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

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

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

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

$$\sigma ^{2}={\frac {t}{\delta t}}\,\varepsilon ^{2}$$

כאשר t הוא הזמן שחלף מאז תחילת ההילוך המקרי, $\varepsilon$ הוא גודל הצעד של ההילוך המקרי, ו$\delta t$ הוא הזמן שחלף בין שני שלבים רצופים.

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

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

$$\sigma ^{2}=6\,D\,t$$

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

$$D={\frac {\varepsilon ^{2}}{6\delta t}}$$

נשים לב כי בשני הביטויים של השונות מעל מתאימים להתפלגות הקשורה לווקטור ${\vec {R}}$ המקשר את שני קצוות של ההילוך המקרי, בתלת־ממד. השונות הקשורה לכל רכיב $R_{x}$, $R_{y}$ or $R_{z}$ היא רק שליש מערך זה (עדיין בתלת־ממד). לכן עבור דו-ממד:

$$D={\frac {\varepsilon ^{2}}{4\delta t}}$$

ועבור חד-ממד:

$$D={\frac {\varepsilon ^{2}}{2\delta t}}$$

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

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

כאן, גודל הצעד היא ההתפלגות נורמלית מצטברת ההפוכה $\Phi ^{-1}(z,\mu ,\sigma )$ כאשר 0 ≤ z ≤ 1 הוא מספר אקראי מפוזר באופן אחיד, וμ וσ הם הסטיות הממוצעת והסטנדרטיות של ההתפלגות הנורמלית, בהתאמה.

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

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

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

$$\sum _{i=0}^{n}{X_{i}}=Z$$

אבל יש לנו את התפלגות עבור הסכום של שני משתנים בלתי תלויים אשר מתפלגים נורמלית, Z = X + Y, והוא ניתן על ידי:$$N(\mu _{X}=\mu _{Y},\sigma _{X}^{2}+\sigma _{Y}^{2})$$

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

$$N(0,2\sigma ^{2})$$

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

$Z\sim N(0,n\sigma ^{2})$

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

$${\sqrt {E|S_{n}^{2}|}}=\sigma {\sqrt {n}}.$$

אבל להילוך מקרי גאוסיאני, זה רק סטיית התקן של ההתפלגות של מרחק ההזזה לאחר n צעדים. לפיכך, אם μ שווה לאפס, ומאחר ושורש ממוצע ריבועים (RMS) מרחק ההזזה הוא סטיית תקן אחת, יש הסתברות 68.27% שהמרחק ההזזה rms אחרי n צעדים ייפלו בין ± σ${\sqrt {n}}$. כמו כן, יש הסתברות של 50% שהמרחק ההזזה לאחר n צעדים ייפלו בין $\pm 0.6745\sigma {\sqrt {n}}$.

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

במערכות בעלות חוסר סדר כגון פרקטלים $\sigma ^{2}$ לא יכולה להיות פרופורציונלית ל$t$ אלא ל$t^{2/d_{w}}$. המעריך $d_{w}$ נקרא מעריך הדיפוזיה האנומלית ויכול להיות גדול יותר או קטן יותר מ-2. דיפוזיה אנומלית יכולה גם לבוא לידי ביטוי כ-σ_r² ~ Dt^α כאשר α הוא פרמטר אנומליה.

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

מספר האתרים השונים אשר ביקר בהם מהלך בודד $S(t)$ נחקר בהרחבה עבור סריג מממדים 2 ו-3, כמו כן עבור פרקטלים. כמות זו שימושית לניתוח של בעיות של מילכוד ותגובות קינטית. כמו כן כמות זו קשורה גם לצפיפות הרטט של המצבים , תהליכי תגובה דיפוזיונית והתפשטות של אוכלוסיות באקולוגיה. ההכללה של הבעיה הזו למספר האתרים השונים בהם ביקרו $N$ הילוכים, $S_{N}(t)$, לאחרונה נלמדה עבור d ממדים בסריג אוקלידי. מספר האתרים השונים בהם ביקרו N הולכים אקראיים לא קשור בצורה פשוטה למספר האתרים השונים אשר ביקר בהם כל אחד מההולכים.

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

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

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

הילוך מקרי באורך K על גרף אינסופי G עם שורש 0 היא תהליך סטוכסטי עם משתנים מקריים $X_{1},X_{2},\dots ,X_{k}$ כך ש $X_{1}=0$ ו-${X_{i+1}}$ הוא קודקוד הנבחר באופן אקראי מהשכנים של $X_{i}$.

לאחר מכן המספר $p_{v,w,k}(G)$ הוא ההסתברות שהילוך באורך k המתחילה מv' מסתיימת בW.

בפרט, אם G הוא גרף עם שורש 0 , $p_{0,0,k}$ היא ההסתברות שלאחר $k$ צעדים ההילוך המקרי יחזור ל0.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

נניח כי חלקיק מוכנס למערכת חד-ממדית, כך שברגע t=0 הוא נמצא ב-x=0. כל חלקיק בתורו עושה צעד ימינה או שמאלה, כאשר אורך הצעד הוא δ, ובכל צעד החלקיק יכול לצעוד ימינה בהסתברות 1/2 או שמאלה בהסתברות 1/2. נסמן ב- $x_{i}(n)$ את מקומו של החלקיק ה-i לאחר n צעדים (שימו לב ש-x יכול להיות גם שלילי, אם החלקיק עשה יותר צעדים שמאלה מאשר ימינה.)

אם נחזור על הניסוי עם עוד חלקיקים, N בסה"כ. מה נוכל לומר על ההתפלגות של $x(n)$של החלקיקי השונים?

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

${\textstyle x(n)=x(n-1)\pm \delta }$.

כאשר אנו מצפים כי עבור מספר גדול של חלקיקים, לכחצי מהם יתאים סימן + ולכחצי סימן - .עכשיו נמצע על כל החלקיקים:$$\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$$

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

$$\langle x(n)\rangle =0$$

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

$$x_{i}^{2}(n)=(x_{i}^{2}(n-1)\pm \delta )^{2}=x_{i}^{2}(n-1)\pm 2x(n-1)\delta +\delta ^{2}$$

לכן בממוצע:

$$\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$$

ניתן לראות כי $\langle 2x(n-1)\delta \rangle =0$ מטעמי סימטריה, אולם כעת האיבר השלישי באגף השמאלי $\langle \delta ^{2}\rangle$ אינו 0. ולכן נקבל:

$$\langle x^{2}(n)\rangle =\langle x^{2}(n-1)\rangle +\langle \delta ^{2}\rangle$$

הממוצע של המרחק בריבוע מהמרכז גדל בכל צעד ב-$\delta ^{2}$. מאחר שאחרי אפס צעדים $\langle x^{2}(0)\rangle =0$, נוכל לקבל כי $\langle x^{2}(n)\rangle =n\delta ^{2}$.

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

$$\langle |x|\rangle ={\sqrt {\langle x^{2}(n)\rangle }}={\sqrt {n}}\delta$$

מעניין לראות כי חלקיק שעושה n צעדים שכולם באותו כיוון היה מגיע למרחק n·δ מהראשית. משמעות הדבר שהיעילות של הילוך מקרי בהרחקת חלקיקים מהראשית מדוכאת פי ${\textstyle {\sqrt {n}}}$ יחסית לתנועה חופשית.

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

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

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

בדיקת השערת הילוך מקרי על ידי הגדלת או הפחתת הערך של מניות פיקטיביות המבוססות על הערך האי-זוגי/זוגי של החלק העשרוני של פאי. התרשים דומה לגרף המניות.

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

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

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

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

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

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

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

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

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

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

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

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

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

שימושים

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

הדמיה של השפעת הסחף הגנטי על 20 אללים באוכלוסיות של 10 ושל 100 פרטים.

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

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

ראו גם

• אקראיות
• תהליך סטוכסטי
• תנועה בראונית
• דיפוזיה
• שרשרת מרקוב
• תהליך פואסון

לקריאה נוספת

• Aldous, David; Fill, Jim, Reversible Markov Chains and Random Walks on Graphs, https://web.archive.org/web/20040921020230/http://stat-www.berkeley.edu/users/aldous/RWG/book.html
• Ben-Avraham D.; Havlin S., Diffusion and Reactions in Fractals and Disordered Systems, Cambridge University Press, 2000.
• Doyle, Peter G.; Snell, J. Laurie (1984). Random Walks and Electric Networks. Carus Mathematical Monographs. Vol. 22. Mathematical Association of America. arXiv:math.PR/0001057. ISBN 978-0-88385-024-4. MR 0920811^{[דרוש מקור]}{{cite book}}: תחזוקה - ציטוט: postscript (link)
• Feller, William (1968), An Introduction to Probability Theory and its Applications (Volume 1). ISBN 0-471-25708-7
• Hughes, Barry D. (1996), Random Walks and Random Environments, Oxford University Press. ISBN 0-19-853789-1
• Mackenzie, Dana, "Taking the Measure of the Wildest Dance on Earth", Science, Vol. 290, 8 December 2000.
• Norris, James (1998), Markov Chains, Cambridge University Press. ISBN 0-521-63396-6
• Pólya G.(1921), "Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Strassennetz", Mathematische Annalen, 84(1-2):149–160, March 1921.
• Révész, Pal (2013), Random Walk in Random and Non-random Environments (Third Edition), World Scientific Pub Co. ISBN 978-981-4447-50-8
• Weiss G. Aspects and Applications of the Random Walk, North-Holland, 1994.
• Woess, Wolfgang (2000), Random Walks on Infinite Graphs and Groups, Cambridge tracts in mathematics 138, Cambridge University Press. ISBN 0-521-55292-3
• Toshikazu Sunada (2012), Topological Crystallography --With a View Towards Discrete Geometric Analysis--, Surveys and Tutorials in the Applied Mathematical Sciences, Vol. 6, Springer
• הדגמה של דיפוזיה כהילוך מקרי
• Biased Random Walks in Biology

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

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

• הילוך מקרי, באתר אנציקלופדיה בריטניקה (באנגלית)
• הילוך מקרי ביישומון ג'אווה
• הילוך מקרי קוונטי
• תנועה בראונית והילוכים מקריים - תרומתו של איינשטיין לפיזיקה הסטטיסטית והשלכותיה על מדע עכשווי
• Does God practice a random walk? The Ž nancial physics’ of a nineteenth-century forerunner, Jules Regnault
• אנימציות תנועת נוזל (באתר של MIT)
• אלדוס ופיל (Aldous and Fill), ‏הילוך מקרי על גרפים
• הילוך מקרי, באתר MathWorld (באנגלית)
• מהלכים מקריים (מתמטיקה), דף שער בספרייה הלאומית