عدد تصادفی چیست؟ (قسمت ۱)

برای همه ما پیش آمده است که با سوالاتی مانند پیدا کردن ادامه دنباله ای عددی مانند دنباله زیر روبرو شویم:5,1,1,2,5,3,3,8,2,4,…گاهی اوقات با تلاش زیاد می توانیم ادامه دنباله را حدس بزنیم و گاهی هم شکست میخوریم در آن لحظه ممکن است تصور کنیم که دنباله هیچ "الگوی" مشخصی ندارد و کاملا تصادفی است که ناگهان متوجه میشویم دوست باهوش تر ما ادامه دنباله را یافته است! نتیجه گیری منطقی و طبیعی که به ذهن می رسد این است که هیچ گاه نمی توان ادعا کرد که یک دنباله تصادفی است چرا که "شاید الگویی دارد که ما نمی دانیم" در مواردی این ممکن است به مغلطه توسل به جهل هم منجر شود! (فکر کنید چرا)مشکلاتی مانند این بسیاری از ریاضیدانانی که بر روی نظریه پیچیدگی محاسباتی کار می کردند را بر آن داشت تا تعریفی ریاضی از "تصادفی بودن" ارائه دهند. تعریف کولموگروف(Kolmogorov) در این میان از همه بیشتر مورد قبول قرار گرفت. این تعریف شهودی، جامع و زیبا است. بر اساس این تعریف دنباله ای تصادفی است که حجم کدی که برای تولید آن دنباله رندم تولید می شود( به صورت مجانبی) بیشتر یا مساوی با خود دنباله باشد. در اینجا منظور از "حجم کد" دقیقا به بایت است. به عبارت ساده تر وقتی هیچ الگوریتمی وجود نداشته باشد که حجم آن از حجم دنباله کمتر باشد دنباله هم قاعدتا هیچ الگویی ندارد.(تعریف algorithmically random)این تعریف بسیار دقیق و از لحاظ تئوریک غنی است اما در کاربرد های واقعی ما به یک تعریف عملیاتی تر نیاز داریم. تعریف عملیاتی دنباله ی تصادفی، بر اساس مفهوم "از لحاظ آماری تصادفی"(statistically random) قرار دارد. بر اساس این تعریف هر دنباله ی تصادفی می بایست تعدادی تست آماری را با موفقیت پشت سر بگذارد تا بتوان نام "رندم" بر آن نهاد. در اینجا وارد جزییات نمی شویم ولی ویژگی هایی مانند پیروی کردن از توزیع یکنواخت(یعنی تمام اعداد شانس مساوی برای حضور در دنباله داشته باشند) یا ویژگی بیشینه آنتروپی از آن دسته اند.حالا چطور اعداد تصادفی را در کامپیوتر ایجاد کنیم؟ هر گاه این سوال را از دانشجویانم میپرسم ابتدا کمی در فکر فرو می روند و سپس شوکه می شوند. چرا که بر خلاف دسترسی راحتی که برنامه ها به تولید اعداد تصادفی ایجاد می کنند یافتن الگوریتم ساخت اعداد تصادفی، غیر ممکن به نظر می رسد!در واقع بیشتر این برنامه ها اصلا اعداد تصادفی واقعی تولید نمی کنند. آن ها اعداد شبه تصادفی تولید می کنند. اعداد شبه تصادفی دارای فرمول هستند و دنباله ای که ایجاد می کنند تست های آماری را با موفقیت پشت سر می گذارند. یکی از معروف ترین الگوریتم های در این زمینه linear congruent generator است که از یک رابطه بازگشتی مانند زیر استفاده می کند:مقادیر m معمولا بزرگ است(مانند m=2^64) و a و c هم به مقادیری ست می شوند که در پکیج های مختلف متفاوت است. یکی از مهمترین قسمت های این فرمول بازگشتی مقدار اولیه ای است که به آن داده می شود و به عنوان دانه(seed) اولیه الگوریتم شناخته می شود. هر دانه دنباله ای کاملا متفاوت ایجاد می کند. با آنکه الگوریتم ایجاد اعداد شبه تصادفی در تقریبا تمامی نرم افزار ها(حتی اپل) به صورت عمومی در دسترس است، این الگوریتم برای نرم افزار متلب نامشخص است و تنها به گفتن: "تولید اعداد شبه تصادفی" اکتفا شده است. متلب دارای قابلیت تولید اعداد تصادفی است که این قابلیت در توابع rand، randn ، randi و randperm قرار گرفته است. تابع rand اعداد شبه تصادفی در بازه 0 تا 1 و به صورت یکنواخت تولید می کند. به طور مثال:برای تولید اعداد تصادفی در بازه دلخواه [a,b] کافی است به صورت زیر عمل کنیم:u = a + (a-b)*randتابع randn اعداد شبه تصادفی با توزیع گاوسی(نرمال) با میانگین صفر و واریانس یک ایجاد می کند(N(0,1)) این توزیع در طبیعت بسیار رخ می دهد و در کاربردهای علمی و مهندسی بسیار مورد استفاده قرار می گیرد به طور مثال:برای تولید اعداد شبه تصادفی با میانگین و واریانس دلخواه کافی است به صورت زیر عمل کنیم:تابع randi هم اعداد تصادفی صحیح تولید می کند. به طور مثال تابع زیر یک ماتریس m در n از اعداد تصادفی در بازه 1 تا x را تولید می کند.همچنین برای تولید اعداد تصادفی در یک بازه به صورت کلی داریم:تابع randperm قدری متفاوت است زیرا وظیفه آن ایجاد یک جایگشت تصادفی از اعداد در یک بازه است. مثلا:با اضافه کردن یک آرگومان دیگر می توان تعدادی از این اعداد را انتخاب کرد.(مثلا سه تا عدد به صورت تصادفی از بازه 1 تا 10)تفاوت این تابع با randi این است که randi انتخاب تصادفی با جایگزینی است اما randperm بدون جایگزینی است.قسمت دوم