When you are listening to the corn pop, are you hearing the Central Limit Theorem?

William A. Massey
1996

The generation of random numbers is too important to be left to chance

Robert R. Coveyou

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

به طور کلی اطلاعات یک واقعه رو متناسب با احتمال رخ دادن اون واقعه تعریف می‌کنن به این ترتیب که هر چه قدر احتمال رخ دادن کم‌تر باشه، اطلاعات اون رخ‌داد بیش‌تر بوده. مثلا به این مثال توجه کنین(۱): در یک کیسه ده توپ داریم با شماره‌های صفر تا نه. توپ شماره صفر سبز رنگه و بقیه‌ی توپ‌ها قرمز رنگ هستند. اگر یک نفر به داخل کیسه دست ببره و یک توپ در بیاره و بگه که رنگش قرمزه، نتیجه‌ای که می‌شه گرفت اینه که عدد روی توپ عددی بوده بین یک تا نه. ولی اگر بگه که رنگ توپ سبزه، به قطع می‌تونیم بگیم که عدد روی توپ صفره. یعنی وقتی که رنگ توپ قرمز بود، اطلاعات خیلی کم‌تری منتقل شد به نسبت وقتی که رنگ توپ سبز بود.

اطلاعات یک واقعه با احتمال p رو برابر با

-log p

تعریف می‌کنند (مثلا در مبنای دو. در این متن تمام لگاریتم‌ها در مبنای دو هستند). در نتیجه در مثالی که گفتیم اطلاعات موجود در بیرون کشیده شدن توپ سبز برابر با

-log 0.1 = 3.32192809

بود در حالی که اطلاعات موجود در بیرون کشیده شدن توپ قرمز برابر با

-log 0.9 = 0.152003093

بود. با این ترتیب برای سکه‌ای که شانس برابر نداشته باشه، فرض کنین که احتمال اومدن شیر برابر با p باشه (و در نتیجه خط برابر با 1-p خواهد بود). با توجه به این که هر کدوم احتمال رخ دادن خودش رو داره و در صورت اتفاق افتادن هر کدوم یک مقدار اطلاعات منتقل شده، پس اطلاعاتی که از یک بار انداختن اون سکه حاصل می‌شه برابره با:

-p*log p – (1-p)*log 1-p

حالا اگر بخواهیم این شکل رو رسم کنیم، می‌تونیم نمودار اطلاعات رو بر اساس احتمال اومدن شیر بکشیم که این شکلی می‌شه (۲):

که به این معناست که اگر احتمال اومدن شیر یک‌دوم باشه، بیش‌ترین اطلاعات از انداختن سکه حاصل می‌شه و هرچه قدر که سکه به سمت ناعادلانه شدن پیش‌تر می‌ره، اطلاعات حاصل از انداختن هربار سکه کم‌تر می‌شه.

منتظر مطالب بعدی باشید!

(۱) این مثال رو از کتاب Dynamics of Complex Systems گرفتم.
(۲) شکل رو در این‌جا ساختم: http://www.walterzorn.com/grapher/grapher_e.htm

چیزهایی هستند که عادی شده‌اند و زیاد به نظر نمی‌رسند، اما وقتی که کسی بتونه به خوبی نشون‌اش بده، تازه متوجه می‌شیم که جریان چیه. برای من یکی از این چیزهای ناشناخته جبر خطی بود که به کمک درس‌های آنلاین امایتی (MIT) دارم یاد می‌گیرم. دکتر Gilbert Strang مدرس این درس از پیش‌گامان قرار دادن درس‌ها به صورت آنلاین هست و تا به حال تاثیر زیادی در این برنامه داشته. این جبر خطی رو هم خیلی ساده و راحت و به شیوایی ارایه می‌کنه. مطالبی می‌گه که من فکر می‌کردم بلد بودم اما تازه متوجه شدم که عملا چیز نمی‌دونستم. از هر زمینه‌ای هم که باشین، حتما در این لیست بزرگ درس‌هایی پیدا می‌کنین که براتون مفید باشه:

http://ocw.mit.edu

آیا اگر یک لیوان شیر یک درصد چربی رو با یک لیوان شیر دو درصد چربی مخلوط کنیم حاصل دو لیوان شیر یک و نیم درصد چربی خواهد بود؟

تعریف درصد چربی شیر چه چیزی باید باشه تا رابطه‌ی بالا برقرار نباشه؟

فرض کنین یک سکه داریم که احتمال اومدن شیر یا خطش برابر نیست (مثلا به احتمال شصت درصد-چهل درصد شیر یا خط می‌یاد). برای این که با استفاده از این سکه بین دو نفر یکی‌شون رو انتخاب کنیم (و بخوایم که انتخاب عادلانه باشه) چه کاری باید بکنیم؟

کمی در مورد جواب فکر کنین…

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

به نظرم باید یک کار کرد: سکه رو دو بار پرتاب می‌کنیم. اگر نتیجه‌ی بار اول با بار دوم فرق داشت (مثلا بار اول شیر و بار دوم خط اومد) یکی از دو نفر رو انتخاب می‌کنیم (فرقی نمی‌کنه که کدوم‌شون باشه به شرط این که قبل از انداختن سکه مساله رو طی کرده باشیم. مثلا اگر شیر-خط اومد نفر اول و اگه خط-شیر اومد نفر دوم). اما اگر هر دو بار یک جور اومد (که به احتمال بیش‌تر اون طرفیه که سکه شانس افتادن بیش‌تری داره) باید کل آزمایش رو از اول تکرار کنیم. این طوری اگر یک نفر رو انتخاب کنیم عادلانه بوده.

اما این روش یک مشکل هم داره: تضمینی در مورد زمان رسیدن به نتیجه (و انتخاب یک نفر) وجود نداره. هرچه‌قدر که سکه تمایل‌اش به یک جهت بیش‌تر باشه احتمال این که مجبور بشیم آزمایش‌ها رو هم تکرار کنیم بیش‌تر می‌شه. در حالت حدی شرایطی رو تصور کنین که سکه همیشه روی یک طرف می‌نشینه. در این حالت هیچ وقت نمی‌شه بین دو نفر یکی‌شون رو به طور تصادفی انتخاب کرد. هر چه قدر احتمال اومدن سکه به نیم نزدیک‌تر باشه سریع‌تر به جواب می‌رسیم و بیش‌ترین حالت‌اش وقتیه که برابر نیم باشه (که در یک آزمایش حتما جواب می‌گیریم با در نظر گرفتن روش معمول سکه انداختن).

اگر موضوع جذب‌تون می‌کنه در مورد مباحثی مثل Information entropy و Information theory بیش‌تر مطالعه کنین.

از این‌جا شروع شد که یک راه حل ساده برای انتخابات در آمریکا به یک مشکل اساسی تبدیل شد. طبق قانون اساسی تعداد نمایندگان مجلس باید متناسب با جمعیت ایالت باشه. برای این منظور یک راه حل ساده استفاده شد که به وسیله‌ی کسی به اسم الکساندر همیلتون پیشنهاد شده بود: با توجه به تعداد نمایندگان مجلس و جمعیت ایالت یک تناسب ساده تشکیل می‌دیم و تعداد نمایندگان هر ایالت مشخص می‌شه. اما یک مشکل هست و اون این که به احتمال زیاد این عدد اعشار هم داره. برای حل این مشکل اول هر ایالت به اندازه‌ی مقدار صحیح عددش نماینده‌هاش رو می‌فرسته (و چون تعدادی اعشاری داشته‌ان پس هنوز مجلس پر نشده). در قدم بعدی ایالت‌هایی که اعشارهای بزرگ‌تری داشته‌ان هرکدوم به ترتیب یک نماینده می‌فرستن تا این که مجلس پر بشه. برای مثال اگه تعداد نماینده‌های مجلس ۱۹ نفر باشه و بنا بر جمعیت تعداد ایده‌آل نماینده‌های ایالت‌ها ۱٫۹ و ۲٫۸۵ و ۳٫۸ و ۴٫۷۵ و ۵٫۷ باشه در اون صورت تعداد نماینده‌های نهایی به ترتیب ۲ و ۳ و ۴ و ۵ و ۵ خواهد بود (دقت کنین که چهار ایالت اول یک نماینده بیش‌تر به مجلس فرستاده‌ان تا مجلس پر بشه).

ولی قضیه به همین سادگی هم نیست. مثلا فرض کنین یک مجلس داریم برای سه ایالت با جمعیت‌های ۳۸۰ و ۳۸۰ و ۲۴۰ نفر. اگر تعداد نمایندگان مجلس ۱۴ نفر باشه طبق قانون گفته شده به هر ایالت ۵ و ۵ و ۴ نماینده می‌رسه. اگر تعداد نمایندگان مجلس رو به ۱۵ نفر افزایش بدیم تعداد نمایندگان هر ایالت در این حالت به ۶ و ۶ و ۳ نفر می‌رسه! یعنی این که وقتی که تعداد نمایندگان زیاد می‌شه تعداد نماینده‌های ایالت سوم کاهش پیدا می‌کنه. آزمایش این قضیه را به خوانندگان علاقه‌مند واگذار می‌کنیم!

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

نکته: این مساله من رو به یاد مساله‌ای در سیستم عامل انداخت به نام آنومالی بلادی.

نتیجه: راه‌حل‌هایی که به نظر ساده می‌یان و سازگار با حس عمومی به نظر می‌رسن الزاما هم در عمل موفق نخواهند بود.

منبع:

Morton D. Davis, Game Theory: A Nontechnical Introduction, 1997