زمان الگوریتم تصادفی

زمان الگوریتم تصادفی خودش یک متغیر تصادفی است که به انتخاب تصادفی وابسته است. در نتیجه زمانی که حساب می کنیم، متوسط بدترین زمان بین انتخابهای تصادفی مختلف است. (ما هیچ فرضی روی ورودی و تصادفی بودن آن نمی کنیم)

قضیه Yao's minimax: بدترین ورودی (worst case) را در نظر بگیرید. بهترین الگوریتم قطعی روی این ورودی جوابش همیشه از هر الگوریتم تصادفی بهتره.

این یک کران پایین برای زمان الگوریتم تصادفی میده. برای به دست آوردن این کران یک ورودی بد پیدا می کنیم (کرانی که پیدا می کنیم به بد بودن این ورودی بستگی داره) و ثابت می کنیم که هیچ الگوریتم قطعی نیست که بتونه برای این خوب کار کنه.

همین قضیه از دید نظریه بازی ها: یک بازی جمع صفر بین آلیس و باب، که آلیس هر بار یه الگوریتم قطعی رو بر می داره و باب یه ورودی رو بر می داره و هزینه هم هزینه ی اجرای الگوریتم با اون ورودیه. پس هر الگوریتم تصادفی یک حرکت آلیس میشه. طبق قضیه minimax ون نیومن، باب حتما یه حرکت تصادفی داره که حداقل به خوبی وقتی که آلیس فقط یک الگوریتم رو انجام بده، کار کنه. (یعنی باب می تونه ورودی رو انتخاب کنه که هیچ الگوریتم قطعی نتونه بهتر از این روی این ورودی جواب بده.)

برای سوال حل کردن با این باید به سری ورودی رو با یه احتمالی مشخص کنیم، بعد مینیمم زمان (یا هر هزینه ی دیگه ای که بود) رو به دست میاریم، بعد نتیجه می گیریم که هیچ الگوریتم تصادفی نمی تونه از این بهتر باشه. (برای هر ورودی ای!)

سوال الگوریتم تصادفی

سوال آخر این توی امتحان پارسال بوده (نقل قول مستقیم از استاد درس!)

http://people.math.gatech.edu/~randall/Randalgs/randalg1.pdf

http://people.math.gatech.edu/~randall/Randalgs/hw1.pdf

الآن برای اولین بار به ذهنم رسید برم ببینم مرجع درس چیه اصلا!

مساله ی پروسه منشعب شونده!

منبع: http://www.cs.nthu.edu.tw/~wkhon/random12/lecture/lecture5.pdf

مساله یه پروسه است که خودش که تموم میشه یه تعداد رندمی از خودش رو شروع می کنه! :))

فرض کنید هر نسخه از این برنامه، n تا نسخه از خودش رو با احتمال p هر کدوم رو شروع می کنه. (دوجمله ای n و p)

تعداد متوسط کپی های ساخته شده توسط یک پروسه چقدره؟

حل:

ایده: (به قول نویسنده اصلی!) نسل ها

در نسل i، پروسه ها توسط پروسه های نسل i-1 ساخته شده اند، متغیر تصادفی yi را تعداد پروسه های نسل i تعریف می کنیم، طبق چیزی که سوال داده توزیع دوجمله ای n و p است.

پس حاصل جمع کل اینها هم یه متغیر با توزیع دوجمله ای است که میانگینش میشه

E(y) = n0p+n1p+n2p+...

ni = تعداد پروسه های نسل i

رابطه ی بین ni ها این طوریه:

ni = np*n(i-1)

(با احتمال شرطی ثابت کرده)

پس اگر np >1 باشه که بینهایت میشه، وگرنه میشه

1/(1-np)

می تونست بگه آزمایش برنولیه:

E(#repeat until success) = 1/p(success)

p(success) = 1-np

p(fail) = np

چون فقط میانگین رو می خواست به دست بیاره، می تونست فقط فکر کنه که np تا پروسه دارن هر بار ساخته میشن!

توپ و ظرف و گراف تصادفی

http://www.cs.nthu.edu.tw/~wkhon/random12/lecture/lecture13.pdf

توپ و ظرف:

m توپ را در n ظرف به صورت یکنواخت و مستقل می اندازیم. می خواهیم به سه سوال زیر جواب بدهیم:

1- توزیع توپ ها چیست؟

2- چند تا ظرف خالی داریم؟

3- بیشترین تعداد توپ در یک ظرف چندتا است؟ (maximum load)

جواب:

3- ماکسیمم لود:

Pr( L > 3 ln(n)/ln(ln(n)) ) < 1/n

2- احتمال خالی بودن هر ظرف: آزمایش برنولی: اگر توپ درون این ظرف افتاد موفقیت و در غیر این صورت شکست

p( success ) = 1/n

p( fail ) = 1-1/n

p(emty bin) = p( fail in all m repeats ) = (1-1/n)^m = e^-(m/n)

1- احتمال اینکه در هر ظرف دقیقا r توپ داشته باشد:

( e^-(m/n) ) * (m/n)^r / r!

که توزیع پواسون است!

توجه: توزیع پواسون با آزمایش پواسون متفاوت است. توزیع پواسون:

Pr(X=r) = e^-(avg) * avg^r / r!

نکته: مجموع متغیرهای پواسون متغیر پواسون با میانگین مجموع آنهاست.

**ارتباط متغیر تصادفی پواسون و نامساوی چرنف:

* می دانیم توزیع توپ ها در هر ظرف یک توزیع دوجمله ای است، که تعداد متغیرهای آن به تعداد ظرفها و احتمال آن 1 تقسیم بر تعداد توپها است.

اگر تعداد تکرار بینهایت باشد، توزیع دوجمله ای به توزیع پواسون تبدیل می شود.

------------------------------------------

گراف رندم

http://www.cs.nthu.edu.tw/~wkhon/random12/lecture/lecture16.pdf

دو نوع گراف رندم داریم:

 G(n,p) که در آن احتمال انتخاب هر یال p است و تعداد راسها n است.

G(n,N) که در آن N یال به صورت یکنواخت از یالهای باقیمانده انتخاب و به گراف قبلی اضافه می کنیم. (شروع از گراف تهی)

فرق این دو تا مثل فرق دوجمله ای و پواسونه، یعنی برای N بزرگ مثل هم هستند تقریبا.

گراف رندم، احتمال انتخاب هر یال p است، چون انتخاب یالها مستقل است می توانیم از نامساوی چرنف استفاده کنیم.

(اگر راسها را انتخاب می کردیم انتخاب یالها مستقل نبود و نمی توانستیم از چرنف استفاده کنیم.)

توپ = یالها

ظرف = راسها

 هر بار دو توپ پرت می کنیم!

**چه زمانی از گراف رندم استفاده می کنیم؟

وقتی که فقط به ازای ورودی های خاصی حالت خیلی بدی رخ می دهد و در اکثر موراد زمان اجرا خوب است.

*مثال: دور همیلتونی

اول الگوریتمی که ارائه می دهد این است که یکی یکی راسها را برود و هر جا به خودش برخورد کرد، این قسمت از مسیر را برعکس کند.

بعد یک الگوریتم دیگر ارائه می دهد که در آن احتمال دیده شدن یک یال بیش از یک بار وجود دارد. که در آن عملیات الگوریتم اول با احتمال رخ دادنشان انتخاب می شوند. الگوریتم دوم برای گراف جهت دار درست کار می کند.

گرافی به این صورت می سازد که هر راس به احتمال q با راسهای دیگر همسایه است. (زیرگراف رندم گراف کامل) -- مزیت: تقارن

در این گراف الگوریتم دوم همان نتیجه ی الگوریتم اول را می دهد.

----

به این نتیجه رسیدم که این طوری به جایی نمی رسم، در نتیجه جواب ها رو می خونم این دفعه! :)

درخت های نزدیک ترین همسایه

http://www.cs.columbia.edu/CAVE/projects/nnsearch/images/nn.png

الگوریتم تصادفی -بقیه فصلها

حوصله ی اینکه بقیه اش رو بخونم ندارم. در نتیجه خلاصه ی ایده های فصل های بعد رو می نویسم:

مسیریابی: برای حذف بدترین حالت روی ورودی جایگشت رندم اعمال کنیم. + تقارن

روش احتمالاتی: برای حل مسائل ترکیبیاتی از احتمال استفاده کنیم (اثبات). برای این کار دو راه هست:

1-حداقل یک x هست که از E(X) کمتر مساوی باشه و یک x هست که حداقل E(x) باشه.

2-اگر احتمال وجود یک خاصیت در یک چیز که تصادفی از یک مجموعه انتخاب شده، بزرگتر از صفر باشه چیزی وجود داره که اون خاصیت رو داشته باشه!

*اگر بتوانیم با احتمال بالایی بگوییم که این چیز مستقل از مجموعه است، به یک الگوریتم لاس وگاس برای پیدا کردن اون چیز با این خاصیت می رسیم.

الگوریتم تصادفی -فصل 3

* ساختمان داده های تصادفی

ساختمان داده با عملیات: جستجو، اضافه کردن و حذف کردن

1- آرایه مرتب شده: زمان جستجو O(logn) زمان حذف و اضافه O(n)

2- انواع درخت های جستجوی متوازن: (مثلا red-black tree و BST) زمان جستجو، حذف و اضافه O(logn)

چون پیاده سازی اینها سخت است:

ساختمان داده های تصادفی:

1- Treap

شرطی که در یک درخت جستجو وجود دارد و باعث سرعت بهتر جستجو می شود این است که به ازای هر گره مقدار کلید گره های سمت راست آن از مقدار کلید این گره بزرگتر و مقدار کلید گره های زیر درخت سمت چپ آن کوچکتر است.

زمان جستجو در درخت به عمق آن درخت بستگی دارد.

در treap یک درخت جستجوی دودویی داریم که heap هم هست، یعنی عناصر بالاتر آن اولویت بیشتری دارند. وجود و یکتایی treap با استقرا روی n ثابت می شود.

اولویت ها را تصادفی از بازه ی صفر تا یک انتخاب می کنیم و اگر تولید اعداد تصادفی را درست انجام بدهیم، احتمال اینکه اعداد متمایز باشند یک است.

ویژگی treap: هر گره در آن اولویت بیشتر از زیر درخت هایش دارد.

زمان: برای محاسبه ی زمان جستجو باید عمق درخت را حساب کنیم. برای این کار به ازای یک گره ی x مسیر از ریشه به آن گره را در نظر می گیریم. اعداد را بر اساس مقدار آنها مرتب و شماره گذاری می کنیم.

E( depth(Xk) ) = sum(E(Xi))

Xi = 1 if i-th node is in the path root-Xk, 0 otherwise

چون گره هایی که بالاتر هستند اولویت بیشتری دارند، چیزی که مطمئنیم اینه که باید اولویت Xi از Xk بیشتر باشه، ولی این کافی نیست، چون ممکنه x توی یه مسیر دیگه بیفته. حالا باید از خاصیت BST بودنش استفاده کنیم و دو حالت داریم: Xk بزرگتر از Xi باشه (یعنی جزو زیر درخت سمت راست Xi باشه). یا کوچکتر باشه (جزو زیر درخت سمت چپ). حالت اول رو فرض کنید. هر عددی که از Xi بزرگتر باشه و از Xk کوچکتر باشه توی زیر درخت سمت راست Xi میفته و قبل از اینکه به Xk برسه. اگه بخوایم توی مسیر بیفته باید اولویتش هم طوری باشه که بین اولویت Xi و Xk بیفته وگرنه جایی بیرون این مسیر میفته.

...

الگوریتم تصادفی -فصل 2

انتخاب و مرتب سازی

n عدد متمایز و عدد صحیح i بین 1 تا n داده شده است. می خواهیم i-امین عنصر را پیدا کنیم.

راه حل معمولی: یک عدد از مجموعه مثلا اولی را بر می داریم و رتبه آن را حساب کرده و همزمان اعداد را به دو مجموعه بزرگتر و کوچکتر از آن تقسیم می کنیم. اگر i بزرگتر از تعداد اعضای مجموعه ی کوچکتر بود درون آن را می گردیم، در غیر این صورت درون مجموعه ی بزرگتر را برای i منهای تعداد اعضای کوچکتر از عدد فعلی می گردیم.

زمان الگوریتم معمولی: O(n^2)

worst case analysis: T(n)<= T(n-1)+O(n) ==> T(n) = O(n^2)

مجموعه حالت ها: n عدد

پیشامد: i-امین عدد

راه حل 1:

انتخاب تصادفی: یک عدد تصادفی انتخاب می کنیم، نه الزاما اولین عدد.

ایده: مشابه باینری سرچ که با تقسیم و حل زمان را بهبود می دهد، اینجا این تابع تصادفی را برای جستجو داریم.

ایده: از روی سوال قبلی (پیدا کردن میانه) می دانیم که نزدیک وسط بودن خیلی کار ما را راحت تر می کند.

زمان:

Xi: متغیر تصادفی رنک عنصر انتخابی در مرحله i ام الگوریتم

E(T(n)) <= sum_j_1_n( pr(Xi=j)T(max(j,n-j) ) +O(n)

pr(Xi=j) = 1/n

split to close to median & far from median : if j=n/4 ==> max(j,n-j)=3n/4

E(T(n)) <= 1/n*( sum_j_1_n/4(T(n-1))+sum_j_n/4_3n/4(T(3n/4))+sum_j_3n/4(T(n)) )+O(n)

E(T(n)) <= 1/n( n/2*T(n-1)+n/2*T(3n/4))+O(n)

E(T(n)) <= 1/2(T(n-1)+T(3n/4))+O(n)

از شباهت این مساله با مساله پیدا کردن میانه حدس می زنیم جواب آن هم O(n) باشد و با استقرا ثابت می کنیم.

راه حل 2: 

ایده: استفاده از تابع میانه به صورت جداگانه

انتخاب تصادفی: از تابع میانه استفاده کنیم و با باینری سرچ آن را به دست بیاوریم.

T(n) = T_find_median(n)+T(n/2)

T_find_median(n) = O(n/delta)

2*delta=1/2 ==> T_find_median = O(n)

=> T(n) = T(n/2)+O(n) ==> T(n)=O(n)

راه حل 3: راه قطعی است که با همین زمان به جواب می رسد!

ایده: غیرتصادفی کردن: روشی ارائه می دهیم که خصوصیت بالا را حفظ کند و تصادفی نباشد.

ابتدا مجموعه را به زیر مجموعه های 5 تایی تقسیم می کنیم بعد در هر کدام میانه را حساب می کنیم و با فراخوانی همین تابع به صورت بازگشتی میانه ی این مجموعه را به دست می آوریم و همراه با به دست آوردن میانه، عمل partitioning هم انجام می دهیم. (مجموعه را به دو قسمت کمتر از میانه و بیشتر از میانه تقسیم می کنیم.)

اثبات: تفاوت این روش با روش قبل این است که اینجا pivot را به صورت رندم انتخاب نمی کنیم که حداکثر می تواند در زمان تاثیر داشته باشد نه درستی، چون در حالت قبل هم که تصادفی انتخاب می کردیم جواب درست همیشه ساخته می شد و فقط زمان متفاوت می شد.

زمان: پیدا کردن میانه یک مجموعه 5 عضوی = O(1)

T(n)<=T(n/5)+O(n)+T(7n/10)

چون هر کدام از مجموعه های partition ها حداکثر 7n/10 عضو دارند. (به دلیل تقسیم های بعدی، n/5/2=n/10 و ceiling(5/2)=3 )

در نهایت زمان T(n) = O(n) به دست می آید.

----------

مرتب سازی:

راه حل 1:

ایده: پیدا کردن میانه

با استفاده از مطالب قسمت قبل (تصادفی معمولی) میانه را پیدا می کنیم، بعد هر کدام از زیر مجموعه ها را بازگشتی مرتب می کنیم، چون قبلا partition کرده بودیم نتیجه مرتب شده است.

زمان: در هر قدم الگوریتم همه ی عناصر را با pivot مقایسه می کنیم و با زمان این مقایسه ها در زیر مساله ها جمع می کنیم. پس زمان کل برابر جمع تعداد مقایسه ها است.

متغیر تصادفی: تعداد عناصر مقایسه شده

حداکثر هر عنصر یک بار با یک عنصر دیگر مقایسه می شود پس متغیرهای تصادفی دیگری به شکل Xij تعریف می کنیم که اگر عناصر i و j مقایسه شوند یک می شوند در غیر این صورت صفر.

اگر i و j در هیچ فراخوانی از تابع مرتب سازی حضور نداشته باشند (زیر مساله ها) مقایسه نمی شوند و Xij=0 خواهد بود. در غیر این صورت تنها در صورتی مقایسه می شوند که یکی از آنها به عنوان pivot انتخاب شود.

pr(Xij=1)=2/(j-i+1)

با جایگذاری به زمان nlogn می رسیم.

راه حل 2: 

ایده: استفاده از پیدا کردن میانه با روش تصادفی دوم

T(n) = T(n/4)+T(3n/4)+O(n)

این راه از راه حل قبلی بدتر است، چون کار تکراری انجام می دهیم. (قسمتی که برای میانه 1/4 را چک می کنیم و بعد برای تقسیم کردن دوباره این کار را انجام می دهیم.) اما در کل همان O(nlogn) می شود.

الگوریتم تصادفی -فصل1

وقتی یه الگوریتم معمولی رو از یه حالت رندم شروع می کنیم تا زمانش به طور میانگین (expected value) بهتر بشه.

چیزهایی که باید حساب کنیم کل حالت های ممکن (S)، یه زیر مجموعه از حالت های ممکن(A)، احتمال اونها (p) و نسبت دادن یه عدد به A یعنی X(متغیر تصادفی) است.

متغیرهای مستقل: متغیرهایی که امید ریاضی حاصل ضرب و احتمال اشتراکشون بشه حاصلضرب امیدریاضی و حاصل ضرب احتمالشون.

نامساوی مارکوف: برای هر X>=0 و t>0 که میانگین X بشه m داریم: pr(x>mt)<=1/t.

آزمایش برنولی: اگر موفقیت و شکست نتیجه ی آزمایش باشد و احتمال موفقیت p باشد، تعداد تکرارهای آزمایش برای رسیدن به اولین موفقیت به طور میانگین عکس احتمال موفقیت است.

آزمایش پواسون: اگر در آزمایش برنولی، احتمال موفقیت تغییر کند، یک آزمایش پواسون داریم. تخمین احتمال کرانهای یک آزمایش پواسون رو با نامساوی چرنف به دست میارن.

--------------------

الگوریتم تصادفی تقریبی برای به دست آوردن میانه: (با به طور کلی kامین عدد)

زمان حل کردن دقیق مساله: = k بار مینیمم رو در بیاریم = O(n)

فرض کنید ما دقیقا عدد وسطی رو نمی خوایم فقط می خوایم تقریبا وسط باشه.

راه حل 0: یک عدد رندم انتخاب می کنیم، اگر تقریبا وسط بود به عنوان جواب بر می گردونیم و پایان؛ در غیر این صورت خطا.

زمان : O(n)

الزاما به جواب درست نمی رسه. یعنی هیچ مزیتی نسبت به راه حل معمولی اش نداره.

ایده: سعی و خطا! :) -- پایه الگوریتم تصادفی

پس باید احتمال موفقیت رو افزایش بدیم. احتمال موفقیت در این حالت تعداد اعداد نزدیک به میانه به تعداد کل اعداده، یعنی با فرض ضریب delta برابر میانه احتمال اینکه درست جواب بده میشه 2*delta.

(  (n/2+delta*n/2)+(n/2-delta*n/2)  )/n = 2*delta

راه حل 1:(مانتی کارلو) تعداد ثابتی (c) بار این کار رو انجام بدیم.

زمان: O(c*n)

احتمال خطا:

(1-2*delta)^c

ایده: می دانیم delta*2 عدد بین صفر و یک است. پس توانهای بزرگترش کوچکتر می شوند.

راه حل 2: (لاس وگاس) تکرار تا رسیدن به جواب.

زمان: آزمایش برنولی است که احتمال موفقیت در آن 2*delta است، پس تعداد تکرار برای رسیدن به موفقیت به طور متوسط: 

p_success = 1/(2*delta)

E(T(n)) = O(n)*1/p_success = O(n)*1/(2*delta) = O(n/delta)

ایده: حذف احتمال خطا با احتمال افزایش زمان اجرا

هدف الگوریتم تصادفی: حذف بدترین حالت (زمان اجرا) و رسیدن به متوسط زمان بهتر

مثال: استخدام بهترین منشی: (هر اخراج به اندازه ی f ضرر می زند)

راه حل معمولی: همه را به ترتیب چک کند و هر وقت آدم بهتری پیدا کرد قبلی را اخراج کند. O(nf)

ایده: روی ورودی یک جایگشت رندم اعمال کنیم.

از آنجایی که بهترین را می خواهیم الگوریتم لاس وگاس را باید به کار ببریم.

هزینه الگوریتم: به تعداد افرادی وابسته است که اشتباهی استخدام شده اند = متغیر تصادفی X

X = sum(Xi) ; Xi = 1 if i-th person is hired, 0 otherwise

E(cost(n)) = E(f*X) = f*sum(E(xi)) = f*sum(Pi) = f*(1/1+1/2+...+1/n) = f*ln(n)

نکته: تصادفی بودن نباید روی ورودی باشد، یعنی به آن بستگی داشته باشد.

مثال: اگر هر بار جای عنصر آخر و i ام آرایه را عوض کنیم، رندم نیست.

مثال: اگر هر بار جای یک عنصر رندم و i ام آرایه را عوض کنیم، رندم است.

میان ترم الگوریتم تصادفی

قراره یه سری از سوالها از جزوه باشه یه سری از تمرینها. بعد از اونجایی که اونها زیادن من می خوام اینو بخونم:

http://www.win.tue.nl/~mdberg/Onderwijs/AdvAlg_Material/course-notes-AA-2013.pdf

این جاییه که استادمون از روش تمرین ها رو داده، احتمالا امتحان هم قراره از همینها بیاد!