آنتروپی و تولید عدد رندم

می خوایم یک عدد تصادفی یکنواخت بسازیم ولی فقط عدد تصادفی سازی داریم که توی کامپیوتر هست. (یک عدد رندم بین 0 و 1 تولید می کنه.)

معمولی که عدد تولید می کنیم خودمون توی برنامه ها (در یک عدد ضرب می کنیم) رندم یکنواخت نیست! :دی دلیل:

خب وقتی یک عدد تصادفی می سازیم احتمال اینکه یه عدد بزرگ ( با تعداد بیت زیاد) درست بشه بیشتر از اینه که عددهای با بیت کمتر ساخته بشن چون تعداد عددهای بزرگ بیشتره.

حالا حالتی رو در نظر بگیرید که بیت بسازیم تا عدد بشه. (حالت مطلوب!) اگر یک سری عدد 0 تا m داشته باشیم که احتمالشون مساوی باشه، باید چطوری بیتها رو رندم انتخاب کنیم؟ دو تا چیز هست که میشه اینجا تغییر داد یکی تعداد بیتهاست اون یکی احتمال 0 و 1 بودنشون.

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

احتمال ساخته شدن یک عدد k بیتی چقدره؟

(2^k)/m

امید ریاضی تعداد بیتها رو حساب می کنیم:

E(#bits) = sum_k_1_lg(m) (k* (2^k)/m)

ثابت می کنیم تعداد بیتهای عددی که با این روش جدید از روی قبلی می سازیم کمتر از log 1/q میشه که q احتمال رخ دادن اون عدده. می دونیم مجموع احتمالها یک میشه، پس 

?????