Cele mai simple fluxuri sunt procesele Markov și lanțurile de decizie. Procese stocastice Markov și fluxuri de evenimente. Fluxuri de evenimente Poisson și

Să considerăm un sistem fizic S=(S 1 ,S 2 ,…S n ), care trece de la o stare la alta sub influența unor evenimente aleatoare (apeluri, eșecuri, lovituri). Să ne imaginăm asta ca și cum evenimentele care transferă sistemul de la o stare la alta ar fi un fel de fluxuri de evenimente.

Fie ca sistemul S să fie în starea S i la momentul t și să se poată muta din el în starea S j sub influența unui flux Poisson de evenimente cu intensitatea ij: de îndată ce apare primul eveniment al acestui flux, sistemul trece instantaneu din S i la S j . După cum știm, probabilitatea acestei tranziții într-un interval de timp elementar (elementul de probabilitate de tranziție) este egală, deci rezultă că densitatea probabilității de tranziție ij într-un lanț continuu de Markov nu este altceva decât intensitatea fluxului de evenimente care transferă sistem de-a lungul săgeții corespunzătoare. Dacă toate fluxurile de evenimente care transferă sistemul S de la o stare la alta sunt Poisson, atunci procesul care are loc în sistem va fi Markovian.

Să punem intensitățile fluxurilor Poisson (densitățile probabilităților de tranziție) pe graficul de stare al sistemului lângă săgețile corespunzătoare. Obținem un grafic de stare etichetat. Pe baza ei, se pot scrie ecuațiile Kolmogorov și se pot calcula probabilitățile stărilor.

Exemplu. Sistem tehnic S este format din două noduri I și II, fiecare dintre acestea, independent de celălalt, poate eșua. Fluxul de eșec al primului nod este Poisson cu intensitatea I , al doilea este tot Poisson cu intensitatea II . Fiecare nod imediat după defecțiune începe să fie reparat (recuperat). Fluxul de restaurări (finalizarea reparației nodurilor) pentru ambele noduri este Poisson cu intensitate. Faceți un grafic de stare a sistemului și scrieți ecuația lui Kolmogorov. Stările sistemului: S 11 - ambele noduri sunt operaționale; S 21 - primul nod este reparat, al doilea este reparabil; S 12, S 22.

t=0 p 11 =1 p 21 =p 22 =p 12 =0

p 11 + p 12 + p 21 + p 22 \u003d 1.

Limita probabilităților de stări pentru un lanț continuu de Markov

Să fie un sistem fizic S=(S 1 ,S 2 ,…S n ) în care are loc un proces aleator Markov cu timp continuu (lanț Markov continuu). Să presupunem că ij = const, i.e. toate fluxurile de evenimente sunt simple (Poisson staționar). După ce am scris sistemul de ecuații diferențiale Kolmogorov pentru probabilitățile de stare și integrând aceste ecuații în condiții inițiale date, obținem p 1 (t), p 2 (t),... p n (t), pentru orice t. Să ne punem următoarea întrebare: ce se va întâmpla cu sistemul S la t. Vor tinde funcțiile p i (t) către anumite limite? Aceste limite, dacă există, se numesc probabilități limită ale stărilor. Este posibil să se demonstreze o teoremă: dacă numărul de stări S este finit și se poate trece din fiecare stare (pentru unul sau altul număr de pași) una la alta, atunci probabilitățile limită ale stărilor există și nu depind de starea initiala a sistemului. Să presupunem că condiția stabilită este îndeplinită și există probabilitățile limită (i=1,2,…n), .

Astfel, la t, se stabilește un anumit regim staționar limitator în sistemul S. Sensul acestei probabilități este că nu este nimic mai mult decât timpul relativ mediu pe care sistemul îl petrece într-o anumită stare. Pentru a calcula p i în sistemul de ecuații Kolmogorov care descriu probabilitățile stărilor, este necesar să se stabilească toate părțile din stânga (derivate) egale cu 0. Sistemul de ecuații algebrice liniare rezultate trebuie rezolvat împreună cu ecuația.

Schema morții și a reproducerii

Știm că, cu un grafic de stare etichetat, putem scrie cu ușurință ecuațiile Kolmogorov pentru probabilitățile de stare, precum și să scriem și să rezolvăm ecuații algebrice pentru probabilitățile finale. În unele cazuri, este posibil să se rezolve ultimele ecuații în avans, în formă literală. În special, acest lucru se poate face dacă graficul de stare al sistemului este așa-numita „schemă de moarte și reproducere”.

Graficul de stare pentru schema morții și reproducerii are forma prezentată în Fig. 19.1. Particularitatea acestui grafic este că toate stările sistemului pot fi trase într-un singur lanț, în care fiecare dintre stările de mijloc (S 1 , S 2 , ..., S n-1) este conectată printr-o săgeată directă și inversă. cu fiecare dintre statele vecine -- dreapta și stânga, iar stările extreme (S 0 , S n) - cu un singur stat vecin. Termenul „schemă a morții și a reproducerii” provine din problemele biologice, în care o schimbare a mărimii unei populații este descrisă printr-o astfel de schemă.

Schema morții și reproducerii se găsește foarte des în diverse sarcini de practică, în special - în teorie la coadă, deci este util, odată pentru totdeauna, să găsim probabilitățile de stare finală pentru acesta.

Să presupunem că toate fluxurile de evenimente care transferă sistemul de-a lungul săgeților graficului sunt cele mai simple (pentru concizie, vom numi atât sistemul S, cât și procesul care are loc în el cel mai simplu).

Folosind graficul din Fig. 19.1, compunem și rezolvăm ecuații algebrice pentru probabilitățile finale ale stărilor (existența acestora decurge din faptul că se poate trece de la fiecare stare una la alta, iar numărul de stări este finit). Pentru prima stare S 0 avem:

Pentru a doua stare S 1:

În virtutea (8.1), ultima egalitate se reduce la forma

unde k ia toate valorile de la 0 la n. Deci, probabilitățile finale p 0 , p 1 ,..., p n satisfac ecuațiile

in plus, trebuie sa tinem cont de conditia de normalizare

p 0 + p 1 + p 2 +…+ p n =1 (8.3)

Să rezolvăm acest sistem de ecuații. Din prima ecuație (8.2) exprimăm р 1 prin р 0 .

Din a doua, ținând cont de (8.4), obținem:

din a treia, ținând cont de (8.5),

și, în general, pentru orice k (de la 1 la N):

Să acordăm atenție formulei (8.7). Numătorul conține produsul tuturor intensităților de la săgețile care duc de la stânga la dreapta (de la început până la starea dată S k), iar numitorul este produsul tuturor intensităților de la săgețile care conduc de la dreapta la stânga (de la început până la S k).

Astfel, toate probabilitățile stărilor p 1 , p 2 , …, p n sunt exprimate prin una dintre ele (p 0). Să substituim aceste expresii în condiția de normalizare (8.3). Obținem prin bracketing p 0:

deci obținem expresia pentru p 0 .

(am ridicat paranteza la puterea lui -1 pentru a nu scrie fracții cu două etaje). Toate celelalte probabilități sunt exprimate în termeni de p 0 (vezi formulele (8.4) - (8.7)). Rețineți că coeficienții de la p 0 în fiecare dintre ei nu sunt altceva decât termeni succesivi ai seriei după unitatea din formula (8.8). Deci, când calculăm p 0 , am găsit deja toți acești coeficienți.

Formulele obţinute sunt foarte utile în rezolvarea celor mai simple probleme de teorie a cozilor.

Sarcinile teoriei cozilor de aşteptare. Clasificarea sistemelor de așteptare și principalele lor caracteristici

În studiul operațiunilor, se întâlnește adesea funcționarea unor sisteme specifice numite sisteme de așteptare (QS). Exemple de astfel de sisteme sunt: centrale telefonice, ateliere de reparații, case de bilete, birouri de informații, magazine, coafor, etc. Fiecare CMO este format dintr-un număr de unități de servicii (sau „dispozitive”), pe care le vom numi canale de servicii. Canalele pot fi: linii de comunicare, puncte de lucru, casierii, vânzători, lifturi, mașini etc. QS poate fi monocanal și multicanal.

Orice QS este conceput pentru a deservi un anumit flux de aplicații (sau „cerințe”) care sosesc la un moment dat aleatoriu. Servirea revendicării continuă pentru un timp, în general vorbind, aleatoriu T aproximativ, după care canalul este eliberat și este gata să primească următoarea revendicare. Natura aleatorie a fluxului de cereri și a timpilor de deservire duce la faptul că în anumite perioade de timp se acumulează un număr inutil de mare de cereri la intrarea în QS (fie intră în coadă, fie lasă QS-ul neservit); în alte perioade, QS-ul va funcționa cu subîncărcare sau chiar va sta inactiv.

Un fel de SP apare în QS cu stări discrete și timp continuu; starea QS-ului se modifică brusc în momentele apariției unor evenimente (sau sosirea unei noi solicitări, sau încheierea serviciului, sau momentul în care cererea, obosită de așteptare, iese din coadă). Pentru a oferi sfaturi cu privire la organizare raţională a acestui proces și a face cerințe rezonabile cu privire la QS, este necesar să se studieze SP și să-l descrie matematic. Aceasta este ceea ce face teoria MO.

Subiectul teoriei cozilor de așteptare este construirea de modele matematice care pun în legătură condițiile de funcționare date ale QS (numărul de canale, performanța acestora, regulile de funcționare, natura fluxului de solicitări) cu caracteristicile care ne interesează - performanța. indicatori ai QS, descriind, dintr-un punct de vedere sau altul, capacitatea acestuia de a face față afluxului de cereri. Ca atare indicatori (în funcție de situație și de obiectivele studiului), pot fi utilizate diferite valori, de exemplu: numărul mediu de aplicații deservite de QS pe unitatea de timp; numărul mediu de canale ocupate; numărul mediu de cereri din coadă și timpul mediu de așteptare pentru serviciu; probabilitatea ca numărul de aplicații din coadă să depășească o anumită valoare etc. Domeniul de aplicare al metodelor matematice ale teoriei ML este în continuă extindere și din ce în ce mai mult depășește sarcinile asociate cu „organizațiile de servicii” în sensul literal de cuvantul. Ca un fel de QS pot fi considerate: calculatoare, sisteme de colectare și prelucrare a informațiilor, ateliere de producție automatizate, linii de producție, sisteme de transport, sisteme de apărare aeriană etc.

Analiza matematică a lucrării QS este mult facilitată dacă procesul acestei lucrări este Markov. Pentru aceasta, este suficient ca toate fluxurile de evenimente care transferă sistemul de la stat la stat (fluxuri de cereri, fluxuri de „servicii”) să fie cele mai simple. Dacă această proprietate este încălcată, atunci descrierea matematică a procesului devine mult mai complicată și este posibil să o aducem la formule explicite, analitice doar în cazuri rare. Cu toate acestea, aparatul celei mai simple teorii markoviane a cozii de așteptare poate fi totuși util pentru o descriere aproximativă a operațiunii QS chiar și în cazurile în care fluxurile de evenimente nu sunt cele mai simple. În multe cazuri, pentru a lua o decizie rezonabilă cu privire la organizarea activității QS, nu este deloc necesar să aveți o cunoaștere exactă a tuturor caracteristicilor sale - adesea este suficientă una aproximativă, orientativă. Mai mult, cu cât QS-ul este mai complex, cu cât conține mai multe canale de servicii, cu atât aceste formule aproximative se dovedesc a fi mai precise.

În cercetarea operațională, se întâlnesc adesea sisteme concepute pentru utilizare reutilizabilă în rezolvarea aceluiași tip de probleme. Procesele rezultate sunt numite procese de service, si sistemele sisteme de așteptare (QS). Exemple de astfel de sisteme sunt sistemele telefonice, atelierele de reparații, sistemele informatice, casele de bilete, magazinele, coaforele și altele asemenea.
Fiecare QS este format dintr-un anumit număr de unități de serviciu (instrumente, dispozitive, puncte, stații), pe care le vom numi canale serviciu. Canalele pot fi linii de comunicație, puncte de operare, calculatoare, vânzători etc. În funcție de numărul de canale, QS sunt împărțite în cu un singur canalȘi multicanal.
Aplicațiile ajung de obicei la CMO nu în mod regulat, ci aleatoriu, formând așa-numitul flux aleatoriu de aplicații (cerințe). Solicitările de service, în general, continuă, de asemenea, pentru o perioadă de timp aleatorie. Natura aleatorie a fluxului de aplicații și a timpului de service duce la faptul că QS-ul este încărcat neuniform: în unele perioade de timp se acumulează un număr foarte mare de aplicații (fie stau în coadă, fie lasă QS-ul neservit), în timp ce în alte perioade. perioadele QS funcționează cu o sarcină insuficientă sau este inactiv.
Subiectul teoriei cozilor este construirea de modele matematice care raportează condițiile date de funcționare ale QS (numărul de canale, performanța acestora, natura fluxului de aplicații etc.) cu indicatorii de performanță QS care descriu capacitatea acestuia de a face față fluxului de aplicatii.

La fel de indicatori de performanta Se utilizează QS: media (în continuare, valorile medii sunt înțelese ca așteptări matematice ale variabilelor aleatoare corespunzătoare) numărul de aplicații deservite pe unitatea de timp; numărul mediu de aplicații din coadă; timpul mediu de așteptare pentru serviciu; probabilitatea de refuzare a serviciului fără așteptare; probabilitatea ca numărul de aplicații din coadă să depășească o anumită valoare etc.

QS sunt împărțite în două tipuri principale (clase): CMO cu erori și href="cmo_length.php">CMO cu așteptare (coadă). Într-un QS cu refuzuri, o solicitare care sosește în momentul în care toate canalele sunt ocupate primește un refuz, părăsește QS și nu participă la procesul de servicii ulterioare (de exemplu, o solicitare pentru convorbire telefonicaîn momentul în care toate canalele sunt ocupate, primește un refuz și lasă QS-ul neservit). Într-un QS cu așteptare, o revendicare care ajunge într-un moment în care toate canalele sunt ocupate nu pleacă, ci sta la coadă pentru service.
QS cu așteptări sunt subdivizate în tipuri diferiteîn funcție de modul în care este organizată coada: cu o lungime limitată sau nelimitată la coadă, cu un timp de așteptare limitat etc.
Procesul de lucru al SMO este proces aleatoriu.
Sub proces aleatoriu (probabilistic sau stocastic). se referă la procesul de schimbare a stării unui sistem în timp în conformitate cu legile probabilistice.
Procesul este numit proces cu stări discrete, dacă stările sale posibile S 1 , S 2 , S 3 ... pot fi enumerate în prealabil, iar trecerea sistemului de la stare la stare are loc instantaneu (salt). Procesul este numit proces în timp continuu dacă momentele posibilelor tranziții ale sistemului de la stare la stare nu sunt fixate în prealabil, ci sunt aleatorii.
Procesul de operare QS este un proces aleatoriu cu stări discrete și timp continuu. Aceasta înseamnă că starea QS-ului se modifică brusc în momente aleatorii ale apariției unor evenimente (de exemplu, sosirea unei noi solicitări, încetarea serviciului etc.).
Analiza matematică a lucrării QS este mult simplificată dacă procesul acestei lucrări este Markov. Procesul aleatoriu este numit Markovian sau proces aleatoriu fără consecințe, dacă pentru orice moment de timp t 0 caracteristicile probabilistice ale procesului în viitor depind numai de starea lui la un moment dat t 0 şi nu depind de când şi cum a ajuns sistemul în această stare.

Un exemplu de proces Markov: sistemul S este un contor într-un taxi. Starea sistemului la momentul t este caracterizată de numărul de kilometri (zecimi de kilometri) parcurși de mașină până în acel moment. Fie ca contorul să arate S 0 în momentul t 0 . Probabilitatea ca în momentul t > t 0 contorul să arate unul sau altul număr de kilometri (mai precis, numărul corespunzător de ruble) S 1 depinde de S 0 , dar nu depinde de momentul la care citirile contorului s-au schimbat înainte de momentul t 0 .
Multe procese pot fi considerate aproximativ markoviane. De exemplu, procesul de a juca șah; sistemul S - grup de piese de șah. Starea sistemului este caracterizată de numărul de piese ale adversarului rămase pe tablă în momentul t 0 . Probabilitatea ca în momentul t > t 0 avantajul material să fie de partea unuia dintre adversari depinde în primul rând de starea sistemului la momentul t 0 , și nu de când și în ce ordine au dispărut piesele din bord până în momentul t 0 .
În unele cazuri, preistoria proceselor luate în considerare poate fi pur și simplu neglijată și modelele Markov pot fi folosite pentru a le studia.
Când se analizează procese aleatorii cu stări discrete, este convenabil să se folosească o schemă geometrică - așa-numita grafic de stare. De obicei, stările sistemului sunt reprezentate prin dreptunghiuri (cercuri), iar posibilele tranziții de la stare la stare sunt reprezentate de săgeți (arce orientate) care leagă stările.
Sarcina 1 . Construiți un grafic al stărilor următorului proces aleatoriu: dispozitivul S este format din două noduri, fiecare dintre ele putând defecta la un moment aleator de timp, după care repararea nodului începe imediat, continuând pentru un timp aleatoriu necunoscut anterior.

Soluţie. Stări posibile ale sistemului: S 0 - ambele noduri sunt operaționale; S 1 - primul nod este reparat, al doilea este reparabil; S 2 - al doilea nod este în curs de reparare, primul este în funcțiune; S 3 - ambele noduri sunt în curs de reparare. Graficul sistemului este prezentat în Fig.1.
Orez. unu
O săgeată direcționată, de exemplu, de la S 0 la S 1 înseamnă tranziția sistemului în momentul defectării primului nod, de la S 1 la S 0 - tranziția în momentul în care repararea acestui nod este finalizată.
Nu există săgeți pe grafic de la S 0 la S 3 și de la S 1 la S 2 . Acest lucru se explică prin faptul că defecțiunile nodurilor se presupune că sunt independente unele de altele și, de exemplu, probabilitatea defecțiunii simultane a două noduri (tranziția de la S 0 la S 3) sau finalizarea simultană a reparațiilor a două noduri (tranziția de la S 0 la S 3). S 3 la S 0) pot fi neglijate.

Flux de evenimente

Pentru descriere matematică Procesul stocastic Markov cu stări discrete și timp continuu, care curge în QS, să facem cunoștință cu una dintre concepte importante teoria probabilității – conceptul de flux al evenimentelor.
Sub fluxul evenimentelor se referă la o secvență de evenimente omogene care urmează unul după altul la un moment dat aleatoriu (de exemplu, un flux de apeluri la o centrală telefonică, un flux de defecțiuni ale computerului, un flux de clienți etc.).
Fluxul este caracterizat intensitatel- frecvența de apariție a evenimentelor sau numărul mediu de evenimente care intră în QS pe unitatea de timp.
Fluxul de evenimente este numit regulat dacă evenimentele urmează unul după altul la anumite intervale de timp egale. De exemplu, fluxul de produse pe o linie de asamblare (la o viteză constantă) este regulat.
Fluxul de evenimente este numit staționar, dacă caracteristicile sale probabilistice nu depind de timp. În special, intensitatea unui flux staționar este o valoare constantă: l(t)=l. De exemplu, fluxul de mașini pe un bulevard oraș nu este staționar în timpul zilei, dar acest flux poate fi considerat staționar în timpul zilei, să zicem, în orele de vârf. Atragem atenția asupra faptului că, în acest din urmă caz, numărul real de mașini care trec pe unitatea de timp (de exemplu, în fiecare minut) poate diferi semnificativ unul de celălalt, dar numărul lor mediu va fi constant și nu va depinde de timp. .
Fluxul de evenimente este numit curge fără efecte secundare, dacă pentru oricare două intervale de timp care nu se intersectează t 1 și t 2 - numărul de evenimente care cad pe unul dintre ele nu depinde de numărul de evenimente care cad pe celelalte. De exemplu, fluxul de pasageri care intră în metrou nu are aproape niciun efect secundar. Și, să zicem, fluxul de clienți care părăsesc ghișeul cu achizițiile lor are deja un efect secundar (fie și doar pentru că intervalul de timp dintre clienții individuali nu poate fi mai mic decât timpul minim de service pentru fiecare dintre aceștia).
Fluxul de evenimente este numit comun, dacă probabilitatea de a atinge un interval de timp mic (elementar) Dt a două sau mai multe evenimente este neglijabil de mică în comparație cu probabilitatea de a atinge un eveniment. Cu alte cuvinte, un flux de evenimente este obișnuit dacă evenimentele apar în el unul câte unul, și nu în grupuri. De exemplu, fluxul de trenuri care se apropie de gară este obișnuit, dar fluxul de vagoane nu este obișnuit.
Fluxul de evenimente este numit cel mai simplu ( sau Poisson staționar) dacă este în același timp staționar, obișnuit și nu are efecte secundare. Denumirea „cel mai simplu” se explică prin faptul că QS cu cele mai simple fluxuri are cea mai simplă descriere matematică. Rețineți că un flux obișnuit nu este cel mai „simplu”, deoarece are un efect secundar: momentele de apariție a evenimentelor într-un astfel de flux sunt fixate rigid.
Cel mai simplu flux ca flux limită apare în teoria proceselor aleatoare la fel de natural ca în teoria probabilităților, se obține o distribuție normală ca limită pentru o sumă de variabile aleatoare: la impunerea (suprapunerea) a unui număr n suficient de mare de fluxuri independente, staţionare şi obişnuite (comparabile între ele ca intensităţi l 1 (i=1,2, ..., n) se obține un flux care este aproape de cel mai simplu cu intensitate eu egală cu suma intensităților fluxurilor de intrare, acestea.
Luați în considerare pe axa timpului Ot (Fig. 2) cel mai simplu flux de evenimente ca o secvență nelimitată de puncte aleatoare.
Orez. 2
Se poate arăta că pentru cel mai simplu flux numărul T evenimente (puncte) care se încadrează într-un interval de timp arbitrar t, distribuite peste legea lui Poisson

, (1)
pentru care așteptarea matematică a unei variabile aleatoare este egală cu varianța acesteia: a=s2 =lt.
În special, probabilitatea ca niciun eveniment (m=0) să nu aibă loc în timpul t este (2)
Aflați distribuția intervalului de timp Tîntre două evenimente adiacente arbitrare ale celui mai simplu flux.
În conformitate cu (15.2), probabilitatea ca niciunul dintre evenimentele ulterioare să nu apară într-un interval de timp de lungime t este egală cu (3)
și probabilitatea evenimentului opus, i.e. funcție de distribuție a variabilelor aleatoare T, da (4)
Densitatea de probabilitate a unei variabile aleatoare este derivata funcției sale de distribuție (Fig. 3), adică.

(5)

Orez. 3
Distribuția dată de densitatea de probabilitate (5) sau funcția de distribuție (4) se numește revelatoare(sau exponenţial). Astfel, intervalul de timp dintre două evenimente arbitrare vecine are o distribuție exponențială, pentru care așteptarea matematică este egală cu abaterea standard a variabilei aleatoare (6)
și invers în ceea ce privește intensitatea debitului l.
Cea mai importantă proprietate a distribuției exponențiale (inerentă numai distribuției exponențiale) este următoarea: dacă intervalul de timp distribuit conform legii exponențiale a durat deja de ceva timp t, atunci aceasta nu afectează legea distribuției părții rămase. a intervalului (Tt): va fi la fel ca și legea de distribuție a întregului interval T.
Cu alte cuvinte, pentru intervalul de timp T între două evenimente învecinate succesive ale unui flux care are o distribuție exponențială, orice informație despre cât timp a trecut acest interval nu afectează legea de distribuție a părții rămase. Această proprietate a legii exponențiale este, în esență, o altă formulare pentru „lipsa efectului secundar” - proprietatea principală a fluxului cel mai simplu.
Pentru cel mai simplu flux cu intensitatea l, probabilitatea de a lovi elementar (mic) intervalul de timp Dt al cel puțin unui eveniment al fluxului este egal conform (4)
(7)
(Rețineți că această formulă aproximativă, obținută prin schimbarea funcției e-lDt doar primii doi termeni ai expansiunii sale în puteri ale lui Dt, cu atât mai precis, cu atât mai mic Dt).

4. Modelare după schema proceselor aleatoare Markov

Pentru a calcula parametrii numerici care caracterizează obiectele stocastice, este necesară construirea unui model probabilistic al fenomenului, ținând cont de factorii aleatorii care îl însoțesc. Pentru descrierea matematică a multor fenomene care se dezvoltă sub forma unui proces aleatoriu, se poate aplica cu succes aparatul matematic dezvoltat în teoria probabilității pentru așa-numitele procese aleatoare Markov. Să explicăm acest concept. Să existe un sistem fizic S, a cărui stare se modifică în timp (în cadrul sistemului S orice poate fi înțeles: un dispozitiv tehnic, un atelier de reparații, un computer etc.). Dacă starea S variază în timp aleatoriu, ei spun că în sistem S are loc un proces aleatoriu. Exemple: procesul de funcționare a computerului (primirea comenzilor pentru un computer, tipul acestor comenzi, eșecuri aleatorii), procesul de țintire a unei rachete ghidate către o țintă (tulburări aleatorii (interferențe) în sistemul de control al rachetelor), procesul de deservire a clienților într-o coaforă sau atelier de reparații (natura aleatorie fluxul de aplicații (cerințe) primite de la clienți).

Un proces aleatoriu se numește proces Markov (sau „un proces fără consecințe”) dacă pentru fiecare dată t0 probabilitatea oricărei stări a sistemului în viitor (la t> t0 ) depinde numai de starea sa în prezent (at t= t0 ) și nu depinde de când și cum a ajuns sistemul în această stare (adică, cum s-a dezvoltat procesul în trecut). Lasa S dispozitiv tehnic, care se caracterizează printr-un anumit grad de deteriorare S. Suntem interesați de modul în care va funcționa în continuare. Ca o primă aproximare, performanța sistemului în viitor (rata de defecțiuni, necesitatea reparației) depinde de starea dispozitivului în acest moment și nu depinde de când și cum a ajuns dispozitivul în starea actuală.

Teoria proceselor aleatoare Markov este o secțiune extinsă a teoriei probabilităților cu o gamă largă de aplicații (fenomene fizice precum difuzia sau amestecarea sarcinii în timpul topirii într-un furnal, procese de așteptare).

4.1. Clasificarea proceselor Markov

Procesele aleatoare Markov sunt împărțite în clase. Prima caracteristică de clasificare este natura spectrului de stări. Un proces aleator (SP) se numește proces cu stări discrete dacă sunt posibile stări ale sistemului S1,S2,S3… pot fi enumerate, iar procesul în sine constă în faptul că din când în când sistemul S sare (instantaneu) dintr-o stare în alta.

Exemplu. Dispozitiv tehnic este format din două noduri I și II, fiecare dintre ele putând eșua. State: S1– ambele noduri funcționează; S2- primul nod a eșuat, al doilea funcționează; S 3 - al doilea nod a eșuat, primul funcționând; S4 ambele noduri au eșuat.

Există procese cu stări continue (tranziție lină de la stare la stare), de exemplu, schimbarea tensiunii în rețeaua de iluminat. Vom lua în considerare doar SP cu stări discrete. În acest caz, este convenabil să folosiți graficul de stări, în care stările posibile ale sistemului sunt notate prin noduri, iar tranzițiile posibile sunt notate cu arce.

A doua caracteristică de clasificare este natura funcționării în timp. SP se numește proces cu timp discret dacă tranzițiile sistemului de la stare la stare sunt posibile numai la momente strict definite, prefixate: t1,t2…. Dacă trecerea sistemului de la stare la stare este posibilă în orice moment aleatoriu necunoscut dinainte, atunci se vorbește de un SP în timp continuu.

4.2. Calculul lanțului Markov în timp discret

S cu stări discrete S1,S2,...snși timp discret t1,t2, … ,tk,...(etapele, etapele procesului, SP pot fi considerate în funcție de argument (numărul pasului)). ÎN caz general Asocierea în participație constă în faptul că există tranziții S1® S1® S2® S3® S4® S1® … în clipe t1,t2,t3....

Vom desemna evenimentul constând în faptul că după k– pași sistemul este în stare Si. Pentru orice k evenimente https://pandia.ru/text/78/060/images/image004_39.gif" width="159" height="25 src=">.

O astfel de secvență aleatorie de evenimente se numește lanț Markov. Vom descrie un lanț Markov (MC) folosind probabilități de stare. Fie probabilitatea ca după k- pași sistemul este în stare Si. Este ușor să vezi asta " k DIV_ADBLOCK389">

Folosesc evenimentele de mai sus https://pandia.ru/text/78/060/images/image008_34.gif" width="119" height="27 src=">. Suma membrilor din fiecare rând al matricei ar trebui să fie egal cu 1. În schimb, matricele de probabilitate de tranziție folosesc adesea un grafic de stare etichetat (ele denotă probabilități de tranziție diferite de zero pe arce, probabilitățile de întârziere nu sunt necesare, deoarece sunt ușor de calculat, de exemplu P11=1-(P12+P13)). Având la dispoziție un grafic de stare etichetat (sau o matrice de probabilități de tranziție) și cunoscând starea inițială a sistemului, putem găsi probabilitățile de stare p1(k),p2(k),…pn(k)" k.

Fie starea inițială a sistemului sm, atunci

p1(0)=0 p2(0)=0...pm(0)=1...pn(0)=0.

Primul pas:

p1(1)=Pm1, p2(1)=Pm2,…pm(1)=Pmm,… ,pn(1)=Pmn.

După al doilea pas, folosind formula probabilității totale, obținem:

p1(2)=p1(1)P11+p2(1)P21+…pn(1)Pn1,

pi(2)=p1(1)P1i+p2(1)P2i+…pn(1)Pni sauhttps://pandia.ru/text/78/060/images/image010_33.gif" width="149" height="47"> (i=1,2,..n).

Pentru MC eterogen probabilitățile de tranziție depind de numărul pasului. Să notăm probabilitățile de tranziție pentru pasul k ca .

Atunci formula pentru calcularea probabilităților stărilor ia forma:

4.3. Lanțuri Markov cu timp continuu

4.3.1. Ecuațiile lui Kolmogorov

În practică, situațiile sunt mult mai frecvente când sistemul trece de la stare la stare are loc în momente aleatorii care nu pot fi specificate în prealabil: de exemplu, defecțiunea oricărui element al echipamentului, sfârșitul reparației (recuperării) acestui element. . Pentru a descrie astfel de procese, într-un număr de cazuri, se poate aplica cu succes schema unui proces aleator Markov cu stări discrete și timp continuu, un lanț Markov continuu. Să arătăm cum sunt exprimate probabilitățile de stare pentru un astfel de proces. Lasa S=(S1,S2,…sn). Notează prin pi(t)- probabilitatea ca în acest moment t sistem S va fi în stat). Evident . Să stabilim sarcina - să stabilim pentru oricare tpi(t). În loc de probabilități de tranziție Pij introducem în considerare densitatea probabilității de tranziție

Dacă nu depinde de t, se vorbește despre un lanț omogen, în rest - despre unul neomogen. Informați-ne pentru toate perechile de stări (este dat un grafic al stărilor etichetat). Se pare că cunoscând graficul de stare etichetat, puteți determina p1(t),p2(t)..pn(t)în funcţie de timp. Aceste probabilități satisfac anumite tipuri de ecuații diferențiale (ecuațiile lui Kolmogorov).

Integrarea acestor ecuații cu o stare inițială cunoscută a sistemului va da probabilitățile de stare dorite în funcție de timp. observa asta p1+p2+p3+p4=1și putem face cu trei ecuații.

Reguli pentru compilarea ecuațiilor lui Kolmogorov. Partea stângă a fiecărei ecuații conține derivata probabilității stării, iar partea dreaptă conține tot atâtea termeni câte săgeți sunt asociate cu starea dată. Dacă săgeata este îndreptată în afara unei stări, termenul corespunzător are semnul minus, dacă se află într-o stare, un semn plus. Fiecare termen este egal cu produsul densității de probabilitate a tranziției corespunzătoare săgeții date, înmulțit cu probabilitatea stării din care provine săgeata.

4.3.2. Fluxul evenimentelor. Cel mai simplu flux și proprietățile sale

Când luăm în considerare procesele care au loc într-un sistem cu stări discrete și timp continuu, este adesea convenabil să ne imaginăm procesul ca și cum tranzițiile sistemului de la o stare la alta ar avea loc sub influența unui anumit tip de fluxuri de evenimente. Un flux de evenimente este o succesiune de evenimente omogene care urmează unul după altul în anumite momente de timp, în general, aleatorii. (Fluxul de apeluri la centrala telefonică; fluxul de defecțiuni (defecțiuni) ale computerului; fluxul de trenuri de marfă care sosesc în gară; fluxul de vizitatori; fluxul de focuri îndreptate către țintă). Vom descrie fluxul de evenimente ca o succesiune de puncte pe axa timpului ot. Poziția fiecărui punct pe axă este aleatorie. Fluxul de evenimente este numit regulat , dacă evenimentele urmează unul după altul la intervale de timp strict definite (mai rar întâlnite în practică). Luați în considerare un tip special de fluxuri, pentru aceasta introducem o serie de definiții. 1. Fluxul evenimentelor este numit staționar , dacă probabilitatea de a lovi unul sau altul număr de evenimente pe un segment de timp de lungime depinde doar de lungimea segmentului și nu depinde de locul exact pe axa ot este situat acest segment (omogenitate în timp) - caracteristicile probabilistice a unui astfel de flux nu ar trebui să se schimbe în timp. În special, așa-numita intensitate (sau densitate) a fluxului de evenimente (numărul mediu de evenimente pe unitatea de timp) este constantă.

2. Fluxul evenimentelor este numit curge fara consecinte, dacă pentru orice interval de timp care nu se suprapun numărul de evenimente care se încadrează pe unul dintre ele nu depinde de câte evenimente au căzut pe celălalt (sau altele, dacă sunt luate în considerare mai mult de două secțiuni). Absența unei consecințe într-un flux înseamnă că evenimentele care formează fluxul apar în momente succesive în timp, independent unele de altele.

3. Fluxul evenimentelor este numit comun , dacă probabilitatea ca două sau mai multe evenimente să lovească segmentul elementar este neglijabil de mică în comparație cu probabilitatea de a lovi un eveniment (evenimentele din flux vin individual, nu în perechi, tripleți etc.).

Se numește un flux de evenimente care are toate cele trei proprietăți cel mai simplu (sau staționar Poisson). Un flux Poisson nestaționar are numai proprietățile 2 și 3. Fluxul de evenimente Poisson (atât staționari, cât și nestaționari) este strâns legat de distribuția Poisson cunoscută. Și anume, numărul de evenimente de curgere care se încadrează pe orice segment este distribuit conform legii Poisson. Să explicăm acest lucru mai detaliat.

Luați în considerare pe axă despret, unde se observă fluxul evenimentelor, o secțiune de lungime t, începând din momentul respectiv t0 și se termină pe moment t0 + t. Este ușor de demonstrat (dovada este dată în toate cursurile de teoria probabilității) că probabilitatea ca exact m evenimente să lovească această secțiune este exprimată prin formula:

(m=0,1…),

Unde dar este numărul mediu de evenimente pe segment t.

Pentru un flux Poisson staționar (cel mai simplu). a=lt, adică nu depinde de locul în care se află pe axă ot se ia aria t. Pentru un flux Poisson instabil, cantitatea dar este exprimat prin formula

și deci depinde de punctul în care t0 începe secțiunea t.

Luați în considerare pe axă ot cel mai simplu flux de evenimente cu intensitate constantă l. Ne va interesa intervalul de timp T dintre evenimentele din acest flux. Fie l intensitatea (numărul mediu de evenimente pe 1 dată) a fluxului. Densitatea de distribuție f(t) variabilă aleatorie T(interval de timp dintre evenimentele adiacente din flux) f(t)= le- lt (t> 0) . O lege de distribuție cu o astfel de densitate se numește exponențială (exponențială). Să găsim valorile numerice ale variabilei aleatoare T: așteptări matematice (medie) și variația rămasă">

Interval de timp Tîntre evenimentele învecinate în cel mai simplu flux este distribuit după o lege exponențială; valoarea sa medie și abaterea standard sunt , unde l este intensitatea curgerii. Pentru un astfel de flux, probabilitatea de apariție a exact unui eveniment de flux într-un interval de timp elementar ∆t este exprimată ca . Vom numi această probabilitate „elementul probabilității de apariție a evenimentului”.

Pentru un flux Poisson nestaționar, legea distribuției pentru intervalul T nu va mai fi exponențială. Forma acestei legi va depinde, în primul rând, de locul în care se află pe axă ot primul dintre evenimente este situat, iar în al doilea rând, pe tipul de dependență . Totuși, dacă se modifică relativ lent și modificarea sa în timpul intervalului dintre două evenimente este mică, atunci legea distribuției intervalului de timp dintre evenimente poate fi considerată aproximativ orientativă, presupunând în această formulă valoarea egală cu valoarea medie din zonă. care ne interesează.

4.3.3. Fluxuri de evenimente Poisson și

lanțuri Markov continue

Luați în considerare un sistem fizic S=(S1,S2,…sn), care trece de la stat la stat sub influența unor evenimente întâmplătoare (apeluri, eșecuri, lovituri). Să ne imaginăm asta ca și cum evenimentele care transferă sistemul de la o stare la alta ar fi un fel de fluxuri de evenimente.

Lasă sistemul S atunci t este într-o stare Siși poate merge de la ea la stat sj sub influenţa unor flux Poisson de evenimente cu intensitate lij: de îndată ce apare primul eveniment al acestui thread, sistemul trece instantaneu de la Siîn sj..gif" width="582" height="290 src=">

4.3.4. Limitarea probabilităților stărilor

Să existe un sistem fizic S=(S1,S2,…sn), în care are loc un proces stocastic Markov cu timp continuu (lanț Markov continuu). Să ne prefacem că lij=const, adică toate fluxurile de evenimente sunt simple (Poisson staționar). După ce am scris sistemul de ecuații diferențiale Kolmogorov pentru probabilitățile de stare și integrând aceste ecuații în condiții inițiale date, obținem p1(t),p2(t),…pn(t), pentru orice t. Ne punem următoarea întrebare: ce se va întâmpla cu sistemul S la t® ¥. Vor caracteristicile pi(t) să lupți pentru niște limite? Aceste limite, dacă există, se numesc probabilități limită ale stărilor. Este posibil să se demonstreze o teoremă: dacă numărul de stări S este finit și se poate trece din fiecare stare (pentru unul sau altul număr de pași) una la alta, atunci probabilitățile limită ale stărilor există și nu depind de starea initiala a sistemului. Să presupunem că condiția enunțată este îndeplinită și că există probabilități limită (i=1,2,...n), .

Astfel, la t® ¥ în sistem S se stabileşte un regim staţionar limitativ. Sensul acestei probabilități este că nu este nimic mai mult decât timpul relativ mediu pe care sistemul îl petrece într-o anumită stare. A calcula piîn sistemul de ecuații Kolmogorov care descriu probabilitățile stărilor, toate părțile din stânga (derivate) trebuie setate egale cu 0. Sistemul de ecuații algebrice liniare rezultate trebuie rezolvat împreună cu ecuația .

4.3.5. Schema morții și a reproducerii

https://pandia.ru/text/78/060/images/image044_6.gif" width="73" height="45 src="> (4,4)

Din a doua, ținând cont de (4.4), obținem:

https://pandia.ru/text/78/060/images/image046_5.gif" width="116" height="45 src="> (4,6)

și, în general, pentru orice k (de la 1 la N):

https://pandia.ru/text/78/060/images/image048_4.gif" width="267" height="48 src=">

deci obținem o expresie pentru p0.

(4. 8)

(am ridicat paranteza la puterea lui -1 pentru a nu scrie fracții cu două etaje). Toate celelalte probabilități sunt exprimate în termeni de p0 (vezi formulele (4.4) - (4.7)). Rețineți că coeficienții de la p0 în fiecare dintre ei nu sunt altceva decât termeni succesivi ai seriei după unitate în formula (4.8). Deci, calculând p0, am găsit deja toți acești coeficienți.

Formulele obţinute sunt foarte utile în rezolvarea celor mai simple probleme de teorie a cozilor.

Procesul QS este un proces aleatoriu. Un proces aleatoriu (probabilistic sau stocastic) este înțeles ca fiind procesul de schimbare a stării unui sistem în timp în conformitate cu modele probabilistice.

Un proces se numește proces cu stări discrete dacă stările sale posibile S1, S2, S3... pot fi enumerate în prealabil, iar tranziția sistemului de la o stare la alta are loc instantaneu (salt). Un proces se numește proces cu timp continuu dacă momentele posibilelor tranziții ale sistemului de la stare la stare nu sunt fixate în prealabil, ci sunt aleatorii.

Procesul de operare QS este un proces aleatoriu cu stări discrete și timp continuu.

Un proces aleatoriu se numește Markov sau proces aleatoriu fără consecințe dacă, pentru orice moment t0, caracteristicile probabilistice ale procesului în viitor depind doar de starea lui curentă t0 și nu depind de când și cum a ajuns sistemul în această stare.

Un exemplu de proces Markov: sistemul S este un contor într-un taxi. Starea sistemului la momentul t este caracterizată de numărul de kilometri parcurși de mașină până în acel moment. Lăsați contorul să arate S0 la momentul t0. Probabilitatea ca în momentul t>t0 contorul să arate unul sau altul număr de kilometri (mai precis, numărul corespunzător de ruble) S1 depinde de S0, dar nu depinde de momentul la care citirile contorului s-au schimbat înainte de momentul respectiv. t0.

În unele cazuri, preistoria proceselor luate în considerare poate fi pur și simplu neglijată și modelele Markov pot fi folosite pentru a le studia.

Când se analizează procese aleatoare cu stări discrete, este convenabil să se folosească o schemă geometrică - așa-numitul grafic de stare. De obicei, stările sistemului sunt reprezentate prin dreptunghiuri (cercuri), iar posibilele tranziții de la stare la stare sunt reprezentate de săgeți (arce orientate) care leagă stările (Fig. 1).

Figura 1 - Graficul de stare

Pentru o descriere matematică a unui proces aleatoriu Markov cu stări discrete și timp continuu, care curge într-un QS, să ne familiarizăm cu unul dintre conceptele importante ale teoriei probabilităților - conceptul de flux de evenimente.

Un flux de evenimente este înțeles ca o secvență de evenimente omogene care urmează unul după altul în anumite momente aleatorii în timp.

Exemplele ar putea fi:

- fluxul de apeluri la centrala telefonica;
- fluxul de incluziuni de dispozitive in reteaua electrica casnica;
- fluxul trenurilor de marfă care sosesc în gara:
- fluxul de defecțiuni (defecțiuni) ale calculatorului;
- fluxul de lovituri îndreptate către țintă.

Fluxul se caracterizează prin intensitatea l - frecvența de apariție a evenimentelor sau numărul mediu de evenimente care intră în QS pe unitatea de timp.

Un flux de evenimente se numește regulat dacă evenimentele urmează unul după altul la intervale regulate. Un astfel de flux este relativ rar în practică, dar prezintă un interes deosebit ca caz limitativ.

Un flux de evenimente este numit staționar dacă caracteristicile sale probabilistice nu depind de timp. În special, intensitatea unui flux staționar este o valoare constantă: .

Un flux de evenimente se numește flux fără efect secundar dacă, pentru oricare două intervale de timp neintersectate și _, numărul de evenimente care se încadrează pe unul dintre ele nu depinde de numărul de evenimente care cad pe celelalte. De exemplu, fluxul de pasageri care intră în metrou are un efect redus sau deloc. Și, să zicem, fluxul de clienți care părăsesc ghișeul cu achizițiile lor are deja consecințe (fie și doar pentru că intervalul de timp dintre clienții individuali nu poate fi mai mic decât timpul minim de service pentru fiecare dintre aceștia).

Un flux de evenimente se numește obișnuit dacă probabilitatea ca două sau mai multe evenimente să lovească un interval de timp mic (elementar) t este neglijabil de mică în comparație cu probabilitatea ca un singur eveniment să se lovească. Cu alte cuvinte, un flux de evenimente este obișnuit dacă evenimentele apar în el unul câte unul, și nu în grupuri.

Se spune că un flux de evenimente este cel mai simplu (sau staționar Poisson) dacă este atât staționar, cât și obișnuit și nu are consecințe.

Cel mai simplu flux ca flux limitator ia naștere în teoria proceselor aleatorii la fel de firesc ca și în teoria probabilității, distribuția normală se obține prin suprapunerea (suprapunerea) a unui număr n suficient de mare de fluxuri independente, staționare și obișnuite (comparabile între ele ca intensități). ), un debit apropiat de cel mai simplu cu intensitatea l, egal cu suma intensităților fluxurilor de intrare:

Considerați cel mai simplu flux de evenimente pe axa timpului ca o secvență nelimitată de puncte aleatorii. (Fig. 2)

Figura 2 - Fluxul de evenimente

Se poate demonstra că pentru cel mai simplu flux, numărul m de evenimente (puncte) care se încadrează pe un interval de timp arbitrar φ este distribuit conform legii Poisson.

pentru care așteptarea matematică a unei variabile aleatoare este egală cu varianța acesteia:

În special, probabilitatea ca niciun eveniment (m = 0) să nu aibă loc în timpul φ este egală cu

Să găsim distribuția intervalului de timp T între două evenimente învecinate arbitrare ale fluxului cel mai simplu.

În conformitate cu formula, probabilitatea ca niciunul dintre evenimentele ulterioare să nu apară într-un interval de timp de lungime t este egală cu

și probabilitatea evenimentului opus, i.e. funcţia de distribuţie a variabilei aleatoare T, este

Densitatea de probabilitate a unei variabile aleatoare este derivata funcției sale de distribuție:

Distribuția dată de densitatea de probabilitate sau funcția de distribuție se numește exponențială (sau exponențială). Astfel, intervalul de timp dintre două evenimente arbitrare adiacente are o distribuție exponențială, pentru care așteptarea matematică este egală cu abaterea standard a variabilei aleatoare.

şi invers în ceea ce priveşte intensitatea debitului l.

Cea mai importantă proprietate a distribuției exponențiale (inerentă numai distribuției exponențiale) este următoarea: dacă intervalul de timp distribuit conform legii exponențiale a durat deja de ceva timp φ, atunci aceasta nu afectează legea distribuției părții rămase. a intervalului (T-φ): va fi aceeași , precum și legea de distribuție a întregului interval T.

Cu alte cuvinte, pentru un interval de timp T între două evenimente învecinate succesive ale unui flux care are o distribuție exponențială, orice informație despre cât timp a trecut acest interval nu afectează legea de distribuție a părții rămase.

Pentru cel mai simplu flux cu intensitatea l, probabilitatea de a atinge cel puțin un eveniment al curgerii pe un interval de timp elementar (mic)?t este, conform

Tehnologii de calcul

Volumul 13, numărul special 5, 2008

Investigarea fluxului semi-markovian al evenimentelor

A. A. Nazarov, S. V. Universitatea de Stat Lopukhova Tomsk, Rusia e-mail: [email protected] pmk. tsu. ru, [email protected] ro

I.R. Garayshina

Filiala Kemerovo universitate de statîn Anzhero-Sudzhensk, Rusia e-mail: [email protected]

În lucrarea depusă se ia în considerare procesul semimarkovian. este luat în considerare modelul limitativ. Rezultatele tratamentului analitic al modelului limitator sunt comparate cu rezultatele obținute prin metoda asimptotică.

Introducere

Există o problemă de extindere a clasei de modele matematice ale fluxurilor de evenimente omogene. Adesea, modelele clasice ale fluxurilor de evenimente aleatoare nu pot fi adecvate fluxurilor reale de informații și telecomunicații. Modelele de flux Poisso și simple nu sunt adesea suficiente pentru o descriere mai plauzibilă și realistă a fluxurilor de intrare pentru sistemele de așteptare. Deși există fluxuri de tip fază și modulate Poisson curge, care sunt mai adecvate situațiilor reale, sunt de mare interes modelele de flux semi-Markov, un caz special al cărora sunt fluxurile de recuperare Markov și toate fluxurile de mai sus. Metodele de studiu a unor astfel de modele sunt destul de complexe și conduc la probleme matematice semnificative. Prin urmare, alături de sarcina extinderii claselor de fluxuri, există problema dezvoltării metodelor de studiere a acestora.

1. Model matematic

Un flux aleatoriu de evenimente omogene (flux) este o secvență ordonată

t\< ¿2 < ■ ■ ■

variabile aleatoare tm - momentele de apariţie a evenimentelor în flux.

Să fie dată o matrice semi-Markov A(x) cu elemente Aklk2 (x).Matricea P = lim A(x) este stocastică, prin urmare, pentru o distribuție inițială dată

definește un lanț Markov k (tm) cu timp discret, pe care îl vom numi un lanț Markov încorporat într-un flux semi-Markov,

A. A. Nazarov, S. V. Lopukhova, I. R. Garayshina

Un flux aleatoriu de evenimente omogene va fi numit semi-Markov dacă legea probabilistică de formare a secvenței (1) este determinată de distribuția inițială și egalități.

Ak1k2 (x) = P (k(bm+1) = k2, bm+1 - bm< х ^^т) = к\ }

pentru toți m > 1.

Să notăm cu n(b) numărul de evenimente ale fluxului semi-markovian care s-au acumulat în timpul b în intervalul .

Obiectivul acestei lucrări este de a stabili distribuția de probabilitate P(n, b) = P(n(b) = n) pentru funcționarea staționară a lanțului Markov ergodic k(lm). În mod evident, procesul n(b) este non-markovian, deci definim încă două procese aleatoare: r(b) este lungimea intervalului de la momentul b până la momentul următorului eveniment din fluxul luat în considerare, k(b). ) este un proces continuu stânga cu timp continuu, valoarea care este constantă pe intervalul (bm,bm+1] și sunt definite de egalitățile k(b) = k(bm+1). În virtutea definițiilor de mai sus , procesul aleator (k(b), n(b), r(b)) este un proces Markov cu timp continuu.

Rețineți că procesul aleatoriu k(b) nu este semi-Markov în definiția clasică a lui , deoarece procesul semi-Markov B(b) este continuu drept și, așa cum este indicat în , nu există ecuații de evoluție diferențială Kolmogorov pentru tranziția sa probabilităților, în timp ce procesul propus mai sus (k(b), n(b), r(b)) este markovian, deci pentru distribuția sa de probabilitate

P (k, n, r, b) = P (k (b) = k, n (b) = n, r (b)< г} (2)

nu este greu de compus un sistem de ecuații diferențiale Kolmogorov

^ dT (u, 1b - 1, 0, b) A (\ 2-^-

db dg dg ^ dg

Denota

H(k, u, r, r) = ^ e „uPR(k, n, r, b),

unde ] = ¡~ ~~ unitate imaginară. Pentru aceste funcții, din sistemul Kolmogorov de ecuații diferențiale, putem scrie

dH (k, u, z, b) dH (k, u, z, b) dH (k, u, 0, b), u ^ dH (u, u, 0, b)

db dg dg ^ dg

Notăm H (u, r, b) = (H (1, u, r, b) , H (2, u, r, b),...) șirul funcției vectoriale, apoi rescriem sistemul de ecuațiile (3) sub formă de matrice

dN(i,g,g) _ dN(i,g,g) dN(i,0,g) Mc,g h n t

dg dg + dg 1 [) "" [ )

a cărei soluție satisface condiția inițială H(u,z, 0) = R(z), unde I este matricea de identitate și distribuția staționară R(z) a procesului Markov bidimensional (k(t), z( t)) este rezolvarea problemei Cauchy

<Ш = <Ш(1-Мг)),

și este definit de egalitatea R(z) = seit / (P - A(x))dx, unde aei = Aici r este un vector

rând de distribuție de probabilitate staționară a valorilor lanțului Markov imbricate

k(tm); E este un vector coloană unitar și matricea A = (P - A(x))dx.

2. Prelimit model

Să avem o ecuație diferențială (4) a cărei soluție H (u,z,t) satisface condiția inițială H(u, z, 0) = R(z). Apoi transformata Fourier - Stieltjess

φ>(u, a, t) = / ejaz dz H (u, z, t) a funcției vectoriale H (u, z, t) satisface ecuația

df(u, a, b). . dH (u, 0, b), .*. . gl, .

m \u003d ~ zaf (u a, + - (e? uA * (a) - /) (5)

si starea initiala

φ(u, a, 0) = R*(a) = ^ e > a2

unde A*(a) = J e>a"2dA(z). Soluția ecuației (5) are forma

φ(u, a, 1) = e~zab [ II*(a) + I (¿>uA*(a) - I) dt] . (6)

Lăsând b să tinde spre infinit în expresia (6), obținem transformata Fourier în m

dH (u, 0, t) ^ ^ "l

din funcţie-vector---. După efectuarea transformării Fourier inversă, determinăm

eu e-j *A*(aj) 1da.

A. A. Nazarov, S. V. Lopukhova, I. R. Raraishshia

Acum egalitatea (6) poate fi scrisă ca

f (scha, g) \u003d e-ab R * (a) +

+ - / e] la I e ~ zutK * (y) (/ - e> uA * (y)) 1 Au (e "uA * (a) - /)<*г). (7)

Știind că H(u, x, r) = H(u, r) = φ(u, 0,1), obținem o expresie pentru funcția vectorială H(u, r):

Atunci distribuția de probabilitate P(n, r) a numărului de evenimente care au loc în timpul r este

tion H(u, b) = MeUn(b = H(u, b)E, are forma

1 C a1 G 1 - e-™b

P(n, 1) = - e~zipNSH)E(1u = - / -^-5

I - A * (y) A * (y) p-1Eyu, (8)

I - A* (y) E<1у

Concluzie

Efectuând studii asimptotice ale fluxului de evenimente semi-markovian, similar studiului fluxurilor de reînnoire Markov, obținem că asimptoticele de ordinul trei pentru funcția caracteristică pot fi scrise ca

MeHan(1) = ^"(re^+^ae^+^aez*)

unde coeficienții s31, a2, a3 pentru un flux semi-Markov sunt determinați în același mod în care sa făcut în lucrări. Egalitățile rezultate (8) determină distribuția de probabilitate P(n, r) a numărului de evenimente care au loc într-un flux semi-Markov staționar dat de matricea semi-Markov A(x) și transformarea sa Fourier-Stieltjess A*(x) Implementarea numerică a formulelor (8) face posibilă găsirea valorilor numerice ale probabilităților P(n, r) pentru o gamă suficient de largă de matrice A*(x) și valori ale lui r. Cu toate acestea, posibilitățile de implementare numerică sunt limitate de resursele de calcul. Pentru valori suficient de mari ale lui r, este firesc să se aplice metoda de analiză asimptotică a fluxului semi-Markov în același mod în care s-a făcut pentru fluxul de reînnoire Markov din Ref. și fluxul de reînnoire Markov sitat în Ref. Prezența algoritmului numeric (8) face posibilă determinarea domeniului de aplicare a rezultatelor asimptotice. Pentru fluxurile considerate cu trei stări ale lanțului Markov imbricat, distanța Kolmogorov - Smirnov dintre distribuții,

obținut asimptotic și prin formulele (8), nu depășește 2-3% pentru anumite valori ale lui t = T, acest lucru ne permite să afirmăm că pentru t > T, utilizarea rezultatelor asimptotice este eficientă, iar pentru t< Т целесообразно использовать формулы (8), полученные в данной работе.

Bibliografie

Korolyuk B.C. Modele stocastice de sisteme. Kiev: Nauk, Dumka, 1989. 208 p.

Nazarov A.A., Lopukhova C.V. Investigarea fluxului de recuperare a lui Markov printr-o metodă asimptotică de ordinul doi // Mater. Internaţional științific conf. „Metode matematice pentru îmbunătățirea eficienței rețelelor de telecomunicații”. Grodno, 2007, p. 170-174.

Lopukhova C.B. Investigarea fluxului semi-Markov prin metoda asimptotică de ordinul trei // Mater. VI Intern. științifice și practice. conf. „Tehnologii informaționale și modelare matematică”. Tomsk: Editura Vol. un-ta, 2007. Partea 2. S. 30-34.

Ar putea fi util să citiți: