Loop-erased random walk
ریاضیات، قدم زن تصادفی حلقه-برداشته یک مدل برای مسیرهای تصادفی ساده می‌باشد که کاربرد مهمی در ترکیبیات، فیزیک و نظریه میدان‌های کوانتومی دارد. این فرایند تصادفی ارتباط نزدیکی با درخت پوشای یکنواخت دارد. فرض کنید که G یک گراف باشد و formula_1 یک مسیر با طول n در G باشد. به بیان دیگر، formula_2 راس‌هایی از G هستند که formula_3 و formula_4 با یک یال بهم متصل هستند. حلقه برداشته مسیر formula_1 یک مسیر ساده جدید است که از حذف همه حلقه‌های formula_1 به ترتیب رخ دادن حلقه‌ها بدست می‌آید. در تعریف رسمی علامت formula_7 را به‌طور استقرایی بدین صورت تعریف می‌کنیم که تعریف بازگشتی زمانی تمام می‌شود که برای یک formula_7 داشته باشیم formula_11. حلقه برداشته مسیر formula_1، یک مسیر ساده است که با نماد formula_13 نشان داده می‌شود.
اگر G یک گراف باشد، v یک راس از گراف G. قدم زن تصادفی R که از راس v شروع شده‌است را در نظر می گیریم. T را که یک زمان توقف برای R انتخاب می‌کنیم. پس یک قدم زن تصادفی حلقه-برداشته تا زمان T برابر formula_14 می‌باشد. به بیان دیگر اگر 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 را با به صورت استقرایی با این روش می سازیم. فرض کنیم formula_15 را تا الان بدست آوردیم. f را یک تابع از G به R با خواص زیر در نظر می گیریم:
formula_16 برای همه formula_17 و formula_18
f به‌طور گسسته در همه مکان‌های دیگر هارمونیک است.
که تابع f بر روی گراف به‌طور گسسته در نقطه x هارمونیک است اگر f(x) برابر میانگین f در همسایه‌های x باشد.
برای انتخاب formula_19 به‌طور تصادفی از بین همسایه‌های راس formula_20 یک راس انتخاب می‌کنیم که احتمال انتخاب هر راس با تابع f آن راس مربوط است. به بیان دیگر، اگر رأس‌های formula_21 همسایه‌ها باشند، راس formula_22 را با احتمال زیر انتخاب می‌کنیم
formula_23
با ادامه این فرایند و محاسبه دوباره f در هر گام، به یک مسیر ساده تصادفی از راس v به راس w می رسیم. توزیع احتمال این مسیر برابر توزیع احتمال قدم زن تصادفی دور-برداشته از راس v به راس w می‌باشد.
فرض کنیم d بعد باشد، که حداقل برابر 2 می‌باشد. Z برابر همه نقاط formula_24 است که formula_25 اعداد صحیح هستند. اگر همه هر راس به رأس‌های نزدیکش وصل کنیم یک گراف نامتناهی بدست می‌آید که درجه هر راس 2d می‌باشد. قدم زن تصادفی دور-برداشته را در این گراف یا زیرگراف‌هایش بررسی می‌کنیم.
یک محاسبه نشان داد که اگر یک قدم زن تصادفی بطول n را در نظر بگیریم، دور برداشته آن طول با اردر برابر آن دارد. نشان داده است که دور-برداشته قدم زن‌های تصادفی با طول n به‌طور تقریبی formula_26 یال دارند.
سایت ویکی‌پدیای انگلیسی https://en.wikipedia.org/wiki/Loop-erased_random_walk