Loop-erased random walk

ریاضیات، قدم زن تصادفی حلقه-برداشته یک مدل برای مسیرهای تصادفی ساده می‌باشد که کاربرد مهمی در ترکیبیات، فیزیک و نظریه میدان‌های کوانتومی دارد. این فرایند تصادفی ارتباط نزدیکی با درخت پوشای یکنواخت دارد.

تعریف

فرض کنید که G یک گراف باشد و $\gamma$ یک مسیر با طول n در G باشد. به بیان دیگر، $\gamma (1),\dots ,\gamma (n)$ راس‌هایی از G هستند که $\gamma (i)$ و $\gamma (i+1)$ با یک یال بهم متصل هستند. حلقه برداشته مسیر $\gamma$ یک مسیر ساده جدید است که از حذف همه حلقه‌های $\gamma$ به ترتیب رخ دادن حلقه‌ها بدست می‌آید. در تعریف رسمی علامت $i_{j}$ را به‌طور استقرایی بدین صورت تعریف می‌کنیم که

$i_{1}=1\,$

$i_{j+1}=\max\{i:\gamma (i)=\gamma (i_{j})\}+1\,$

تعریف بازگشتی زمانی تمام می‌شود که برای یک $i_{j}$ داشته باشیم $\gamma (i_{j})=\gamma (n)$. حلقه برداشته مسیر $\gamma$، یک مسیر ساده است که با نماد $\mathrm {LE} (\gamma )$ نشان داده می‌شود.

اگر G یک گراف باشد، v یک راس از گراف G. قدم زن تصادفی R که از راس v شروع شده‌است را در نظر می گیریم. T را که یک زمان توقف برای R انتخاب می‌کنیم. پس یک قدم زن تصادفی حلقه-برداشته تا زمان T برابر $LE(R([1,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 را با به صورت استقرایی با این روش می سازیم. فرض کنیم $\gamma (1),...,\gamma (n)$ را تا الان بدست آوردیم. f را یک تابع از G به R با خواص زیر در نظر می گیریم:

$f(\gamma (i))=0$ برای همه $i\leq n$ و $f(w)=1$

f به‌طور گسسته در همه مکان‌های دیگر هارمونیک است.

که تابع f بر روی گراف به‌طور گسسته در نقطه x هارمونیک است اگر f(x) برابر میانگین f در همسایه‌های x باشد.

برای انتخاب $\gamma (n+1)$ به‌طور تصادفی از بین همسایه‌های راس $\gamma (n)$ یک راس انتخاب می‌کنیم که احتمال انتخاب هر راس با تابع f آن راس مربوط است. به بیان دیگر، اگر رأس‌های $x_{1},...,x_{d}$ همسایه‌ها باشند، راس $x_{i}$ را با احتمال زیر انتخاب می‌کنیم

${\frac {f(x_{i})}{\sum _{j=1}^{d}f(x_{j})}}.$

با ادامه این فرایند و محاسبه دوباره f در هر گام، به یک مسیر ساده تصادفی از راس v به راس w می رسیم. توزیع احتمال این مسیر برابر توزیع احتمال قدم زن تصادفی دور-برداشته از راس v به راس w می‌باشد.

شبکه

فرض کنیم d بعد باشد، که حداقل برابر 2 می‌باشد. Z^d برابر همه نقاط $(a_{1},...,a_{d})$ است که $a_{i}$ اعداد صحیح هستند. اگر همه هر راس به رأس‌های نزدیکش وصل کنیم یک گراف نامتناهی بدست می‌آید که درجه هر راس 2d می‌باشد. قدم زن تصادفی دور-برداشته را در این گراف یا زیرگراف‌هایش بررسی می‌کنیم.

یک محاسبه نشان داد که اگر یک قدم زن تصادفی بطول n را در نظر بگیریم، دور برداشته آن طول با اردر برابر آن دارد. نشان داده است که دور-برداشته قدم زن‌های تصادفی با طول n به‌طور تقریبی $n/\log ^{1/3}n$ یال دارند.

منابع

سایت ویکی‌پدیای انگلیسی https://en.wikipedia.org/wiki/Loop-erased_random_walk