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

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

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