از قمارخانه‌های مونت‌کارلو تا بمب اتمی

در این پست تمام موضوعاتی را که در این وبلاگ به آن پرداخته بودم را با توجه به فرموده استاد در یک فایل ورد جمع بندی کرده  و لینک دانلود آن را برایتان قراردادم.

http://persiandrive.com/669238

نوشته شده در ۱۳٩٢/٤/۱ساعت ۳:٠۳ ‎ب.ظ توسط فاطمه متولیان نظرات () |

Manhattan   پروژه

پروژه منهتن یک پروژه تولیدی تحقیقاتی است که اولین بمب های اتم را در طول جنگ جهانی دوم تولید کرد. این کار با رهبری ایالات متحده و حمایت انگلیس و کانادا انجام شد. از سال1946، این پروژه تحت راهنمایی و رهبری سر لشکرLeslie Groves از گروه مهندسین ارتش آمریکا بوده است. پروژه منهتن به تدریج در سال1939 شروع به کار کرد اما با رشد بیشتر بیش از 130000 نفر را استخدام کرد و ارزش سهام آن تقریبا از 2 دلار به حدود 26 دلار در سال2013 رسید. بیش از 90% ارزش سهام آن، مربوط به کارخانه های ساخت و تولید مواد اتمی و شکافت پذیر بود که کمتر از 10% آن مربوط به گسترش و تولید سلاح های نظامی بوده است. تحقیقات و تولید در بیش از 30 محل در ایالات متحده،انگلیستان و کانادا انجام می شود. دو نوع از یمب های اتمی در طول جنگ تولید شده اند. یک سلاح ساده نظامی اتمی شبیه تفنگ با استفاده از اورانیوم 235 و یک ایزوتوپی ساخته شده است که تنها با 7% اورانیوم طبیعی ترکیب می شود.

سه روش برای غنی سازی اورانیوم بکار گرفته شده است:

1-الکترومغناطیس          2-گازی(روش گازی)         3-گرمایی

اکثر این کار درOak Ridge،Tennessee انجام شده است.

موازی با کار روی اورانیوم تلاش دیگری برای پلوتونیوم انجام می شد. رآکتورها درOak Ridge و  Hanp-ordواشنگتن ساخته شده اند که در این رآکتورها، اورانیوم تابانده تبدیل به پلوتونیوم می شود. سپس پلوتونیوم به صورت شیمیایی از اورانیوم جدا می شود. طرح ساخته شده از نوع تفنگی با استفاده از پلوتونیوم به صورت غیر عملی مورد تست و امتحان قرار گرفت و در نتیجه سلاحی دیگر با ترکیب پیچیده تری(کمپلکس) از نوع انفجاری در قالب یک طرح جامع و طی تلاش ساختاری در لابراتور تحقیق و طراحی پروژه های سلاح های نظامی درLos Alomos در نیومکزیکو آمریکا ساخته شد.

پروژه منهتن طی یک پروژه امنیتی کاملا بسته اجرا شد اما جاسوسان برنامه های اتمی در اتحادیه جماهیر شوروی هنوز برنامه را تحت نفوذ خود قرار داده اند. همچنین ابن برنامه توسط آگاهی و دانش عمومی در پروژه های انرژی هسته ای آلمان نیز حمایت و پشتیبانی شده است.

از طریق عملکرد با عملیاتAlsos ، پرسنل پروژه منهتن که در اروپا انجام وظیفه می کردند، گاهی در پشت خطوط دشمن قرار می گرفتند، جایی که آنها مواد هسته ای را جمع آوری و توده می کردندو در آنجا دانشمندان آلمانی نیز حضور داشتند. اولین سلاح هسته ای که تا به حال و همیشه منفجر شده است، یک بمب انفجاری در تست Trinity(سه گانه) بوده است که در محدوده توبخانه و بمباران Alamogorob نیومکزیکو در 16ژولای 1945 هدایت و اداره شده است.

یک سلاح شکل تفنگ به نام Little boy(پسر کوچک) و یک نوع انفجاری به نامFat Man(مرد چاق) به ترتیب در بمباران اتمی هیروشیما و ناگاساکی مورد استفاده قرار گرفته شدند . بلافاصله در سالهای پس از جنگ، پروژه منهتن از تست های اسلحه ها در Bikini Atoll به عنوان قسمتی از تقاطع عملیاتی، اسلحه های جدیدی را تولید کرد که باعث گسترش شبکه آزمایشگاههای مردمی شد و توسط مرکز تحقیقات پزشکی به رادیولوژی حمایت گردید و این اساس و پایداری برای تشکیل نیرو یا ناوگان هسته ای شد. این پروژه، کنترلی روی تحقیقات و تولید سلاح اتمی آمریکا اعمال داشت تا اینکه شکل گیری کمیسیون انرژی اتمی ایالات متحده در ژانویه1947 به وقوع انجامید.

منابع:

در آگوست 1939، فیزیک دانان مهم و برجسته Leoszilard وEugeneWigner نامه ای را مطرح کردند که تولید و گسترش پتانسیل"بمب های بسیار قدرتمند یک نوع جدید" را هشدار دادند. آنها ایالات متحده را مورد خطاب قرار داده تا قدم هایی برای بدست آوردن ذخایر سنگ معدن اورانیوم بردارند و تحقیقاتEnrico Fermi(فرمیوم) و دیگر واکنش های زنجیره هسته ای را هر چه سریعتر انجام دهند. این کارها می بایست توسط آلبرت انیشتین انجام شده و تحویل رئیس جمهور FranKlin D. Roosevelt می شد.

Roosevelt ، Lyman Briggs را از دفتر ملی استانداردها فراخواند تا از کمیته مشاور برای اورانیوم برای بررسی مسائل مطرح شده در نامه ارسالی کمک بگیرد. Lyman Briggsجلسه ای را راجع به این مطلب در21اکتبر 1939 با حضور Szilard،Edward Teller و Wigner تشکیل داد. کمیته در ماه نوامبر به Roosevelt گزارش داد که اورانیوم یک منبع مملکتی برای بمب ها با قابلیت تخریب سازی بسیار بیشتر از هر نوع شناخته شده در حال حاضر می باشد.

Briggs پیشنهاد کرد که کمیته ملی تحقیقات دفاعی ،  167000دلار صرف تحقیقات روی اورانیوم بخصوص ایزوتوپ اورانیوم 235 و در نهایت پلوتونیوم کشف شده کند. در 28 ژوئن 1941، Roosevelt، دستور اجرایی 8807 را امضاء کرد که این دستوری برای تاسیس مرکز تحقیقات و توسعه ملی(OSRD) با ریاست Vannevar Bush بود. این مرکز این اجازه و این قدرت را داشت تا پروژه های بزرگ و مهندسی را علاوه بر کارهای تحقیقاتی راه اندازی و انجام دهد.

کمیته ملیNDRC(تحقیقات دفاعی) در زمینه اورانیوم، به عنوان کمیته اورانیوم S-1 مرکزOSRD برگزیده شد که کلمه"اورانیوم" به زودی و به دلیل امنیتی از آن انداخته و حذف شد. در بریتانیا ،Otto Frisch و Rudolf Peierls در دانشگاه BIRMINGHAM، پیشرفت و نفوذ پیروزمندانه ای را در زمینه بررسی مقدار بحرانی اورانیوم 235 در ژوئن 1939 انجام داده اند. محاسبات آنها نشان می دهد که این پیشرفت ملی حجم بزرگی از10 کیلوگرم(221B) بوده که به حد کافی برای حمل توسط یک بمب افکن در یک روز کوچک بوده است. سپس روش مربوط به نامه Frisch-Peierls1940 ، پروژه بمب اتمی بریتانیا و کمیتهMaud را آغاز کرد که بصورت متفق القول و هم رای پیشنهاد دادند که گسترش و تولیدیک بمب اتمی را دنبال کنند.یکی از اعضای آن، فیزیکدان استرالیاییMark Oliphant بود که در پایان آگوست1941 به ایالات متحده رفت و کشف کرد که اطلاعات و داده های فراهم شده توسط کمیتهMaud بدست هیچ فیزیکدان کلیدی آمریکایی نرسیده بوده است، آنگاه Oliphant ترتیبی داد تا پیدا کند که چرا یافته های کمیته ها ظاهرا نادیده گرفته شده است.

او با کمیته اورانیوم ملاقاتی داشت و با Berkeley در کالفرنیا دیدار کرد، جایی که او به شکل بسیار متقاعد و مجاب شده با Earnet O.Lawrence صحبت کرد. لاورنس به حد کافی تحت تاثیر واقع شده بودتا تحقیق خود را راجع به اورانیوم آغاز کند. او به ترتیب با James B.Conant ،Arthur Compton و GOERGE Pegram صحبت کرد. بنابراین ماموریتOliphant یک موفقیت بوده که اکنون ، فیزیکدان کلیدی آمریکایی آگاه از قدرت نهفته یک بمب اتمی است.

در یک جلسه میان رئیس جمهورPresident) Roosevelt)  ، و نائب رئیس Heny A.Wallance در 9 اکتبر 1941، رئیس جمهور برنامه اتمی را تصویب کرد. برای کنترل آن، او گروهی را با خط مشی بالا و عالی تشکیل داد که شامل خودش(اگر چه او هرگز مایل به شرکت در جلسه ای نبود)،Wallace،Bush،Conant، منشیWarHenryl.Stimon و رئیس ستاد ارتش، ژنرال جورج مارشال بود. Roosevelt ، ارتش را به عنوان مجری پروژه بجای ناوگان دریایی انتخاب کرد زیرا ارتش تجربه بیشتری در مدیریت پروژه های بسیار بزرگ داشته است.

همچنین او توافق کرد تا تلاش را با ارتش بریتانیا انجام دهد و در11 اکتبر، پیغامی رابه نخست وزیرWinston Churchill ارسال کرد و پیشنهاد داد تا آنها را راجع به موضوعات اتمی مذاکره و مکاتبه کنند.

 طرح های پیشنهادی:

کمیته S-1 اولین ملاقات خود را در 18 دسامبر 1941"که با جدیت و فوریت همراه بود" به دنبال حمله به بندرگاه مروارید(Pearl)  و آمادگی بعدی جنگ توسط ایالات متحده در ژاپن و آلمان برگزار کرد.

کار بر اساس اقدام روی 3 روش متفاوت برای جدا سازی ایزوتوپ به منظور جدا کردن اورانیوم 235 از اورانیوم 238 انجام می شد.

Lawrence و تیم او در دانشگاه کالیفرنیا،Berkeley جداسازی الکترومغناطیس را مورد بررسی و تبادل نظر قرار دادند در حالی که تیم Eger Murphree و Wakefield Beam راجع به انتشار و پخش گازی در دانشگاه کلمبیا کار می کردند و Philip Abelson تحقیقات را به سمت پخش حرارتی و گرمایی در موسسه Carnegie واشنگتن و سپس در لابراتور تحقیقات دریایی هدایت می کرد.

همچنین مورفی(Murphee) رئیس پروژه ناموفق جداسازی از طریق سانتریفیوژ بود. ضمنا دو خط تحقیقاتی راجع به تکنولوژی رآکتورهای هسته ای وجود دارند که Harold Urey تحقیقاتش را در آن راجع به آب های سنگین در کلمبیا ادامه می دهد در حالیکه Arthur Compton دانشمندان در حال کار را تحت نظارت خود در دانشگاه کلمبیا و دانشگاهPrinceton به دانشگاه شیکاگو در آورد ودر عین حال آزمایشگاه متالوژی را در اوایل 1942 تاسیس کرد تا راجع به پلوتونیوم و رآکتورهایی به مطالعه بپردازد که از گرافیت به عنوان یک تعدیل کننده نوترون استفاده می کند.

بریگز،کمپتون،لاورنس،مورفی و اوری در 23 می 1942 همدیگر را ملاقات کردند تا پیشنهادات کمیته S-1 را به مرحله نهایی برسانند که این پیشنهادات برای دنبال کردن هر 5 تکنولوژی فراخوانده می شوند.

این مطلب توسط  Bush،Conant و ژنرال فرماندهW.lhelm D.styer، رئیس خدمات تامین ستاد سرلشکرBrehon B.Somervell تصویب شده است که او نماینده ارتش را به موضوعات هسته ای اختصاص داده بود. سپس Bush،Conant پیشنهاداتی را به گروه خط مشی های برتر با بودجه پیشنهادی 54میلیون دلار برای ساخت شرکت (بنگاه) مهندسین ارتش ایالات متحده،31 میلیون دلار برای تحقیقات و توسعه توسط OSRD و 5 میلیارد دلار برای احتمالات ممکن در سال محاسباتی(مالیاتی) 1943 ارائه دادند. گروه خط مشی های برتر به نوبت آن را به رئیس جمهور در 17 ژوئن 1942 ارسال کرد و آن را بوسیله نوشتن کلمه"OKFDR" بر روی آن سند ، آن را تایید کرد.

منابع:

ترجمه سایت ویکی پدیا

نوشته شده در ۱۳٩٢/۳/٢٥ساعت ٦:٤٢ ‎ب.ظ توسط فاطمه متولیان نظرات () |

قدم زدن تصادفی یک بعدی روی شبکه ای از اعداد صحیح تنها یک تقریب خام برای حرکت براونی است.اما حرکت بروانی چیست؟ تئوری ریاضی حرکت بروانی  توسط نوربت وینر کشف شد .بنابراین ، حرکت بروانی اغلب فرایند وینر نامیده می شود.

حرکت بروانی توسط سه اصل تعریف می شود،Wt  متغیر تصادفی محل ذره در زمان t است(در اینجا t متغیر پیوسته است)

-  W0=0

-  برای t1<t2<…<tn ، تفاوت  مستقل هستند.

-  برای  ،Wt-Ws  توزیع نرمال با میانگین 0 و واریانس (c(t-s است، که در آن c>0 یک ثابت عددی است.

با فرض استقلال ، می بینیم که برای به دست آوردن حرکت براونی در بعدهای بالاتر، برای مثال دو بعد ، می توانیم به سادگی مراحل قدم زدن متناوب را در جهت  x و سپس در جهت y بسازیم. ما همچنین می توانیم یک جهت را به تصادف انتخاب کنیم  و توزیع نرمال اندازه گام را در این جهت بگیریم. نمودار بالا سمت چپ در شکل زیر یک شبیه سازی دو بعدی حرکت بروانی است .در هر گام، جهت جدید به طور تصادفی انتخاب و اندازه گام با توجه به توزیع نرمال با انحراف معیار ثابت انتخاب می شود.این به مشاهده موقعیت ذره در فواصل زمانی ثابت مربوط می شود.

نمودار سمت راست پایین در شکل ، 400 نقطه انتهایی این قدم ها را نشان می دهد. که تجسم چگالی احتمالی از رسیدن فاصله ذرات در 2000 مرحله است. همانطور که در بالا ذکر شد، این یک  چگالی نرمال 2 بعدی توزیع شده  متقارن اطراف مبدا است.

برای آشنایی بیش تر با حرکت بروانی به وبلاگ خانم موسایی http://autstat14.persianblog.ir/  مراجعه کنید.

 

 

کد اجرایی متلب

 

 

منابع:

کتاب Explorations in Monte Carlo Methods

نوشته شده در ۱۳٩٢/۳/٢٤ساعت ۱:٥۸ ‎ب.ظ توسط فاطمه متولیان نظرات () |

الگوریتم نمونه گیر مستقل

نمونه گیر مستقل که توسط تیرنی پیشنهاد شد، یک حالت خاص از الگوریتم متروپلیس-هستینگز است . که  توزیع پیشنهادی(q(y|x  مستقل از X است .بدین معنی که(q(y|x)=g(y است. این روش وضعیت بعدی را به طور مستقل از وضعیت قبلی تولید می کند. پس احتمال پذیرش برابر است با

به طور کلی نمونه گیر مستقل می تواند خیلی خوب و یا خیلی بد کار کند. برای اینکه نمونه گیر مستقل خوب کار کند، توزیع پیشنهادیq باید یک تقریب خوب برای f باشد یعنی خیلی شبیه توزیع هدف باشد . بهتر آن است که توزیع پیشنهادی دارای دنباله ای کلفت تر از توزیع هدف باشد ، زیرا در غیر اینصورت بسیاری از نقاط توزیع پیشنهادی در دنباله نخواهد بود و این باعث می شود  بسیار بزرگتر از  باشد که احتمال پذیرش کوچکی را نتیجه می دهند که باعث حرکت نکردن زنجیر خواهد شد.

منابع:

کتاب شبیه سازی آماری دکتر صادق رضایی و رسول طهماسبی

کتاب  Handbook of Monte Carlo Methods 

نوشته شده در ۱۳٩٢/۳/٢۳ساعت ٤:۱۸ ‎ب.ظ توسط فاطمه متولیان نظرات () |

ایده زنجیر مارکوف به سال 1953 برمی گردد، وقتیکه متروپلیس و همکارانش مقاله" چگونگی محاسبه معادلات با استفاده از ماشین های محاسبات سریع" را منتشر کردند.[MRRTT] نویسندگان در حال تلاش برای حل مسائل موجود در فیزیک به علت تصادفی بودن حرکت جنبشی اتم ها و مولکول ها بودند. مقادیر اندازه گیری از سیستم انتظارات بیش از حد توزیع از مکان،جهت و سرعت اتم ها و مولکول ها است. مقاله ای که به جهان معرفی شد به طور باورنکردنی در شبیه سازی الگوریتم متروپلیس مفید بود. در  واقع این الگوریتم بیشترین تاثیر را در توسعه علوم و مهندسی داشته است. الگوریتم متروپلیس قلب بیشتر روش های نمونه گیری MCMC است. ایده اصلی پشت MCMC ، ساخت زنجیر مارکوف که توزیع پایا (تغییر ناپذیر)  ، توزیع نمونه گیری مورد نظر است.

الگوریتم متروپلیس- هستینگز

الگوریتم متروپلیس- هستینگز با یک چگالی هدف f آغاز می شود و سپس  یک چگالی شرطی(q(Y|X که به آن توزیع پیشنهادی می گویند، متناسب با مسئله مورد نظر انتخاب می شود. (q(Y|X باید طوری انتخاب شود که نمونه گیری از آن ساده باشد. چگالی انتقال مارکوف چگونگی رفتن از وضعیت x  به y را توصیف می کند. مشابه روش قبول- رد ، الگوریتم متروپلیس مبنای استراتژی "آزمون و خطا" است. 

برای نمونه از یک چگالی (f(x به یک ثابت نرمال شناخته شده ، مقدار دهی اولیه به برخی از X0 برای f(X0)>0 . سپس برای هر  t=0,1,2,….,T-1   مراحل زیر را اجرا می کنیم.

1- با توجه به وضعیت فعلی Xt ،   را تولید کنید.

2-  تولید کنید وتابع زیر ارائه کنید.

وقتیکه

احتمال  ، احتمال پذیرش نامیده می شود. 

برای اجرای این الگوریتم ، بعد از تولید یک نقطه کاندیدای y از توزیع پیشنهادی، عدد تصادفی U را از توزیع یکنواخت (0,1) تولید می کنیم. اگر  آنگاه Y را به عنوان وضعیت جدید زنجیر می پذیریم و قرار می دهیم Xt+1=Y در غیر اینصورت Xt+1=Xt .

مهمترین بحث در الگوریتم متروپلیس-هستینگز ، انتخاب توزیع پیشنهادی است. هرچند که هر توزیع پیشنهادی در نهایت نمونه هایی از توزیع هدف f تولید خواهد کرد، ولی سرعت همگرایی و تعداد تکرارهای لازم برای رسیدن به همگرایی به انتخاب توزیع پیشنهادی بستگی دارد.

الگوریتم متروپلیس

از نظر تاریخی ابتدا الگوریتم متروپلیس ارائه شد و سپس به الگوریتم متروپلیس-هستینگز تعمیم یافت، ولی همانطور  که خواهیم دید الگوریتم متروپلیس یک حالت خاص از الگوریتم متروپلیس-هستینگز می باشد. در الگوریتم متروپلیس توزیع های پیشنهادی متقارن را در نظر می گیریم  که دارای شکل (q(Y|X)=q(X|Y برای همه X ها و Y ها هستند. مراحل این الگوریتم نیز مشابه الگوریتم متروپلیس- هستینگز است.

منابع:

 کتاب شبیه سازی آماری دکتر صادق رضایی و رسول طهماسبی

 کتاب Explorations in Monte Carlo Methods 

کتاب  Handbook of Monte Carlo Methods : دانلود

نوشته شده در ۱۳٩٢/۳/٢۳ساعت ٢:٢٥ ‎ب.ظ توسط فاطمه متولیان نظرات () |

الگوریتم برای تولید اعداد تصادفی از یک توزیع احتمال مثل (f(x به وسیله تولید اعداد تصادفی از برخی از توزیع احتمال دیگر مثل (g(x ، وقتیکه برای f و g نسبت روبه رو برقرار باشد   برای همه x ها  ، با ثابت k ، الگوریتم به شرح زیر کار می کند:

-   r را یک عدد تصادفی از (g(x بگیرید.

-   s را یک عدد تصادفی از یک توزیع یکنواخت در بازه (0,1) بگیرید .

-  (c=ksg(r محاسبه کنید.

-  اگر (c>f(r باشد، r را رد کرده و به مرحله اول بر می گردیم ، اگر  باشد r را به عنوان یک عدد تصادفی f قبول می کنیم.

منابع:

کتاب Dictionary of Statistics

نوشته شده در ۱۳٩٢/۳/٢۳ساعت ۱:٤٠ ‎ب.ظ توسط فاطمه متولیان نظرات () |

قدم زدن تصادفی

درحالیکه زنجیر مارکوف می تواند به عنوان یک قدم زدن تصادفی در نظر گرفته شود ، یک قدم زدن تصادفی همیشه  یک نمونه از زنجیر مارکوف نیست. برای مثال ، گام بعدی قدم زدن تصادفی می تواند به کل تاریخ قدم زدن تا آن زمان بستگی داشته باشد . این مورد" خود- گریز" قدم زدن است ، که دارای برنامه های کاربردی در مطالعه درشت مولکول ها است. قدم زدن تصادفی در حرکت ذرات در برخورد (مثل حرکت براونی)، در مسئله قمارباز(شانس یا بد شانسی قمارباز) ، و در مدل های ریاضی در امور مالی (مانند قیمت گذاری معامله ها) به کار می رود.

 

انتشار  (Diffusion)

 در سال 1828 ، گیاه شناس  معروف رابرت براون مقاله ای با عنوان ،" محاسبه مختصری از مشاهدات میکروسکوپی ذرات موجود در دانه گرده گیاهان" چاپ کرد. او از طریق میکروسکوپ مشاهده کرده بود ، دانه های گرده در آب ایستاده اند و با دیدن اینکه آنها ثابت و نامنظم قرار گرفتند شگفت زده شد. ما حالا می دانیم که دانه تحت تاثیر دیده نشده از برخوردشان با مولکول های آب حرکت می کند. خود مولکول های آب  تحت حرکت نامنظم ثابتی به علت برخورد با یکدیگر هستند. میانگین سرعت آن ها، و در نتیجه انرژی جنبشی آنها ، با دما افزایش می یابد. انرژی از طریق متوسط این برخوردها تکثیر می شود.

 مولکول آب همچنین  از یک مکان به مکان دیگر با میانگین نتیجه برخوردها حرکت می کند. دانه های گرده این کار را آهسته تر انجام می دهند. این نوع انتقال انتشار نامیده می شود..

 قدم زدن تصادفی روی شبکه اعداد تصادفی روی  خط واقعی  با یک ذره را در نظر بگیرید.

 ذره از مبدا شروع می کند و با احتمال p   یک گام به راست می رود و با احتمال q=1-p یک گام به چپ می رود. اگرp=q=1/2 باشد ، انتخاب می تواند به وسیله ضربه خوب به یک سکه انتخاب شود. شکل زیر هیستوگرام نقطه انتهایی 200000 قدم زدن تصادفی  هر 30 مرحله را نشان می دهد:

همانطورکه با قضیه حد مرکزی انتظار می رود  ، هیستوگرام نزدیک توزیع نرمال است. با افزایش تعداد مراحل و کوچک کردن آن ها می توانیم معادله انتشار یک- بعدی را به دست آوریم.

 کد اجرایی متلب

 

 

 

انتشار به عنوان حد قدم زدن تصادفی

برای سادگی ، در نظربگیرید زمان  به دوره های جدا از هم تقسیم شده است و درهر چنین دوره ای یک ذره به طور تصادفی در طول خط حرکت می کند ، یک گام  به راست با احتمال p یا یک گام  به چپ با احتمال q=1-p می رود. بعد از مدت زمان n ذره درجایی دیگر در بازه از  به  نسبت به نقطه شروع آن قرار می گیرد. مبدا را0  بگیرید.

(P(m,n احتمال اینکه ذره به  تغییر وضعیت می دهد را نشان می دهد. ، m گام راست از مبدا، بعد از مدت زمان n ،  است . ما میخواهیم (p(m,n را حساب کنیم. آن می خواهد به تشخیص قدم زدن تصادفی با nگام کمک کند یک چیزی مثل پرتاب n سکه  سنگین. برای هر سکه که رو می آید ما یک قدم  به راست بر می داریم و برای هر سکه که پشت می آید یک قدم به چپ بر می داریم. فرض کنید r  تعداد گام هایی که به راست می رویم  و l تعداد گام هایی که به چپ می رویم است.

سپس در موقعیت  باید اختلاف آنها m باشد، m=r-l وقتیکه n=r+lاست. بنابراین r می تواند با جمع m و n معین شود و l با تفاضل آن ها،

مثل آزمایش پرتاب یک تاس ، تعداد راه های انتخاب r  که به راست حرکت می کند از n  برابر است با:

اگر q احتمال رفتن به راست و p احتمال رفتن به چپ باشد،پس

 

رابطه بالا توزیع دو جمله ای است . اگر آزمایش قدم زدن تصادفی با n=100 مرحله به تعداد زیاد انجام شود، سپس هیستوگرام نتایج وضعیت ذره تقریبا نزدیک توزیع نرمال است(به وسیله قضیه حد مرکزی). 

منابع:

کتاب Explorations in Monte Carlo Methods

نوشته شده در ۱۳٩٢/۳/٢۳ساعت ۱:۳۳ ‎ب.ظ توسط فاطمه متولیان نظرات () |

قدم زدن تصادفی روی گراف

زنجیر مارکوف می تواند توسط یک نوع گراف به شرح زیر نشان داده شود.

یال مستقیم توسعه یافته از یک راس مثل x  به راس دیگری مثل y ، اگر یک تغییر حالت از x به y در یک تکرار ممکن باشد. مجموعه همه وضعیت هایی که می تواند از x در یک تکرار برسد "همسایگی" x است، توسط Nxنشان داده شده است. هر چنین یال مستقیمی یک احتمال pxy همراه آن است. این احتمال یالی است که می خواهد در تکرار بعدی انتخاب شود وقتیکه زنجیر در حال حاضر در وضعیت x است.

شکل زیر نمایش گراف چهار وضعیت یک زنجیر مارکوف و ماتریس آن است.

زنجیر در بعضی از وضعیت ها شروع می شود، مثلا X0 ، که ممکن است به صورت تصادفی با توجه به توزیع نقطه شروع انتخاب شود.و ار آنجا به بعد رنجیر از وضعیتی به وضعیت دیگر با توجه به همسایگی های موجود حرکت می کند.

با توجه به اینکه زنجیر در برخی تکرارها در وضعیت X است، وضعیت بعدی  مطابق با چگالی گسسته داده شده توسط انتخاب می شود . 

توجه کنید که مجموع احتمالات خروجی از هر راس x باید 1 باشد .

 

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

برای مثال ، مدل فرضی زیر را برای بازار سهام در نظر بگیرید: نسبت به دیروز،نواسانات امروز در بازار را می توان بالا،پایین یا بدون تغییر  در نظر گرفت که به شرح زیر است:

-  اگر دیروز بالا بود، پس احتمال برای امروز: بالا 0.3 ،بدون تغییر 0.2 ، پایین 0.5 است.

- اگر دیروز بدون تغییر بود، پس احتمال برای امروز: بالا 0.4 ، بدون تغییر 0.2 ،پایین 0.4 است.

- اگر دیروز پایین بود، پس احتمال برای امروز: بالا 0.4 ،بدون تغییر  0.3 ، پایین 0.3 است.

شبیه سازی یک زنجیر کوچک

برای شبیه سازی زنجیر بازار سهام، اول تصمیم به شروع یک وضعیت می گیریم. ما می توانیم به  طور تصادفی انتخاب کنیم یا برخی از حالت های معین را فرض کنیم. برای مثال  می گوییم که دیروز"بالا" بود و ما می خواهیم بازار امروز را شبیه سازی کنیم. برای انجام این کار در بین موارد بالا  احتمال بالا 0.3 ،بدون تغییر 0.2 ، پایین 0.5  را انتخاب می کنیم. برای این کار ممکن است از روش CDF استفاده کنیم. 

برای CDFوارون نقاط انفصال تجمعی 0.3 ، 0.5 و 1 هستند ،که یک آزمایش برای   می سازد.

اگر U<0.3 ما در وضعیت "بالا" می مانیم اگر  باشد به وضعیت "بدون تغییر" حرکت می کنیم. و اگر  باشد به وضعیت" پایین" حرکت می کنیم. برای انجام این کار در نرم افزار ، نرم افزار برای ساختن توزیع تجمعی ماتریس C برای زنجیر با استفاده از ردیف های ماتریس مفید است:


سپس حلقه شبیه سازی به صورت زیر است:

اجرای الگوریتم بالا از یک نمونه زنجیر خبر می دهد ، یعنی  دنباله وضعیت های Xt ،  ،به عنوان نتیجه اعداد تصادفی که انتخاب کردیم رخ داده است.

متناوبا، می توانیم هیستوگرام را اجرا کنیم. در این راه ما کسر زمانی که زنجیر در هر وضعیت صرف می کند را به دست می آوریم.

اگر دوباره هیستوگرام بعد از هر تکرار t رسم شود، خواهیم دید که ابتدا نمودار تغییر قابل ملاحضه ای می کند اما در نهایت  تقریبا ثابت می شود. این نشان می دهد که یکی از خواص اساسی یک زنجیر مارکوف منظم، وجود یک توزیع ناوردا است. در بیشتر موارد  نمونه خاص یک زنجیر  مورد نظر ما نیست، نسبتا نمونه های عمومی آن مورد نظر ما است،به عبارت دیگر خواصی که در همه نمونه ها صدق می کند مورد بررسی ما قرار میگیرد.

 

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

در مدل بازار،اگر ما این فرکانس ها را بدانیم ، ما می دانیم  که آیا  وضعیت"بالا" بیش تر رخ می دهد یا "پایین" و می توانیم رانش بازار را پیش بینی کنیم.

در بیش تر قسمت ها ما نمونه های خاص زنجیر را در نظر  نمی گیریم ، بلکه نمونه های عمومی آن ( خواص قابل قبول همه نمونه ها) را در نظر داریم.

فرض کنید ما زنجیر بازار سهام را در وضعیت "بالا" شروع می کنیم و دقیقا یک بار تکرار می کنیم که نمونه متغیر تصادفی X1 است.

 اگر این کار را چندین بار انجام دهیم و هیستوگرام نتیجه ، هیستوگرام توزیع X1است.  اگر بتوانیم این کار را بی نهایت بار انجام دهیم ، هیستوگرام "بالا" را 0.3 ،"بدون تغییر" را 0.2 و "پایین" را 0.5  نشان می دهد چون این احتمال انتقال وضعیت "بالا" است، بنابراین مطابق نمونه هایی که قبلا ذکر کردم خواهد بود.

به طور مشابه، ما می توانیم همه این ها را برای X برای هر t>0 انجام دهیم.

مهمترین ابزار در فهم زنجیر مارکوف ، بردار احتمال وضعیت ؛ یا به طور خلاصه ؛ بردار احتمال pt است که احتمال توزیع Xt است.

درک رفتار pt یک هدف اصلی درک زنجیر مارکوف است، به طور خاص، رفتار بلند مدت pt مورد نظر است. به طور قراردادی فرض می کنیم pt یک بردار ردیف باشد. اگر X0 را متغیر تصادفی برای شروع وضعیت نشان دهیم، پس p0 توزیع شروع است.برای مثال آن می تواند  باشد ، که به معنی شروع قطعی در وضعیت "بالا " است.

نمایش ماتریس زنجیر

زنجیر مارکوف می تواند به وسیله ماتریس (P=(pxy با احتمال pxy در انتقال از وضعیت x به y در یک تکرار زنجیره ای معرفی شود که ماتریس انتقال احتمال یا به طور خلاصه ماتریس انتقال نامیده می شود. مجموع درایه های هر سطر ماتریس P (با توجه به رابطه قبل) باید 1 باشد. Pt بردار احتمال متغیر تصادفی Xt بگیرید. سپس ما می توانیم pt+1 را به صورت زیر محاسبه کنیم.

برای مثال، ماتریس انتقال بازار سهام به صورت زیر در نظر بگیرید.

با شروع زنجیر در وضعیت "بالا" ، p1 به صورت زیر محاسبه می شود:

و به همین ترتیب برای هر مقدار t ادامه دهید به وسیله رابطه بازگشتی روشن است که pt=p0Pt است.

در ادامه با مثال بالا ، چند توزیع بعدی pt به صورت زیر است.

توجه دارید که چگونه توزیع ها به مقدار ثابت میل می کند ،توزیع ناوردا.

توزیع ناوردا

در زنجیر مارکوف منظم ، بردار احتمال pt به توزیع ناوردا(پایا)  میل می کند. به این دلیل  به این توزیع ، توزیع ناوردا می گوییم که  است.

شرایطی که P برای منظم بودن باید داشته باشد:

1- ساده نشدنی: یعنی در نمایش ماتریس یک پیشروی مسیر مستقیم از هر راس به هر راس دیگر وجود دارد.(همه وضعیت ها در دسترس باشد)

2- نادوره ای: به این معنی که هیچ عدد صحیح d>1 وجود ندارد به طوری که  تعداد تکرار ها بین بازگشت از هر وضعیت به خودش  مضربی از d باشد ، برای مثال شکل زیر یک زنجیر دوره ای است.

اولین شرط یک نوع شرط آمیختگی روی زنجیراست ، که اشاره می کند که تنها منطقه ناوردا کل فضای وضعیت است.

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

اگر شرط دوم نقض شود (مثل شکل زیر)، پس pt نوسان خواهد کرد و همگرا نمی شود.

در مثال بازار سهام بالا ، حل مسئله با معادله  برای پیدا کردن

سخت نیست.

شکل بالا یک زنجیر دوره ای با دوره d=2 است. برای هر وضعیت x ، تعداد تکرارها بین بازگشت به x مضربی از 2 است.

منابع:

کتاب  Explorations in Monte Carlo Methods

نوشته شده در ۱۳٩٢/۳/٢٢ساعت ۱۱:۱۱ ‎ب.ظ توسط فاطمه متولیان نظرات () |

Design By : nightSelect.com