فرآیندهای مارکوفی

یک فرآیند تصادفی مارکوفی نامیده می شود (از نام ریاضیدان روسی آندری آندریویچ مارکوف) اگر در هر زمانی احتمال شرطی یک رویداد آینده دلخواه با توجه به کل گذشته فرآیند - یعنی X (s) برای همه s ≤ t - برابر باشد. احتمال مشروط آن رویداد آینده فقط X (t) را داده است. بنابراین، به منظور اظهارنظر احتمالی در مورد رفتار آینده یک فرآیند مارکوف، دانستن کل تاریخچه فرآیند مفیدتر از دانستن وضعیت فعلی آن نیست. توزیع شرطی X (t + h) با داده X (t) احتمال انتقال فرآیند نامیده می شود. اگر این توزیع شرطی به t بستگی نداشته باشد، گفته می شود که فرآیند دارای احتمالات انتقال "ایستا" است. یک فرآیند مارکوف با احتمالات انتقال ثابت ممکن است به مفهوم پاراگراف قبل یک فرآیند ثابت باشد یا نباشد. اگر Y₁، ی₂،… متغیرهای تصادفی مستقل هستند و X (t) = Y₁+⋯+ Y_تی، فرآیند تصادفی X (t) یک فرآیند مارکوف است. با توجه به X (t) = x، احتمال شرطی که X (t + h) متعلق به یک بازه (a, b) است فقط احتمال این است که Y_{t + 1}+⋯+ Y_{t + h}متعلق به بازه ترجمه شده (a - x، b - x) است. و به دلیل استقلال، اگر مقادیر X (1)،...، X (t - 1) نیز داده شوند، این احتمال شرطی یکسان خواهد بود. اگر Y ها به طور یکسان و همچنین مستقل توزیع شوند، این احتمال انتقال به t بستگی ندارد، و سپس X (t) یک فرآیند مارکوف با احتمالات انتقال ثابت است. گاهی اوقات X ( t ) یک راه رفتن تصادفی نامیده می شود، اما این اصطلاح کاملاً استاندارد نیست. از آنجایی که هر دو فرآیند پواسون و حرکت براونی از راه رفتن تصادفی توسط فرآیندهای محدود کننده ساده ایجاد می شوند، آنها نیز فرآیندهای مارکوف با احتمالات انتقال ثابت هستند. فرآیند Ostein-Uhlenbeck که به عنوان راه حل (19) برای معادله دیفرانسیل تصادفی (18) تعریف شده است نیز یک فرآیند مارکوف با احتمالات انتقال ثابت است.

فرآیند Ostein-Uhlenbeck و بسیاری از فرآیندهای مارکوف دیگر با احتمالات انتقال ثابت مانند فرآیندهای ثابت به صورت t → ∞ رفتار می کنند. به طور کلی، توزیع شرطی X (t) با داده X (0) = x به صورت t → ∞ به توزیعی که توزیع ثابت نامیده می شود، همگرا می شود که به مقدار شروع X (0) = x بستگی ندارد. علاوه بر این، با احتمال 1، نسبت زمانی که فرآیند در هر زیر مجموعه ای از فضای حالت خود صرف می کند، به احتمال ثابت آن مجموعه همگرا می شود. و اگر X (0) برای شروع توزیع ثابت داده شود، فرآیند تبدیل به یک فرآیند ثابت می شود. فرآیند Ostein-Uhlenbeck تعریف شده در رابطه (19) ساکن است اگر V (0) دارای توزیع نرمال با میانگین 0 و واریانس σ2 / (2 m f ) باشد.

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

مدل انتشار Ehrenfest

The Ehrenfest model of diffusion (named after the Austrian Dutch physicist Paul Ehrenfest) was proposed in the early 1900s in order to illuminate the statistical interpretation of the second law of thermodynamics, that the entropy of a closed system can only increase. Suppose N molecules of a gas are in a rectangular container divided into two equal parts by a permeable membrane. The state of the system at time t is X ( t ), the number of molecules on the left-hand side of the membrane. At each time t = 1, 2,… a molecule is chosen at random (i.e., each molecule has probability 1/ N to be chosen) and is moved from its present location to the other side of the membrane. Hence, the system evolves according to the transition probability p ( i , j ) = P X ( t + 1) = j | X ( t ) = i>، جایی که

رفتار بلندمدت فرآیند ارنفست را می توان از قضایای کلی در مورد فرآیندهای مارکوف در زمان گسسته با فضای حالت گسسته و احتمالات انتقال ثابت استنتاج کرد. فرض کنید T (j) اولین بار t ≥ 1 را نشان دهد به طوری که X (t) = j و T (j) = ∞ را اگر X (t) ≠ j برای همه t تنظیم کنید. فرض کنید که برای همه حالت های i و j ممکن است فرآیند از i به j در چند مرحله برود - یعنی P T (j)<∞| X (0) = i>> 0. If the equations have a solution Q ( j ) that is a probability distribution—i.e., Q ( j ) ≥ 0, and Σ Q ( j ) = 1—then that solution is unique and is the stationary distribution of the process. Moreover, Q ( j ) = 1/ E T ( j )| X (0) = j>; و برای هر حالت اولیه j، نسبت زمان t که X (t) = i با احتمال 1 به Q (i) همگرا می شود.

برای مورد خاص فرآیند ارنفست، فرض کنید که N بزرگ است و X (0) = 0. با توجه به پیش بینی قطعی قانون دوم ترمودینامیک، آنتروپی این سیستم فقط می تواند افزایش یابد، به این معنی که X (t )به طور پیوسته افزایش می یابد تا زمانی که نیمی از مولکول ها در هر طرف غشاء قرار گیرند. در واقع، با توجه به مدل تصادفی شرح داده شده در بالا، احتمال زیادی وجود دارد که X (t) در ابتدا افزایش می یابد. با این حال، به دلیل نوسانات تصادفی، سیستم گاهی اوقات از پیکربندی هایی که دارای آنتروپی بزرگ هستند به پیکربندی هایی با آنتروپی کوچکتر حرکت می کند و در نهایت بر خلاف قانون دوم ترمودینامیک، حتی به حالت اولیه خود باز می گردد.

وضوح پذیرفته شده این تضاد این است که مدت زمانی که چنین سیستمی باید کار کند به منظور کاهش قابل مشاهده در آنتروپی ممکن است به حدی طولانی باشد که کاهش هرگز به صورت تجربی تأیید نشود. برای در نظر گرفتن تنها شدیدترین مورد ، اجازه دهید اولین بار t ≥ 1 را که در آن x (t) = 0-یعنی. ، زمان بازگشت اول به پیکربندی شروع با تمام مولکول ها در سمت راست غشای را نشان می دهد. می توان با تعویض در معادله (20) تأیید کرد که توزیع ثابت مدل Ehrenfest توزیع دوتایی و از این رو E (T) = 2 N است. به عنوان مثال ، اگر N فقط 100 باشد و انتقال با نرخ 10 6 در ثانیه اتفاق می افتد ، E (T) به ترتیب 10 15 سال است. از این رو ، در مقیاس ماکروسکوپی ، که در آن می توان اندازه گیری های تجربی را انجام داد ، قانون دوم ترمودینامیک را در خود جای داده است.

پیاده روی تصادفی متقارن

یک فرآیند مارکوف که به روشهای کاملاً متفاوت و غافلگیرکننده رفتار می کند ، پیاده روی تصادفی متقارن است. یک ذره یک نقطه با مختصات عدد صحیح را در فضای اقلیدسی D- بعدی اشغال می کند. در هر زمان t = 1 ، 2 ،… از محل فعلی خود به یکی از نزدیکترین همسایگان خود با احتمالات برابر 1/(2 د) ، مستقل از حرکات گذشته خود حرکت می کند. برای d = 1 این مربوط به حرکت یک قدم به راست یا چپ با توجه به نتیجه پرتاب یک سکه عادلانه است. ممکن است نشان داده شود که برای d = 1 یا 2 ذرات با احتمال 1 به موقعیت اولیه خود و از این رو به هر موقعیت ممکن بی نهایت بارها و بارها باز می گردد ، اگر پیاده روی تصادفی به طور نامحدود ادامه یابد. در سه یا چند بعد ، در هر زمان تعداد مراحل احتمالی که باعث افزایش فاصله ذرات از مبدا می شود بسیار بزرگتر از تعداد کاهش فاصله است ، با این نتیجه که ذرات در نهایت از مبدا دور می شود و هرگز برنگرددبشرحتی در یک یا دو بعد ، اگرچه ذرات در نهایت به موقعیت اولیه خود باز می گردد ، زمان انتظار انتظار می رود تا زمانی که بازده بی نهایت باشد ، توزیع ثابت وجود ندارد و نسبت زمان ذرات در هر حالت به 0 می رسد!

مدلهای صف

ساده ترین سیستم خدمات یک صف تک سرور است که در آن مشتریان می رسند ، منتظر نوبت خود هستند ، توسط یک سرور واحد سرو می شوند و عزیمت می کنند. فرآیندهای تصادفی مرتبط ، زمان انتظار مشتری N و تعداد مشتریان در صف در زمان t است. به عنوان مثال ، فرض کنید که مشتریان در بعضی مواقع 0 = T وارد می شوند₀ 1 2حرفهای_حرفزمان خدمات مورد نیاز مشتری N ، n = 0 ، 1 ، 2 ،… را مشخص کنید و شما را تنظیم کنید_حرف= t_حرف- t_{n - 1}بشرزمان انتظار ، w_حرف، از مشتری n ، رابطه w را برآورده می کند₀= 0 و ، برای n ≥ 1 ، w_حرف= حداکثر (0 ، W_{n - 1}+ v_{n - 1}- تو_حرف). برای دیدن این موضوع ، مشاهده کنید که مشتری n باید به همان مدت زمان 10 (n - 1) مشتری به علاوه زمان خدمات (n - 1) مشتری منهای زمان بین زمان ورود (n (n) منتظر بماند (n - 1)- 1) مشتری TH و N ، که در طی آن مشتری (N - 1) در حال حاضر منتظر است اما مشتری Nth نیست. اگر این مقدار منفی باشد ، یک استثنا اتفاق می افتد و سپس زمان انتظار مشتری N 0 است. فرضیات مختلفی را می توان در مورد مکانیسم های ورودی و خدمات انجام داد. یک احتمال این است که مشتریان طبق یک فرآیند پواسون وارد می شوند و زمان خدمات آنها متغیرهای تصادفی مستقل و یکسان توزیع شده است که همچنین مستقل از فرآیند ورود هستند. سپس ، از نظر y_حرف= v_{n - 1}- تو_حرف، که متغیرهای تصادفی مستقل ، یکسان توزیع شده هستند ، رابطه بازگشتی تعریف W_حرفW می شود_حرف= حداکثر (0 ، W_{n - 1}+ y_حرف). این فرآیند یک فرایند مارکوف است. این اغلب به یک پیاده روی تصادفی با سد بازتابنده در 0 گفته می شود ، زیرا هر زمان که مثبت باشد مانند یک پیاده روی تصادفی رفتار می کند و هر زمان که سعی کند منفی شود ، برابر با 0 باشد. مقادیر مورد علاقه میانگین و واریانس زمان انتظار مشتری N است و از آنجا که تعیین دقیق این موارد بسیار دشوار است ، میانگین و واریانس توزیع ثابت. مدل های صف واقع گرایانه تر سعی می کنند سیستم هایی را با چندین سرور و کلاس های مختلف مشتری که مطابق با اولویت های خاص ارائه می شوند ، در خود جای دهد. در بیشتر موارد ، تجزیه و تحلیل ریاضی از سیستم غیرممکن است ، که برای به دست آوردن نتایج عددی باید بر روی رایانه شبیه سازی شود. بینش های به دست آمده از تجزیه و تحلیل نظری موارد ساده می تواند در انجام این شبیه سازی ها مفید باشد. تئوری صف در تلاش برای درک ترافیک در سیستم های تلفنی ریشه های خود را داشت. تحقیقات امروزی ، از جمله موارد دیگر ، با مشکلات مرتبط با سیستم های رایانه ای چند کاربر تحریک می شود.

منعکس کننده موانع در سایر مشکلات نیز بوجود می آید. به عنوان مثال ، اگر b (t) حرکتی براون را نشان دهد ، سپس x (t) = b (t) + c t حرکت براون را با رانش c نامیده می شود. این مدل برای حرکت قهوه ای یک ذره تحت تأثیر یک میدان نیروی ثابت مانند گرانش مناسب است. می توان یک سد بازتابنده را در 0 اضافه کرد تا بازتاب ذرات براونی را از پایین ظرف خود به حساب آورد. نتیجه الگویی برای رسوب است ، که برای c<0 in the steady state as t → ∞ gives a statistical derivation of the law of pressure as a function of depth in an isothermal atmosphere. Just as ordinary Brownian motion can be obtained as the limit of a rescaled random walk as the number of steps becomes very large and the size of individual steps small, Brownian motion with a reflecting barrier at 0 can be obtained as the limit of a rescaled random walk with reflection at 0. In this way, Brownian motion with a reflecting barrier plays a role in the analysis of queuing systems. In fact, in mode probability theory one of the most important uses of Brownian motion and other diffusion processes is as approximations to more complicated stochastic processes. The exact mathematical description of these approximations gives remarkable generalizations of the central limit theorem from sequences of random variables to sequences of random functions.

نظریه ریسک بیمه

The ruin problem of insurance risk theory is closely related to the problem of gambler’s ruin described earlier and, rather surprisingly, to the single-server queue as well. Suppose the amount of capital at time t in one portfolio of an insurance company is denoted by X ( t ). Initially X (0) = x> 0. During each unit of time, the portfolio receives an amount c>0 در حق بیمه. در مواقع تصادفی مطالبات علیه شرکت بیمه مطرح می شود ، که باید مبلغ V را بپردازد_حرف>0 برای حل و فصل ادعای n. اگر n (t) تعداد ادعاهای مطرح شده در زمان t را نشان می دهد ، پس مشروط بر اینکه این مقدار در همه زمان های اولیه مثبت بوده استحرف is identically equal to 2 for all n , and (iv) at each time t a claim occurs with probability p or does not occur with probability q independently of what occurs at other times, then the process X ( t ) is the same stochastic process as Peter’s fortune, which is absorbed if it ever reaches the state 0. The probability of Peter’s ultimate ruin against an infinitely rich adversary is easily obtained by taking the limit of equation (6) as m → ∞. The answer is ( q / p ) x if p>q —i. e. ، بازی برای پیتر مطلوب است و اگر p ≤ q. فرضیات جالب تر برای مشکل خطر بیمه این است که تعداد مطالبات n (t) یک فرایند پواسون و اندازه مطالبات v است₁، v₂، ... متغیرهای تصادفی مثبت مستقل ، توزیع شده هستند. جای تعجب آور است که تحت این فرضیات احتمال خراب شدن نهایی به عنوان تابعی از ثروت اولیه دقیقاً همان احتمال ثابت است که زمان انتظار در صف تک سرور با ورودی پواسون از x فراتر می رود. متأسفانه ، هیچ مشکلی برای حل دقیقاً آسان نیست ، اگرچه یک راه حل تقریبی بسیار خوب در ابتدا توسط ریاضیدان سوئدی هارالد کرامر حاصل شده است.

نظریه مارتینگال

به عنوان نمونه نهایی ، به نظر می رسد که یکی از ایده های غالب نظریه احتمال مدرن ذکر شود ، که در عین حال مستقیماً از رابطه احتمال با بازی های شانس به سر می برد. فرض کنید که x₁، ایکس₂، ... هر فرآیند تصادفی است و برای هر n = 0 ، 1 ،… ، f_حرف= f_حرف( ایکس₁،…، ایکس_حرف) یک تابع (قابل اندازه گیری) از مشاهدات نشان داده شده است. روند تصادفی جدید f_حرفاگر E (F_حرف|ایکس₁،…، ایکس_{n - 1}) = F_{n - 1} for every value of n>0 و تمام مقادیر x₁،…، ایکس_{n - 1}بشراگر دنباله X S در آزمایشات پی در پی یک بازی شانس و f باشد_حرفآیا ثروت یک قمارباز پس از محاکمه N است ، سپس وضعیت Martingale می گوید که این بازی کاملاً عادلانه است به این معنا که ، مهم نیست که تاریخ گذشته بازی ، ثروت مورد انتظار قمارباز پس از یک آزمایش دیگر دقیقاً برابر استبه ثروت فعلی او. به عنوان مثال ، اجازه دهید x₀= x ، و برای n ≥ 1 اجازه دهید x_حرفبرابر 1 یا 1 −1 مطابق با سکه ای که دارای احتمال p از سرها است و q = 1 - p از دمها سر یا دم را در قسمت N می چرخاند. اجازه دهید s_حرف= x₀+ ⋯+ x_حرفبشرسپس f_حرف= s_حرف- n (p - q) و f_حرف= (q / p) s n martingales هستند. یکی از نتایج اساسی تئوری مارتینگاله این است که ، اگر قمارباز آزاد باشد هر زمان و با استفاده از هر استراتژی ، بازی را ترک کند ، فقط به شرط آنکه این استراتژی آینده را پیش بینی نکند ، بازی منصفانه باقی می ماند. این بدان معنی است که ، اگر N زمان توقف را که استراتژی قمارباز به او می گوید بازی را ترک کند ، نشان می دهد تا ثروت نهایی او F باشد_حرف، سپس

به طور دقیق ، این نتیجه بدون برخی شرایط اضافی که باید برای هر برنامه خاص تأیید شود ، صحیح نیست. برای دیدن اینکه چقدر کارآمد است ، یک بار دیگر مشکل ویرانی قمارباز را در نظر بگیرید و اجازه دهید n اولین ارزش n باشد به گونه ای که s_حرف= 0 یا متر ؛یعنی N نشان دهنده زمان تصادفی است که ابتدا خراب می شود و بازی به پایان می رسد. در مورد P = 1/2 ، استفاده از معادله (21) به Martingale f_حرف= s_حرف، همراه با مشاهده ای که f_حرف= یا 0 یا متر ، برابری x = f را به دست می آورد₀= E (F_حرف|ج₀= x) = m [1 - q (x)] ، که می تواند بلافاصله حل شود تا پاسخ در معادله (6) ارائه شود. برای P ≠ 1/2 ، یکی از Martingale f استفاده می کند_حرف= (q / p) s n و استدلال مشابه برای به دست آوردن آن که معادله اول در (6) به راحتی دنبال می شود. مدت مورد انتظار بازی با یک استدلال مشابه بدست می آید.

یک نتیجه به خصوص زیبا و مهم ، قضیه همگرایی مارتینگاله است ، که دلالت بر این دارد که یک مارتینگاله غیر منفی با احتمال 1 به عنوان n → arore همگرا می شود. این بدان معناست که ، اگر ثروت پی در پی یک قمارباز یک مارتینگیل (غیر منفی) را تشکیل دهد ، آنها نمی توانند به طور نامحدود به نوسان خود ادامه دهند اما باید به برخی از ارزش های محدود کننده نزدیک شوند.

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