مولدهای اعداد شبهتصادفی
مولد عدد شبهتصادفی یک رابطه بازگشتی قطعی است که از یک بذر اولیه، دنبالهای طولانی و قابل بازتولید از اعداد تولید میکند که از توزیع یکنواخت در بازه واحد، نمونهبرداریهای مستقل را شبیهسازی میکند.
Definition
مولد عدد شبهتصادفی الگوریتمی است که توسط یک حالت، یک تابع انتقال که حالت را پیش میبرد، و یک تابع خروجی که هر حالت را به یک عدد نگاشت میکند، تعریف میشود و دنبالهای تناوبی تولید میکند که از نظر آماری از اعداد تصادفی یکنواخت غیرقابل تشخیص است.
Scope
این موضوع شامل ساخت مولدهای یکنواخت (همنهشتی خطی، فیبوناچی تأخیری، ثبات تغییر بازخورد تعمیمیافته، و مولدهای ترکیبی)، ویژگیهای ساختاری که کیفیت آنها را تعیین میکنند مانند طول دوره و رفتار شبکهای یا توزیع یکنواخت، و آزمونهای تجربی و نظری مورد استفاده برای تأیید آنها میشود. مولدهای امن رمزنگاری تنها به عنوان یک هدف طراحی متضاد ذکر شدهاند.
Core questions
- کدام روابط بازگشتی دورههای طولانی و یکنواختی خوب در ابعاد بالا را به همراه دارند؟
- کیفیت یک مولد چگونه با ساختار شبکهای و توزیع یکنواخت آن اندازهگیری میشود؟
- کدام مجموعههای آزمون تجربی انحراف از تصادفی بودن را تشخیص میدهند؟
- مولدها چگونه بذردهی و ترکیب میشوند تا دوره را گسترش داده و خواص آماری را بهبود بخشند؟
Key concepts
- بذر و حالت
- طول دوره
- توزیع یکنواخت
- ساختار شبکهای
- آزمون طیفی
- مولدهای ترکیبی
Key theories
- مولدهای بازگشتی خطی
- روابط بازگشتی همنهشتی خطی و ثبات تغییر، یک حالت عدد صحیح را با استفاده از حساب پیمانهای پیش میبرند؛ دوره و ساختار شبکهای خروجیهای متوالی آنها توسط خواص نظری اعداد ضربکننده و پیمانه تعیین میشود.
- توزیع یکنواخت و مرسن تویستر
- مولدهای مبتنی بر ثباتهای تغییر بازخورد تعمیمیافته پیچیده، دورههای بسیار بزرگ و توزیع یکنواخت اثباتپذیر در ابعاد زیاد را به دست میآورند، که آنها را به یک پیشفرض پرکاربرد برای شبیهسازی آماری تبدیل کرده است.
Clinical relevance
مولد پیشفرض در یک بسته آماری، قابلیت بازتولید و اعتبار هر شبیهسازی، بوتاسترپ و نتیجه مونتکارلو را که تولید میکند، تعیین میکند؛ درک دوره و توزیع یکنواخت به متخصصان کمک میکند تا از مولدهایی که بینظمیهای پنهان آنها میتواند شبیهسازیهای با ابعاد بالا را مختل کند، اجتناب کنند.
History
لهمر روش همنهشتی خطی را در سال ۱۹۴۹ پیشنهاد کرد؛ تحلیلهای بعدی نقصهای شبکهای پارامترهای بد انتخاب شده را آشکار کرد، که انگیزه آزمون طیفی، مولدهای ترکیبی، و در نهایت طرحهای توزیع یکنواخت با دوره طولانی مانند مرسن تویستر در سال ۱۹۹۸ را فراهم آورد.
Key figures
- Donald Knuth
- Pierre L'Ecuyer
- Makoto Matsumoto
- Derrick Henry Lehmer
Related topics
Seminal works
- knuth1997
- matsumoto1998
Frequently asked questions
- چه چیزی یک مولد شبهتصادفی را بهتر از دیگری میکند؟
- یک مولد خوب دارای دوره بسیار طولانی است، خروجیهای خود را حتی در ابعاد زیاد به طور یکنواخت توزیع میکند، آزمونهای آماری استاندارد را با موفقیت پشت سر میگذارد، و سریع و قابل بازتولید است. مولدهای ضعیف میتوانند دورههای کوتاه یا الگوهای شبکهای قابل مشاهدهای داشته باشند که شبیهسازیها را مغرضانه میکنند.
- چرا بذر اهمیت دارد؟
- بذر حالت شروع را تثبیت میکند، بنابراین کل دنباله توسط آن تعیین میشود. ثبت بذر باعث میشود یک شبیهسازی دقیقاً قابل بازتولید باشد، در حالی که انتخاب بیدقت بذرها میتواند باعث همپوشانی یا همبستگی جریانها در اجراهای موازی شود.