نمونه سوال الگوریتم تصادفی (هارپلد)

https://sarielhp.org/teach/13/b_574_rand_alg/final/practice.pdf

لینک درس: https://sarielhp.org/teach/13/b_574_rand_alg/

نسخه‌ی تغییریافته‌ی جمع‌کننده‌ی کوپن (coupon collector)

http://phillong.info/misc/coupon.pdf
بار دیگر به من اثبات شد هیچی از الگوریتم تصادفی بلد نیستم.
شاید بد نباشد بشینم سوالهای کتاب متوانی را حل کنم. آنجا حساب کردن جمع آن جمله‌های آخر را به عنوان سوال دارد. باز آدم آنها را بلد باشد شاید بتواند این را حل کند.
من هر چی حل کردم رسید به یک جایی که نمی‌شد حسابش کرد.
برای رابطه بازگشتی هم سعی کردم مستقیم مال احتمال را به دست بیارم، در حالی که این مثلاً اومده جمع را در آورده.
سر همین که چرا می‌توانسته امید ریاضی جمع وزنها را برای حساب کردن امید ریاضی آن یکی به کار ببره هم فکر کردم تا فهمیدم چون مخرجش وابسته به آن نبوده ثابت به حساب می‌آمده و از امید ریاضی می‌شده که بیاریمش بیرون.

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

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

سوال ۱- الف) متغیر تصادفی مشخصه را به ازای رأی دادن هر نفر به کاندیدای X یک می‌گذاریم و ۰ در غیر این صورت.

Pr(V_i=1) = 1/2

با فرض انتخاباتی که ۲ تا کاندیدا داشته باشد و صورت سوال هم گفته فرض کنید از بین افرادی که رأی می‌دهند انتخاب شده باشند.

E[sum_{i=1}^{5000} V_i] = 5000*E[V_i]=5000/2=2500

حالا از نامساوی چرنف استفاده می‌کنیم:

pr( sum_i V_i > 1.02 E(sum_i V_i) ) < e^0.02/(1.02^1.02) = 0.6085

pr( sum_i V_i < 0.98 E(sum_i V_i) ) < ( e^(-0.02)/(0.98)^(0.98) )^2500 = 0.60449

==> 1

pr( sum_i V_i > 1.05 E(sum_i V_i) ) < ( e^(0.05) / 1.05^1.05 )^2500 = 0.046

pr( sum_i V_i < 0.95 E(sum_i V_i) ) < ( e^(- 0.05)/(0.95^0.95) )^2500 = 0.0416

==> 0.0876

pr( sum_i V_i >1.1 E(sum_i V_i) ) < ( (e^0.1)/(1.1^1.1) )^2500 = 0.00000554289

pr( sum_i V_i < 0.9 E(sum_i V_i) ) < (e^(-0.1) / (0.9^0.9) )^2500 = 0.00000240289

==>0.00000794578

ب) 

E = n * 1/2 = n/2

pr( V > 1.01 * n/2 ) < e^(-n/2 * 0.01^2 /3) = e^(-n/60000)

pr( V < 0.99 * n/2) < e^(-n/2 * 0.01^2 /2) = e^(-n/40000)

1-0.95=0.05

n=20000

prob=0.04241

1-0.05=0.95

n=20000

به خاطر تقارن فرقی نمی‌کند و فکر کنم می‌شد از اول مثل یک توزیع دوجمله‌ای در نظر گرفتش. احتمالاً استفاده از قضیه حد مرکزی کار جالب‌تری بود.

۲-الف) متغیر تصادفی X_ij را ۱ می‌گذاریم اگر عنصر i و j با هم مقایسه شوند و در غیر این صورت آن را صفر می‌گذاریم. در این صورت امیدریاضی تعداد کل مقایسه‌ها جمع روی i,j ها خواهد بود. تنها حالتی که i و j با هم مقایسه شوند این است که یکی از آنها به عنوان pivot انتخاب شده باشد و در مراحل قبلی هیچ pivot-ای از بازه‌ی بین مقادیر x_i و x_j و بازه‌ی میانه تا نزدیک‌ترین سر بازه انتخاب نشده باشد. با عوض کردن تعریف X_ij به متغیر مشخصه‌ی مقایسه‌ی i-امین بزرگترین عنصر و j-امین بزرگترین عنصر می‌شود به شکل ساده‌تر روی i و j تحلیل را ادامه داد (به جای x_i و x_j). سه حالت ممکن است پیش بیاید: میانه کوچکتر از i باشد یا میانه بزرگتر از j باشد یا بین i و j باشد.

حالت اول: میانه کوچکتر از i باشد. فضای حالت‌های تأثیرگذار m,...,j است و حالت مطلوب برای ما حالتی است که i یا j انتخاب شده باشند.

حالت دوم: میانه بزرگتر از j باشد. فضای حالت‌های تأثیرگذار i,...,m است و حالت‌های مطلوب برای ما i یا j است.

حالت سوم: اگر pivot بین i و j بیفتد، وقتی خودش را با بقیه مقایسه می‌کند یا i را حذف می‌کند یا j را. پس هیچ حالت مطلوبی ندارد.

احتمال انتخاب شدن هر عددی از این بازه همچنان یکنواخت خواهد بود، چون حالت‌های همه‌ی مقادیر این بازه یکسان است. پس احتمال انتخاب شدن pivot خوب در حالت اول 2/(j-m) و در حالت دوم 2/(m-i) و در حالت سوم 2/(j-i+1) است. پس جواب می‌شود:

sum_{i=n/2+1}^{n-1} sum_{j=i+1}^n 2/(j-n/2) +

sum_{i=1}^{n/2-2} sum_{j=i+1}^{n/2-1} 2/(n/2-i)

= n/2+2H(n/2)-3 + n-2-2H(n/2-1) = 3n/2+4/n-5

پس از نظر امید ریاضی فرقی بین الگوریتم‌ها نیست. من خود حالت‌هایی که i=n/2 یا j=n/2 باشد حساب نکردم ولی آنها هم باید حساب بشوند.

ب) با استفاده از نامساوی مارکوف به دست میاد:

pr( sum X_ij > a ) <= 3n/(2a)

3n/(2a) = 1/2 ==> a = 3n

1-pr(sum X_ij > 3n ) >=1-1/2

pr(sum X_ij < 3n) >=1/2

pr(sum X_ij > 3n/2+n ) <= (3/2 n)/(3/2 n+n) = (3/2) / (3/2+1)=3/5

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

راه دیگری که به ذهنم رسید قضیه 3.10 کتاب بود (صفحه 57). باید اول انحراف معیار را حساب کنیم.

E(X^2) = E[(sum_ij X_ij)^2]= E[sum X^2_ij]+E[sum_ij <> i'j' X_ij X_i'j']

=E[X_ij]+sum_ij <> i'j' E[X_ij X_i'j']

چون متغیرهای X_ij مشخصه بودند (باینری!) پس توان ۲ آنها با خودشان برابر می‌شود. در نتیجه امید توان ۲ آنها هم با امید خودشان برابر می‌شود که در قسمت قبل حساب کردیم.

E[X_ij X_i'j']=Pr(X_ij=1, X_i'j'=1) = pr(X_ij=1) pr(X_i'j'=1 | X_ij=1)

حالت‌هایی که بازه‌ی مقادیر صفر نمی‌شود حالت‌هایی هستند که i'j' داخل ij قرار می‌گیرد و حالت‌هایی که دو بازه یک نقطه مشترک دارند.

در این سوال، الگوریتم ممکن است چند بار pivot انتخاب کند و مجموعه بزرگتر/کوچکتر بشود، ولی ما جایی را در نظر می‌گیریم که تکلیف i و j مشخص می‌شود و بقیه حالت‌ها تأثیری در جواب ندارند (به خاطر تقارن ناشی از یکنواخت بودن انتخاب pivot در هر مجموعه).

i < i' < j' < j <n/2 ==> good pivot<i ==> pr (good pivot) = 1/i

n/2 < i < i' < j' < j ==> j<good pivot ==> pr (good pivot) = 1/(n-j+1)

پس امیدریاضی می‌شود:

\sum_{i=1}^{n/2} (n/2-i)^3/3! 1/i = \sum_i n^3/(48i) -n^2/8+ni/4-i^2 = n^3/48 H(n/2) - n^3/16+n/4 (n/2)(n/2+1)/2 - n/2 *(n/2+1) (n+1)/6 ~ n^3/48 H(n/2)

به علاوه‌ی همین که می‌شود حدوداً n^3/24 H(n/2). پس واریانس می‌شود:

Var(sum_ij X_ij) = n^3/24 H(n/2) +3n/2 - (9/4 n^2) ~ n^3/24 H(n/2)

sigma ~ sqrt{n^3 log n}

|m-3n/2| < sqrt{n^3 log n}

m < 3n/2 +/- n^3/2 sqrt{log n}

pr( sum X_ij >= m ) >= 1/2

با چک کردن کتاب کنوث (جلد ۳) فهمیدم که اشتباه حساب کردم و مقدارش به گفته‌ی این بزرگوار  این است:

sqrt{(21-2pi^2)/3} n ~0.65 n

تا جایی که من سرچ کردم اسمش anti-concentration inequalities است و راه‌حل کلی ساده‌ای نداشت.

۳- تابع مولد گشتاور توزیع پواسون با میانگین a برابر است با:

e^{a(e^t-1)}

متغیرهای x و y مستقلند پس:

E~x,y[e^{t(x+y)}]=E~x,y[e^{tx} e^{ty}] = E~x[e^{tx}] E~y[e^{ty}]

e^{(a+b)(e^t-1)}= e^{a(e^t-1)} * e^{b(e^t-1)}

پس اثبات شد.

۴- الف) توزیع میانگین n تا متغیر تصادفی با این توزیع نرمال را به دست می‌آوریم.

N(m,1) --> N(nm,n)-->N(m,n/n^2)=N(m,1/n)

با احتمال 99.7% مقدار در بازه‌ی m+/-3/sqrt{n} می‌افتد.

https://en.wikipedia.org/wiki/Normal_distribution#Standard_deviation_and_coverage

ب) میانه و میانگین توزیع نرمال برابرند. در نتیجه مقل قسمت الف.

ج) توزیع میانگین متغیرهای نرمال N(m,1) به تعداد n/2 تا و متغیرهای نرمال N(m,n) به تعداد n/2 تا:

N(nm, n/2+n/2 * n) --> N(m, 1/n^2 (n/2+n/2 * n) ) = N(m, 1/(2n)+1/2)

پس با احتمال ۹۹.۷٪ مقدار در بازه‌ی m+/-3sqrt{1/(2n)+1/2} می‌افتد.

میانه‌ی n/2 متغیر تصادفی اول می‌شود m و میانه‌ی n/2 متغیر تصادفی دوم هم می‌شود m. پس میانه‌ی کل هم می‌شود m.

در چرنف تنها چیزی که تأثیر دارد میانگین است. میانگین میانه‌ی متغیرهای تصادفی که میانگین همه‌ی آنها روی m است باز هم m می‌شود، چون نمودارها در دو طرف m به ازای همه‌ی توزیع‌های داده شده برابر می‌شود. پس فرقی نمی‌کند.

۵) الف) خود صورت سوال گفته است چه کار کنیم. ما هم همین کار را می‌کنیم. هر ضلع مربع را به sqrt{n/log n} قسمت مساوی تقسیم می‌کنیم. احتمال اینکه هر مربع حداقل یک نفر داشته باشد را حساب می‌کنیم:

احتمال اینکه در پرتاب اول توپ در یک خانه خاص بیفتد برابر است با:

p=(log n )/ n

چون n بار این آزمایش را تکرار می‌کنیم، توزیع دوجمله با احتمال p داریم. پس امید ریاضی آن می‌شود:

np=n log n / n = log n

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

pr( x > n/log n * E[x] ) <= e^{-log n * n^2/ log^2 n *1/3} = e^{-n^2/(3 log n)}

(1-p)^n=(1-log n/n)^n =e^{-n/log n}=o(1)

در نتیجه احتمال موفقیت که ۱ منهای این مقدار است با احتمال بالا است.

راه دیگر:

چون n/log n تا از این متغیرها داریم، احتمال اینکه حداقل یکی شکست خورده باشد طبق union bound حداکثر می‌شود:

n/log n (1-log n/n)^n  = n/log n (e^{-n/log n}) = e^{log n/log log n - n/log n}

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

1-e^{log n/log log n - n/log n} >= 1-e^{log n- n/log n} > 1-e^{n/(2log n)}=1-o(1)

یعنی با احتمال بالایی هر مربع حداقل یک نفر دارد.

احتمال اینکه در فاصله‌ای که سوال گفته k تا همسایه داشته باشد را حساب می‌کنیم.

طول ضلع هر مربع می‌شود:

1/(sqrt{n/log n}) = sqrt{log n / n}

تعداد متغیرهایی که در این فاصله می‌افتند برابر است با:

pi*[ 10 (log n / n)^{1/2} / sqrt{log n / n}  ]^2 ~ 314

n'*p=  314 (log n )/ n

pr(x>= k) = pr(x>=c log n) = pr(x >= cn/314 E(x) ) <= e^{-314 log n / n (cn/314)^2/3} = e^{-314/3 c^2 n log n} = o(1)

پس با احتمال بالایی هر کسی با همه‌ی خانه‌های مجاور خود همسایه است، در نتیجه کل گراف با احتمال بالا همبند است.

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

سوالها: 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

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

http://theory.stanford.edu/~valiant/teaching/CS265_2018/index.html
سوالهای تمرین این درس روی سایتش هست که احتمالاً در سری جدید شروع می‌کنم به حل کردن اینها. چون اکثر کامنت‌هایی که برای مطالب وبلاگ‌ها می‌گیرم درخواست حل سوالهاست.

سوالهای پایان ترم الگوریتم تصادفی (امسال)

۵ تا سوال
سوال ۴ و ۶ تمرین
- ثابت کنید تعداد min cut ها میشه n(n-1)/2 حداکثر
- ثابت کنید تعداد بیت های استخراجی حداکثر n* antropi میشه
- یک قدم زدن تصادفی که در یک حلقه‌ی m بار تکرار بود و مقداری برای m می‌خواست که احتمال شکست حداکثر ۱/۲ بشود.

یک سوال امتحان میان ترم تصادفی (۹۴)

Let N := {1, . . . , n} and let f : N × N → R be a function. Assume for simplicity that f(i, j) ̸= f(i ′ , j′ ) if (i, j) ̸= (i ′ , j′ ). We want to compute the value M := min1⩽i,j⩽n f(i, j). This can of course easily be done in O(n 2 ) time, by simply evaluating all f(i, j)’s—we assume that evaluating f(i, j) takes O(1) time—and then finding the minimum of all these values. Now suppose we have a magic subroutine Test(i, x) available that returns true if min1⩽j⩽n f(i, j) ⩽ x and false otherwise. The function Test runs in T ∗ (n) time.
(i) Describe a randomized incremental algorithm to compute M that runs in O(n log n+ nT∗ (n)) expected time. Argue that your algorithm is correct and show that your algorithm runs in the required time. Hint: Define F(i) = min1⩽j⩽i f(i, j) and observe that M = min1⩽i⩽n F(i).
(ii) Describe a randomized divide-and-conquer algorithm to compute M that runs in O(n log n+nT∗ (n)) expected time. Argue that your algorithm is correct and show that your algorithm runs in the required time.

Expected linear time MST algorithm

https://en.wikipedia.org/wiki/Expected_linear_time_MST_algorithm

قدم زدن تصادفی: گرافهای نامتناهی و قدم‌زدن چندگانه

گفته یک آدم مست ممکنه راهش را پیدا کنه، اما یک پرنده‌ی مست ممکنه هیچ وقت راهش را پیدا نکنه!

https://www.cs.bris.ac.uk/Research/Algorithms/events/BAD16/Slides/sauerwald.pdf

یک کران پایین با استفاده از مسئله‌ی جمع کردن کوپن داده (باید از همه‌ی انواع کوپن داشته باشید، باید چند تا بخرید تا با احتمال بالایی برنده بشوید؟):

https://en.wikipedia.org/wiki/Coupon_collector%27s_problem

ثابت کرده که برای گسترگرافها کمتره. (البته الآن مقاله‌ای که من ارائه می‌دهم برای یک گسترگرافه و ثابت کرده لگاریتم n تقسیم بر توان ۲ گسترش گراف است.)

چیزی که انگار هیچ کس در نظر نگرفته این است که گذشتن همزمان چند نفر از یک رأس کار خوبی نیست. البته این به اسم intersection time ازش حرف زده.

زمان لازم برای پوشش گراف با قدم‌زدن‌های تصادفی موازی

https://arxiv.org/pdf/0705.0467.pdf