توپ و ظرف و گراف تصادفی
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 است، چون انتخاب یالها مستقل است می توانیم از نامساوی چرنف استفاده کنیم.
(اگر راسها را انتخاب می کردیم انتخاب یالها مستقل نبود و نمی توانستیم از چرنف استفاده کنیم.)
توپ = یالها
ظرف = راسها
هر بار دو توپ پرت می کنیم!