ajeev Motwani's Recent Teaching Activity

http://theory.stanford.edu/~rajeev/courses.html

آنتروپی و تولید عدد رندم

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

معمولی که عدد تولید می کنیم خودمون توی برنامه ها (در یک عدد ضرب می کنیم) رندم یکنواخت نیست! :دی دلیل:

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

حالا حالتی رو در نظر بگیرید که بیت بسازیم تا عدد بشه. (حالت مطلوب!) اگر یک سری عدد 0 تا m داشته باشیم که احتمالشون مساوی باشه، باید چطوری بیتها رو رندم انتخاب کنیم؟ دو تا چیز هست که میشه اینجا تغییر داد یکی تعداد بیتهاست اون یکی احتمال 0 و 1 بودنشون.

فعلا فرض کنید احتمال یک بودن هر بیت رو p فرض کنیم. می خوایم به دست بیاریم که چند تا بیت بسازیم که احتمال عددها یکسان بشه.

احتمال ساخته شدن یک عدد k بیتی چقدره؟

(2^k)/m

امید ریاضی تعداد بیتها رو حساب می کنیم:

E(#bits) = sum_k_1_lg(m) (k* (2^k)/m)

ثابت می کنیم تعداد بیتهای عددی که با این روش جدید از روی قبلی می سازیم کمتر از log 1/q میشه که q احتمال رخ دادن اون عدده. می دونیم مجموع احتمالها یک میشه، پس 

?????

میان ترم الگوریتم تصادفی شریف - واقعی!

کیفیتش هم داغونه اصلا خونده نمیشه!

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

1-

مجموعه ی X را داریم و n عضوی است. مجموعه ی زیر مجموعه های k عضوی X را که اشتراک دو به دوی آنها تهی نباشد، F می نامیم. ثابت کنید تعداد اعضای F از انتخاب k-1 از n-1 کمتر مساوی است.

حل: تعداد کل زیر مجموعه های k عضوی X می شود انتخاب k از n. اگر یک عضو را در همه مشترک بگیریم می شود انتخاب k-1 از n-1. پس این را می شود ساخت باید ثابت کنیم که بهتر از این نمی شود.

یک عضو از F مثلا a را در نظر بگیرید. یک زیرمجموعه از X که با a اشتراک داره رو b بگیرید. می دونیم میشه یه جایگشتی روی a داد که اعضای a اشتراک b همه شون بیفتن ته a و میشه یه جایگشتی روی b داد که این اعضا بیفتن اولش. حالا می خوایم بگیم که تعداد b ها به ازای یک a چندتاست؟

یکی اینکه همه ی جایگشت های a رو حساب کنیم، چون b هم می دونیم k عضویه و فرض هم کردیم که دیگه a و b اشتراکی ندارند، تعداد حالت های b میشه این:

k!*(n-k)!*|F|

کلا (n-1)! جایگشت دوری داریم، حداکثر k تا از اعضای F می تونه توی هر جایگشت دوری اومده باشه، پس در کل میشه:

k* (n-1)!

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

منبع: http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Ko%E2%80%93Rado_theorem

اثبات های دیگه ی این: http://www.math.ucsd.edu/~ronspubs/90_03_erdos_ko_rado.pdf

2- 

تعداد مسیرهای همیلتونی توی گراف کامل که رندم جهت دهی شده چند تاست؟ (امید ریاضی)

طول هر مسیر = n

احتمال اینکه یک جایگشت از رئوس یک مسیر تشکیل بدن:

(1/2)^n-1

تعداد کل جایگشت ها هم n! تا است. پس کلا میشه:

n!*(1/2)^n-1

3-

گراف n راس و m یال داریم، بزرگترین زیرگراف تهی این گراف بیشتر از n/2d راس دارد. که d = میانگین درجه ی هر راس = 2m/n

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

1/(deg(v)+1)

چون باید هیچ کدوم از همسایه های اون راس توی گراف نباشن و خودش باشه.

می خوایم ثابت کنیم که یه چیزی وجود داره که یه چیزی رو بیشتر از یه مقداری داره، یعنی باید امید ریاضی اش رو حساب کنیم بعد بگیم حتما یکی هست که از امید ریاضی بیشتر باشه.

E(X) = E(sigma(Xi)) = sigma(E(Xi)) = sigma(1/(di+1)) >= (n^2) / sigma(di+1) = n^2/(n+2m) = n/(1+d) >= n/(2d)

راه دیگر: با گراف رندمی که احتمال وجود هر راسی p است، (پس احتمال وجود هر یال p2 است) یک سر هر یال را حذف کنیم. X = تعداد راسها و Y = تعداد یالها

E(X-Y) = np-np2 = np(1-p) ==> minimize ==> p = 1/d

4-

ماکسیمم درجه ی گراف رندم با احتمال انتخاب هر یال 1/2

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

5-

یک مجموعه رو با دو رنگ آبی و قرمز رنگ کردیم، اختلاف تعداد آبی و قرمزها حداکثر چندتاست؟

رندم رنگ می کنیم و آبی = 1 و قرمز = -1. بعد t=2|red|*ln(|blue|) :D

6-

ثابت کنید زمان اجرای quick sort به احتمال یک منهای یک nام O(nlogn) است.

احتمال اینکه طول مسیر از این بیشتر بشه رو حساب می کنیم. باید ببینیم کدوم انتخاب های تصادفی هستند که زمان رو زیاد می کنند (ارتفاع رو زیاد می کنند.) و ثابت کنیم تعدادشون کمه.

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

خوبی این تمرینها این است که همه جواب دارند، نمونه ی امتحانش هم هست.

http://www.cs.helsinki.fi/u/jkivinen
http://www.cs.helsinki.fi/u/jkivinen/opetus/ra1/spring2013
http://www.cs.helsinki.fi/u/jkivinen/opetus/ra1/spring2013/exam-prob.pdf

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

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

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

قضیه 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