ولگشت

۵ نمونه‌ای از ولگشت؛ محور افقی زمان و محور عمودی مکان متحرک را نشان می‌دهد.

ولگشت یا قدم‌زدن تصادفی (به انگلیسی: random walk)‏، مطالعهٔ رفتار یک مسیر تشکیل شده از گام‌های تصادفی و پی در پی با استفاده از ابزار ریاضیات است. نتایج کاوش در مورد این موضوع در شاخه‌های مختلف علم همچون علوم کامپیوتر، فیزیک، بوم شناسی، اقتصاد، روانشناسی و موارد دیگر به عنوان مدلی پایه برای فرایندهای تصادفی در طول زمان، استفاده شده‌است. به عنوان مثال، مسیر طی شده توسط یک مولکول هنگام حرکت درون گاز یا مایع، مسیر حرکت یک حیوان علف خوار، نوسانات قیمت سهام و وضعیت مالی یک قمارباز؛ مواردی است که می‌تواند با ولگشت مدل سازی شود. عنوان ولگشت را نخستین بار کارل پیرسون در سال ۱۹۰۵ میلادی به کار برد.

انواع مختلفی از ولگشت مورد توجه‌است. معمولاً ولگشت بعنوان زنجیره مارکف فرض می‌شود، در حالی که موارد پیچیدهٔ دیگری نیز وجود دارد و مورد توجه‌است. ولگشت می‌تواند روی یک گراف، خط مستقیم، صفحهٔ مسطح یا در فضایی با ابعاد بالاتر رخ دهد. زمان میان گام‌ها نیز در انواع ولگشت متفاوت است. معمولاً ولگشت در زمان گسسته رخ می‌دهد و با اعداد طبیعی اندیس دهی می‌شود ($X_0,X_1,X_2,\dots$). اما در برخی موارد فاصلهٔ زمانی میان گام‌ها نیز تصادفی است و مشخصهٔ زمانی پیوسته تعریف می‌شود. ولگشت موضوعی اساسی در مباحث فرایندهای مارکف است و با مدل‌های پخش رابطه دارد. ویژگی‌های مختلف ولگشت همچون توزیع پراکندگی، زمان اولین عبور و نرخ برخورد به طور گسترده مطالعه شده‌است.

صفحهٔ مشبک؛ هر نقطه یک گره است.

ولگشت در صفحهٔ مشبک

یکی از انواع معروف ولگشت، حالتی است که روی صفحهٔ مسطح و شبکه مانند رخ می‌دهد. یک متحرک فرضی با شروع از یک گره، هر بار با احتمالی مشخص به گره‌ای دیگر می‌رود (قدم می‌زند). در ولگشت ساده، متحرک تنها مجاز است به گره‌های مجاور منتقل شود و در حالت ولگشت متقارن ساده بر روی شبکهٔ متناهی، احتمال انتقال متحرک به هر گرهٔ شبکه برابر است.

ولگشت در یک بعد

خطی در نظر بگیرید که در فاصله‌های برابر با اعداد صحیح مدرج شده‌است. حالت ساده و ملموس ولگشت را می‌توان روی این خط در نظر گرفت که از $S_0 = 0$ آغاز می‌شود و متحرک در هر مرحله با احتمال برابر، یک گام به جلو (1+) یا عقب (۱-) می‌رود. با تعریف $S_n:=\sum_{j=1}^nZ_j.$ سری $\{S_n\}\,\!$ یک ولگشت ساده بر $\mathbb Z$ نامیده می‌شود.

موقعیت متحرک پس از n گام، کجاست؟ مسلماً نمیتوان موقعیت تصادفی متحرک را محاسبه کرد. اما میتوان در مورد توزیع آن بحث کرد. به راحتی با استفاده از خاصیت جمع پذیری، میتوان نشان داد که امید ریاضی یا متوسط سری $S_n\,\!$ برابر صفر است: $E(S_n)=\sum_{j=1}^n E(Z_j)=0$

همچنین با استفاده از استقلال گام ها نتیجه میشود که : $E(S_n^2)=n$ . این نشان میدهد که متوسط جابجایی متحرک پس از n گام باید از مرتبهء $\sqrt n$ باشد. به عبارت دیگر : $\lim_{n\to\infty} \frac{E(|S_n|)}{\sqrt n}= \sqrt{\frac 2{\pi}}.$