المشي العشوائي

من الأمثلة البسيطة على المشي العشوائي المشي العشوائي على خط الأعداد الصحيحة .${\displaystyle \mathbb {Z} }$، والتي تبدأ من 0 وتتحرك في كل خطوة بمقدار +1 أو -1 باحتمالية متساوية.

يمكن توضيح هذه العملية كما يلي: يوضع مؤشر عند الصفر على خط الأعداد، ثم تُرمى قطعة نقدية متوازنة. إذا ظهر الوجه (صورة)، يُحرك المؤشر وحدة واحدة إلى اليمين. وإذا ظهر الظهر (كتابة)، يُحرك المؤشر وحدة واحدة إلى اليسار. بعد خمس رميات، يمكن أن يكون المؤشر عند -5، أو -3، أو -1، أو 1، أو 3، أو 5. عند خمس رميات، وظهور ثلاثة وجوه وظهرين، بأي ترتيب، سيستقر المؤشر عند 1. هناك 10 طرق للوصول إلى 1 (برمي ثلاثة وجوه وظهرين)، و10 طرق للوصول إلى -1 (برمي ثلاثة ظهورين ووجهين)، و5 طرق للوصول إلى 3 (برمي أربعة وجوه وظهر واحد)، و5 طرق للوصول إلى -3 (برمي أربعة ظهورين ووجه واحد)، وطريقة واحدة للوصول إلى 5 (برمي خمسة وجوه)، وطريقة واحدة للوصول إلى -5 (برمي خمسة ظهورين). انظر إلى الشكل أدناه للاطلاع على توضيح للنتائج المحتملة لخمس رميات.

لتعريف هذه المسيرة بشكل رسمي، خذ متغيرات عشوائية مستقلة${\displaystyle Z_{1},Z_{2},\dots }$حيث تكون قيمة كل متغير إما 1 أو -1، باحتمالية 50% لكل قيمة، وتعيين${\displaystyle S_{0}=0}$و${\textstyle S_{n}=\sum _{j=1}^{n}Z_{j}.}$المسلسل​${\displaystyle \{S_{n}\}}$يُطلق عليه اسم المشي العشوائي البسيط على${\displaystyle \mathbb {Z} }$تُعطي هذه السلسلة (مجموع سلسلة من -1 و1) المسافة الإجمالية المقطوعة، إذا كان طول كل جزء من المسار واحدًا. القيمة المتوقعة${\displaystyle E(S_{n})}$ل${\displaystyle S_{n}}$يساوي صفرًا. أي أن متوسط ​​جميع رميات العملة يقترب من الصفر مع ازدياد عدد الرميات. وينتج هذا عن خاصية الجمع المحدود للتوقع: $${\displaystyle E(S_{n})=\sum _{j=1}^{n}E(Z_{j})=0.}$$

حساب مماثل، باستخدام استقلال المتغيرات العشوائية وحقيقة أن${\displaystyle E(Z_{n}^{2})=1}$، مما يدل على ما يلي: $${\displaystyle E(S_{n}^{2})=\sum _{i=1}^{n}E(Z_{i}^{2})+2\sum _{1\leq i<j\leq n}E(Z_{i}Z_{j})=n.}$$

هذا يشير إلى أن${\displaystyle E(|S_{n}|)\,\!}$ينبغي أن تكون مسافة الإزاحة المتوقعة بعد n خطوة من رتبة${\displaystyle {\sqrt {n}}}$في الواقع ، ^{[ 5 ]}$${\displaystyle \lim _{n\to \infty }{\frac {E(|S_{n}|)}{\sqrt {n}}}={\sqrt {\frac {2}{\pi }}}.}$$

للإجابة على سؤال كم مرة سيعبر مسار عشوائي خطًا حدوديًا إذا سُمح له بالاستمرار في السير إلى الأبد، فإن مسارًا عشوائيًا بسيطًا على${\displaystyle \mathbb {Z} }$سيعبر كل نقطة عددًا لا نهائيًا من المرات. لهذه النتيجة أسماء عديدة: ظاهرة عبور المستوى ، أو التكرار ، أو إفلاس المقامر . والسبب في التسمية الأخيرة هو أن المقامر الذي يملك مبلغًا محدودًا من المال سيخسر في النهاية عند لعبه لعبة عادلة ضد بنك يملك مبلغًا لا نهائيًا من المال. سيتحرك مال المقامر بشكل عشوائي، وسيصل إلى الصفر في مرحلة ما، وتنتهي اللعبة.

إذا كان a و b عددين صحيحين موجبين، فإن العدد المتوقع للخطوات حتى يصل مسار عشوائي بسيط أحادي البعد يبدأ من 0 إلى b أو -a هو ab . واحتمالية وصول هذا المسار إلى b قبل -a هي${\displaystyle a/(a+b)}$ويمكن استنتاج ذلك من حقيقة أن المشي العشوائي البسيط هو مارتينجال . ويمكن حساب هذه التوقعات واحتمالات النجاح في${\displaystyle O(a+b)}$في سلسلة ماركوف العشوائية أحادية البعد العامة.

يمكن استنتاج بعض النتائج المذكورة أعلاه من خصائص مثلث باسكال . عدد المسارات المختلفة المكونة من n خطوة، حيث تكون كل خطوة إما +1 أو -1، هو 2^ ⁿ . بالنسبة للمسار العشوائي البسيط، يكون احتمال كل مسار من هذه المسارات متساوياً. لكي يكون S _^n مساوياً للعدد k، من الضروري والكافي أن يزيد عدد مرات ظهور +1 في المسار عن عدد مرات ظهور -1 بمقدار k . وبالتالي، يجب أن يظهر +1 ( n  + k )/2 مرة خلال n خطوة من خطوات المسار، ومن ثم عدد المسارات التي تحقق هذا الشرط. ${\displaystyle S_{n}=k}$يساوي عدد طرق اختيار ( ن  + ك )/2 عنصرًا من مجموعة مكونة من ن عنصرًا، ^{[ 6 ]} ويرمز له بـ ${\textstyle n \choose (n+k)/2}$لكي يكون لهذا معنى، من الضروري أن يكون n  + k عددًا زوجيًا، مما يعني أن n و k إما أن يكونا زوجيين أو فرديين. وبالتالي، فإن احتمال ${\displaystyle S_{n}=k}$يساوي${\textstyle 2^{-n}{n \choose (n+k)/2}}$من خلال تمثيل عناصر مثلث باسكال بدلالة المضروب واستخدام صيغة ستيرلينغ ، يمكن الحصول على تقديرات جيدة لهذه الاحتمالات للقيم الكبيرة لـ${\displaystyle n}$.

تتضح هذه العلاقة مع مثلث باسكال عند قيم n الصغيرة . عند صفر دورة، يكون الاحتمال الوحيد هو البقاء عند الصفر. أما عند دورة واحدة، فهناك احتمال واحد للوقوف على -1 أو احتمال واحد للوقوف على 1. عند دورتين، يمكن أن يتحرك المؤشر عند 1 إلى 2 أو يعود إلى الصفر. ويمكن أن يتحرك المؤشر عند -1 إلى -2 أو يعود إلى الصفر. لذلك، هناك احتمال واحد للوقوف على -2، واحتمالان للوقوف على الصفر، واحتمال واحد للوقوف على 2.

ك	-5	-4	-3	-2	-1	0	1	2	3	4	5
${\displaystyle P[S_{0}=k]}$						1
${\displaystyle 2P[S_{1}=k]}$					1		1
${\displaystyle 2^{2}P[S_{2}=k]}$				1		2		1
${\displaystyle 2^{3}P[S_{3}=k]}$			1		3		3		1
${\displaystyle 2^{4}P[S_{4}=k]}$		1		4		6		4		1
${\displaystyle 2^{5}P[S_{5}=k]}$	1		5		10		10		5		1

تصف نظرية النهاية المركزية وقانون اللوغاريتم المتكرر جوانب مهمة من سلوك المسارات العشوائية البسيطة على${\displaystyle \mathbb {Z} }$. على وجه الخصوص، يستلزم الأمر الأول أنه مع زيادة n ، تقترب الاحتمالات (المتناسبة مع الأرقام في كل صف) من التوزيع الطبيعي .

وبعبارة أدق، مع العلم أن${\textstyle \mathbb {P} (X_{n}=k)=2^{-n}{\binom {n}{(n+k)/2}}}$وباستخدام صيغة ستيرلينغ، يكون لدينا

$${\displaystyle {\log \mathbb {P} (X_{n}=k)}=n\left[\left({1+{\frac {k}{n}}+{\frac {1}{2n}}}\right)\log \left(1+{\frac {k}{n}}\right)+\left({1-{\frac {k}{n}}+{\frac {1}{2n}}}\right)\log \left(1-{\frac {k}{n}}\right)\right]+\log {\frac {\sqrt {2}}{\sqrt {\pi }}}+o(1).}$$

إصلاح التحجيم${\textstyle k=\lfloor {\sqrt {n}}x\rfloor }$، ل${\textstyle x}$تم إصلاحها، وباستخدام التوسيع${\textstyle \log(1+{k}/{n})=k/n-k^{2}/2n^{2}+\dots }$متى${\textstyle k/n}$يختفي، ويتبعه

$${\displaystyle {\mathbb {P} \left({\frac {X_{n}}{n}}={\frac {\lfloor {\sqrt {n}}x\rfloor }{\sqrt {n}}}\right)}={\frac {1}{\sqrt {n}}}{\frac {1}{2{\sqrt {\pi }}}}e^{-{x^{2}}}(1+o(1)).}$$

بأخذ النهاية (وملاحظة أن${\textstyle {1}/{\sqrt {n}}}$(يتوافق مع تباعد شبكة القياس) نجد الكثافة الغاوسية${\textstyle f(x)={\frac {1}{2{\sqrt {\pi }}}}e^{-{x^{2}}}}$في الواقع، بالنسبة لمتغير عشوائي متصل تمامًا${\textstyle X}$بكثافة${\textstyle f_{X}}$هذا صحيح${\textstyle \mathbb {P} \left(X\in [x,x+dx)\right)=f_{X}(x)dx}$، مع${\textstyle dx}$بما يتوافق مع تباعد متناهي الصغر.

كتعميم مباشر، يمكن النظر في المسارات العشوائية على الشبكات البلورية (الرسوم البيانية التغطية الأبيلية ذات العدد اللانهائي من التكرارات على الرسوم البيانية المحدودة). في الواقع، من الممكن إثبات نظرية النهاية المركزية ونظرية الانحراف الكبير في هذا السياق. ^{[ 7 ] [ 8 ]}

في الأبعاد الأعلى، تتمتع مجموعة النقاط التي يتم السير عليها عشوائيًا بخصائص هندسية مثيرة للاهتمام. في الواقع، نحصل على شكل كسري منفصل ، أي مجموعة تُظهر تشابهًا ذاتيًا عشوائيًا على نطاقات واسعة. على نطاقات صغيرة، يمكن ملاحظة "التعرج" الناتج عن الشبكة التي يتم السير عليها. مسار السير العشوائي هو مجموعة النقاط التي تمت زيارتها، تُعتبر مجموعة بغض النظر عن وقت وصول السير إلى تلك النقطة. في بُعد واحد، يكون المسار ببساطة جميع النقاط بين أدنى ارتفاع وأعلى ارتفاع وصل إليه السير (كلاهما، في المتوسط، من رتبة${\displaystyle {\sqrt {n}}}$).

لتوضيح الحالة ثنائية الأبعاد، يمكن تخيل شخص يسير عشوائيًا في مدينة. المدينة لا نهائية عمليًا، ومرتبة على شكل شبكة مربعة من الأرصفة. عند كل تقاطع، يختار الشخص عشوائيًا أحد المسارات الأربعة الممكنة (بما في ذلك المسار الذي سلكه في الأصل). رسميًا، هذا مسار عشوائي على مجموعة جميع النقاط في المستوى ذات الإحداثيات الصحيحة .

للإجابة على سؤال عودة الشخص إلى نقطة البداية الأصلية للمسار، يُعدّ هذا مكافئًا ثنائي الأبعاد لمسألة عبور المستوى المذكورة سابقًا. في عام ١٩٢١، أثبت جورج بوليا أن الشخص سيعود حتمًا تقريبًا في مسار عشوائي ثنائي الأبعاد، ولكن في ثلاثة أبعاد أو أكثر، يتناقص احتمال العودة إلى نقطة البداية مع ازدياد عدد الأبعاد. في ثلاثة أبعاد، ينخفض ​​الاحتمال إلى حوالي ٣٤٪. ^{[ ٩ ]} وقد اشتهر عالم الرياضيات شيزو كاكوتاني بالإشارة إلى هذه النتيجة بالمقولة التالية: "سيجد الرجل السكران طريقه إلى المنزل، لكن الطائر السكران قد يضل طريقه إلى الأبد". ^{[ ١٠ ]}

احتمالية التكرار تكون بشكل عام${\displaystyle p=1-\left({\frac {1}{(2\pi )^{d}}}\int _{[-\pi ,\pi ]^{d}}{\frac {\prod _{i=1}^{d}d\theta _{i}}{1-{\frac {1}{d}}\sum _{i=1}^{d}\cos \theta _{i}}}\right)^{-1}}$والتي يمكن اشتقاقها عن طريق الدوال المولدة ^{[ 11 ]} أو عملية بواسون. ^{[ 12 ]}

هناك صيغة أخرى لهذا السؤال، طرحها بوليا أيضاً، وهي: "إذا انطلق شخصان من نفس نقطة البداية، فهل سيلتقيان مجدداً؟" ^{[ 13 ]} يمكن إثبات أن الفرق بين موقعيهما (مساران عشوائيان مستقلان) هو أيضاً مسار عشوائي بسيط، لذا فإنهما يلتقيان مجدداً بشكل شبه مؤكد في مسار ثنائي الأبعاد، ولكن بالنسبة للأبعاد الثلاثة فأكثر، يتناقص الاحتمال مع ازدياد عدد الأبعاد. كما أثبت بول إردوش وصموئيل جيمس تايلور في عام 1960 أنه بالنسبة للأبعاد الأقل من أو تساوي 4، فإن مسارين عشوائيين مستقلين يبدآن من أي نقطتين معطيتين يتقاطعان بشكل شبه مؤكد لعدد لا نهائي من المرات، ولكن بالنسبة للأبعاد الأعلى من 5، فإنهما يتقاطعان بشكل شبه مؤكد لعدد محدود من المرات فقط. ^{[ 14 ]}

تُعطى الدالة التقاربية للمسار العشوائي ثنائي الأبعاد مع ازدياد عدد الخطوات بتوزيع رايلي . ويُعدّ التوزيع الاحتمالي دالةً لنصف القطر من نقطة الأصل، بينما يكون طول الخطوة ثابتًا في كل خطوة. في هذه الحالة، يُفترض أن طول الخطوة يساوي 1، وN هو العدد الإجمالي للخطوات، وr هو نصف القطر من نقطة الأصل. ^{[ 15 ]}

$${\displaystyle P(r)={\frac {2r}{N}}e^{-r^{2}/N}}$$

عملية وينر هي عملية عشوائية ذات سلوك مشابه للحركة البراونية ، وهي ظاهرة فيزيائية تتمثل في انتشار جسيم دقيق في سائل. ( يُطلق على عملية وينر أحيانًا اسم "الحركة البراونية"، على الرغم من أن هذا في الواقع خلط بين النموذج والظاهرة التي يتم نمذجتها).

عملية وينر هي الحدّ القياسي للمشي العشوائي في بُعد واحد. هذا يعني أنه إذا وُجد مسار عشوائي بخطوات صغيرة جدًا، فإنه يُقارب عملية وينر (وبدقة أقل، الحركة البراونية). بتعبير أدق، إذا كان حجم الخطوة ε، فإنه يلزم القيام بمسار طوله L /ε² ^لتقريب طول وينر L. عندما يؤول حجم الخطوة إلى الصفر (ويزداد عدد الخطوات تناسبًا)، يتقارب المشي العشوائي إلى عملية وينر بالمعنى المناسب. رسميًا، إذا كان B هو فضاء جميع المسارات ذات الطول L ذات الطوبولوجيا القصوى، وإذا كان M هو فضاء القياس على B ذي طوبولوجيا المعيار، فإن التقارب يكون في الفضاء M. وبالمثل، فإن عملية وينر في عدة أبعاد هي الحدّ القياسي للمشي العشوائي في نفس عدد الأبعاد.

المسار العشوائي هو شكل كسري منفصل (دالة ذات أبعاد صحيحة؛ 1، 2، ...)، بينما مسار عملية وينر هو شكل كسري حقيقي، وهناك صلة بينهما. على سبيل المثال، لنفترض مسارًا عشوائيًا حتى يصل إلى دائرة نصف قطرها يساوي r مضروبًا في طول الخطوة. متوسط ​​عدد الخطوات التي يقطعها هو r² ^. هذه الحقيقة هي الصيغة المنفصلة لحقيقة أن مسار عملية وينر هو شكل كسري ذو بُعد هاوسدورف 2. 

في بُعدين، يبلغ متوسط ​​عدد النقاط التي تقع على حدود مسار المشي العشوائي نفسه r ^4/3 . وهذا يتوافق مع حقيقة أن حدود مسار عملية وينر هي كسورية ذات بُعد 4/3، وهي حقيقة تنبأ بها ^{ماندلبروت} باستخدام المحاكاة ، ولكن لم يتم إثباتها إلا في عام 2000 بواسطة لولر وشرام وفيرنر . ^{[ 16} ]

تتمتع عملية وينر بالعديد من التناظرات التي لا تتمتع بها عملية المشي العشوائي. فعلى سبيل المثال، تكون عملية وينر ثابتة عند الدوران، بينما لا تكون عملية المشي العشوائي كذلك، لأن الشبكة الأساسية ليست ثابتة (عملية المشي العشوائي ثابتة عند الدوران بزاوية 90 درجة، بينما تكون عملية وينر ثابتة عند الدوران بزاوية 17 درجة، على سبيل المثال). هذا يعني أنه في كثير من الحالات، يكون حل المسائل المتعلقة بعملية المشي العشوائي أسهل عند تحويلها إلى عملية وينر، ثم حل المسألة هناك، ثم تحويلها مرة أخرى. من ناحية أخرى، يكون حل بعض المسائل أسهل باستخدام عمليات المشي العشوائي نظرًا لطبيعتها المتقطعة.

يمكن ربط المشي العشوائي وعملية وينر ، أي أنهما يظهران على نفس فضاء الاحتمالات بطريقة تعتمد على بعضهما البعض، مما يجعلهما متقاربين للغاية. أبسط أنواع هذا الربط هو تضمين سكوروهود ، ولكن توجد روابط أكثر دقة، مثل نظرية تقريب كوملوس-ماجور-توسنادي .

يخضع تقارب المسار العشوائي نحو عملية وينر لنظرية النهاية المركزية ونظرية دونسكر . بالنسبة لجسيم في موضع ثابت معروف عند الزمن t  =  0، تنص نظرية النهاية المركزية على أنه بعد عدد كبير من الخطوات المستقلة في المسار العشوائي، يتوزع موضع الجسيم وفقًا لتوزيع طبيعي ذي تباين كلي قدره :

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

حيث يمثل t الوقت المنقضي منذ بداية المشي العشوائي،${\displaystyle \varepsilon }$وهو حجم خطوة من خطوات المشي العشوائي، و${\displaystyle \delta t}$هو الوقت المنقضي بين خطوتين متتاليتين.

يتوافق هذا مع دالة غرين لمعادلة الانتشار التي تتحكم في عملية وينر، مما يشير إلى أنه بعد عدد كبير من الخطوات، يتقارب المشي العشوائي نحو عملية وينر.

في ثلاثة أبعاد، يكون التباين المقابل لدالة غرين لمعادلة الانتشار هو: $${\displaystyle \sigma ^{2}=6\,D\,t.}$$

من خلال مساواة هذه الكمية مع التباين المرتبط بموقع المتجول العشوائي، يحصل المرء على معامل الانتشار المكافئ الذي يجب مراعاته لعملية وينر التقاربية التي يتقارب إليها المتجول العشوائي بعد عدد كبير من الخطوات: $${\displaystyle D={\frac {\varepsilon ^{2}}{6\delta t}}}$$(صالح فقط في وضع ثلاثي الأبعاد).

يتوافق التعبيران عن التباين أعلاه مع التوزيع المرتبط بالمتجه${\displaystyle {\vec {R}}}$الذي يربط طرفي المسار العشوائي، في ثلاثة أبعاد. التباين المرتبط بكل مكون${\displaystyle R_{x}}$،${\displaystyle R_{y}}$أو${\displaystyle R_{z}}$يمثل ثلث هذه القيمة فقط (ولا يزال في البعد الثلاثي).

بالنسبة للرسوم ثنائية الأبعاد: ^{[ 17 ]}

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

بالنسبة لـ 1D: ^{[ 18 ]}

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

عدد المواقع المختلفة التي يزورها شخص واحد يسير عشوائياً${\displaystyle S(t)}$تمت دراسة هذه الكمية على نطاق واسع للشبكات المربعة والمكعبة وللأشكال الكسورية. ^{[ 19 ] [ 20 ]} وهي مفيدة لتحليل مسائل الاحتجاز والتفاعلات الحركية. كما أنها مرتبطة بكثافة الحالات الاهتزازية، ^{[ 21 ] [ 22 ]} وعمليات تفاعلات الانتشار ^{، [ 23 ]} وانتشار التجمعات السكانية في علم البيئة. ^{[ 24 ] [ 25 ]}

يتم إعطاء معدل المعلومات للمشي العشوائي الغاوسي بالنسبة لمسافة الخطأ التربيعي، أي دالة تشويه المعدل التربيعي، بشكل بارامتري بواسطة [ ^{26 ] .}$${\displaystyle R(D_{\theta })={\frac {1}{2}}\int _{0}^{1}\max\{0,\log _{2}\left(S(\varphi )/\theta \right)\}\,d\varphi ,}$$$${\displaystyle D_{\theta }=\int _{0}^{1}\min\{S(\varphi ),\theta \}\,d\varphi ,}$$ أين${\displaystyle S(\varphi )=\left(2\sin(\pi \varphi /2)\right)^{-2}}$لذلك، يستحيل التشفير${\displaystyle {\{Z_{n}\}_{n=1}^{N}}}$باستخدام رمز ثنائي أقل من${\displaystyle NR(D_{\theta })}$بتات واستعادتها بمتوسط ​​خطأ تربيعي متوقع أقل من${\displaystyle D_{\theta }}$من ناحية أخرى، بالنسبة لأي${\displaystyle \varepsilon >0}$يوجد${\displaystyle N\in \mathbb {N} }$كبيرة بما يكفي ورمز ثنائي لا يزيد عن${\displaystyle 2^{NR(D_{\theta })}}$العناصر المتميزة بحيث يكون متوسط ​​الخطأ التربيعي المتوقع في الاستعادة${\displaystyle {\{Z_{n}\}_{n=1}^{N}}}$من هذا الكود على الأكثر${\displaystyle D_{\theta }-\varepsilon }$.

في الاقتصاد المالي ، تُستخدم فرضية السير العشوائي لنمذجة أسعار الأسهم وعوامل أخرى. ^{[ 27 ]} وقد وجدت الدراسات التجريبية بعض الانحرافات عن هذا النموذج النظري، لا سيما في الارتباطات قصيرة الأجل وطويلة الأجل .

في صناعة أشباه الموصلات ، تُستخدم المسارات العشوائية لتحليل تأثيرات المعالجة الحرارية على العُقد الصغيرة. ويُطبَّق هذا الأسلوب لفهم انتشار الشوائب والعيوب وغيرها من المواد المطعِّمة خلال مراحل التصنيع الحرجة. كما تُستخدم معالجات المسارات العشوائية لدراسة انتشار المواد المتفاعلة والناتجة والبلازما خلال عمليات الترسيب الكيميائي للبخار . وقد استُخدم الانتشار المتصل لدراسة تدفق الغازات، على نطاقات ماكروسكوبية، في مفاعلات الترسيب الكيميائي للبخار. إلا أن صغر الأبعاد وزيادة التعقيد قد أجبرنا على معالجتها باستخدام المسارات العشوائية. وهذا يُتيح تحليلًا دقيقًا للعمليات العشوائية ، على المستوى الجزيئي وما دونه، في صناعة أشباه الموصلات.

في علوم الحاسوب ، استُخدمت المسارات العشوائية لتقدير حجم شبكة الإنترنت . ^{[ 28 ]} وفي برمجة الحاسوب، من الممكن حساب قيمة باي باستخدام مسار عشوائي. ^{[ 29 ]}

استُخدمت المسارات العشوائية في تحليل الشبكات لحساب احتمالية ربط عقدتين غير مرتبطتين في المستقبل بناءً على الحالة الراهنة للشبكة. وتُناقش خوارزميات متنوعة في المرجع ^{[ 30 ]} ، بما في ذلك خوارزمية PageRank والمسارات العشوائية الخاضعة للإشراف.

في تجزئة الصور ، تُستخدم المسارات العشوائية لتحديد التصنيفات (مثل "كائن" أو "خلفية") التي تُربط بكل بكسل. ^{[ 31 ]} تُعرف هذه الخوارزمية عادةً باسم خوارزمية تجزئة المسارات العشوائية .

استخدم موقع تويتر عمليات المشي العشوائي لتقديم اقتراحات بشأن الأشخاص الذين يجب متابعتهم. ^{[ 32 ]}

كما ذُكر، فإن نطاق الظواهر الطبيعية التي خضعت لمحاولات وصفها بنوع من أنواع المشي العشوائي واسعٌ للغاية. وينطبق هذا بشكل خاص على مجالات الفيزياء، ^{[ 33 ] [ 34 ]} والكيمياء، ^{[ 35 ]} وعلوم المواد ، ^{[ 36 ] [ 37 ]} وعلم الأحياء. ^{[ 38 ] [ 39 ] [ 40 ]}

المسار العشوائي ذو الطول k على الرسم البياني G الذي قد يكون لانهائيًا وله جذر يساوي صفرًا هو عملية عشوائية ذات متغيرات عشوائية${\displaystyle X_{1},X_{2},\dots ,X_{k}}$بحيث${\displaystyle X_{1}=0}$و ${\displaystyle {X_{i+1}}}$هو رأس يتم اختياره عشوائيًا وبشكل منتظم من بين جيرانه${\displaystyle X_{i}}$ثم الرقم${\displaystyle p_{v,w,k}(G)}$هي احتمالية أن تنتهي مسيرة عشوائية طولها k تبدأ من v عند w . على وجه الخصوص، إذا كان G رسمًا بيانيًا جذره 0 ،${\displaystyle p_{0,0,2k}}$هو احتمال أن${\displaystyle 2k}$يعود المشي العشوائي ذو الخطوات إلى 0 .

استكمالاً للمثال المذكور في القسم السابق حول الأبعاد الأعلى، لنفترض الآن أن مدينتنا لم تعد شبكة مربعة مثالية. عندما يصل الشخص إلى مفترق طرق معين، فإنه يختار بين الطرق المتاحة باحتمالية متساوية. وبالتالي، إذا كان للمفترق سبعة مخارج، فسيسلك الشخص كل مخرج باحتمالية سُبع. هذه هي المسيرة العشوائية على الرسم البياني. هل سيصل الشخص إلى منزله؟ اتضح أنه في ظل شروط معتدلة، لا تزال الإجابة نعم، ^{[ 48 ]} ولكن اعتمادًا على الرسم البياني، قد لا تكون الإجابة على السؤال البديل "هل سيلتقي شخصان مرة أخرى؟" هي أنهما سيلتقيان عددًا لا نهائيًا من المرات بشكل شبه مؤكد. ^{[ 49 ]}

مثال على حالة يصل فيها الشخص إلى منزله بشكل شبه مؤكد هو عندما تكون أطوال جميع المربعات بين a و b (حيث a و b أي عددين موجبين محدودين). لاحظ أننا لا نفترض أن الرسم البياني مستوٍ ، أي أن المدينة قد تحتوي على أنفاق وجسور. إحدى طرق إثبات هذه النتيجة هي ربطها بالشبكات الكهربائية . خذ خريطة للمدينة وضع مقاومة مقدارها 1 أوم على كل مربع. الآن، قِس "المقاومة بين نقطة واللانهاية". بعبارة أخرى، اختر قيمة R ، ثم خذ جميع النقاط في الشبكة الكهربائية التي تبعد مسافة أكبر من R عن نقطتنا، وقم بتوصيلها معًا. هذه الآن شبكة كهربائية محدودة، ويمكننا قياس المقاومة من نقطتنا إلى النقاط الموصولة. خذ R إلى اللانهاية. تُسمى هذه النهاية المقاومة بين نقطة واللانهاية . اتضح أن ما يلي صحيح (يمكن إيجاد برهان بسيط في كتاب دويل وسنيل):

نظرية : يكون الرسم البياني عابراً إذا وفقط إذا كانت المقاومة بين نقطة ما واللانهاية محدودة. ولا يهم أي نقطة يتم اختيارها إذا كان الرسم البياني متصلاً.

بمعنى آخر، في نظام عابر، يكفي التغلب على مقاومة محدودة للوصول إلى اللانهاية من أي نقطة. أما في نظام متكرر، فالمقاومة من أي نقطة إلى اللانهاية لا نهائية.

إن هذا التوصيف للزوال والتكرار مفيد للغاية، وعلى وجه التحديد يسمح لنا بتحليل حالة مدينة مرسومة في المستوى مع تحديد المسافات.

المسار العشوائي على الرسم البياني هو حالة خاصة جدًا من سلسلة ماركوف . على عكس سلسلة ماركوف العامة، يتمتع المسار العشوائي على الرسم البياني بخاصية تُسمى التناظر الزمني أو الانعكاسية . وبصورة مبسطة، تعني هذه الخاصية، التي تُسمى أيضًا مبدأ التوازن التفصيلي ، أن احتمالات اجتياز مسار معين في اتجاه أو آخر ترتبط ارتباطًا وثيقًا (إذا كان الرسم البياني منتظمًا ، فإنها متساوية). لهذه الخاصية تبعات مهمة.

ابتداءً من ثمانينيات القرن الماضي، انصبّ اهتمامٌ كبيرٌ على ربط خصائص الرسم البياني بالمسارات العشوائية. فبالإضافة إلى الربط بالشبكة الكهربائية المذكور آنفًا، توجد روابط مهمة مع متباينات المحيط المتساوي (انظر المزيد هنا) ، ومتباينات دالية مثل متباينتي سوبوليف وبوانكاريه ، وخصائص حلول معادلة لابلاس . وقد ركّز جزءٌ كبيرٌ من هذا البحث على رسوم كايلي البيانية للمجموعات المولدة نهائيًا . وفي كثير من الحالات، تُعمَّم هذه النتائج المنفصلة على المتشعبات ومجموعات لي ، أو تُشتق منها .

في سياق الرسوم البيانية العشوائية ، ولا سيما نموذج إردوش-ريني ، تم التوصل إلى نتائج تحليلية لبعض خصائص المشاة العشوائيين. وتشمل هذه النتائج توزيع أوقات الوصول الأولى ^{[ 50 ]} والأخيرة ^{[ 51 ]} للمشاة، حيث يُحدد وقت الوصول الأول بالمرة الأولى التي يدخل فيها المشاة إلى موقع سبق زيارته في الرسم البياني، بينما يُحدد وقت الوصول الأخير بالمرة الأولى التي لا يستطيع فيها المشاة القيام بخطوة إضافية دون إعادة زيارة موقع سبق زيارته.

يُعد كتاب ألدوس وفيل الإلكتروني مرجعًا جيدًا للمشي العشوائي على الرسوم البيانية . أما بالنسبة للمجموعات، فيُرجى مراجعة كتاب ويس. إذا كانت نواة الانتقال${\displaystyle p(x,y)}$هو نفسه عشوائي (بناءً على بيئة)${\displaystyle \omega }$عندما يتضمن قانون المشي العشوائي عنصر العشوائية، يُطلق على هذه العملية اسم "المشي العشوائي في بيئة عشوائية".${\displaystyle \omega }$يُطلق على هذا القانون اسم القانون المُهذّب؛ من ناحية أخرى، إذا${\displaystyle \omega }$إذا اعتُبر القانون ثابتًا، يُطلق عليه قانون مُخمّد. انظر كتاب هيوز، أو كتاب ريفيز، أو محاضرات زيتوني.

يمكننا التفكير في اختيار كل حافة ممكنة بنفس الاحتمالية لتعظيم عدم اليقين (الإنتروبيا) محليًا. ويمكننا أيضًا القيام بذلك على مستوى العالم - في المشي العشوائي ذي الإنتروبيا القصوى (MERW)، نريد أن تكون جميع المسارات متساوية الاحتمالية، أو بعبارة أخرى: لكل رأسين، يكون كل مسار بطول معين متساوي الاحتمالية. ^{[ 52 ]} يتميز هذا المشي العشوائي بخصائص تحديد موقع أقوى بكثير.

توجد عدة نماذج مثيرة للاهتمام للمسارات العشوائية، حيث تعتمد كل خطوة فيها على الخطوات السابقة بطريقة معقدة. جميعها أكثر تعقيدًا من حيث الحل التحليلي مقارنةً بالمسار العشوائي المعتاد؛ ومع ذلك، يمكن الحصول على سلوك أي نموذج من نماذج المسار العشوائي باستخدام الحواسيب. ومن الأمثلة على ذلك:

• المشي المتجنب للذات . ^{[ 53 ]}

المشي المتجنب للذات بطول ن${\displaystyle \mathbb {Z} ^{d}}$هو المسار العشوائي المكون من n خطوة والذي يبدأ من نقطة الأصل، ويجري الانتقالات فقط بين المواقع المتجاورة في${\displaystyle \mathbb {Z} ^{d}}$لا يعود المسار إلى الموقع نفسه، ويتم اختياره بشكل عشوائي من بين جميع هذه المسارات. في بُعدين، وبسبب ظاهرة الاحتجاز الذاتي، يكون المسار النموذجي الذي يتجنب نفسه قصيرًا جدًا، ^{[ 54 ]} بينما في الأبعاد الأعلى، يتجاوز هذا المسار جميع الحدود. وقد استُخدم هذا النموذج بكثرة في فيزياء البوليمرات (منذ ستينيات القرن الماضي).

• المشي العشوائي بعد إزالة الحلقة . ^{[ 55 ] [ 56 ]}
• المشي العشوائي المعزز . ^{[ 57 ]}
• عملية الاستكشاف .
• المشي العشوائي متعدد العوامل . ^{[ 58 ]}

تتمتع عملية المشي العشوائي المختارة لزيادة معدل الإنتروبيا بخصائص تحديد موقع أقوى بكثير.

المسارات العشوائية هي مسارات يكون فيها اتجاه الحركة في وقت ما مرتبطًا باتجاه الحركة في الوقت التالي. وتُستخدم هذه المسارات لنمذجة حركات الحيوانات. ^{[ 59 ] [ 60 ]}