Үзіліссіз уақыт Марков тізбектерінің ықтималдық қасиеттері
Continuous-time Markov chain
Үйкеліс тізбегі (CTMC) теориясы: математикалық қасиеттері, күйлердің өзгеру ықтималдығы, экспоненциалды таралымдар. Математикалық модельдеуге арналған.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Ықтималдық тұжырымдамасы
Үздіксіз уақыт Марков тізбектерінің математикалық қасиеттері
Probability concept
the mathematical properties of continuous time Markov chains
Үздіксіз уақыт Марков тізбегі (CTMC) – бұл үздіксіз стохастикалық процесс, онда әрбір күй үшін процесс экспоненциалды кездейсоқ шамаға сәйкес күйін өзгертеді, содан кейін стохастикалық матрицаның ықтималдықтарымен көрсетілген басқа күйге көшеді. Баламалы тұжырымдама процесті экспоненциалды кездейсоқ шамалар жиынтығының ең кіші мәніне сәйкес күйін өзгертеді, әрбір мүмкін күйге қарай, ағымдағы күймен анықталатын параметрлермен. Үш күйлі CTMC мысалы: процесс күту уақытынан кейін ауысады – экспоненциалды кездейсоқ шама, мұнда i – оның ағымдағы күйі. Әрбір кездейсоқ шама тәуелсіз және осындай , және ауысу кезінде процесс секіру тізбегіне сәйкес қозғалады, бұл дискретті уақыт Марков тізбегі және стохастикалық матрица:
A continuous time Markov chain (CTMC) is a continuous stochastic process in which, for each state, the process will change state according to an exponential random variable and then move to a different state as specified by the probabilities of a stochastic matrix. An equivalent formulation describes the process as changing state according to the least value of a set of exponential random variables, one for each possible state it can move to, with the parameters determined by the current state. An example of a CTMC with three states is as follows: the process makes a transition after the amount of time specified by the holding time—an exponential random variable , where i is its current state. Each random variable is independent and such that , and When a transition is to be made, the process moves according to the jump chain, a discrete time Markov chain with stochastic matrix:
Теңдей, бәсекелес экспоненталардың қасиеті бойынша, бұл CTMC i күйінен басқа күйге өзгеріп отырады, ең кіші екі кездейсоқ шамаға сәйкес, олар тәуелсіз және осындай , мұнда параметрлер Q матрицасымен берілген.
Equivalently, by the property of competing exponentials, this CTMC changes state from state i according to the minimum of two random variables, which are independent and such that for where the parameters are given by the Q matrix
Кез келген диагональдық емес элемент – бұл секіру тізбегінің i күйінен j күйіне қозғалу ықтималдығы, i күйінің күту уақытына бөлінген. Диагональдық элементтер әр қатардың қосындысы 0-ге тең болу үшін таңдалады. CTMC Марков қасиетін қанағаттандырады, оның мінез-құлқы тек оның ағымдағы күйіне ғана байланысты, өткен мінез-құлқына емес, себебі экспоненциалдық үлестірімнің және дискретті уақыт Марков тізбектерінің есте сақтамау қасиетіне ие.
Each non diagonal entry can be computed as the probability that the jump chain moves from state i to state j, divided by the expected holding time of state i. The diagonal entries are chosen so that each row sums to 0. A CTMC satisfies the Markov property, that its behavior depends only on its current state and not on its past behavior, due to the memorylessness of the exponential distribution and of discrete time Markov chains.
Жүгіру тізбегі/ұстақтау уақыты қасиеттері
Біз Марков процесі бастапқы таралуы және жылдамдық матрицасы арқылы анықталады деп айтамыз: -ның траекториялары дерлік нақтылы түрде оңнан үздіксіз, -ның траекторияларын оңнан үздіксіз ету үшін өзгертуге болады, дерлік нақтылы түрде (сарапшыларға ескерту: бұл шарт процестің жарылмайтынын көрсетеді), күй тізбегі бастапқы таралуымен дискретті уақыт Марков тізбегін құрайды (секіру тізбегі қасиеті) және ауысу матрицасы мен ұсталу уақыты қасиеттеріне ие.
We say is Markov with initial distribution and rate matrix to mean: the trajectories of are almost surely right continuous, let be a modification of to have (everywhere) right continuous trajectories, almost surely (note to experts: this condition says is non explosive), the state sequence is a discrete time Markov chain with initial distribution (jump chain property) and transition matrix and (holding time property).
Байланыс кластары
Байланыс кластары, уақытшалық сипат, қайталану және оң және нөлдік қайталану дискретті уақыттық Марков тізбектеріндегідей дәл осылай анықталады.
Communicating classes, transience, recurrence and positive and null recurrence are defined identically as for discrete time Markov chains.
2-ші мысал
Оң жақтағы сурет {1,2,3,4,5,6,7,8,9} күй кеңістігі бар Pac Man-ді модельдеудің дискретті Марков тізбегін сипаттайды. Ойыншы Pac Man-ді лабиринт арқылы басқарады, Pac Dots жейді. Осы уақытта оны арбақтар қуалайды. Қолайлы болу үшін лабиринт шағын 3x3 тор болып, арбақтар көлденең және тік бағытта кездейсоқ қозғалады. 2 және 8 күйлері арасындағы құпия жолды екі бағытта да пайдалануға болады. Ықтималдығы нөлге тең жазбалар келесі ауысу жылдамдығы матрицасынан алынып тасталады:
The image to the right describes a discrete time Markov chain modeling Pac Man with state space {1,2,3,4,5,6,7,8,9}. The player controls Pac Man through a maze, eating pac dots. Meanwhile, he is being hunted by ghosts. For convenience, the maze shall be a small 3x3 grid and the ghosts move randomly in horizontal and vertical directions. A secret passageway between states 2 and 8 can be used in both directions. Entries with probability zero are removed in the following transition rate matrix:
Бұл Марков тізбегі толық байланысты, себебі арбақтар кез келген күйден кез келген күйге шекті уақыт ішінде өте алады. Құпия жолдың болуына байланысты Марков тізбегі сондай-ақ апериодты, себебі арбақтар кез келген күйден кез келген күйге жұп және тақ сан күй өзгерістері арқылы көше алады. Сондықтан, бірегей стационарлық үлестірім бар және оны элементтерінің қосындысы 1-ге тең болуы керек деген шектеумен шешіледі. Бұл сызықтық теңдеудің шешімі: Орталық күй және құпия жолға жақын шекаралық күйлер 2 және 8 ең көп, ал бұрыштық күйлер ең аз талданды.
This Markov chain is irreducible, because the ghosts can fly from every state to every state in a finite amount of time. Due to the secret passageway, the Markov chain is also aperiodic, because the ghosts can move from any state to any state both in an even and in an uneven number of state transitions. Therefore, a unique stationary distribution exists and can be found by solving , subject to the constraint that elements must sum to 1. The solution of this linear equation subject to the constraint is
The central state and the border states 2 and 8 of the adjacent secret passageway are visited most and the corner states are visited least.
Уақытты кері ауыстыру
CTMC Xt үшін уақытпен кері бұрылған процесс Келли леммасы бойынша осы процестің алға бағытталған процесс сияқты стационарлық таралымымен бірдей болады деп анықталады. Егер кері процесс алға бағытталған процесспен сәйкес келсе, тізбек қайтымды деп аталады. Колмогоров критерийіне сәйкес, процесс қайтымды болуы үшін қажетті және жеткілікті жағдай – жабық циклдағы ауысу ықтималдықтарының көбейтіндісі екі бағытта да бірдей болуы керек.
For a CTMC Xt, the time reversed process is defined to be By Kelly's lemma this process has the same stationary distribution as the forward process. A chain is said to be reversible if the reversed process is the same as the forward process. Kolmogorov's criterion states that the necessary and sufficient condition for a process to be reversible is that the product of transition rates around a closed loop must be the same in both directions.