ولگشت

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

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

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

ارتباط با زنجیرهٔ مارکوف

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

ولگشت در یک بعد با مثالی دیگر

فردی را تصور کنید که روی محور xها در نقطه صفر ایستاده‌است. این فرد هر بار می‌تواند به راست یا چپ حرکت کند، فارغ از اینکه در گام قبلی چه انتخابی داشته‌است.
فرض کنیم فرد n1 گام به سمت راست برمی‌دارد و هر گام به راست با احتمال p باشد، از طرفی هر گام به چپ هم با احتمال q باشد و در مجموع n2 گام هم به چپ بردارد.
اگر تعداد کل گام‌های فرد را N در نظر بگیریم داریم:
N=n1 + n2
p+q=۱
حال بیایید احتمال اینکه فرد پس از N قدم در خانهٔ i ام قرار بگیرد را بنویسیم:
pppppp...ppp * qqqq...qqqqqq
اگر هر گامی که فرد برمی‌دارد را بنویسیم و در پایان گام‌های چپ و راست را جداگانه بنویسیم، سطر بالا را خواهیم داشت که هر گام راست با احتمال p و هر گام چپ با احتمال q برداشته شده‌است و ما در پایان، n1 عدد گام به راست داریم هرکدام با احتمال p : 
و نیز n2 گام به چپ با احتمال q برای هر یک: 
در نهایت احتمال اینکه فرد بعد از طی کردن N گام در خانهٔ i ام باشد به صورت زیر است:
این رابطه را تعمیم می‌دهند و از نتیجه آن برای Nهای بزرگ و سیستم‌های آماری استفاده می‌کنند.

ولگشت گاوسی

یک ول گشت، که اندازه گامش با توجه به یک توزیع نرمال متغیر است، به عنوان یک مدل برای داده‌های زمانی دنیای واقعی بکار می‌رود (مانند بازارهای مالی)
معادله یBlack–Scholes برای مدل‌سازی گزینهٔ قیمت (مثلا) از یک ول گشت گاوسی به عنوان فرض اساسی استفاده می‌کند.
در این‌جا، اندازهٔ گام، معکوس تجمعی توزیع نرمال  می‌باشد؛ که  عدد تصادفی ای است که به‌طور یکنواخت توزیع شده‌است و همان‌طور که انتظار می‌رود، و میانگین و انحراف معیار تابع توزیع نرمال هستند.
اگر  غیر صفر باشد، ول گشت حول یک روند خطی تغییر خواهد کرد. اگر مقدار اولیهٔ ول گشت vₛباشد، پس از n گام، مقدار مورد انتظار vₛ + n μ خواهد بود.
در حالت خاص که برابر با صفر است، پس از n گام، توزیع احتمال فواصل انتقالی، با (N (0, n σ² نشان داده می‌شود که () N نماد توزیع نرمال، n تعداد گام‌ها و  از معکوس تجمعی توزیع نرمال که در بالا داده شده هستند.
اثبات:
ول گشت گاوسی می‌تواند به عنوان مجموع دنباله ای از متغیرهای تصادفی توزیع شدهٔ غیر وابسته و یک جور، در نظر گرفته شود که Xᵢ از معکوس تجمعی توزیع نرمال با میانگین برابر صفر و  از معکوس تجمعی توزیع نرمال اصلی می‌آیند
=Z
اما ما توزیع را برای جمع دو متغیر تصادفی که بطور نرمال توزیع شده‌اند و غیر وابسته هستند، داریم که به صورت زیر هستند:
Z = X + Y
(N (μX + μY, σ²X + σ²Y اینجا
در مورد ما μX = μY = 0 and σ²X = σ²Y = σ² می‌دهد:
(N (0, 2σ²
با استقراء پس از nگام خواهیم داشت:
(Z ~ N(0, nσ²
برای گام‌های توزیع شده، با توجه به هر توزیعی با میانگین صفر، و یک واریانس محدود (نه لزوماً تنها یک توزیع نرمال)، جذر میانگین مربعی فاصله انتقالی، پس ازn مرحله، به‌صورت زیر است:
اما برای ولگشت گاوسی، این فقط انحراف معیار توزیع فاصله انتقالی پس از n مرحله می‌باشد.
بنابر این اگر μ صفر باشد، و جذر میانگین مربعی فاصله انتقالی هم یک انحراف معیار باشد، احتمال ۶۸٫۲۷٪ وجود دارد که جذر میانگین مربعی فاصله انتقالی، بعد از n گام بین   ±
باشد.
به علاوه، ۵۰٪ احتمال دارد که فاصله انتقالی در n گام بعد، بین ± ۰٫۶۷۴۵ بیفتد.

پخش غیرعادی

در سیستم‌های بی نظم، مانند پوشش‌های پر منفذ یا خود متشابه‌ها، ممکن است با  متناسب نباشد بلکه با  متناسب باشد.  توان پخش غیرعادی نامیده می‌شود و می‌تواند بزرگتر یا کوچکتر از ۲ باشد.
پخش غیرعادی، هم چنین می‌تواند به صورت σᵣ² ~ Dtα بیان شود که α پارامتر غیرعادی است.
برخی پخش‌ها در محیط تصادفی، حتی متناسب با یک توانی از لگاریتم زمان هستند. مثلاً Sinai`s walk یا Brox diffusion را ببینید.