Loop-erased random walk

در ریاضیات، قدم زن تصادفی حلقه-برداشته یک مدل برای مسیرهای تصادفی ساده می‌باشد که کاربرد مهمی در ترکیبیات، فزیک و نظریه میدان‌های کوانتومی دارد. این فرایند تصادفی ارتباط نزدیکی با درخت پوشای یکنواخت دارد.
تعریف
فرض کنید که G یک گراف باشد و یک مسیر با طول n در G باشد. به بیان دیگر، راس‌هایی از G هستند که و با یک یال بهم متصل هستند. حلقه برداشته مسیر یک مسیر ساده جدید است که از حذف همه حقله‌های بترتیب رخ دادن حلقه‌ها بدست می‌آید. در تعریف رسمی علامت را بطور استقرایی بدین صورت تعریف می‌کنیم که
تعریف بازگشتی زمانی تمام می‌شود که برای یک داشته باشیم . حلقه برداشته مسیر ، یک مسیر ساده است که با نماد نشان داده می‌شود.
اگر G یک گراف باشد، v یک راس از گراف G. قدم زن تصادفی R که از راس v شروع شده‌است را در نظر می‌گیریم. T را که یک زمان توقف برای R انتخاب می‌کنیم. پس یک قدم زن تصادفی حلقه-برداشته تا زمان T برابر می‌باشد. به بیان دیگر اگر T گام اول قدم زن تصادفی R را در نظر بگیریم و همه حلقه‌های این مسیر را بترتیب رخ دادن آن‌ها حذف کنیم یک مسیر ساده تصادفی بدست می‌آید. زمان توقف T می‌تواند ثابت باشد هرچند بطور معمول T را زمان ورود قدم زن تصادفی به یک زیر مجموعه از راس‌ها می‌گیرند.
درخت پوشای یکنواخت
یک درخت پوشا که بطور تصادفی از بین تمام درخت‌های پوشا با احتمال برابر انتخاب شده‌است را درخت پوشای یکنواخت می‌خوانیم. برای ایجاد چنین درختی الگوریتم ویلسون از قدم زن تصادفی دور-برداشته‌استفاده می‌کند.
بطور مثال، فرض کنید G یک گراف باشد. یک درخت پوشای G یک زیر گراف G شامل همه راس‌ها و برخی از یال‌ها می‌باشد که یک درخت باشد، یعنی همبند باشد ولی دور نداشته باشد. درخت پوشای یکنواخت یک درخت پوشا است که بطور تصادفی با احتمال یکسان بین همه درخت‌های پوشای گراف G انتخاب شده‌است.
حال فرض کنید که v و w دو راس از G باشند. هر درخت پوشا شامل دقیقا یک مسیر ساده بین دو راس v و w می‌باشد. انتخاب این مسیر از درخت پوشای یکنواخت یک مسیر ساده تصادفی به ما می‌دهد. توزیع احتمال این مسیر ساده تصادفی برابر توزیع احتمال قدم زن تصادفی دور برداشته‌ای است که از راس v شروع شده و در راس w توقف یافته‌است.
نتیجه‌ای که می‌توان گرفت این است که قدم زن تصادفی دور-برداشته نسبت به نقطه شروع و پایان متقارن می‌باشد، بطور دقیق‌تر توزیع احتمال قدم زن تصادفی دور-برداشته که از راس v شروع و در راس w توقف یافته‌است با توزع احتمال قدم زن تصادفی دور-برداشته‌ای که از راس w شروع و در راس v توقف یافته‌است برابر است که این یک نتیجه بدیهی نمی‌باشد زیرا دور-برداشته یک مسیر و مسیر معکوسش یکسان نیستند.
انتخاب یک درخت پوشای یکنواخت دشوار می‌باشد زیرا تعداد درخت‌های پوشا حتی برای گراف‌های کوچک بیش از حدی است که بتوان همه آن‌ها را لیست کرد. بنابرین روش‌های دیگر نمونه برداری یکنواخت مورد نیاز است که در اینجا به الگوریتم ولیسون اشاره می‌کنیم.
در الگوریتم ویلسون به این‌گونه عمل می‌کنیم که دو راس را انتخاب می‌کنیم و یک قدم زن تصادفی دور-برداشته بین آن‌ها پیدا می‌کنیم، سپس یک راس سوم که در مسیر انتخاب شده نیست را انتخاب کرده و یک قدم زن تصادفی دور-برداشته از راس سوم تا مسیر بدست آمده انتخاب می‌کنیم و این کار را تا زمانی که یک درخت پوشا بدست بیاید انجام می‌دهیم. اثبات می‌شود که درخت پوشای بدست آمده یک درخت پوشای یکنواخت می‌باشد.
قدم زن تصادفی لاپلاس
یک روش دیگر نشان دادن قدم زن تصادفی دور-برداشته ریشه در جواب‌های معادله گسسته لاپلاس دارد. اگر G یک گراف باشد و راس‌های v و w در G باشند. یک مسیر تصادفی بین v و w را با به صورت استفرایی با این روش می‌سازیم. فرض کنیم را تا الان بدست آوردیم. f را یک تابع از G به R با خواص زیر در نظر می‌گیریم:
برای همه و
f بطور گسسته در همه مکان‌های دیگر هارمونیک است.
که تابع f بر روی گراف بطور گسسته در نقطه x هارمونیک است اگر f(x) برابر میانگین f در همسایه‌های x باشد.
برای انتخاب بطور تصادفی از بین همسایه‌های راس یک راس انتخاب می‌کنیم که احتمال انتخاب هر راس با تابع f آن راس مربوط است. به بیان دیگر، اگر راس‌های همسایه‌ها باشند، راس را با احتمال زیر انتخاب می‌کنیم
با ادامه این فرایند و محاسبه دوباره f در هر گام، به یک مسیر ساده تصادفی از راس v به راس w می‌رسیم. توزیع احتمال این مسیر برابر توزیع احتمال قدم زن تصادفی دور-برداشته از راس v به راس w می‌باشد.
شبکه
فرض کنیم d بعد باشد، که حداقل برابر 2 می‌باشد. Z d برابر همه نقاط است که اعداد صحیح هستند. اگر همه هر راس به راس‌های نزدیکش وصل کنیم یک گراف نامتناهی بدست می‌آید که درجه هر راس 2d می‌باشد. قدم زن تصادفی دور-برداشته را در این گراف یا زیرگراف‌هایش بررسی می‌کنیم.
یک محاسبه نشان داد که اگر یک قدم زن تصادفی بطول n را در نظر بگیریم، دور برداشته آن طول با اردر برابر آن دارد. نشان داده است که دور-برداشته قدم زن‌های تصادفی با طول n بطور تقریبی یال دارند.