حل تمرین اول الگوریتم تصادفی استنفورد (۲۰۱۸)

سوالها: http://theory.stanford.edu/~valiant/teaching/CS265_2018/ps1.pdf

سوال ۱- قسمت اول) یک راه حل این است که سکه را دو بار بیندازیم، احتمال HT و TH با هم مساوی هستند و اگر چیزی غیر از این آمد یعنی HH یا TT دوباره آزمایش را تکرار می‌کنیم. احتمال جواب ندادن آزمایش ۱۷/۲۵ است، پس به طور متوسط باید ۲۵/۱۸ بار تکرارش کنیم.

قسمت دوم) دو بار سکه را می‌اندازیم. اگر HH آمد اعلام موفقیت می‌کنیم، اگر HT یا TH آمد اعلام شکست می‌کنیم، اگر TT آمد آزمایش را تکرار می‌کنیم. احتمال موفقیت ۳/۴ است، پس به طور متوسط باید ۴/۳ بار تکرارش کنیم (آزمایش برنولی با احتمال موفقیت p به طور متوسط نیاز به p^(-1) بار تکرار دارد تا به موفقیت برسد).

قسمت سوم) بعد از k بار سکه انداختن، اعدادی که در قسمت اول به دست می‌آیند جملات (1/5+4/5(^k هستند و در قسمت دوم جملات (1/2+1/2)^k هستند. برای اینکه بتوانیم احتمال مورد نظر خودمان را به دست بیاوریم باید بتوانیم آنها را به دو دسته تقسیم کنیم که جمع یکی از آن دسته‌ها احتمال مورد نظر ما باشد. در هر دو قسمت تعداد اعشاری از جملات را باید انتخاب کنیم که همین نشان می‌دهد این کار غیرممکن است.

سوال ۲- الف) احتمال اینکه یک نفر آلوده باشد k/n است (تقسیم تعداد حالت‌ها). احتمال آلوده بودن حداقل یک نفر از m نفر = ۱-احتمال آلوده نبودن هیچ کدام

=1-(1-k/n)^m

حالا فرض کنید به این احتمال بگوییم p. چون آلوده بودن یک گروه متغیر ۰ و ۱ (مشخصه) است پس احتمال آن با امید ریاضی آن برابر است. در کل n/m تا گروه داریم پس امید ریاضی کل (طبق خاصیت خطی بودن امیدریاضی که در سوال هم راهنمایی کرده) می‌شود جمع اینها، یعنی:

n/m p = n/m (1-(1-k/n)^m)

ب) اول اینکه n/m تا را که طبق الگوریتم مجبوریم انجام بدهیم برای مشخص شدن وضعیت گروه‌ها.

تعداد تست‌هایی که باید روی اعضای گروه‌ها انجام بدهیم به تعداد اعضای گروه‌های آلوده است. طبق قسمت الف، امیدریاضی تعداد گروه‌های آلوده را داریم، پس در کل تعداد تست‌ها برابر است با:

n/m+n (1-(1-k/n)^m)

روش دیگر محاسبه‌اش این است که هر گروهی که ۱ بود باید m تا تست دیگر هم انجام بدهیم. احتمال ۱ بودن را در قسمت قبل حساب کردیم، به کمک آن امید ریاضی را حساب می‌کنیم:

n/m * [p* (m+1)+ (1-p)*1]=np+n/m

در الگوریتم اول که همه را تست می‌کند n تا تست کلاً داریم، پس نسبت این دو حالت می‌شود:

p+1/m = [1-(1-k/n)^m]+1/m

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

در مقابل جمله‌ی اول می‌توانیم از دومی صرف نظر کنیم چون صورت سوال هم گفته خیلی بهتر بشود. برای زیاد کردن (1-k/n)^m باید m را تا جای ممکن کم کنیم چون عدد 1-k/n بین ۰ و ۱ است و هر چه توانش کمتر باشد بزرگتر می‌شود. این مقدار m=2 است (چون به ازای ۱ می‌شود همان الگوریتم اول).

قسمت سوم) طبق قسمت قبل می‌شود:

n/2+n(1-(1-k/n)^2)=3n/2-n(1-k/n)^2

سوال ۳- الف) در هر حالت باید به یک ترتیبی یالها را فشرده کند پس می‌توانیم دقیقاً همان اثبات قبلی را تکرار کنیم تا جایی که k تا رأس بماند. تعداد مراحل می‌شود n-k چون n تا رأس داریم و هر بار که دو تا را با هم ادغام می‌کنیم (با فشرده کردن یال) یکی از تعداد رأسها کم می‌شود. احتمال اینکه یک یال در i مرحله‌ی اول فشرده نشود همان F_i اثبات کتاب است. به جای حساب کردن F_{n-2} ما باید F_{n-k} را حساب کنیم. با همان روش کتاب می‌رسیم به:

prod_{i=1}^{n-k} (n-i-1)/(n-i+1) = (n-2)/n ... (k-1)/(k+1)

= (n-2) ... (k-1) / [ n ... (k+1) ] = k (k-1) / [ n (n-1) ]

احتمال اینکه با اجرای الگوریتم روی k به یک min-cut برسیم طبق قضیه کتاب 2/(k(k-1)) است. اگر آن را L بار تکرار کنیم و بهترین جوابش را در نظر بگیریم، احتمال اینکه جواب به دست نیاید می‌شود:

(1-2/k(k-1) )^ L <= e^{-2L/k(k-1)}

پس احتمال موفقیتش حداقل می‌شود:

1-e^{-2L/k(k-1)}

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

k (k-1) / [ n (n-1) ] * [1-e^{-2L/k(k-1)} ]

ب) ما در قسمت اول که n-k تا از فشرده‌سازی‌هایمان را استفاده کردیم، پس 2n-(n-k) = n+k تای دیگر باقی می‌ماند. یک نسخه‌ی k رأسی به x-2 تا فشرده‌سازی نیاز دارد که یک یالش باقی بماند (منظور از x تعداد یالهای min-cut است، یعنی همان چیزی که در کتاب اسمش را k گذاشته بود). به لطف این قید می‌توانیم برای L کران پیدا کنیم، یعنی (n+k)/x. واضح است که هر چقدر تعداد تکرارها بیشتر باشد جوابش بدتر نمی‌شود در نتیجه ما L را هر چه نزدیک‌تر به این مقدار بگذاریم بهتر است، ولی ما تنها کرانی که می‌توانیم روی x داشته باشیم همین است که از k کمتر مساوی است پس

L=(n+k)/k = n/k+1

با جایگذاری این مقدار در عبارت قسمت قبل به دست می‌آید:

k (k-1) / [ n (n-1) ] * [1-e^{-2(n/k+1)/k(k-1)} ]

به ظاهر عبارتش میاد که اگر k=n بگذاریم بهترین جوابش است. با این کار مقدار زیر به دست می‌آید:

1-(1-2/n(n-1) )^2 ~ 4/n^2

خودش در راهنمایی سوال یک تقریب (هم‌ارزی) استفاده کرده است که ما هم با فرض ثابت بودن L می‌توانیم همین را استفاده کنیم:

1-(1-2/k(k-1) )^{n/k+1} = 2(n/k+1)/k^2

k (k-1) / [ n (n-1) ] * [2(n/k+1)/k^2] =k^2 * n / [ n^2 * k^3] = 1/(nk) = 1/n^2