הילוך מקרי

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

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

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

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

הגדרה[עריכת קוד מקור | עריכה]

הילוך מקרי בזמן בדיד[עריכת קוד מקור | עריכה]

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

הילוך מקרי בזמן רציף[עריכת קוד מקור | עריכה]

יהי משתנה מקרי כלשהו. עבור כל נגדיר

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

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

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

הילוך מקרי בסריג[עריכת קוד מקור | עריכה]

מודל פופולרי הוא של הילוך מקרי על סריג, בו בכל שלב המיקום קופץ לאתר אחר לפי התפלגות כלשהי. במקרה של הילוך מקרי פשוט, המיקום יכול לקפוץ רק לאתרים שכנים על הסריג. במקרה פשוט של הילוך מקרי סימטרי על סריג בו מספר השכנים של כל קודקוד סופי, ההסתברות זהה לקפיצת המיקום לכל אחד מהשכנים המידיים. כלומר, בכל קודקוד, הצעד הבא מפולג אחיד על פני הקודקודים השכנים. הדוגמה היסודית ביותר היא של הילוך מקרי על הסריג השלם ה-d-ממדי (המכונה לעיתים סריג היפרקובי) .[10]

הילוך מקרי על סריג חד-ממדי[עריכת קוד מקור | עריכה]

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

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

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

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

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

מה שמרמז כי , מרחק ההזזות הצפוי לאחר n צעדים, צריך להיות מסדר גודל של . ובעצם:[11]

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

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

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

חלק מהתוצאות שהוזכרו לעיל ניתן להסיק ממאפייני משולש פסקל. מספר ההליכות השונות של n צעדים בהם כל צעד הוא 1+ או 1- הוא 2n.עבור הילוך מקרי פשוט, כל אחת מההליכות האלו סבירה באותה מידה. על מנת ש- Sn יהיה שווה למספר k זה הכרחי ומספיק שמספר הפעמים אשר תתבצע צעידה של 1+ יעלה על אלה של 1- ב- 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).בממדים גבוהים יותר לסט יש מאפיינים גאומטריים מעניינים. למעשה מקבלים פרקטל דיסקרטי.

היחס לתהליך וינר[עריכת קוד מקור | עריכה]

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

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

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

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

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

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

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

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

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

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

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

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

נשים לב כי בשני הביטויים של השונות מעל מתאימים להתפלגות הקשורה לווקטור המקשר את שני קצוות של ההילוך המקרי, בתלת ממד. השונות הקשורה לכל רכיב , or היא רק שליש מערך זה (עדיין בתלת ממד). לכן עבור דו-ממד:[16]

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

הילוך מקרי גאוסיאני[עריכת קוד מקור | עריכה]

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

כאן, גודל הצעד היא ההתפלגות נורמלית מצטברת ההפוכה כאשר 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 צעדים ייפלו בין .

דיפוזיה אנומלית[עריכת קוד מקור | עריכה]

במערכות בעלות חוסר סדר כגון פרקטלים לא יכולה להיות פרופורציונלית ל אלא ל. המעריך <המתמטיקה> d_w </ מתמטיקה> נקרא מעריך הדיפוזיה האנומלית ויכול להיות גדול יותר או קטן יותר מ-2. [18] דיפוזיה אנומלית יכולה גם לבוא לידי ביטוי כ-σr2 ~ Dtα כאשר α הוא פרמטר אנומליה.

מספר אתרים שונים[עריכת קוד מקור | עריכה]

מספר האתרים השונים אשר ביקר בהם מהלך בודד נחקר בהרחבה עבור סריג מממדים 2 ו-3, כמו כן עבור פרקטלים.[19][20] כמות זו שימושית לניתוח של בעיות של מילכוד ותגובות קינטית. כמו כן כמות זו קשורה גם לצפיפות הרטט של המצבים ,[21][22] תהליכי תגובה דיפוזיונית [23] והתפשטות של אוכלוסיות באקולוגיה.[24] ההכללה של הבעיה הזו למספר האתרים השונים בהם ביקרו הילוכים, , לאחרונה נלמדה עבור d ממדים בסריג אוקלידי.[25] מספר האתרים השונים בהם ביקרו N הולכים אקראיים לא קשור בצורה פשוטה למספר האתרים השונים אשר ביקר בהם כל אחד מההולכים.

וריאציות של הילוכים מקריים[עריכת קוד מקור | עריכה]

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

הילוך מקרי בגרפים[עריכת קוד מקור | עריכה]

הילוך מקרי באורך K על גרף אינסופי G עם שורש 0 היא תהליך סטוכסטי עם משתנים מקריים כך ש כך ש ו- הוא קודקוד הנבחר באקראי באופן מהשכנים של .

לאחר מכן המספר הוא ההסתברות שהילוך באורך k המתחילה מv' מסתיימת בW.

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

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

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

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

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

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

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

החל בשנת 1980, מחקר רב הושקע בחיבור תכונות של הגרף להילוכים מקריים. בנוסף לחיבור לרשת החשמל שתואר לעיל, יש קשרים חשובים לאי-שוויון איזופרימטרי, אי-שוויון פונקציונלי כגון סובולב (סובולב אי שוויון) ופואנקרה (אי שוויון פואנקרה[26]) והמאפיינים של הפתרונות של המשוואה לפלס. חלק משמעותי של מחקר זה התמקד בגרף קיילי.[27] לדוגמה, ההוכחה דייב באייר ו פרסי דיאקוניס כי 7 עירבובי ריפל שאפל[28] מספיקים כדי לערבב חפיסת הקלפים היא תוצאה על הילוך מקרי על חבורת הסימטריות , ההוכחה משתמשת במבנה הקבוצה באופן מהותי. במקרים רבים תוצאות בדידות אלה נגזרות מהיריעה וחבורת לי.

הילוך מקרי עם אינטראקציה עצמית[עריכת קוד מקור | עריכה]

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

  • הילוך תוך כדי הימנעות עצמית.[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. נסמן ב- את מקומו של החלקיק ה-i לאחר n צעדים (שימו לב ש-x יכול להיות גם שלילי, אם החלקיק עשה יותר צעדים שמאלה מאשר ימינה .)

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

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

.

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

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

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

לכן בממוצע:

ניתן לראות כי מטעמי סימטריה, אולם כעת האיבר השלישי באגף השמאלי אינו 0. ולכן נקבל:

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

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

מעניין לראות כי חלקיק שעושה n צעדים שכולם באותו כיוון היה מגיע למרחק 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]

הילוך מקרי בביולוגיה[עריכת קוד מקור | עריכה]

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

מידול תנועה ביולוגית[עריכת קוד מקור | עריכה]

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

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

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

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

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

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

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

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

שימושים[עריכת קוד מקור | עריכה]

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

ראו גם[עריכת קוד מקור | עריכה]

לקריאה נוספת[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]

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

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ Pearson, K. (1905). The Problem of the Random Walk. Nature. 72, 294.
  2. ^ Van Kampen N. G., Stochastic Processes in Physics and Chemistry, revised and enlarged edition (North-Holland, Amsterdam) 1992.
  3. ^ Redner S., A Guide to First-Passage Process (Cambridge University Press, Cambridge, UK) 2001.
  4. ^ Goel N. W. and Richter-Dyn N., Stochastic Models in Biology (Academic Press, New York) 1974.
  5. ^ Doi M. and Edwards S. F., The Theory of Polymer Dynamics (Clarendon Press, Oxford) 1986
  6. ^ De Gennes P. G., Scaling Concepts in Polymer Physics (Cornell University Press, Ithaca and London) 1979.
  7. ^ Risken H., The Fokker–Planck Equation (Springer, Berlin) 1984.
  8. ^ 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 .
  9. ^ Cox D. R., Renewal Theory (Methuen, London) 1962.
  10. ^ Révész Pal, Random walk in random and non random environments, World Scientific, 1990
  11. ^ http://mathworld.wolfram.com/RandomWalk1-Dimensional.html
  12. ^ M. Kotani, T. Sunada (2003). "Spectral geometry of crystal lattices". Contemporary. Math. 338: 271–305. doi:10.1090/conm/338/06077.
  13. ^ 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.
  14. ^ Pólya's Random Walk Constants
  15. ^ Dana Mackenzie, Taking the Measure of the Wildest Dance on Earth, Science, Vol. 290, no. 5498, pp. 1883–1884.
  16. ^ [1]
  17. ^ [2]
  18. ^ D. Ben-Avraham and S. Havlin, Diffusion and Reactions in Fractals and Disordered Systems, Cambridge University Press, 2000.
  19. ^ Weiss, George H.; Rubin, Robert J. (1982). "Random Walks: Theory and Selected Applications" 52. עמ' 363–505. ISSN 1934-4791. doi:10.1002/9780470142769.ch5. 
  20. ^ Blumen, A.; Klafter, J.; Zumofen, G. (1986). "Models for Reaction Dynamics in Glasses" 1. עמ' 199–265. Bibcode:1986PCMLD...1..199B. ISSN 0924-459X. doi:10.1007/978-94-009-4650-7_5. 
  21. ^ Alexander, S.; Orbach, R. (1982). "Density of states on fractals : " fractons "". Journal de Physique Lettres 43 (17): 625–631. ISSN 0302-072X. doi:10.1051/jphyslet:019820043017062500. 
  22. ^ Rammal, R.; Toulouse, G. (1983). "Random walks on fractal structures and percolation clusters". Journal de Physique Lettres 44 (1): 13–22. ISSN 0302-072X. doi:10.1051/jphyslet:0198300440101300. 
  23. ^ Smoluchowski, M.V. (1917). "Versuch einer mathematischen Theorie der Koagulationskinetik kolloider Lösungen". Z. Phys. Chem (29): 129–168. ,Rice, S.A. (1 במרץ 1985). Diffusion-Limited Reactions. Comprehensive Chemical Kinetics 25. Elsevier. ISBN 0-444-42354-0. בדיקה אחרונה ב-13 באוגוסט 2013. 
  24. ^ Skellam, J. G. (1951). "Random Dispersal in Theoretical Populations". Biometrika 38 (1/2): 196. ISSN 0006-3444. doi:10.2307/2332328. ,Skellam, J. G. (1952). "Studies in Statistical Ecology: I. Spatial Pattern". Biometrika 39 (3/4): 346. ISSN 0006-3444. doi:10.2307/2334030. 
  25. ^ Larralde, Hernan; Trunfio, Paul; Havlin, Shlomo; Stanley, H. Eugene; Weiss, George H. (1992). "Territory covered by N diffusing particles". Nature 355 (6359): 423–426. Bibcode:1992Natur.355..423L. ISSN 0028-0836. doi:10.1038/355423a0. ,Larralde, Hernan; Trunfio, Paul; Havlin, Shlomo; Stanley, H.; Weiss, George (1992). "Number of distinct sites visited by N random walkers". Physical Review A 45 (10): 7128–7138. Bibcode:1992PhRvA..45.7128L. ISSN 1050-2947. doi:10.1103/PhysRevA.45.7128. ; for insights regarding the problem of N random walkers, see Shlesinger, Michael F. (1992). "New paths for random walkers". Nature 355 (6359): 396–397. Bibcode:1992Natur.355..396S. ISSN 0028-0836. doi:10.1038/355396a0.  and the color artwork illustrating the article.
  26. ^ Evans, Lawrence C. (2010). "§5.8.1". Differential Equations, Partial (2nd ed.). p. 290. ISBN 0-8218-4974-3
  27. ^ http://mathworld.wolfram.com/CayleyGraph.html
  28. ^ קובץ:Https://www.youtube.com/watch?v=adNeBLkP8ZM
  29. ^ Neal Madras and Gordon Slade (1996), The Self-Avoiding Walk, Birkhäuser Boston. ISBN 0-8176-3891-1.
  30. ^ 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 
  31. ^ Gregory Lawler (1996). Intersection of random walks, Birkhäuser Boston. ISBN 0-8176-3892-X.
  32. ^ Gregory Lawler, Conformally Invariant Processes in the Plane, book.ps.
  33. ^ Robin Pemantle (2007), A survey of random processes with reinforcement.
  34. ^ 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. 70 (9): 1343–6. Bibcode:1993PhRvL..70.1343P. PMID 10054352. doi:10.1103/PhysRevLett.70.1343. 
  35. ^ 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 356 (6365): 168–70. Bibcode:1992Natur.356..168P. PMID 1301010. doi:10.1038/356168a0. 
  36. ^ Y. Liu, P. Cizeau, M. Meyer, C.-K. Peng, H. E. Stanley (1997). "Correlations in economic time series". Physica A 245 (3–4): 437. doi:10.1016/S0378-4371(97)00368-3. 
  37. ^ 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. 81 (3): 729. Bibcode:1998PhRvL..81..729K. doi:10.1103/PhysRevLett.81.729. 
  38. ^ http://press.princeton.edu/chapters/s8275.pdf
  39. ^ Cootner, Paul H. (1964). The random character of stock market prices. MIT Press. ISBN 978-0-262-03009-0.
  40. ^ Malkiel, Burton G. (1973). A Random Walk Down Wall Street (6th ed.). W.W. Norton & Company, Inc. ISBN 0-393-06245-7.
  41. ^ 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.
  42. ^ Amoeba discoideum Dictyosteliumame
  43. ^ Leo Grady (2006): "Random Walks for Image Segmentation", IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 1768–1783, Vol. 28, No. 11
  44. ^ Ralf Engbert, Konstantin Mergenthaler, Petra Sinn, and Arkady Pikovsk: "An integrated model of fixational eye movements and microsaccades"
  45. ^ Nosofsky, 1997
  46. ^ 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