جواب سوال 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) >=