Molte operazioni che devono essere analizzate quando si sceglie la soluzione ottimale si sviluppano come processi casuali che dipendono da una serie di fattori casuali.

Per descrizione matematica molte operazioni che si sviluppano sotto forma di un processo casuale possono essere applicate con successo apparato matematico, sviluppato nella teoria della probabilità per i cosiddetti processi casuali di Markov.

Spieghiamo il concetto di processo casuale di Markov.

Che ci sia un sistema S, il cui stato cambia nel tempo (sotto il sistema S tutto può essere compreso: un'impresa industriale, un dispositivo tecnico, un'officina di riparazione, ecc.). Se lo stato del sistema S cambia nel tempo in modo casuale, imprevedibile, lo dicono nel sistema S perdite processo casuale.

Esempi di processi casuali:

fluttuazioni dei prezzi nel mercato azionario;

servizio clienti in un parrucchiere o un'officina di riparazione;

adempimento del piano di approvvigionamento del gruppo di imprese, ecc.

Il corso specifico di ciascuno di questi processi dipende da una serie di fattori casuali e imprevedibili, come ad esempio:

ricezione in borsa di notizie imprevedibili su cambiamenti politici;

la natura casuale del flusso di applicazioni (requisiti) provenienti dai clienti;

interruzioni occasionali nell'adempimento del piano di fornitura, ecc.

DEFINIZIONE. Viene chiamato il processo casuale nel sistema markoviano(o processo senza conseguenze) se ha la seguente proprietà: per ogni momento t 0 la probabilità di qualsiasi stato del sistema in futuro (a t > t0) dipende solo dal suo stato nel presente (con t = t0) e non dipende da quando e come il sistema è arrivato a questo stato (cioè, come il processo si è sviluppato in passato).

In altre parole, in un processo casuale di Markov, il suo sviluppo futuro dipende solo dallo stato presente e non dipende dalla “preistoria” del processo.

Considera un esempio. Lascia che il sistema S rappresenta un mercato azionario che esiste da tempo. Siamo interessati a come funzionerà il sistema in futuro. È chiaro, almeno in prima approssimazione, che le caratteristiche della performance futura (le probabilità di caduta dei prezzi di determinati titoli in una settimana) dipendono dallo stato del sistema in quel momento (il più vari fattori come decisioni governative o risultati elettorali) e non dipendono da quando e come il sistema ha raggiunto il suo stato attuale (non dipendono dalla natura del movimento di prezzo di queste azioni in passato).

In pratica si incontrano spesso processi casuali che, con uno o un altro grado di approssimazione, possono essere considerati markoviani.

La teoria dei processi casuali di Markov ha una vasta gamma di applicazioni differenti. Saremo principalmente interessati all'applicazione della teoria dei processi casuali di Markov alla costruzione di modelli matematici di operazioni, il cui corso ed esito dipende essenzialmente da fattori casuali.

I processi casuali di Markov sono suddivisi in classi a seconda di come e in quali istanti nel tempo il sistema S" può cambiare i suoi stati.

DEFINIZIONE. Viene chiamato il processo casuale processo con stati discreti, se i possibili stati del sistema s x , s 2 , s v... possono essere elencati (numerati) uno dopo l'altro, e il processo stesso consiste nel fatto che di volta in volta il sistema S salta (istantaneamente) da uno stato all'altro.

Ad esempio, lo sviluppo del progetto S svolto congiuntamente da due dipartimenti, ciascuno dei quali può commettere un errore. Sono possibili i seguenti stati del sistema:

5, - entrambi i reparti funzionano normalmente;

S 2 - il primo reparto ha sbagliato, il secondo funziona bene;

S 3 - il secondo reparto ha sbagliato, il primo funziona bene;

S 4 Entrambi i reparti hanno commesso un errore.

Il processo che ha luogo nel sistema è che in alcuni punti del tempo passa ("salta") casualmente da uno stato all'altro. Il sistema ha quattro possibili stati in totale. Davanti a noi c'è un processo con stati discreti.

Oltre ai processi con stati discreti, ci sono processi casuali con stati continui: questi processi sono caratterizzati da una transizione graduale e graduale da uno stato all'altro. Ad esempio, il processo di modifica della tensione nella rete di illuminazione è un processo casuale con stati continui.

Considereremo solo processi casuali con stati discreti.

Quando si analizzano processi casuali con stati discreti, è molto conveniente utilizzare uno schema geometrico, il cosiddetto grafo di stato. Grafico di stato raffigura geometricamente i possibili stati del sistema e le sue possibili transizioni da uno stato all'altro.

Che ci sia un sistema S con stati discreti:

Ogni stato sarà rappresentato da un rettangolo e le possibili transizioni ("salta") da uno stato all'altro da frecce che collegano questi rettangoli. Un esempio di grafico di stato è mostrato in fig. 4.1.

Si noti che le frecce segnano solo le transizioni dirette da uno stato all'altro; se il sistema può passare dallo stato s2 a 5 3 solo attraverso s y quindi le frecce segnano solo le transizioni s2-> e l, 1 -> 5 3 ma non s2 -» s y Diamo un'occhiata ad alcuni esempi:

1. Sistema S- un'impresa che può trovarsi in uno dei cinque possibili stati: S]- lavora con profitto;

s2- ha perso la prospettiva di sviluppo e ha cessato di realizzare un profitto;

5 3 - è divenuto oggetto di eventuale acquisizione;

s4- è sotto controllo esterno;

s5- l'immobile della società liquidata viene venduto all'asta.

Il grafico di stato dell'impresa è mostrato in Fig. 4.2.

Riso. 4.2

• 2. Sistema S- una banca con due filiali. Sono possibili i seguenti stati del sistema:
• 5, - entrambi i rami lavorano con profitto;

S 2 - il primo reparto lavora senza profitto, il secondo con profitto;

5 3 - il secondo reparto lavora senza profitto, il primo con profitto;

S 4 - entrambe le filiali operano senza scopo di lucro.

Si presume che non vi sia alcun miglioramento della condizione.

Il grafico di stato è mostrato in fig. 4.3. Si noti che il grafico non mostra una possibile transizione dallo stato S] direttamente a s 4 , che si avvererà se la banca immediamente opererà in perdita. La possibilità di un tale evento può essere trascurata, il che è confermato dalla pratica.

Riso. 4.3

3. Sistema S- una società di investimento composta da due operatori (dipartimenti): I e II; ognuno di loro può a un certo punto iniziare a lavorare in perdita. Se ciò accade, la direzione dell'azienda prende immediatamente misure per ripristinare il lavoro redditizio del dipartimento.

Possibili stati del sistema: S- l'attività di entrambi i reparti è redditizia; s2- il primo reparto viene restaurato, il secondo lavora con profitto;

s3- il primo reparto lavora con profitto, il secondo viene restaurato;

s4- entrambi i reparti sono in fase di ripristino.

Il grafico dello stato del sistema è mostrato in fig. 4.4.

4. Nelle condizioni dell'esempio precedente, l'attività di ciascun operatore, prima che cominci a ripristinare il proficuo lavoro del dipartimento, è esaminata dalla direzione aziendale al fine di adottare misure per migliorarla.

Per comodità, numereremo gli stati del sistema non con uno, ma con due indici; il primo significherà lo stato del primo commerciante (1 - lavora con profitto, 2 - la sua attività è allo studio della direzione, 3 - ripristina l'attività redditizia del dipartimento); il secondo - gli stessi stati per il secondo trader. Per esempio, s 23 vorrà dire: l'attività del primo trader è allo studio, il secondo è il ripristino di un lavoro redditizio.

Possibili stati del sistema S:

sei tu- l'attività di entrambi i trader è redditizia;

s l2- il primo trader lavora con profitto, l'attività del secondo è studiata dal management dell'azienda;

5 13 - il primo commerciante lavora con profitto, il secondo ripristina l'attività redditizia del dipartimento;

s2l- l'attività del primo trader è studiata dal management, il secondo lavora con profitto;

S 22 - l'attività di entrambi i trader è studiata dal management;

• 5 23 - è allo studio il lavoro del primo commerciante, il secondo commerciante sta ripristinando la proficua attività del dipartimento;
• 5 31 - il primo commerciante ripristina l'attività redditizia del dipartimento, il secondo lavora con profitto;
• 5 32 - la proficua attività del dipartimento viene ripristinata dal primo commerciante, è allo studio il lavoro del secondo commerciante;
• 5 33 - entrambi i commercianti ripristinano il lavoro redditizio del loro dipartimento.

Ci sono nove stati in totale. Il grafico di stato è mostrato in fig. 4.5.

In questa sezione, utilizziamo il metodo dei processi di Markov per trovare il demodulatore ottimale. La nostra presentazione è superficiale, quindi, per una considerazione più dettagliata, i lettori interessati dovrebbero fare riferimento a fonti aggiuntive (in particolare). E questa volta assumeremo che il messaggio sia un processo casuale gaussiano con una rappresentazione finita in variabili di stato, ad es.

dove è un processo casuale gaussiano bianco con funzione di covarianza

Sebbene non utilizziamo questo fatto nel corso della presentazione, va sottolineato che la procedura descritta in questa sezione può essere eseguita anche quando l'equazione di stato e l'equazione di osservazione sono non lineari e hanno la forma

Si noti che sotto alcune restrizioni imposte è un processo di Markov vettoriale, che non è necessariamente un gaussiano. Nessuno dei metodi precedentemente considerati consente di risolvere problemi con i messaggi di questa classe. La maggior parte dei risultati che si otterranno in questa sezione possono essere ottenuti anche per il processo più generale descritto dalle equazioni (78) e (79).

Torniamo ora al modello sotto forma di un processo casuale descritto da relazioni Per semplicità di notazione, consideriamo un messaggio che è un processo scalare gaussiano di Markov e con il quale l'oscillazione trasmessa è modulata da un tipo di modulazione inerziale . L'oscillazione ricevuta viene scritta come

Il processo di comunicazione soddisfa l'equazione differenziale del primo ordine

Pertanto, per ogni messaggio finito è un processo stazionario e ha uno spettro di Butterworth del primo ordine. Inoltre, poiché il processo di Markov è del primo ordine, la sua densità di probabilità in assenza di qualsiasi osservazione soddisfa l'equazione di Fokker-Planck [vedi. (3.79)]

Tuttavia, poiché è stata osservata durante l'intervallo di tempo, la densità di probabilità che ci interessa non è una densità incondizionata, ma una densità dovuta alla fluttuazione osservata. Indichiamo questa densità con

Si noti che (86) è la densità di probabilità di uno variabile casuale(una quantità che denota il valore di a nel momento dovuto alla fluttuazione osservata, ed è una caratteristica ben definita. Si può dimostrare che questa densità di probabilità soddisfa l'equazione

dove le aspettative matematiche sono tratte dalla densità Se introduciamo formalmente la derivata

allora la (87) può essere formalmente scritta come un'equazione differenziale

La relazione tra la densità a posteriori e la stima dell'errore standard minimo è ben nota. La stima dell'errore quadratico medio minimo è la media condizionale della densità a posteriori (vedi p. 73 del primo volume), cioè

Moltiplicando entrambe le parti della (89) per A, integrando rispetto e tenendo conto delle corrispondenti condizioni agli estremi dell'intervallo, otteniamo (vedi problema 7.2.2)

Si noti che (91) contiene ancora valore atteso da Come previsto, questa equazione non è risolta per il caso generale della modulazione. quando metodi lineari modulazione è facile mostrare (per esempio, 18] o problema 7.2.1) che si riduce a Per molti problemi di modulazione non lineare, il successo può essere ottenuto espandendosi in un certo numero di termini differenti dell'equazione (91). Quindi, se assumiamo che l'errore di stima sia piccolo e poniamo delle condizioni ai momenti di ordine superiore, possiamo trascurare i termini del secondo ordine e di quelli superiori e ottenere la seguente equazione approssimativa (una derivazione dettagliata è data nel Capitolo 4 della prenotare):

dove denota una stima approssimativa dell'errore quadratico medio minimo. La funzione è un condizionale approssimato [nel quadrato medio dell'errore] che soddisfa l'equazione differenziale

con condizione al contorno

Si noti che l'equazione di stima (92) e l'equazione di dispersione (93) sono accoppiate. Si noti inoltre che l'errore quadratico medio condizionato [i.e. e.errore a condizione che le approssimazioni che devono essere fatte siano valide quando l'errore è piccolo.

Vediamo che l'equazione (92) può essere implementata sotto forma di un diagramma a blocchi mostrato in Fig. 7.3. Questa implementazione è molto simile alla struttura dello stimatore di massima probabilità a posteriori sintetizzata nel Cap. 2, con l'unica differenza che il filtro nel loop è ora implementato automaticamente. Lo svantaggio di questa implementazione è la presenza di comunicazione tra i loop.

Nel caso della modulazione angolare, si può dimostrare che questo accoppiamento può essere solitamente trascurato. Ad esempio, con modulazione di fase

Si presume che sia molto maggiore della frequenza più alta nello spettro dei messaggi e che il sistema sia in uno stato statisticamente stazionario. In questo caso, è dimostrato che

soddisfa l'equazione di dispersione durante la sostituzione

Per un processo di Markov del primo ordine, questa equazione ha la forma

Lo schema a blocchi del ricevitore è mostrato in fig. 7.4. Questa struttura coincide esattamente con la parte realizzabile del ricevitore approssimato in termini di probabilità massima a posteriori, che è stata sintetizzata in precedenza (si veda il problema in (68) può ora essere interpretato come un errore quadratico medio condizionato approssimato.

Riso. 7.4. Ricevitore ottimale: modulazione di fase, comunicazione dello spettro Butterworth del primo ordine.

Poiché la maggior parte dei dettagli dell'output è stata omessa, è importante notare i limiti del risultato. L'equazione differenziale (91), che determina la media condizionale, è esatta. Tuttavia, le approssimazioni associate all'ottenimento di (92)-(93) corrispondono all'ipotesi di linearizzazione. Pertanto, il nostro risultato è una stima approssimativa del minimo dell'errore quadratico medio corrispondente al primo termine dell'espansione in una serie della stima esatta. Per ottenere una migliore approssimazione, puoi tenere Di più termini di espansione (vedi, ad esempio, ). La difficoltà di questa procedura è che l'approssimazione a due termini è già così complicata che probabilmente non ha alcun interesse pratico.

Sotto processo casuale comprendere il cambiamento nel tempo degli stati di alcuni sistemi fisici in un modo casuale precedentemente sconosciuto. in cui per sistema fisico intendiamo qualsiasi dispositivo tecnico, gruppo di dispositivi, impresa, industria, sistema biologico, ecc.

processo casuale viene chiamato il flusso nel sistema Markovsky – se per qualsiasi momento, le caratteristiche probabilistiche del processo in futuro (t > ) dipendono solo dal suo stato in un dato momento ( regalo ) e non dipendono da quando e come il sistema è arrivato a questo stato nel passato .(Ad esempio, un contatore Geiger che registra il numero di particelle cosmiche).

I processi di Markov sono generalmente divisi in 3 tipi:

1. catena markoviana – un processo i cui stati sono discreti (cioè possono essere rinumerati) e anche il tempo entro il quale viene considerato è discreto (cioè, il processo può cambiare i suoi stati solo in determinati momenti). Tale processo va (cambia) per gradi (in altre parole, in cicli).

2. Processo di Markov discreto - l'insieme degli stati è discreto (può essere enumerato) e il tempo è continuo (transizione da uno stato all'altro - in qualsiasi momento).

3. Processo Markov continuo – l'insieme degli stati e il tempo sono continui.

In pratica, i processi di Markov nella loro forma pura non si incontrano spesso. Tuttavia, si ha spesso a che fare con processi per i quali l'influenza della preistoria può essere trascurata. Inoltre, se tutti i parametri del "passato", da cui dipende il "futuro", sono inclusi nello stato del sistema nel "presente", allora può anche essere considerato markoviano. Tuttavia, ciò comporta spesso un aumento significativo del numero di variabili prese in considerazione e l'impossibilità di ottenere una soluzione al problema.

Nella ricerca operativa Grande importanza occupare il cosiddetto Processi stocastici di Markov con stati discreti e tempo continuo.

Il processo è chiamato processo a stati discreti, se tutti i suoi possibili stati , ,... possono essere enumerati (rinumerati) in anticipo. La transizione del sistema da uno stato all'altro passa quasi istantaneamente: salta.

Il processo è chiamato processo a tempo continuo, se i momenti di passaggio da stato a stato possono durare valori casuali sull'asse del tempo.

Per esempio : Dispositivo tecnico S è costituito da due nodi , ognuno dei quali in un momento casuale può fallire ( rifiutare). Dopodiché, la riparazione del nodo inizia immediatamente ( recupero) che continua per un tempo casuale.

Sono possibili i seguenti stati del sistema:

Entrambi i nodi sono OK;

Il primo nodo è in riparazione, il secondo funziona.

- il secondo nodo è in riparazione, il primo è funzionante

Entrambi i nodi sono in riparazione.

La transizione del sistema da uno stato all'altro avviene in momenti casuali quasi istantaneamente. È conveniente visualizzare gli stati del sistema e la relazione tra di loro utilizzando grafico di stato .

stati

Transizioni

Le transizioni e sono assenti perché i guasti e il ripristino degli elementi avvengono in modo indipendente e casuale e la probabilità di guasto simultaneo (recupero) di due elementi è infinitesima e può essere trascurata.

Se tutti i flussi di eventi traducono il sistema S da stato a stato protozoi, poi processi, che scorre in un tale sistema sarà Markovsky. Ciò è dovuto al fatto che il flusso più semplice non ha un effetto collaterale, ad es. in esso, il "futuro" non dipende dal "passato" e, inoltre, ha la proprietà dell'ordinarietà: la probabilità del verificarsi simultaneo di due o più eventi è infinitamente piccola, ad es. è impossibile spostarsi dallo stato dichiarare senza passare diversi stati intermedi.

Per chiarezza, sul grafico di stato, è conveniente annotare l'intensità del flusso di eventi che trasferisce il sistema da stato a stato lungo la freccia data ad ogni freccia di transizione ( - l'intensità del flusso di eventi che trasferisce il sistema dallo stato in. Un tale grafico è chiamato segnato.

Usando un grafico di stato del sistema etichettato, si può costruire modello matematico questo processo.

Considera le transizioni del sistema da uno stato al precedente o al successivo. Un frammento del grafico di stato in questo caso sarà simile a questo:

Lascia che il sistema al momento tè in uno stato di .

Denota (t)- probabilità dell'i-esimo stato del sistemaè la probabilità che il sistema in un momento tè in uno stato di . Per ogni momento t =1 è vero.

Determiniamo la probabilità che al momento t+∆t il sistema sarà nello stato. Questo può essere nei seguenti casi:

1) e non lo lasciò durante il tempo ∆ t. Ciò significa che durante il tempo ∆t non è sorto un evento che porta il sistema in uno stato (flusso con intensità) o un evento che lo mette in uno stato (flusso con intensità). Determiniamo la probabilità di ciò per ∆t piccoli.

Secondo la legge esponenziale della distribuzione del tempo tra due requisiti vicini, corrispondenti al flusso di eventi più semplice, la probabilità che, nell'intervallo di tempo ∆t, non si verifichino requisiti nel flusso con intensità λ1 sarà uguale a

Espandendo la funzione f(t) in una serie di Taylor (t>0) otteniamo (per t=∆t)

f(∆t)=f(0)+ (0)* ∆t + *∆ + *∆ +…=

= +(-l) *∆t+ (∆ + *(∆ +…” 1-l*∆t per ∆t®0

Allo stesso modo, per un flusso con intensità λ 2 otteniamo .

La probabilità che nell'intervallo di tempo ∆t (per ∆t®0) nessun requisito sarà uguale a

(∆t)/ = (∆t/ * (∆t/ = (1- *∆t)(1- *∆t) =

1 - - *∆t + 1 - ( + )*∆t + b.m.

Pertanto, la probabilità che il sistema non abbia lasciato lo stato durante il tempo ∆t, per piccolo ∆t sarà uguale a

P( / )=1 – ( + )* ∆t

2) Il sistema era in uno stato S i -1 e per il tempo passò allo stato S i . Cioè, almeno un evento si è verificato nel flusso con intensità. La probabilità di ciò è uguale al flusso più semplice con intensità λ sarà

Nel nostro caso, la probabilità di tale transizione sarà uguale a

3)Il sistema era in uno stato e durante il tempo ∆t è passato nello stato . La probabilità di questo sarà

Allora la probabilità che il sistema in quel momento (t+∆t) sia nello stato S i è uguale a

Sottrarre P i (t) da entrambe le parti, dividere per ∆t e passando al limite con ∆t→0 otteniamo

Sostituendo i valori corrispondenti delle intensità delle transizioni da stati a stati, otteniamo il sistema equazioni differenziali descrivendo il cambiamento nelle probabilità degli stati del sistema come funzioni del tempo.

Queste equazioni sono chiamate equazioni Kolmogorov-Chapman per un processo di Markov discreto.

aver chiesto condizioni iniziali(ad esempio P 0 (t=0)=1,P i (t=0)=0 i≠0) e risolvendoli si ottengono espressioni per le probabilità dello stato del sistema in funzione del tempo. Le soluzioni analitiche sono abbastanza facili da ottenere se il numero di equazioni ≤ 2,3. Se ce ne sono più, le equazioni vengono solitamente risolte numericamente su un computer (ad esempio, con il metodo Runge-Kutta).

Nella teoria dei processi casuali provato , che cosa se il numero n stati del sistema di certo e da ciascuno di essi è possibile (in un numero finito di passi) passare a un altro, allora c'è un limite , a cui tendono le probabilità quando t→ . Tali probabilità sono chiamate probabilità finali stati e lo stato stazionario - modalità stazionaria funzionamento del sistema.

Dal momento che in modalità stazionaria tutto , quindi, tutti =0. Uguagliando le parti di sinistra del sistema di equazioni con 0 e integrandole con l'equazione =1, otteniamo un sistema di lineari equazioni algebriche, risolvendo il quale troviamo i valori delle probabilità finali.

Esempio. Lascia che nel nostro sistema i tassi di guasto e ripristino degli elementi siano i seguenti

Fallimenti 1el:

2el:

Riparazione 1el:

2el:

P 0 + P 1 + P 2 + P 3 \u003d 1

0=-(1+2)P 0 +2P 1 +3 P 2

0=-(2+2)P 1 +1P 0 +3P 3

0=-(1+3)P 2 +2P 0 +2P 3

0=-(2+3)P 3 +2P 1 +1P 2

Decidere questo sistema, noi abbiamo

P 0 =6/15=0,4; P 1 =3/15=0,2; P2=4/15=0,27; P3=2/15≈0,13.

Quelli. in uno stato stazionario, il sistema in media

il 40% è nello stato S 0 (entrambi i nodi sono sani),

20% - in condizioni S 1 (il 1° elemento è in riparazione, il 2° è in buone condizioni),

27% - in condizioni S 2 (il 2° elettrico è in riparazione, 1 è in buone condizioni),

13% - in condizione S 3 - entrambi gli elementi sono in riparazione.

Conoscere le probabilità finali lo consente Valutare le prestazioni medie del sistema e riparare il carico del servizio.

Lascia che il sistema nello stato S 0 porti un reddito di 8 unità. per unità di tempo; nello stato S 1 - reddito 3 sr.u.; nello stato S 2 - reddito 5; nello stato S 3 - reddito \u003d 0

Prezzo riparazione per unità di tempo per el-ta 1- 1 (S 1, S 3) unità arb., el-ta 2- (S 2, S 3) 2 arb. Quindi in modalità stazionaria:

Reddito di sistema per unità di tempo sarà:

W max =8P 0 +3P 1 +5P 2 +0P 3 =8 0.4+3 0.2+5 0.27+0 0.13=5.15 c.u.

Costo di riparazione in unità volta:

W rem =0P 0 +1P 1 +2P 2 +(1+2)P 3 =0 0.4+1 0.2+2 0.27+3 0.13=1.39 c.u.

Profitto per unità di tempo

W \u003d W doh -W rem \u003d 5,15-1,39 \u003d 3,76 unità

Dopo aver speso determinate spese, è possibile modificare l'intensità λ e μ e, di conseguenza, l'efficienza del sistema. La fattibilità di tali spese può essere valutata ricalcolando P i . e indicatori di prestazione del sistema.

Lascia che s.p. avvenga in qualche sistema. con stati discreti
e tempo discreto, cioè il passaggio del sistema da uno stato all'altro avviene solo in determinati momenti
. Questi momenti sono chiamati passi processo (di solito la differenza tra momenti di osservazione adiacenti
uguale a un numero costante - la lunghezza del passo, presa come unità di tempo);
l'inizio del processo.

Questo s.p. può essere visto come una sequenza (catena) di eventi
.

lo stato iniziale del sistema, cioè prima del 1° passaggio;
stato del sistema dopo il 1° passaggio,
lo stato del sistema dopo il 2° passo, ecc.), ad es. eventi della forma
dove.

Viene chiamato un processo casuale di Markov con stati discreti e tempo discreto catena markoviana(catena di Markov).

Notare che catena markoviana, in cui le probabilità condizionate degli stati nel futuro dipendono solo dallo stato nell'ultimo stadio (e non dipendono dai precedenti), è chiamato semplice catena di Markov. (A.A. Markov 1856-1922 - matematico russo).

Un esempio di un tale sistema può fungere da dispositivo tecnico, i cui possibili stati sono i seguenti:

buon lavoro;

ispezione e manutenzione preventiva;

Lavoro di riparazione;

cancellazione per inutilità;

Il grafico dello stato dei lavori è mostrato in figura

Riso. 1.11 (AA Belov, et al.)

Dall'analisi del grafico si evince che dallo stato di normale funzionamento del vertice il sistema può entrare in uno stato di manutenzione preventiva , e quindi tornare a . O spostati da in stato di manutenzione , dopodiché ritorna a , o passare allo stato di cancellazione. Stato è finito, poiché il passaggio da esso è impossibile. Transizione da di nuovo dentro significa un ritardo in questo stato.

In pratica, ci sono spesso sistemi i cui stati formano una catena in cui ciascuno stato (salvo estremi e ) è collegato da una retta e feedback con due vicini
e gli stati estremi - con uno vicino (vedi Fig.)

Fig.1.12(Belov...)

Un esempio di tale sistema è un dispositivo tecnico costituito dallo stesso tipo di nodi. Ogni stato del sistema è caratterizzato dal numero di guasti nodi al momento della verifica.

Il compito principale dello studio è trovare le probabilità dello stato su qualsiasi
passo. Calcoleremo le probabilità degli stati del sistema discreto

Qui considereremo solo semplici catene di Markov. Inoltre, considereremo brevemente anche i concetti di processi di Markov continui.

Con un tempo discreto di cambiamento negli stati del sistema, viene chiamata ogni transizione da uno stato all'altro fare un passo.

Dalla definizione di catena di Markov deriva che per essa la probabilità della transizione del sistema in uno stato di
m passo dipende solo dallo stato in cui il sistema era sul precedente
fare un passo.

dove
probabilità incondizionata che
m passo il sistema sarà nello stato . Per trovare queste probabilità, è necessario conoscere la distribuzione di probabilità iniziale, cioè probabilità di stato
al momento
(inizio del processo) e il cd probabilità di transizione
Markov incatenato
passo.

probabilità di transizione
è chiamata probabilità di transizione condizionata del sistema sul

m passo, nello stato
m passo lei era in grado , cioè.

(43),

dove il primo indice punta al numero dello stato precedente e il secondo indice al numero dello stato successivo del sistema.

Si chiama la catena di Markov omogeneo, se il valore
quelli. probabilità condizionali
non dipendono dal numero di prove, altrimenti dette eterogenee.

Inoltre, considereremo solo catene omogenee, che possono essere specificate usando il vettore - la probabilità degli stati al momento
e matrici ( chiamata matrice di transizione)

(44)
.

Elementi di matrice
hanno le proprietà di base delle matrici quadrate ordinarie e inoltre le seguenti proprietà:

un)
, b)
per ogni fisso
, cioè. la somma degli elementi di ogni riga matrici di transizioneè uguale a uno (come la probabilità di eventi di transizione da uno stato a qualsiasi altro stato possibile - formare un gruppo completo di eventi).

La probabilità dello stato del sistema al passaggio successivo è determinata dalla formula ricorsiva:

In determinate condizioni (ergodicità, omogeneità, assenza di cicli) nella catena di Markov, modalità stazionaria, in cui le probabilità degli stati del sistema non dipendono dal numero di passo. Tali probabilità sono chiamate marginale probabilità (o finali) della catena di Markov:

.

C'è un'affermazione.

Teorema 17.1.Per matrici transizione delle probabilità passi
la formula è valida

(45)
,

Prova. Per la regola della moltiplicazione di due matrici quadrate
ordine che abbiamo

dove

allo stesso tempo, dalla definizione della matrice di transizione, è noto che
per ogni
.

Sommiamo entrambi i lati dell'uguaglianza
per tutti
, e cambiando l'ordine di somma dopo aver applicato la proprietà a) due volte, lo otteniamo
matrice di transizione in due passaggi. Allo stesso modo, ragionando in modo coerente passo dopo passo, otteniamo la nostra affermazione nel caso generale.

Esempio 3 Viene data la matrice di transizione

.

Trova le matrici di probabilità di transizione
.

Basandoci sulla regola della moltiplicazione di due matrici, otteniamo

.

Esercizio. Controlla se l'uguaglianza è vera

Va notato che una catena di Markov discreta finita è un'ulteriore generalizzazione dello schema di Bernoulli, inoltre, al caso dei processi dipendenti; le prove indipendenti sono un caso speciale di una catena di Markov. Qui sotto "evento"

si riferisce allo stato del sistema e "test" si riferisce al cambiamento nello stato del sistema.

Se una " prove” (esperimenti) sono indipendenti, quindi il verificarsi di un determinato evento in qualsiasi esperimento non dipende dai risultati dei test precedentemente eseguiti.

Compiti. a) Sono fornite le matrici di transizione

1.
;

2.
;

3.
.

Trova in ogni caso la matrice
.

Risposte: a) 1.
;

2.
;

3.

c) Sono fornite le matrici di transizione

;
.

Trova
.

Risposte: c) 1.
;2.
;

3.
.

Commento. In generale, discreto catena markoviana
è un processo casuale di Markov il cui spazio degli stati è finito o numerabile e l'insieme degli indici
- l'insieme di tutti gli interi non negativi o di qualche suo sottoinsieme (finito o numerabile). Possiamo parlare di come circa il risultato
esima prova.

Spesso è conveniente identificare lo spazio degli stati del processo con l'insieme di interi non negativi
e in questi casi si dice che è in uno stato , Se
.

Probabilità di colpire una variabile casuale
in uno stato (chiamata probabilità di transizione a un passo), come sopra indicato, è indicato
, cioè.

Questa notazione sottolinea che, nel caso generale, le probabilità di transizione dipendono non solo dagli stati iniziale e finale, ma anche dal momento della transizione.

Nei casi in cui le probabilità di transizione a un passo non dipendono dalla variabile temporale (cioè dal valore , allora si dice che abbia un processo di Markov probabilità di transizione stazionaria. Quindi, per quanto segue, notiamo che esiste un'uguaglianza da cui non dipende , e denota la probabilità di transizione in una prova dallo stato in uno stato .

Di solito le probabilità combinato in una matrice quadrata (finita o numerabile) a seconda del processo in esame:

,

ed è chiamata matrice di Markov, o matrice delle probabilità di transizione catena markoviana.

Nella matrice
i riga rappresenta la distribuzione di probabilità di r.v.
purché
. Se il numero di stati è finito, allora - finale matrice quadrata, il cui ordine (numero di righe) è uguale al numero di stati.

Naturalmente, le probabilità soddisfare le due seguenti condizioni:

un)
,

b)
per ogni fisso

La condizione b) riflette il fatto che ogni processo provoca qualche transizione da uno stato all'altro. Per comodità se ne parla anche transizione e nel caso in cui lo stato rimanga invariato. C'è un'affermazione.

Teorema 17.2.Il processo è completamente definito se vengono fornite le probabilità(46), cioè.

e la distribuzione di probabilità della variabile casuale .

Prova. Mostriamolo per ogni finito come vengono calcolate le probabilità

poiché secondo la formula della probabilità totale, qualsiasi altra probabilità relativa a variabili casuali può essere ottenuta sommando i termini (termini) della forma (47).

Per definizione di probabilità condizionata, abbiamo

Ma dalla definizione di un processo di Markov, otteniamo

Mettendo l'uguaglianza (49) in (48) otteniamo

Continuando questo processo in sequenza, otteniamo:

Il processo è completamente definito. Cosa doveva essere dimostrato.

Processi casuali di Markov.

Supponiamo di dover studiare un "sistema fisico" S(il cui processo di funzionamento può essere descritto in modo esplicito), che può cambiare il suo stato nel tempo (transizioni da uno stato all'altro) in modo casuale e prima sconosciuto. Qualsiasi cosa può essere intesa come un "sistema fisico": un dispositivo tecnico, un gruppo di tali dispositivi, un'impresa, un'industria, un organismo vivente, una popolazione e così via.

Assumiamo che il sistema in esame S può essere descritto da un insieme di possibili stati del sistema precedentemente noti si, determinabile in base alla "natura fisica" del processo di funzionamento del sistema oggetto di studio, ossia .

- io Lo stato del sistema dipende da K parametri.

In una situazione reale, lo stato del sistema può dipendere dalle relazioni di causa ed effetto tra gli stati e i processi che si verificano nel sistema. Cioè, la natura del comportamento del sistema è impressa dalla "preistoria" della natura del comportamento del sistema e da un insieme di alcuni fattori casuali (processi perturbativi esterni o interni). Siamo di fronte a molti "scenari suggeriti" del processo di funzionamento del sistema. E la stessa “scelta” dello “scenario comportamentale” dominante (come si comporterà il sistema in esame) è casuale.

Va notato che il passaggio dallo stato S io per dichiarare S j è stocastico. Iniziamo a considerare il funzionamento del sistema dallo stato iniziale S 0 , che corrisponde all'ora t 0. Cioè, ciò che è accaduto al sistema prima del tempo t 0 si riferisce al "suo passato", alla sua preistoria.

Definizione: Un processo casuale in un sistema è chiamato processo di Markov se per qualsiasi momento di tempo t 0 le caratteristiche probabilistiche del processo in futuro dipendono solo dal suo stato attuale t 0 e non dipendono da quando e come il sistema è arrivato a questo stato.

Assumiamo che lo stato del sistema sia descritto dalla funzione S(t), l'argomento di questa funzione è il tempo t continuamente sono noti i punti temporali del passaggio del sistema da uno stato all'altro t: t 1 <t 2 < … <t n. Inoltre, il passaggio da uno stato all'altro avviene "saltando", quasi istantaneamente.

Siamo giunti alla conclusione che il processo di funzionamento del sistema è associato a una catena di stati discreti: S 1® S 2 ® … ® S n-1® S n (transizione successiva da uno stato all'altro, senza "saltare" attraverso nessuno stato). Cioè, il sistema in esame è descritto da un processo casuale di Markov con stati discreti e tempo continuo.

Sappiamo dalla teoria della probabilità che la funzione di densità di probabilità per n-esimo stato è ricercato come funzione di densità articolare per l'intera "preistoria" del processo del sistema che arriva a questo stato: .

In pratica, i processi di Markov non si verificano nella loro forma pura, ma spesso si ha a che fare con processi per i quali l'influenza della preistoria può essere trascurata. Quando si studiano tali processi, è possibile utilizzare i modelli di Markov.

Considerando il processo come un processo di Markov, la descrizione analitica del modello è semplificata, poiché assumiamo che lo stato del sistema dipenda solo da uno stato precedente: .

Le catene di Markov sono definite da un insieme di stati ben definiti: . A seconda di quando e come si verificano le "transizioni", le catene di Markov sono divise in discrete, per le quali il tempo di transizione da uno stato all'altro è fisso, ed è determinato dalla probabilità di questa transizione, e continue, per le quali gli stati sono discreti, il tempo è continuo e le transizioni da uno stato all'altro avvengono in momenti casuali, non conosciuti in anticipo.

Quando si analizzano processi casuali con stati discreti, è conveniente utilizzare uno schema geometrico, il cosiddetto grafo di stato.

Definizione. Un grafo è una raccolta di molti vertici V e l'insieme delle coppie ordinate di vertici UN={(un 1 un io)( un 2 un j) …), i cui elementi sono detti spigoli G(V,UN).

Gli stati del sistema sono associati ai vertici del grafo e le transizioni da uno stato all'altro sono associate alle corde che indicano la “direzione del flusso” del processo.

Nell'esempio seguente, considereremo una tecnica per studiare le catene di Markov utilizzando un grafico di stato etichettato.

Esempio 1. TEA funzionamento tecnico della vettura.

Un modello TEA semplificato implica la presenza di almeno quattro dei seguenti stati: S 1 - diagnostica dello stato dell'auto, S 2 - lavoro sulla linea (l'auto è in buone condizioni), S 3 - manutenzione, S 4 - risoluzione dei problemi (riparazione).

Il grafico etichettato corrispondente al sistema dato

m ij è la densità di probabilità di transizione dallo stato S io dire S j (si® Sj), dove P ij(D t) è la probabilità che questa transizione avvenga durante l'intervallo di tempo Dt.

Per piccoli valori di Dt, è vera la seguente uguaglianza approssimativa.

Le probabilità di transizione sono determinate dal sistema di equazioni differenziali (Kolmogorov) secondo le seguenti regole:

1) ad ogni vertice è assegnato uno stato corrispondente, descritto dalla probabilità che il sistema sia in esso, quindi il numero di stati determina il numero di equazioni nel sistema;

2) sul lato sinistro dell'equazione - la derivata della probabilità dello stato corrispondente;

3) ci sono tanti termini sul lato destro quante sono le transizioni (rami) nel grafico etichettato associato allo stato dato;

4) ogni elemento del lato destro è uguale al prodotto della densità di probabilità di transizione e la densità di probabilità dello stato da cui è stata effettuata la transizione;

5) sul lato destro con il segno “+” ci sono elementi (sommati) che descrivono l'ingresso del sistema in questo stato, e con il segno “-” elementi (sottrai) che descrivono l'“uscita” del sistema da questo stato;

6) per semplificare la “risolvibilità”, viene introdotta nel sistema un'equazione normalizzante che descrive il gruppo completo di eventi: , dove N è il numero di vertici nel grafico di stato etichettato.

Per il grafico di stato in esame, otteniamo il seguente sistema di equazioni:

Questo sistema di equazioni sarà più facile da risolvere nel caso in cui descriva il processo di funzionamento stazionario del sistema tecnico in studio (di solito l'ingresso del sistema nel modo di funzionamento stazionario richiede da 2 a 4 cicli).

In pratica si ritiene che l'assunzione della stazionarietà del funzionamento del sistema sia giustificata se il tempo del funzionamento del sistema nel suo insieme è di un ordine di grandezza superiore a (20¸40) × cicli di funzionamento del sistema (singolo “successivo” passaggio attraverso i rami del grafico).

La stazionarietà della modalità di funzionamento implica l'uguaglianza a zero delle derivate temporali delle probabilità di stato, cioè .

Il sistema di equazioni si riduce alla seguente forma:

e la sua soluzione non è più difficile.

Il sistema di equazioni secondo Kolmogorov consente di risolvere il problema di trovare le probabilità per la modalità stazionaria (probabilità finali) dalle densità di probabilità note delle transizioni lungo i rami del grafico, nonché il problema inverso, ad es. trovare le densità di probabilità per date probabilità finali.

Esempio #2.

Considera un sistema tecnico S, costituito da due nodi paralleli (due postazioni presso le stazioni di servizio, due riempitrici presso le stazioni di servizio). Assumeremo che le transizioni del sistema da uno stato all'altro avvengano istantaneamente, in momenti casuali. Non appena il nodo si guasta, viene "istantaneamente" per la riparazione e dopo averlo portato in condizioni di lavoro, inizia anche "istantaneamente" ad essere utilizzato.

Riteniamo che questo sistema sia completamente descritto da soli quattro stati: S 0 - entrambi i nodi sono operativi; S 1 - il primo nodo è in riparazione, il secondo è riparabile; S 2 - il secondo nodo è in riparazione, il primo è riparabile; S 3 - entrambi i nodi sono in riparazione.

l 1 , l 2 è la densità di probabilità di fallimento del primo e del secondo post, m 1 , m 2 – densità di probabilità di ripristino rispettivamente del primo e del secondo nodo.

Componiamo un sistema di equazioni differenziali secondo Kolmogorov per le probabilità degli stati di questo sistema.

Per risolvere le equazioni di Kolmogorov e trovare valori numerici per le probabilità degli stati corrispondenti, è necessario impostare le condizioni iniziali.

Assumiamo che all'istante iniziale entrambi i nodi del sistema in studio siano operativi, il sistema sia nello stato S 0 , cioè P 0 (t=0)=1 e tutte le altre probabilità iniziali sono uguali a zero: P 1 (0)=P 2 (0)=P 3 (0)=0.

Questo sistema di equazioni è facilmente risolvibile se il sistema opera in uno stato stazionario e tutti i processi che si verificano in esso sono stazionari.

La stazionarietà del modo di funzionamento implica l'uguaglianza a zero delle derivate temporali delle probabilità di stato, cioè io=1, 2, … , n, , dove nè il numero di stati possibili. E tenendo conto dell'intero gruppo di eventi, l'equazione viene aggiunta

L'ultima, cosiddetta condizione di normalizzazione, permette di escludere una delle equazioni dal sistema...

Risolviamo questo sistema con i seguenti dati: l 1 =1, l 2 =2, m 1 =2, m 2=3. Scriviamo il sistema senza la quarta equazione.

Risolvendoli, otteniamo: P 0 =0,4; P 1 =0,2; P 2 @0,27; P 3 @0,13.

Quelli. in modalità stazionaria, il nostro sistema sarà in uno stato di S 0 - entrambi i nodi sono sani, ecc.

I valori di queste probabilità finali possono aiutare a stimare l'efficienza media del sistema e il carico degli organi di riparazione. Assumiamo che il sistema S capace S 0 genera un reddito di 8 unità convenzionali (c.u.) per unità di tempo, nello stato S 1 3cu, in S 2 5c.u., ma capace S 3 non genera reddito.