قدم زدن تصادفی روی دایره و گراف آبنبات چوبی

(مرجع http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15750-s02/www/ )

سوالهای کتاب (مبحث زنجیره مارکوف)

حل:

تقارن ندارد و احتمالها یکنواخت هم نیستند، پس حالت خاص نیست. با matlab حساب کردم این شد: 

>> P^33

ans =

    0.2346    0.3048    0.2631    0.1975

    0.2346    0.3048    0.2631    0.1975

    0.2346    0.3048    0.2631    0.1975

    0.2346    0.3048    0.2631    0.1975

جوابش همون طور که می بینید همه ی سطرهاش مساویند.

حل:

راه حل دوم: با رسم گراف آن می بینیم که احتمال تغییر وضعیت 1-p و احتمال ماندن در هر وضعیت p است.

حل:

با یک random walk گراف را رنگ می کنیم. راس اولی که در آن هستیم، قرمز می کنیم و راس بعدی را آبی و ادامه می دهیم. (بقیه اش سخت بود راه حل رو بخونید:)

جواب
حجم: 282 کیلوبایت

مرجع: http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15750-s02/www/sol7.ps

سوال تمرین تصادفی (مبحث آنتروپی)

جواب سوال 4: نمونه سوال آنتروپی

1- یک تاس n وجهی داریم که احتمال آمدن هر وجه آن pi است. ثابت کنید آنتروپی آن وقتی ماکسیمم است که pi=1/n باشد.

H(X) = sum(H(Xi))

طبق نامساوی حسابی هندسی (مثلا) مجموع وقتی ماکسیمم می شود که همه با هم برابر باشند.

i,j: H(Xi) = H(Xj) ==> pi = pj = 1/n

2- 

فرض می کنیم یک سکه با احتمال q داریم و می خواهیم اعداد n بیتی بسازیم.

دو به توان آنتروپی n بار پرتاب سکه:

2^(n*H(q)) = q^nq * (1-q)^n(1-q)

چیزی که باید ثابت کنیم این است:

C(n,nq) >= q^nq * (1-q)^(n-nq) / ( 2*sqrt(n) )

از باز کردن سمت چپ استفاده می کنیم:

C(n,nq) = n!/ ( (nq)! (n-nq)! )

طبق فرمول استرلینگ داریم:

n! > sqrt(2*pi*n)*(n/e)^n

1/n! > 1/ ( sqrt(2*pi*n) * (n/e)^n * e^1/(12n) )

به جای صورت و مخرج از فرمولهای بالا جایگذاری می کنیم و ساده می کنیم.

جمله ی (n/e)^n را هم به دو جمله با توانهای nq و n-nq می شکنیم:

C(n,nq) >= (e^1/12n) / ( q^-nq * (1-q)^-n(1-q) * e^(1/12nq+1/12(n-nq) )

C(n,nq) >= 2^nH(q)

پس کافی است ثابت کنیم:

e^ (1/12n-1/12nq-1/12(n-nq) ) >= 1/ (2*sqrt(n) )

ساده می کنیم:

1/12n-1/12nq-1/12(n-nq) = 1/(12n) * ( 1-1/q-1/(1-q) )

1/ ( 2*sqrt(n) ) = 1/2* n^-1/2

نامساوی حسابی هندسی:

1/q+1/(1-q) = 1/( q*(1-q) ) >= 4

1-1/q-1/(1-q) <= -3

e^ (1/12n-1/12nq-1/12(n-nq) ) >= e^-3*(1/12n) = e^-1/(4n)

یعنی باید ثابت کنیم

e^ -1/(4n) >= 1/ (2*sqrt(n) )

e^-1/(4n) = (1/e)^1/(4n) >= (1/2)^1/(4n) >= 

جواب سوال 3

من فکر کردم همین نامساوی اجتماع چندتا پیشامد کمتر از جمع احتمال تک تکشونه خوبه براش!

جواب سوال 2

باید تقریب رو از روی نمونه گیری به روی تعداد نمونه ها ببریم. (با به دست آوردن رابطه ی بین دقت نمونه گیری و تعداد تکرارهای اون)

جواب سوال 1

از این استفاده می کنیم که زمان متوسطی که فرض کردیم در واقع cover time گراف است یعنی همه ی راسها دیده می شوند.

سوالهای باقی مانده

1- چطور ثابت کنیم قدم زدن تصادفی را می شود در زمان کمتری انجام داد؟

2- تقریب اپسیلون و دلتا برای یک نمونه گیری تصادفی را چطور ثابت کنیم؟ (تعداد نمونه گیری ها را به دست بیاوریم)

3- چطور می توانیم از نامساوی چرنف استفاده کنیم، برای متغیرهای نامستقل (وابسته)؟

4- نمونه سوال آنتروپی؟

تقریب اپسیلون و دلتا

مثال: (ادامه سوال independent set های گراف)

قدم زدن تصادفی و زنجیره مارکوف