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