حل تمرین‌های فصل ۲ مبحث جویباری از درس داده‌های حجیم

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

مرجع: https://www.cs.dartmouth.edu/~ac/Teach/CS49-Fall11/Notes/lecnotes.pdf

۱- 

pr( h(x)=y , h(x')=y' ) = pr( Ax+b (mod 2)= y, Ax'+b (mod 2)=y') = pr( for all i: sum_j a_ij x_j +b_i = y_i, sum_j a_ij x'_j +b_i = y'_i) = prod_i pr( sum_j a_ij x_j +b_i = y_i, sum_j a_ij x'_j +b_i = y'_i) = prod_i pr( sum_j a_ij (x_j-x'_j)=y_i-y'_i) pr( sum_j a_ij x_j +b_i = y_i) = prod_i pr( sum_j a_ij x_j +b_i = y_i)^2

می‌توانیم ماتریس را به صورت k تا بردار n بعدی (هش با بردار) مستقل در نظر بگیریم. هش با بردار تصادفی دودویی روی یک بردار دودویی داده شده را می‌خواهیم احتمالش را حساب کنیم. از آنجا که به ازای هر بردار تصادفی هش، برداری هست که بیت‌هایش برعکس این است (اگر ۰ باشد ۱ است و برعکس)، پس احتمال اینکه صفر آمدنش با یک آمدنش برابر است. پس حالا جمع (xor) دو تا عدد تصادفی یکنواخت باید بشود یک مقدار داده شده، پس احتمالش ۱/۲ است.

= prod_i 1/4 = 1/4^k = 1/(2^k)^2 = 1/|Y|^2

۲- در ورودی دو تا بردار n-بعدی تصادفی a,b و بردار n-بعدی x را داریم، احتمال اینکه k بیت آخر ax+b هر مقداری بگیرد چقدر است؟

چون تناظر یک به یک داده شده است، پس احتمال اینکه هر برداری انتخاب شود برابر است با:

1/|Y|

مشابه بالا به دست می‌آید:

pr( ax+b = y, ax'+b=y') = pr(ax+b=y) pr(a(x-x')+b=y-y') = pr(ax+b=y)^2 = 1/|Y|^2

در مورد مقایسه این روش با قسمت قبل هم می‌بینیم که فرقی ندارند. قسمت قبل حالت خاص این است. چون احتمالها یکسان به دست می‌آیند.