ولگشت

ولگشت یا گام تصادفی یا گشت تصادفی یا قدم زدن تصادفی ( به انگلیسی: random walk ) ، مطالعهٔ رفتار یک مسیر تشکیل شده از گام های تصادفی و پی در پی با استفاده از ابزار ریاضیات است. نتایج کاوش در مورد این موضوع در شاخه های مختلف علم همچون علوم کامپیوتر، فیزیک، بوم شناسی، اقتصاد، روانشناسی و موارد دیگر به عنوان مدلی پایه برای فرایندهای تصادفی در طول زمان، استفاده شده است. به عنوان مثال، مسیر طی شده توسط یک مولکول هنگام حرکت درون گاز یا مایع، مسیر حرکت یک حیوان علف خوار، نوسانات قیمت سهام و وضعیت مالی یک قمارباز؛ مواردی است که می تواند با ولگشت مدل سازی شود. عنوان ولگشت را نخستین بار کارل پیرسون در سال ۱۹۰۵ میلادی به کار برد.
انواع مختلفی از ولگشت مورد توجه است. معمولاً ولگشت به عنوان زنجیره مارکف فرض می شود، در حالی که موارد پیچیدهٔ دیگری نیز وجود دارد و مورد توجه است. ولگشت می تواند روی یک گراف، خط مستقیم، صفحهٔ مسطح یا در فضایی با ابعاد بالاتر رخ دهد. زمان میان گام ها نیز در انواع ولگشت متفاوت است. معمولاً ولگشت در زمان گسسته رخ می دهد و با اعداد طبیعی اندیس دهی می شود ( X 0 , X 1 , X 2 , … ) . اما در برخی موارد فاصلهٔ زمانی میان گام ها نیز تصادفی است و مشخصهٔ زمانی پیوسته تعریف می شود. ولگشت موضوعی اساسی در مباحث فرایندهای مارکف است و با مدل های پخش رابطه دارد. ویژگی های مختلف ولگشت همچون توزیع پراکندگی، زمان اولین عبور و نرخ برخورد به طور گسترده مطالعه شده است.
یکی از انواع معروف ولگشت، حالتی است که روی صفحهٔ مسطح و مشبک رخ می دهد. یک متحرک فرضی با شروع از یک گره، هر بار با احتمالی مشخص به گره ای دیگر می رود ( قدم می زند ) . در ولگشت ساده، متحرک تنها مجاز است به گره های مجاور منتقل شود و در حالت ولگشت متقارن ساده بر روی شبکهٔ متناهی، احتمال انتقال متحرک به هر گرهٔ شبکه برابر است. مدل ولگشت مطرحی که بیشتر از همه مطالعه و شناخته شده است، ولگشت در صفحه مشبکی d - بعدی است: z d .
مدل ولگشت روی صفحهٔ متناهی بعد، ولگشت متقارن کران دار ساده نام دارد. در این حالت احتمال انتقال قدم زن به خانه های مجاور به دلیل در نظر داشتن حاشیه و گوشه های صفحه به محل قدم زن بستگی دارد.
ابتدا سعی می کنیم مسئله را مجسم کنیم. یک نشان گر را در نقطه صفر روی محور قرار می دهیم و به کمک یک سکه شیر یا خط می اندازیم. اگر شیر آمد، نشان گر را یه خانه به سمت راست می بریم، اگر خط آمد، نشان گر را در خانهٔ سمت چپ می گذاریم. بعد از ۵ بار سکه انداختن، نشان گر می تواند در یکی از خانه های ۱ و - ۱ و ۳ و - ۳ و ۵ و - ۵ باشد. اگر سه بار شیر بیاید و دو بار خط، نشان گر روی ۱ می رود. به ۱۰ حالت نشان گر می تواند به خانهٔ ۱ برود، و همچنین به ۱۰ حالت می تواند به - ۱ برود ( چون کاملاً متقارن است و حالت سه بار شیر آمدن و دو بار خط آمدن ( حرکت به ۱ ) برابر با سه بار خط آمدن و دو بار شیر آمدن است ( حرکت به - ۱ ) . ۵ حالت برای رفتن به خانهٔ ۳ است ( با چهار بار شیر آمدن و یک بار خط آمدن ) و ۵ حالت برای رفتن به - ۳ ( با چهار بار خط آمدن و یک بار شیر آمدن ) . تنها یک حالت برای رفتن به خانهٔ ۵ و - ۵ است ( ۵ بار شیر آمدن – ۵ بار خط آمدن ) . در تصویر زیر حالت های ممکن نشان داده شده اند: