markov chain با توزیع دلخواه

می خواهیم با اضافه کردن طوقه به گراف فعلی، کاری کنیم که markov chain ما به یک توزیع دلخواه همگرا شود.

متغیر ما اینجا احتمال یالها است (رفتن از یک حالت مساله به حالت دیگر).

توزیع یکنواخت:

x = (x1,...,xn)

xi*pij=xj*pji

اگر x برداری باشد که به آن همگرا می شویم و pij احتمال رفتن از i به j باشد؛ در صورتی که شرط بالا برقرار باشد به توزیع دلخواه x می رسیم.

در حالت خاص تقارن (pij=pji) به توزیع یکنواخت می رسیم. (معادل گراف بدون جهت)

برای برقرار شدن شرط بالا باید به شکل زیر احتمالها را به روز کنیم:

different i,j

pij = min(1,xi/xj) if xi is a neighbor of xj

pij = 0 otherwise

else

pii = 1-sum(pij) (different i,j)

یعنی برای به روز کردن احتمالها به جای اینکه چندین طوقه اضافه کنیم، یک طوقه اضافه می کنیم اما وزن یالها را طوری تغییر می دهیم که به توزیع مورد نظرمان برسیم (pij=xi/xj) و بقیه احتمال را به طوقه می دهیم (pii).