הילוך מקרי
הילוך מקרי (מכונה גם "הילוך שיכור") הוא סוג של תהליך סטוכסטי, המתאר תנועה אקראית לאורך זמן בדיד או רציף. הילוך מקרי הוצג לראשונה על ידי קרל פירסון בשנת 1905.[1]
![](http://up.wiki.x.io/wikipedia/commons/thumb/d/da/Random_Walk_example.svg/257px-Random_Walk_example.svg.png)
לדוגמה, המצב הכספי של מהמר המשתתף בהימורים רבים בזה אחר זה ניתן למידול כהילוך מקרי. מודלים של הילוך מקרי משמשים בתחומים רבים: אקולוגיה, כלכלה, פסיכולוגיה, מדעי המחשב, פיזיקה, כימיה וביולוגיה.[2][3][4][5][6][7][8][9]
הילוכים מקריים יכולים להיות על גרפים, על ישר, במישור ובכלל בממדים גבוהים יותר, כמו גם על גבי משטחים. הילוכים מקריים מתוארים כתלויים במשתנה של זמן, בדיד או רציף.
הגדרה
עריכההילוך מקרי בזמן בדיד
עריכהתהא סדרה של משתנים מקריים, בלתי תלויים ושווי-התפלגות. לכל נגדיר . אז סדרת המשתנים המקריים היא הילוך מקרי בזמן בדיד.
הילוך מקרי בזמן רציף
עריכהיהי משתנה מקרי כלשהו. עבור כל נגדיר
כאשר סדרה של משתנים מקריים בלתי-תלויים ושווי-התפלגות המייצגים את ה"קפיצות", ו הוא מספר הצעדים בקטע , כלומר מספר הצעדים שהתרחשו עד לזמן .
משפחת המשתנים המקריים היא הילוך מקרי בזמן רציף. באופן מדויק יותר, הילוך מקרי רציף בו הקפיצות בלתי-תלויות, מכונה ספרבילי. ישנה גם הגדרה להילוך מקרי בזמן רציף שאינו ספרבילי דווקא.
נשים לב כי פונקציית הצפיפות של ההילוך בזמן עבור ערך כלשהו, היא סכום על כל , של האפשרות לקבל ב- צעדים את הערך , בהינתן שהתבצעו צעדים אחרי זמן . כלומר, מתקבלת הנוסחה
בין השאלות הטבעיות שניתן לשאול על הילוך מקרי במרחב אינסופי עם שורש מוגדר (כגון הילוך מקרי על חבורה) אפשר למנות את קצב הגידול של המרחק מהשורש, האנטרופיה של המקום, קצב הדעיכה של הסתברות החזרה (אותו אפשר לקשור לאמנביליות לפי משפט של Kesten).
הילוך מקרי בסריג
עריכהמודל פופולרי הוא של הילוך מקרי על סריג, בו בכל שלב הסמן קופץ לאתר אחר בהתאמה להתפלגות מסוימת. במקרה של הילוך מקרי פשוט, הסמן יכול לנוע רק אל אתרים שכנים על פני הסריג. במקרה פשוט של הילוך מקרי סימטרי על סריג בו מספר השכנים של כל קודקוד סופי, ההסתברות זהה עבור קפיצה לכל אחד מהשכנים. כלומר, בכל קודקוד, הצעד הבא מפולג אחיד על פני הקודקודים השכנים. הדוגמה היסודית ביותר היא של הילוך מקרי על הסריג השלם ה-d-ממדי (המכונה לעיתים סריג על קובייתי) .[10]
הילוך מקרי על סריג חד-ממדי
עריכהדוגמה יסודית היא הילוך מקרי על ציר המספרים השלמים ( ), אשר מתחילה ב-0 ובכל שלב נעה 1+ או 1- בהסתברות שווה.
ניתן לתאר הילוך זה באופן הבא: סמן ממוקם על ציר המספרים השלמים בנקודה ומטבע הוגן מוטל. אם המטבע נוחת על עץ, הסמן מועבר לנקודה , ואם על פלי, הסמן מועבר לנקודה . לאחר חמש הטלות, הסמן יכול להיות באחת מבין הנקודות 1, 1-, 3, 3-, 5, או 5-. למשל לאחר חמש הטלות של שלוש עץ ושני פלי (הסדר לא משנה), הסמן יסיים בערך 1. בפירוט, ישנן עשר דרכים לנחיתה על 1 (על ידי הטלת שלוש פעמים עץ ושני פעמים פלי), עשר דרכים לנחיתה על 1- (על ידי הטלת שלוש פעמים עץ ושתי פעמים פלי), חמש דרכים לנחיתה על 3 (על ידי הטלת ארבע פעמים עץ ופעם אחת פלי), חמש דרכים לנחיתה על 3- (על ידי הטלת ארבע פעמים פלי ופעם אחת עץ), דרך אחת של נחיתה על 5 (על ידי הטלת חמש פעמים עץ) ודרך אחת של נחיתה על 5- (על ידי הטלת חמש פעמים פלי). ראו איור להלן להמחשה של התוצאות האפשריות של 5 הטלות.
כדי להגדיר הילוך זה באופן פורמלי, נתבונן בסדרת משתנים מקריים בלתי תלויים , כאשר כל משתנה הוא בעל ערך של 1 או 1- בהסתברות שווה, ונקבע כי ו- . הסדרה נקראת הילוך מקרי על . התוחלת של ( ) היא אפס. כלומר, הממוצע של כל הטלות המטבע שואף לאפס כגידול במספר הטלות. זה נובע מתכונת האדיטיביות של התוחלת:
חישוב דומה הנעזר בחוסר התלות של המשתנים המקריים והעובדה ש מראה כי:
מה שמרמז כי , מרחק ההזזות הצפוי לאחר n צעדים, צריך להיות מסדר גודל של . למעשה:[11]
תוצאה זו מראה כי דיפוזיה אינה יעילה לערבוב, בגלל הדרך שבה השורש הריבועי מתנהג עבור גדול.
נשאלת השאלה "כמה פעמים ההילוך המקרי יחזור לנקודת ההתחלה לו נאפשר לו להימשך לנצח?". הילוך מקרי פשוט ב- יחצה כל נקודה מספר אינסופי של פעמים בהסתברות 1. לתוצאה זו ישנם שמות רבים: "תופעה חוצת רמות", "הישנות" או "חורבן המהמר". הסיבה לשם האחרון היא כדלקמן: מהמר עם כמות סופית של כסף בסופו של דבר יפסיד בעת שישחק משחק הוגן כנגד "הבית", לצורך העניין עם כמות אינסופית של כסף. הכסף של המהמר יבצע הילוך מקרי שבשלב מסוים יגיע לאפס ויסיים את המשחק.
אם a ו-b הם שלמים וחיוביים, אזי המספר הצפוי של צעדים עד שהילוך מקרי פשוט חד-ממדי המתחיל ב-0 יגיע לנקודה b או a- הוא . ההסתברות שהילוך מקרי זה יגיע ל-b לפני a- היא , טיעון שיכול למשל לנבוע מהעובדה שהילוך מקרי פשוט הוא מרטינגל.
חלק מהתוצאות שהוזכרו לעיל ניתן להסיק ממאפייני משולש פסקל. מספר ההליכות השונות בעלי n צעדים בהם כל צעד הוא אורך אחד, ימינה או שמאלה, הוא 2n. עבור הילוך מקרי פשוט, כל אחת מההליכות האלו סבירה באותה מידה. על מנת ש- Sn יהיה שווה למספר k הכרחי ומספיק עבורנו שמספר הפעמים אשר יתבצע צעד ימינה יעלה על אלה ששמאלה ב-k פעמים. מספר ההליכות אשר מקיים שווה למספר הדרכים של בחירת n + k)/2) אלמנטים מתוך n, כלומר : .כדי שהביטוי הנ"ל יהיה שונה מאפס, יש צורך שיתקיים כי n + k יהיה מספר זוגי. לכן, ההסתברות ש שווה ל . על ידי ייצוג ערכים של משולש פסקל במונחים של עצרת ושימוש בנוסחת סטירלינג, אפשרי לקבל אומדנים טובים להסתברויות הבאות לערכים גדולים של .
אם המרחב מוגבל רק למספרים הטבעיים + , מספר הדרכים שבהן הילוך מקרי ינחת על כל מספר נתון בחמש הטלות יכול להיות מוצג כ־{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 |
---|---|---|---|---|---|---|---|---|---|---|---|
1 | |||||||||||
1 | 1 | ||||||||||
1 | 2 | 1 | |||||||||
1 | 3 | 3 | 1 | ||||||||
1 | 4 | 6 | 4 | 1 | |||||||
1 | 5 | 10 | 10 | 5 | 1 |
משפט הגבול המרכזי ו-law of the iterated logarithm מתארים היבטים חשובים של התנהגות של הילוך מקרי פשוט ב- . בפרט, משפט הגבול המרכזי טוען כי כאשר n גדל, ההסתברות (פרופורציונלי למספרים בכל שורה) מתקרבת להתפלגות נורמלית.
כהכללה ישירה, אחד יכול לשקול הילוך מקרי על סריג גבישי. למעשה זה אפשרי לקיים את משפט הגבול המרכזי ומשפט הסטייה הגדול בהגדרה זו.[12][13]
שרשרת מרקוב
עריכההילוך מקרי חד-ממדי הוא גם מודל של שרשרת מרקוב, אשר מרחב המצבים שלה ניתן על ידי השלמים עבור מספר כלשהו p אשר מקיים , הסתברויות המעבר (ההסתברות של Pi,j לעבור ממצב i למצב j) נתון בתור: .
בממדים גבוהים יותר
עריכהניתן לחשוב על שיכור שהולך בצורה אקראית בעיר. העיר היא בגודל אינסופי ומסודרת ברשת ריבועית, ובכל צומת השיכור בוחר אחד מארבעת המסלולים האפשריים (כולל האחד שממנו בא) בהסתברות שווה.
האם השיכור יחזור לביתו מהבר? זו מקבילה בשני ממדים של הבעיה שדנו בה לעיל. במקרה של הילוך מקרי 2-ממדי, התשובה היא כמעט בוודאות כן. אבל עבור 3 ממדים או גבוהים יותר, ההסתברות של חזרה למקור יורדת ככל שגדל מספר הממדים. בשלושה ממדים, ההסתברות יורדת לכ-34%. [14]
המסלול של הילוך מקרי הוא אוסף האתרים שבהם הוא ביקר, האתרים נחשבים כסט עם התעלמות ל"מתי" ההילוך הגיע לנקודה. בממד אחד, המסלול הוא פשוט כל הנקודות בין הגובה המינימלי והמקסימום שההילוך השיג (שניהם בממוצע מסדר גודל של √n).בממדים גבוהים יותר לסט יש מאפיינים גאומטריים מעניינים. למעשה מקבלים פרקטל דיסקרטי. המתמטיקאי שיזואו קאקוטאני נודע כמי שהתייחס לתוצאה זו עם הציטוט הבא: "אדם שיכור ימצא את דרכו הביתה, אולם ציפור שיכורה עלולה ללכת לאיבוד לנצח".[15]
היחס לתהליך וינר
עריכהתהליך וינר הוא תהליך סטוכסטי עם התנהגות דומה לזו תנועה בראונית (לפעמים תהליך וינר נקרא "תנועה בראונית", אם כי מדובר בבלבול בין תופעה למודל המתאר אותה).
תהליך וינר הוא גבול הסקאלה של הילוך מקרי בממד 1. זה אומר שאם לוקחים הילוך מקרי עם צעדים קטנים מאוד, מתקבל קירוב לתהליך וינר (ופחות מדויק, לתנועה בראונית). לייתר דיוק, אם גודל הצעד הוא ε, צריך לבצע הילוך באורך L/ε2 לעורך וינר משוער של L . ככל שגודל הצעד נוטה ל-0 (ומספר הצעדים גדל באופן יחסי) הילוך מקרי מתכנס לתהליך וינר. באופן פורמלי, אם B הוא המרחב של כל הנתיבים באורך L עם הטופולוגיה המרבית, ואם M הוא המרחב של המדידה מעל B עם טופולוגיה הנורמה, אז ההתכנסות היא במרחב M . באופן דומה, תהליך וינר בכמה ממדים הוא גבול קנה המידה של הילוך מקרי באותו מספר הממדים.
הילוך מקרי הוא פרקטל בדיד (פונקציה עם ממדים שלמים; 1,2,...), אבל מסלול תהליך וינר הוא פרקטל אמיתי, ויש קשר בין שניהם. לדוגמה, ביצוע צעדים מהילוך מקרי עד אשר המסלול עושה מעגל ברדיוס r·l (כאשר l הוא אורך הצעד). המספר הממוצע של צעדים אשר הוא מבצע הוא r2. עובדה זו היא גרסה דיסקרטית של העובדה שתהליך וינר הוא פרקטל של ממד האוסדורף.
בשני ממדים, המספר הממוצע של הנקודות אשר לאותו ההילוך יש על השפה של מסלולו הוא r4/3. זה מתאים לעובדה שהגבול של המסלול בתהליך וינר הוא פרקטל של ממד 4/3, עובדה שחזה בנואה מנדלברוט בעזרת שימוש בסימולציות אבל הוכח רק בשנת 2000 על ידי ג'ורג לורל, עודד שרם, וונדלין ורנר.[16]
תהליך וינר נהנה מהרבה סימטריות על פני הילוך מקרי. לדוגמה, תהליך וינר הוא אינווריאנטי לסיבובים, בעוד הילוך מקרי לא, שכן הרשת הבסיסית היא לא (הילוך מקרי הוא אינווריאנטי לסיבובים ב-90 מעלות, אבל תהליכי וינר הם בלתי משתנה לסיבובים כללים, למשל, 17 מעלות). משמעות הדבר היא כי במקרים רבים, בעיות של הילוך מקרי קלות יותר לפתור על ידי תרגומם לתהליך וינר, לפתור את הבעיה שם, ולאחר מכן לתרגום בחזרה. מצד השני, כמה בעיות קלות יותר לפתור עם הילוכים מקריים בשל אופייה הבדיד.
הילוך מקרי ותהליך וינר יכולים להיות מצומדים, זה בא לידי ביטוי כאשר שניהם באותו מרחב ההסתברות באופן תלוי שמאלץ אותם להיות די קרובים. הצימוד הפשוט ביותר הוא הטבעת Skorokhod, אבל צימודים אחרים, מדויקים יותר קיימים גם כן.
ההתכנסות של הילוך מקרי כלפי תהליך וינר נשלטת על ידי משפט הגבול המרכזי. לחלקיק במיקום ידוע בt = 0, המשפט אומר לנו כי לאחר מספר רב של צעדים בהילוך מקרי עם עצמאות סטטיסטית, המיקום של החלקיק מתפלג לפי התפלגות נורמלית עם שונות:
כאשר t הוא הזמן שחלף מאז תחילת ההילוך המקרי, הוא גודל הצעד של ההילוך המקרי, ו הוא הזמן שחלף בין שני שלבים רצופים.
זה מתאים לפונקציית גרין של משוואת דיפוזיה אשר שולטת בתהליך וינר, מה שמוכיח כי, לאחר מספר רב של צעדים, מרחק ההילוך המקרי מתכנס לתהליך וינר.
בשלושה ממדים, השונות המקבילה לפונקציית גרין של משוואת דיפוזיה היא:
על ידי השוואת כמות זו עם השונות הקשורה למצב של הילוך מקרי, מקבלים את מקדם הדיפוזיה אשר מתאים לתהליך וינר אסימפטוטי אשר עבורו ההילוך המקרי מתכנס לאחר מספר רב של צעדים:
נשים לב כי בשני הביטויים של השונות מעל מתאימים להתפלגות הקשורה לווקטור המקשר את שני קצוות של ההילוך המקרי, בתלת־ממד. השונות הקשורה לכל רכיב , or היא רק שליש מערך זה (עדיין בתלת־ממד). לכן עבור דו-ממד:[17]
ועבור חד-ממד:[18]
הילוך מקרי גאוסיאני
עריכההילוך מקרי אשר גודל הצעד בו משתנה כתלות בהתפלגות נורמלית, משמש כמודל לנתונים בזמן אמת כגון שווקים פיננסיים. מודל בלק ושולס למשל, מציג נוסחה לאפיון מחירי אופציות המשתמשת בהילוך מקרי גאוסיאנית כהנחת בסיס.
כאן, גודל הצעד היא ההתפלגות נורמלית מצטברת ההפוכה כאשר 0 ≤ z ≤ 1 הוא מספר אקראי מפוזר באופן אחיד, וμ וσ הם הסטיות הממוצעת והסטנדרטיות של ההתפלגות הנורמלית, בהתאמה.
אם μ אינו אפס, ההילוך המקרי ישתנה בצורה ליניארית. אם vs הוא הערך ההתחלתי של ההילוך המקרי, הערך הצפוי לאחר n צעדים יהיו vs + nμ.
למקרה המיוחד שבו μ שווה לאפס, אחרי n צעדים, התפלגות ההסתברות של מרחק ההזזה ניתנת על ידי N(0, nσ2), שכאשר N() הוא הסימון בהתפלגות הנורמלית, n הוא מספר הצעדים, וσ הוא משתנה של ההתפלגות הנורמלית המצטברת ההפוכה כמו שניתן לעיל.
הוכחה: הילוך מקרי גאוסיאני יכולה להיות מיוצג כסכום של סדרה של משתנים מקריים בלתי תלויים ואשר מתפלגים באופן זהה, Xi מההתפלגות הנורמלית המצטברת ההפוכה עם תוחלת ששווה לאפס ו-σ של הפוך המקורי מצטברים התפלגות נורמלית:
אבל יש לנו את התפלגות עבור הסכום של שני משתנים בלתי תלויים אשר מתפלגים נורמלית, Z = X + Y, והוא ניתן על ידי:
במקרה שלנו, μX = μY = 0 ו σ2X = σ2Y = σ2 נקבל:
ולכן עבור n צעדים יש לנו:
לצעדים שהתפלגו על פי כל ההתפלגות עם תוחלת אפס ושונות סופיות (לא בהכרח רק התפלגות נורמלית), שורש ממוצע הריבועים עבור מרחק ההזזה לאחר n צעדים מתקבל כ:
אבל להילוך מקרי גאוסיאני, זה רק סטיית התקן של ההתפלגות של מרחק ההזזה לאחר n צעדים. לפיכך, אם μ שווה לאפס, ומאחר ושורש ממוצע ריבועים (RMS) מרחק ההזזה הוא סטיית תקן אחת, יש הסתברות 68.27% שהמרחק ההזזה rms אחרי n צעדים ייפלו בין ± σ . כמו כן, יש הסתברות של 50% שהמרחק ההזזה לאחר n צעדים ייפלו בין .
דיפוזיה אנומלית
עריכהבמערכות בעלות חוסר סדר כגון פרקטלים לא יכולה להיות פרופורציונלית ל אלא ל . המעריך נקרא מעריך הדיפוזיה האנומלית ויכול להיות גדול יותר או קטן יותר מ-2. [19] דיפוזיה אנומלית יכולה גם לבוא לידי ביטוי כ-σr2 ~ Dtα כאשר α הוא פרמטר אנומליה.
מספר אתרים שונים
עריכהמספר האתרים השונים אשר ביקר בהם מהלך בודד נחקר בהרחבה עבור סריג מממדים 2 ו-3, כמו כן עבור פרקטלים.[20][21] כמות זו שימושית לניתוח של בעיות של מילכוד ותגובות קינטית. כמו כן כמות זו קשורה גם לצפיפות הרטט של המצבים ,[22][23] תהליכי תגובה דיפוזיונית [24] והתפשטות של אוכלוסיות באקולוגיה.[25] ההכללה של הבעיה הזו למספר האתרים השונים בהם ביקרו הילוכים, , לאחרונה נלמדה עבור d ממדים בסריג אוקלידי.[26] מספר האתרים השונים בהם ביקרו N הולכים אקראיים לא קשור בצורה פשוטה למספר האתרים השונים אשר ביקר בהם כל אחד מההולכים.
וריאציות של הילוכים מקריים
עריכהמספר סוגים של תהליכים סטוכסטיים אשר דומים להילוכים מקריים טהורים כבר נידונו, אבל במקרים של מבנה פשוט מותר להיות כלליים יותר. המבנה הטהור יכול להיות מאופיין על ידי צעדים אשר מתפלגים בצורה עצמאית וזהה.
הילוך מקרי בגרפים
עריכההילוך מקרי באורך K על גרף אינסופי G עם שורש 0 היא תהליך סטוכסטי עם משתנים מקריים כך ש ו- הוא קודקוד הנבחר באופן אקראי מהשכנים של .
לאחר מכן המספר הוא ההסתברות שהילוך באורך k המתחילה מv' מסתיימת בW.
בפרט, אם G הוא גרף עם שורש 0 , היא ההסתברות שלאחר צעדים ההילוך המקרי יחזור ל0.
נניח כעת שהעיר שלנו היא כבר לא רשת ריבוע מושלמת. כאשר השיכור שלנו מגיע לצומת מסוימת הוא בוחר בין הכבישים הזמינים השונים בהסתברות שווה. לכן, אם יש לצומת שבע יציאות השיכור יבחר בכל אחת עם הסתברות של שביעית. זהו הילוך מקרי בגרף. האם השיכור שלנו יגיע לביתו? מתברר שבתנאים לא כל כך קשים, התשובה היא עדיין כן. לדוגמה, אם באורכים של כל אבני הם בין a ו-b (כאשר a ו-b הם כל שני מספרים חיוביים סופיים), אז השיכור כמעט בוודאות יגיע לביתו. נשים לב שאין הנחה שהגרף הוא גרף מישורי, כלומר העיר עשויה להכיל מנהרות וגשרים. דרך אחת להוכיח תוצאה זו היא באמצעות הקשר לרשתות חשמל. ניקח מפה של העיר ונמקם נגד אחד של 0 אוהם בכל אזור. עכשיו נמדוד את "ההתנגדות בין נקודה ואינסוף". במילים אחרות, נבחר מספר R וניקח את כל הנקודות ברשת החשמל עם מרחק גדול יותר מ-R מהנקודה שלנו ונחבר בניהם. זוהי עכשיו רשת חשמל סופית ואנו יכולים למדוד את ההתנגדות מהנקודה שבחרנו לנקודות המקושרות אם ניקח את R עד אינסוף. המגבלה נקראת "ההתנגדות בין נקודה ואינסוף". מתברר שהנ"ל הוא אמיתי (ניתן למצוא הוכחה יסודית בספרו של דויל וסנל - Doyle and Snell):
משפט: גרף הוא בתנועה (לש"מ), אם ורק אם ההתנגדות בין נקודה ואינסוף היא סופית. זה לא חשוב שהנקודה נבחרה אם הגרף מחובר.
במילים אחרות, מערכת בתנועה (לש"מ), צריך רק להתגבר על התנגדות סופית להגיע לאינסוף מכל נקודה. במערכת חוזרת ונשנית, ההתנגדות מכל נקודה לאינסוף היא אינסופית.
אפיון זה של מערכת חוזרת ונשנית ומערכת בתנועה הוא מאוד שימושי, ובמיוחד זה מאפשר לנו לנתח את המקרה של עיר אשר משורטטת במישור עם מרחקים מוגבלים.
הילוך מקרי על גרף הוא מקרה מיוחד של שרשרת מרקוב. שלא כמו שרשרת מרקוב כללית, הילוך מקרי בגרף מקיים סימטרית זמן או הפיכות. באופן כללי, התכונה הזו המכונה גם "תנאי איזון מפורט", משמעותן היא כי ההסתברויות לעבור דרך בכיוון אחד או אחר מקיימת קשר פשוט מאוד בין השניים (אם הגרף הוא גרף רגיל, ההסתברויות שוות). יש למאפיין זה השלכות חשובות.
החל בשנת 1980, מחקר רב הושקע בחיבור תכונות של הגרף להילוכים מקריים. בנוסף לחיבור לרשת החשמל שתואר לעיל, יש קשרים חשובים לאי-שוויון איזופרימטרי, אי-שוויון פונקציונלי כגון סובולב (סובולב אי שוויון) ופואנקרה (אי שוויון פואנקרה[27]) והמאפיינים של הפתרונות של המשוואה לפלס. חלק משמעותי של מחקר זה התמקד בגרף קיילי.[28] לדוגמה, ההוכחה דייב באייר ו פרסי דיאקוניס כי 7 ערבובי ריפל שאפל[29] מספיקים כדי לערבב חפיסת הקלפים היא תוצאה על הילוך מקרי על החבורה הסימטרית , שמשתמשת באלגברה. במקרים רבים תוצאות בדידות אלה נגזרות מהיריעה וחבורת לי.
הילוך מקרי עם אינטראקציה עצמית
עריכהישנם מספר מודלים מעניינים של הילוכים מקריים בהם כל צעד תלוי בעבר באופן מסובך. כולם מורכבים מידי לפתרון אנליטי מאשר ההילוך המקרי הרגיל; עדיין, ההתנהגות של כל מודל של הילוך מקרי היא בת השגה באמצעות מחשבים. דוגמאות כלליות:
- הילוך תוך כדי הימנעות עצמית.[30] הילוך מקרי תוך הימנעות עצמית באורך n בZ^d היא נתיב בן n צעדים אקראיים המתחיל בראשית, עושה מעברים רק בין אתרים סמוכים בZ^d, לא מבקר באותו אתר פעמיים, ונבחר באופן אחיד בין כל השבילים הללו. בשני ממדים, בשל המילכוד העצמי, המרחק של הימנעות עצמית אופיינית הוא מאוד קצר,[31] ואילו בממד גבוה יותר הוא גדל מעבר לכל גבול. מודל זה לעיתים קרובות נעשה שימוש בפיזיקת פולימרים (מאז 1960).
- הילוך מקרי מוחק לולאה (Gregory Lawler).[32][33]
- הילוך מקרי מחוזק (Robin Pemantle 2007).[34]
הילוך מקרי ארוך טווח עם קורלציה
עריכההילוך מקרי ארוך טווח עם קורלציה נמצא בהרבה מערכות ביולוגיות, אקלימיות וכלכליות.
דוגמאות להילוכים מקריים
עריכהדיפוזיה כהילוך מקרי
עריכהנניח כי חלקיק מוכנס למערכת חד-ממדית, כך שברגע t=0 הוא נמצא ב-x=0. כל חלקיק בתורו עושה צעד ימינה או שמאלה, כאשר אורך הצעד הוא δ, ובכל צעד החלקיק יכול לצעוד ימינה בהסתברות 1/2 או שמאלה בהסתברות 1/2. נסמן ב- את מקומו של החלקיק ה-i לאחר n צעדים (שימו לב ש-x יכול להיות גם שלילי, אם החלקיק עשה יותר צעדים שמאלה מאשר ימינה.)
אם נחזור על הניסוי עם עוד חלקיקים, N בסה"כ. מה נוכל לומר על ההתפלגות של של החלקיקי השונים?
ראשית, לכל חלקיק בנפרד ברור כי מיקומו אחרי הצעד ה-n יהיה במרחק δ+ או δ– ממיקומו אחרי הצעד ה-(n-1), כלומר:
כאשר אנו מצפים כי עבור מספר גדול של חלקיקים, לכחצי מהם יתאים סימן + ולכחצי סימן - .עכשיו נמצע על כל החלקיקים:
ניתן לראות שהממוצע על δ± נותן אפס, כי לחצי מהחלקיקים יש + ולחצי יש -. המיקום הממוצע של החלקיקים איננו משתנה עם התקדמות הצעדים, והוא כמובן שווה לאפס, כי הבעיה סימטרית לגמרי. כלומר:
אך מה לגבי הממוצע של ריבוע המרחק מהראשית? שוב נבדוק את הקשר בין המצב אחרי הצעד ה-n למצב אחרי הצעד ה-(n-1):
לכן בממוצע:
ניתן לראות כי מטעמי סימטריה, אולם כעת האיבר השלישי באגף השמאלי אינו 0. ולכן נקבל:
הממוצע של המרחק בריבוע מהמרכז גדל בכל צעד ב- . מאחר שאחרי אפס צעדים , נוכל לקבל כי .
המסקנה הזו מעניינת מאוד: בערך מוחלט, המרחק הממוצע מהראשית שחלקיק מגיע אליו ב-n צעדים הוא:
מעניין לראות כי חלקיק שעושה n צעדים שכולם באותו כיוון היה מגיע למרחק n·δ מהראשית. משמעות הדבר שהיעילות של הילוך מקרי בהרחקת חלקיקים מהראשית מדוכאת פי יחסית לתנועה חופשית.
הילוך מקרי בכלכלה
עריכהנבדק במקור על ידי מוריס קנדל (Maurice Kendall) בשנת 1953, התאוריה קובעת כי תנודות במחיר המניה אינן תלויות זה בזה להן את אותה התפלגות הסתברות, אבל על פני תקופה של זמן, המחירים ישמרו על מגמת עלייה. כלומר, התייחסות של הילוך מקרי למחירי מניות, אומרת כי הסיכוי של המחיר העתידי של המניה לעלות זהה לסיכוי שלה לרדת.
השערת ההילוך המקרי
עריכההשערת ההילוך המקרי היא תאוריה פיננסית, לפיה מחירי המניות בשוק מתפתחים בהתאם להילוך מקרי ולכן לא ניתן לחזות אותם. זה עולה בקנה אחד עם תאוריית השוק היעיל.
את המושג ניתן לייחס לברוקר הצרפתי ז'יל רניו (Jules Regnault) שפרסם ספר בשנת 1863, ולאחר מכן למתמטיקאי הצרפתי לואי באשליה (Louis Bachelier) דוקטורנט אשר עבודתו שכותרתה "התאוריה של ספקולציה"[39] (1900) כללה כמה תובנות ופרשנות ראויות לציון. אותם הרעיונות פותחו מאוחר יותר על ידי בית הספר סלואן MIT של פרופסור פול קוטנר (Paul Cootner) בספר 1964 הוא "התווים אקראיים של מחירי שוק המניות".[40] המונח הפך לפופולרי בעקבות הספר, "הילוך מקרי בוול סטריט", 1973 על ידי ברטון מלכיאל (Burton Malkiel), פרופסור לכלכלה באוניברסיטת פרינסטון,[41] והיה בשימוש קודם לכן במאמר של יוג'ין פאמה (Eugene Fama) ב-1965 "הילוך מקרי במחירי שוק המניות", שהיה גרסה פחות טכנית של תזת הדוקטורט. התאוריה שמחירי המניות נעים באופן אקראי הוצעה קודם לכן על ידי מוריס קנדל (Maurice Kendall) במאמר ב-1953, "ניתוח של כלכלת סדרת הזמן, חלק 1: מחירים".[42]
הילוך מקרי בביולוגיה
עריכהמידול תנועה ביולוגית
עריכההאקולוג הבריטי ג'ון סקלאם (John G. Skellam) היה אחד הראשונים בספרות להשתמש בהילוכים מקריים למודל ספציפי של פיזור אוכלוסיות בעלי חיים. סקלאם ולוין דנו בתוקף ובמגבלות של מודל ההילוך המקרי הפשוט והאיזוטרופיים, בפרט בבעיה של ריבוי אינסופי בסקלת זמן קטנה הנובעות מחוסר קורלציה, והעובדה שמודל זה לא יכול להסביר את אינטראקציה של יחידים או השתנות סביבה.
אוקובו (1980) דן במגוון רחב של בעיות דיפוזיה ביולוגית במגוון רחב של הגדרות, ומספק דיון מפורט בפיתוח והמגבלות של מודלים של הילוכים מקריים שונים.
מוריי (1993) נותן סקירה קצרה של כמה בעיות בדיפוזיה ביולוגית שיכולים למדל באמצעות מודלים של הילוך מקרי פשוט.
מילון מונחים שימושיים של מונחים הקשורים לתנועה מכוונת והילוכים מקריים על ידי טרנקוילו (Tranquillo) ואלט התפרסם בלט והופמן (1990), אשר מכיל הרבה מודלים אחרים של תנועה ביולוגית וכולל דיונים על מגבלות ניסיוניות של התבוננות בתנועה בקני מידה שונה.
תנועה של בעלי חיים ומיקרו-אורגניזמים כהילוך מקרי
עריכהפאטלק (Patlak) פיתח גרסה מורחבת של מודל ההילוך המקרי, אשר כלל קורלציה בין פעולות רצופות, לא הומוגניות בסביבה ובכוחות חיצוניים, וכמו כן איפשר למהירות ומרווח זמן בין שלבים להשתנות. אך המודל הוא כלי כללי, ומעשי רק כאשר כמה הנחות מפשטות נעשות על התנועה. "Siniff & Jessen" היה אחד הראשונים בספרות לשימוש במודל סימולציה של הילוך מקרי מתואם, שכלל את חלוקת פון מיזס כהתפלגות ההסתברות לזווית המפנה בכל שלב.
המשימה לשפוט את הדיוק הסטטיסטי של התוצאות של סימולציות בהשוואה לנתונים של תנועת שועל אשר נצפתה קשה מפני שאין קריטריון של טיב התאמה - הבעיה היא אחת מבעיות זיהוי תבנית.
לאבלי ודלקוויסט (1975) השתמש במודל של הילוך מקרי כדי לתאר את התנועה של חיידק Escherichia כאשר אין כיוון מועדף והראה כיצד להפיק מקדם הדיפוזיה לשטף של חיידקים. הם דנו גם בכמה אמצעים סטטיסטיים בתפוצה רחבה כאשר יש כיוון מועדף, אבל לא קשר את זה למודל הילוך מקרי לתנועה של תאים בודדים. הילוכים מקריים עם קורלציה כבר היו בשימוש על ידי הול (1977) כאשר לומד את התנועה של אמבה,[43] Kareiva & Shigesada מודל פרפרי כרוב המטילים ביצים או בחיפוש לאתרי צוף, ועוד רבים אחרים. Bovet & Benhamou הגדירו עד מודל סימולציה של הילוך מקרי עם קורלציה והציעו פיתולים כאמצעי המרחבי של המסלול שאינו תלוי באורך הדגימה שהוטל. לאחרונה, באיירס (2000) השתמש בסימולציות של הילוכים מקריים מתואמים ללמוד פיזור חיפושיות קליפה ביערות, ובאיירס (2001) משתמש באותו מודל הסימולציה למצוא קורלציה בין שורש ממוצע הריבועים ומרחק פיזור.
שימושים
עריכה- שימושים עיקריים להילוך מקרי
- בכלכלה פיננסית, "השערת ההילוך המקרי" משמשת מודל מחירי מניות וגורמים אחרים. מחקרים אמפיריים מצאו כמה סטיות ממודל תאורטי זה, במיוחד בטווח קצר וקורלציות ארוכות טווח.
- בגנטיקה של אוכלוסיות, הילוך מקרי מתאר את התכונות הסטטיסטיות של סחיפה גנטית.
- בפיזיקה, הילוכים מקריים משמשים כמודלים מפושטים של תנועה בראונית ודיפוזיה כגון התנועה האקראית של מולקולות בנוזלים וגזים. כמו כן, הילוכים מקריים, ובפרט כאלה עם אינטראקציה עצמית, משחקים תפקיד בתורת השדות הקוונטית.
- באקולוגיה מתמטית, הילוכים מקריים משמשים לתיאור תנועות של בעלי חיים בודדים, כדי לתמוך באופן אמפירי בתהליכים של ביו-דיפוזיה, ומדי פעם למודל דינמיקת אוכלוסייה.
- בפיזיקת פולימר, הילוך מקרי מתאר שרשרת אידיאלית. זהו המודל הפשוט ביותר ללמוד פולימרים.
- בתחומים אחרים של מתמטיקה, הילוך מקרי משמש לחישוב פתרונות למשוואת לפלס, להעריך את המידה ההרמונית, ועבור מבנים שונים בניתוח וקומבינטוריקה.
- במדעי מחשב, הילוכים מקריים משמשים להעריך את הגודל של האינטרנט. בכנס 2006 של "World Wide Web", בר-יוסף ואחרים פרסמו את הממצאים שלהם ואת האלגוריתמים שלהם לאותו הדבר.
- בפילוח תמונה, הילוכים מקריים משמשים כדי לקבוע את התוויות (כלומר, "חפץ" או "רקע") כדי לקשר כל פיקסל.[44]
- בחקר המוח, הילוכים מקריים משמשים מודל של נוירונים במוח.
- בראייה, תנועות עיניים ראייתית מתוארות היטב על ידי הילוך מקרי.[45]
- בפסיכולוגיה, הילוכים מקריים מתארים את היחס בין הזמן הדרוש כדי לקבל החלטה וההסתברות שהחלטה מסוימת תיעשה.[46]
- הילוכים מקריים יכולים לדגום משטח מדינה שגודלה אינו ידוע או גדול מאוד, לדוגמה לבחור דף אקראי מהאינטרנט.
- הילוכים מקריים שימשו גם כדי לדגום גרפים מסיביים באינטרנט, כגון רשתות חברתיות באינטרנט.
- ברשת אלחוטית, הילוך מקרי משמש למודל תנועת צומת.
- הילוכים מקריים משמשים מודל להימורים.
- באינטרנט, אתר טוויטר משתמש בהילוך מקרי כדי לתת הצעות אחרי מי לעקוב.[47]
ראו גם
עריכהלקריאה נוספת
עריכה- 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 (באנגלית)
- מהלכים מקריים (מתמטיקה), דף שער בספרייה הלאומית
הערות שוליים
עריכה- ^ Pearson, K. (1905). The Problem of the Random Walk. Nature. 72, 294.
- ^ Van Kampen N. G., Stochastic Processes in Physics and Chemistry, revised and enlarged edition (North-Holland, Amsterdam) 1992.
- ^ Redner S., A Guide to First-Passage Process (Cambridge University Press, Cambridge, UK) 2001.
- ^ Goel N. W. and Richter-Dyn N., Stochastic Models in Biology (Academic Press, New York) 1974.
- ^ Doi M. and Edwards S. F., The Theory of Polymer Dynamics (Clarendon Press, Oxford) 1986
- ^ De Gennes P. G., Scaling Concepts in Polymer Physics (Cornell University Press, Ithaca and London) 1979.
- ^ Risken H., The Fokker–Planck Equation (Springer, Berlin) 1984.
- ^ Weiss, George H. (1994), Aspects and Applications of the Random Walk, Random Materials and Processes, North-Holland Publishing Co., Amsterdam, ISBN 0-444-81606-2, MR 1280031.
- ^ Cox D. R., Renewal Theory (Methuen, London) 1962.
- ^ Révész Pal, Random walk in random and non random environments, World Scientific, 1990
- ^ http://mathworld.wolfram.com/RandomWalk1-Dimensional.html
- ^ M. Kotani, T. Sunada (2003). "Spectral geometry of crystal lattices". Contemporary. Math. 338: 271–305. doi:10.1090/conm/338/06077.
- ^ M. Kotani, T. Sunada (2006). "Large deviation and the tangent cone at infinity of a crystal lattice". Math. Z. 254: 837–870. doi:10.1007/s00209-006-0951-9.
- ^ Pólya's Random Walk Constants
- ^ Rick Durrett, Probability: Theory and Examples, 2019, עמ' 297
- ^ Dana Mackenzie, Taking the Measure of the Wildest Dance on Earth, Science, Vol. 290, no. 5498, pp. 1883–1884.
- ^ [1]
- ^ [2]
- ^ D. Ben-Avraham and S. Havlin, Diffusion and Reactions in Fractals and Disordered Systems, Cambridge University Press, 2000.
- ^ Weiss, George H.; Rubin, Robert J. (1982). Random Walks: Theory and Selected Applications. Vol. 52. pp. 363–505. doi:10.1002/9780470142769.ch5. ISSN 1934-4791.
- ^ Blumen, A.; Klafter, J.; Zumofen, G. (1986). Models for Reaction Dynamics in Glasses. Vol. 1. pp. 199–265. Bibcode:1986PCMLD...1..199B. doi:10.1007/978-94-009-4650-7_5. ISSN 0924-459X.
- ^ Alexander, S.; Orbach, R. (1982). Density of states on fractals : " fractons ". Journal de Physique Lettres. Vol. 43. pp. 625–631. doi:10.1051/jphyslet:019820043017062500. ISSN 0302-072X.
- ^ Rammal, R.; Toulouse, G. (1983). Random walks on fractal structures and percolation clusters. Journal de Physique Lettres. Vol. 44. pp. 13–22. doi:10.1051/jphyslet:0198300440101300. ISSN 0302-072X.
- ^ Smoluchowski, M.V. (1917). Versuch einer mathematischen Theorie der Koagulationskinetik kolloider Lösungen. Z. Phys. Chem. pp. 129–168.,Rice, S.A. (1 במרץ 1985). Diffusion-Limited Reactions. Comprehensive Chemical Kinetics. Vol. 25. Elsevier. ISBN 0-444-42354-0. נבדק ב-13 באוגוסט 2013.
{{cite book}}
: (עזרה) - ^ Skellam, J. G. (1951). Random Dispersal in Theoretical Populations. Biometrika. Vol. 38. p. 196. doi:10.2307/2332328. ISSN 0006-3444.,Skellam, J. G. (1952). Studies in Statistical Ecology: I. Spatial Pattern. Biometrika. Vol. 39. p. 346. doi:10.2307/2334030. ISSN 0006-3444.
- ^ Larralde, Hernan; Trunfio, Paul; Havlin, Shlomo; Stanley, H. Eugene; Weiss, George H. (1992). Territory covered by N diffusing particles. Nature. Vol. 355. pp. 423–426. Bibcode:1992Natur.355..423L. doi:10.1038/355423a0. ISSN 0028-0836.,Larralde, Hernan; Trunfio, Paul; Havlin, Shlomo; Stanley, H.; Weiss, George (1992). Number of distinct sites visited by N random walkers. Physical Review A. Vol. 45. pp. 7128–7138. Bibcode:1992PhRvA..45.7128L. doi:10.1103/PhysRevA.45.7128. ISSN 1050-2947.; for insights regarding the problem of N random walkers, see Shlesinger, Michael F. (1992). New paths for random walkers. Nature. Vol. 355. pp. 396–397. Bibcode:1992Natur.355..396S. doi:10.1038/355396a0. ISSN 0028-0836. and the color artwork illustrating the article.
- ^ Evans, Lawrence C. (2010). "§5.8.1". Differential Equations, Partial (2nd ed.). p. 290. ISBN 0-8218-4974-3
- ^ http://mathworld.wolfram.com/CayleyGraph.html
- ^ קובץ:Https://www.youtube.com/watch?v=adNeBLkP8ZM
- ^ Neal Madras and Gordon Slade (1996), The Self-Avoiding Walk, Birkhäuser Boston. ISBN 0-8176-3891-1.
- ^ S. Hemmer and P. C. Hemmer (1984), "An average self-avoiding random walk on the square lattice lasts 71 steps", J. Chem. Phys., 81: 584, Bibcode:1984JChPh..81..584H, doi:10.1063/1.447349
- ^ Gregory Lawler (1996). Intersection of random walks, Birkhäuser Boston. ISBN 0-8176-3892-X.
- ^ Gregory Lawler, Conformally Invariant Processes in the Plane, book.ps.
- ^ Robin Pemantle (2007), A survey of random processes with reinforcement.
- ^ C.-K. Peng, J. Mietus, J. M. Hausdorff, S. Havlin, H. E. Stanley, A. L. Goldberger (1993). "Long-range anticorrelations and non-gaussian behavior of the heartbeat". Phys. Rev. Lett. pp. 1343–6. Bibcode:1993PhRvL..70.1343P. doi:10.1103/PhysRevLett.70.1343. PMID 10054352.
{{cite web}}
: תחזוקה - ציטוט: multiple names: authors list (link) - ^ C.-K. Peng, S. V. Buldyrev, A. L. Goldberger, S. Havlin, F. Sciortino, M. Simons, H. E. Stanley (1992). "Long-range correlations in nucleotide sequences". Nature. pp. 168–70. Bibcode:1992Natur.356..168P. doi:10.1038/356168a0. PMID 1301010.
{{cite web}}
: תחזוקה - ציטוט: multiple names: authors list (link) - ^ Y. Liu, P. Cizeau, M. Meyer, C.-K. Peng, H. E. Stanley (1997). Correlations in economic time series. Physica A. Vol. 245. p. 437. doi:10.1016/S0378-4371(97)00368-3.
{{cite book}}
: תחזוקה - ציטוט: multiple names: authors list (link) - ^ E. Koscielny-Bunde, A. Bunde, S. Havlin, H. E. Roman, Y. Goldreich, H.-J. Schellenhuber (1998). "Indication of a universal persistence law governing atmospheric variability". Phys. Rev. Lett. p. 729. Bibcode:1998PhRvL..81..729K. doi:10.1103/PhysRevLett.81.729.
{{cite web}}
: תחזוקה - ציטוט: multiple names: authors list (link) - ^ http://press.princeton.edu/chapters/s8275.pdf
- ^ Cootner, Paul H. (1964). The random character of stock market prices. MIT Press. ISBN 978-0-262-03009-0.
- ^ Malkiel, Burton G. (1973). A Random Walk Down Wall Street (6th ed.). W.W. Norton & Company, Inc. ISBN 0-393-06245-7.
- ^ Kendall, M. G.; Bradford Hill, A (1953). "The Analysis of Economic Time-Series-Part I: Prices". Journal of the Royal Statistical Society. A (General) (Blackwell Publishing) 116 (1): 11–34. JSTOR 2980947.
- ^ Amoeba discoideum Dictyosteliumame
- ^ Leo Grady (2006): "Random Walks for Image Segmentation", IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 1768–1783, Vol. 28, No. 11
- ^ Ralf Engbert, Konstantin Mergenthaler, Petra Sinn, and Arkady Pikovsk: "An integrated model of fixational eye movements and microsaccades"
- ^ Nosofsky, 1997
- ^ Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang, and Reza Bosagh Zadeh WTF: The who-to-follow system at Twitter, Proceedings of the 22nd international conference on World Wide Web