Matrice degli stati di transizione di una catena di Markov. Catene di Markov regolari. Notiamo alcune delle sue caratteristiche

da solo, e in parte lo consideriamo dovuto al fatto che la sua presentazione non richiede l’introduzione di un gran numero di nuovi termini.

Consideriamo il problema di un asino che si trova esattamente tra due pagliai: paglia di segale e paglia di grano (Fig. 10.5).

L'asino si trova tra due pagliai: “Segale” e “Grano” (Fig. 10.5). Ogni minuto o si sposta di dieci metri verso il primo pagliaio (con probabilità), o verso il secondo pagliaio (con probabilità), oppure rimane dove si trovava (con probabilità); questo comportamento è chiamato unidimensionale passeggiata casuale. Assumeremo che entrambi i pagliai siano “assorbenti”, nel senso che se un asino si avvicina a uno dei pagliai, rimarrà lì. Conoscendo la distanza tra due pagliai e la posizione iniziale dell'asino, puoi porre diverse domande, ad esempio: in quale pagliaio finirà con maggiore probabilità e quale è il tempo più probabile che impiegherà per arrivarci?

Riso. 10.5.

Per approfondire questo problema, supponiamo che la distanza tra le scosse sia di cinquanta metri e che il nostro asino sia a venti metri dalla scossa “Grano”. Se i luoghi in cui è possibile sostare sono indicati da (- gli shock stessi), allora la sua posizione iniziale può essere specificata dal vettore la cui componente-esima è pari alla probabilità che si trovi inizialmente in . Inoltre, dopo un minuto, le probabilità della sua posizione sono descritte dal vettore e dopo due minuti dal vettore. È chiaro che calcolare direttamente la probabilità che si trovi in un determinato luogo dopo il passare dei minuti diventa difficile. Si è scoperto che il modo più conveniente per farlo è entrare matrice di transizione.

Sia la probabilità che si sposti da a in un minuto. Ad esempio, e. Queste probabilità sono chiamate probabilità di transizione e viene chiamata la matrice - matrice di transizione. Nota che ogni elemento della matrice è non negativo e che la somma degli elementi di una qualsiasi delle righe è uguale a uno. Da tutto ciò ne consegue che - il vettore riga iniziale sopra definito, la posizione dell'asino dopo un minuto è descritta dal vettore riga e dopo minuti - dal vettore. In altre parole, la componente -esima del vettore determina la probabilità che dopo pochi minuti l'asino finisca in .

Questi concetti possono essere generalizzati. Chiamiamo vettore di probabilità un vettore riga, le cui componenti sono tutte non negative e la loro somma dà come risultato uno. Poi matrice di transizioneè definita come una matrice quadrata in cui ogni riga è un vettore di probabilità. Ora possiamo definire una catena di Markov (o semplicemente una catena) come una coppia, dove c'è - matrice di transizione, e c'è un vettore riga. Se consideriamo ogni elemento di come la probabilità di transizione da una posizione all'altra e come il vettore iniziale delle probabilità, allora arriviamo al concetto classico catena di Markov stazionaria discreta, che può essere trovato nei libri sulla teoria della probabilità (vedi Feller V. Introduzione alla teoria della probabilità e alle sue applicazioni. Vol. 1. M.: Mir. 1967) La posizione è solitamente chiamata stato della catena. Descriviamo vari modi le loro classificazioni.

Ci interesserà quanto segue: è possibile passare da uno stato all'altro e, in tal caso, in quanto tempo più breve. Ad esempio, nel problema dell'asino puoi andare da a in tre minuti, ma non puoi andare da a a affatto. Pertanto, non saremo interessati principalmente alle probabilità in sé, ma al fatto che siano positive o meno. Quindi c'è la speranza che tutti questi dati possano essere rappresentati sotto forma di un digramma, i cui vertici corrispondono agli stati e gli archi indicano se è possibile passare da uno stato all'altro in un minuto. Più precisamente, se ogni stato è rappresentato dal vertice corrispondente).

Processo casuale di Markov a stati discreti e tempo discreto chiamata catena di Markov . Per un tale processo, momenti t1, t2 quando il sistema S possono cambiare stato, sono considerati come passi successivi del processo, e l'argomento da cui dipende il processo non è il tempo T, e il numero del passo è 1, 2, K, Il processo casuale in questo caso è caratterizzato da una sequenza di stati S(0), S(1), S(2), S(k), Dove S(0)- stato iniziale del sistema (prima del primo passo); S(1)- stato del sistema dopo il primo passo; S(k)- stato del sistema dopo K esimo passo...

Evento ( S(k) = S i), consistente nel fatto che subito dopo K del passo esimo il sistema è nello stato S i (io= 1, 2,), è un evento casuale. Sequenza di stati S(0), S(1), S(k), può essere considerata come una sequenza di eventi casuali. Questa sequenza casuale di eventi viene chiamata catena di Markov , se per ogni passo la probabilità di transizione da qualsiasi stato S i a qualsiasi S j non dipende da quando e come il sistema è arrivato allo stato S i . Stato iniziale S(0) può essere predeterminato o casuale.

Probabilità degli stati della catena di Markov sono chiamate probabilità Pi(k) cosa viene dopo K passo (e fino a ( K+ 1)esimo) sistema S sarà in grado di S i (io = 1, 2, N). Ovviamente, per qualsiasi K.

Distribuzione di probabilità iniziale della catena di Markovè detta distribuzione di probabilità degli stati all’inizio del processo:

P1 (0), P2 (0), Pi (0), Pn (0).

Nel caso speciale, se lo stato iniziale del sistema S esattamente conosciuto S(0) = S i, quindi la probabilità iniziale Р io (0)= 1 e tutti gli altri sono uguali a zero.

La probabilità di transizione (probabilità di transizione) a K-esimo passo dallo Stato S i in uno stato Sjè detta probabilità condizionata che il sistema S Dopo K l'esimo passo potrà Sj a condizione che immediatamente prima (dopo K- 1 passo) era in uno stato S i.

Poiché il sistema può trovarsi in uno dei N stati, quindi per ogni momento del tempo T deve essere impostato n2 probabilità di transizione P ij, che sono opportunamente rappresentati sotto forma della seguente matrice:

Dove Р ij- probabilità di transizione ad un passo dallo stato S i in uno stato Sj;

P ii- probabilità di ritardo del sistema nello stato S i.

Tale matrice è chiamata matrice di transizione o matrice di probabilità di transizione.

Se le probabilità di transizione non dipendono dal numero del passo (in tempo), ma dipendono solo da quale stato viene effettuata la transizione, allora il corrispondente viene chiamata una catena di Markov omogeneo .

Probabilità di transizione di una catena di Markov omogenea Р ij formare una matrice quadrata di dimensioni n m.

Notiamo alcune delle sue caratteristiche:

1. Ogni linea caratterizza lo stato selezionato del sistema e i suoi elementi rappresentano le probabilità di tutte le possibili transizioni in un passaggio da quello selezionato (da io th) stato, inclusa la transizione in se stessi.

2. Gli elementi delle colonne mostrano le probabilità di tutte le possibili transizioni del sistema da un passaggio a uno dato ( J-f) stato (in altre parole, la riga caratterizza la probabilità che il sistema passi da uno stato, la colonna - a uno stato).

3. La somma delle probabilità di ciascuna riga è uguale a uno, poiché le transizioni formano un gruppo completo di eventi incompatibili:

4. Lungo la diagonale principale della matrice delle probabilità di transizione ci sono le probabilità P ii che il sistema non uscirà dallo Stato S i, ma ci resterà.

Se per una catena di Markov omogenea vengono fornite la distribuzione di probabilità iniziale e la matrice delle probabilità di transizione, allora le probabilità degli stati del sistema Pi(k) (io, j= 1, 2, N) sono determinati dalla formula ricorrente:

Esempio 1. Consideriamo il processo di funzionamento del sistema: un'auto. Lascia che l'auto (sistema) durante un turno (giorno) sia in uno dei due stati: riparabile ( S1) e difettoso ( S2). Il grafico dello stato del sistema è mostrato in Fig. 3.2.

Riso. 3.2.Grafico dello stato del veicolo

Come risultato delle osservazioni di massa del funzionamento del veicolo, è stata compilata la seguente matrice delle probabilità di transizione:

Dove Pag. 11= 0,8 - probabilità che l'auto rimanga in buone condizioni;

Pag. 12= 0,2 - probabilità che l'auto passi dallo stato “buono” allo stato “difettoso”;

Pag. 21= 0,9 - probabilità che l'auto passi dallo stato “difettoso” allo stato “buono”;

Pag.22= 0,1 - probabilità che l'auto rimanga nello stato “difettoso”.

Viene fornito il vettore delle probabilità iniziali degli stati dell'auto, ovvero P1 (0)= 0 e R2 (0)=1.

È necessario determinare le probabilità degli stati dell'auto dopo tre giorni.

Utilizzando la matrice delle probabilità di transizione e la formula (3.1), determiniamo le probabilità degli stati Pi(k) dopo il primo passo (dopo il primo giorno):

P1 (1) = P1 (0)×P11 + P2 (0)×P21 = 0?0,8 + 1?0,9 = 0,9;

P2(1) = P1 (0)×P12 + P2 (0)×P22 = 0?0,2 + 1?0,1 = 0,2.

Le probabilità degli stati dopo il secondo passaggio (dopo il secondo giorno) sono le seguenti:

P1 (2) = P1 (1)×P11 + P2 (1)×P21= 0,9×0,8 + 0,1×0,9 = 0,81;

= 0,9×0,2 + 0,1×0,1 = 0,19.

Le probabilità degli stati dopo il terzo passaggio (dopo il terzo giorno) sono uguali:

P1 (3) = P1 (2)×P11 + P2 (2)×P21= 0,81×0,8 + 0,19×0,9 = 0,819;

= 0,81×0,2 + 0,19×0,1 = 0,181.

Pertanto, dopo il terzo giorno l'auto sarà in buone condizioni con una probabilità di 0,819 e in uno stato “difettoso” con una probabilità di 0,181.

Esempio 2. Durante il funzionamento, un computer può essere considerato come un sistema fisico S, che a seguito del controllo potrebbe ritrovarsi in uno dei seguenti stati: S1- Il computer sia pienamente operativo; S2- Il computer ha dei difetti nella RAM, in cui può risolvere i problemi; S3- Il computer presenta difetti significativi e può risolvere una classe limitata di problemi; S4- Il computer è completamente guasto.

Nel momento iniziale, il computer è pienamente operativo (state S1). Il computer viene controllato a orari prestabiliti t1, t2, t3. Il processo che si svolge nel sistema S, possono essere considerati omogenei catena di Markov con tre passaggi (primo, secondo, terzo controllo informatico). La matrice delle probabilità di transizione ha la forma

Determinare le probabilità degli stati del computer dopo tre controlli.

Soluzione. Il grafico di stato ha la forma mostrata in Fig. 3.3. Accanto a ciascuna freccia c'è la probabilità di transizione corrispondente. Probabilità dello stato iniziale P1 (0) = 1, P2(0) = P3 (0) = P4 (0) = 0.

Riso. 3.3. Grafico dello stato del computer

Usando la formula (3.1), tenendo conto nella somma delle probabilità solo quegli stati da cui è possibile una transizione diretta a un dato stato, troviamo:

P1(1) = P1(0)×P11= 1×0,3 = 0,3;

P2(1) = P1(0)×P12= 1×0,4 = 0,4;

P3 (1) = P1 (0)×P13= 1×0,1 = 0,1;

P4 (1) = P1 (0)×P14= 1×0,2 = 0,2;

P1 (2) = P1 (1)×P11= 0,3×0,3 = 0,09;

P2 (2) = P1 (1)×P12 + P2 (1)×P22= 0,3×0,4 + 0,4×0,2 = 0,20;

P3 (2) = P1 (1)×P13 + P2 (1)×P23 + P3 (1)×P33 = 0,27;

P4 (2) = P1 (1)×P14 + P2 (1)×P24 + P3 (1)×P34 + P4 (1)×P44 = 0,44;

P1 (3) = P1 (2)×P11= 0,09×0,3 = 0,027;

P2 (3) = P1 (2)×P12 + P2 (2)×P22= 0,09×0,4 + 0,20×0,2 = 0,076;

P3 (3) = P1 (2)×P13 + P2 (2)×P23 + P3 (2)×P33 = 0,217;

P4 (3) = P1 (2)×P14 + P2 (2)×P24 + P3 (2)×P34 + P4 (2)×P44 = 0,680.

Quindi, le probabilità degli stati del computer dopo tre controlli sono le seguenti: P1 (3) = 0,027; P2 (3) = 0,076; P3 (3) = 0,217; P4 (3) = 0,680.

Compito 1. Un certo bersaglio viene colpito con quattro colpi alla volta t1, t2, t3, t4.

Possibili stati del sistema: S1- il bersaglio è illeso; S2- il bersaglio è leggermente danneggiato; S3- l'obiettivo ha subito danni significativi; S4- il bersaglio è completamente colpito. Nel momento iniziale il bersaglio è in uno stato S1. Determina le probabilità degli stati target dopo quattro colpi se la matrice delle probabilità di transizione ha la forma.

Catene di Markov

introduzione

§ 1. Catena di Markov

§ 2. Catena di Markov omogenea. Probabilità di transizione. Matrice di transizione

§3. Uguaglianza di Markov

§4. Distribuzione stazionaria. Teorema della probabilità limite

§5. Dimostrazione del teorema sulle probabilità limite in una catena di Markov

§6. Applicazioni delle catene di Markov

Conclusione

Elenco della letteratura usata

introduzione

Il nostro tema lavoro del corso Catene di Markov. Le catene di Markov prendono il nome dall'eminente matematico russo Andrei Andreevich Markov, che lavorò a lungo sui processi casuali e diede un contributo importante allo sviluppo di questo campo. Recentemente, puoi sentire parlare dell'uso delle catene di Markov in una varietà di aree: moderne tecnologie web, quando si analizzano testi letterari o anche quando si sviluppano tattiche per una squadra di calcio. Chi non sa cosa siano le catene di Markov può avere la sensazione che si tratti di qualcosa di molto complesso e quasi incomprensibile.

No, è proprio il contrario. Una catena di Markov è uno dei casi più semplici di sequenza di eventi casuali. Ma, nonostante la sua semplicità, spesso può essere utile anche quando si descrivono fenomeni piuttosto complessi. Una catena di Markov è una sequenza di eventi casuali in cui la probabilità di ciascun evento dipende solo da quello precedente, ma non dagli eventi precedenti.

Prima di approfondire, dobbiamo considerare alcune questioni ausiliarie generalmente note, ma assolutamente necessarie per un’ulteriore esposizione.

L'obiettivo del mio corso è studiare più in dettaglio le applicazioni delle catene di Markov, dell'enunciazione dei problemi e dei problemi di Markov.

§1. catena di Markov

Immaginiamo che venga eseguita una sequenza di test.

Definizione. Una catena di Markov è una sequenza di prove in ciascuna delle quali compare uno ed uno solo degli eventi incompatibili del gruppo completo, e la probabilità condizionata che l'evento si verifichi nella esima prova è , purché il fatto sia avvenuto nel IV processo , non dipende dai risultati dei test precedenti.

Ad esempio, se la sequenza delle prove forma una catena di Markov e il gruppo completo è costituito da quattro eventi incompatibili, ed è noto che l'evento si è verificato nella sesta prova, allora la probabilità condizionata che l'evento si verifichi nella settima prova non dipende su quali eventi sono apparsi nella prima, seconda, ..., quinta prova.

Si noti che i test indipendenti sono un caso speciale di catena di Markov. Infatti, se i test sono indipendenti, il verificarsi di un determinato evento in qualsiasi test non dipende dai risultati dei test eseguiti in precedenza. Ne consegue che il concetto di catena di Markov è una generalizzazione del concetto di prove indipendenti.

Spesso, quando presentano la teoria delle catene di Markov, aderiscono a una terminologia diversa e parlano di un certo sistema fisico, che in ogni momento del tempo si trova in uno degli stati: , e cambia il suo stato solo in momenti separati nel tempo, quello ovvero, il sistema si sposta da uno stato all'altro (ad esempio, da a ). Per le catene di Markov, la probabilità di andare in qualsiasi stato è al momento dipende solo dallo stato in cui si trovava il sistema in quel momento e non cambia perché i suoi stati in momenti precedenti diventano noti. Inoltre, in particolare, dopo il test il sistema può rimanere nello stesso stato (“spostarsi” da stato a stato).

Per illustrare, consideriamo un esempio.

Esempio 1. Immaginiamo che una particella situata su una linea retta si muova lungo questa linea retta sotto l'influenza di shock casuali che si verificano in momenti . Una particella può essere localizzata in punti con coordinate intere: ; Le pareti riflettenti si trovano nei punti. Ogni spinta sposta la particella verso destra con probabilità e verso sinistra con probabilità, a meno che la particella non sia vicina a un muro. Se la particella è vicino al muro, qualsiasi spinta la sposta di un'unità all'interno dello spazio tra i muri. Qui vediamo che questo esempio di particella che cammina è una tipica catena di Markov.

Pertanto, gli eventi sono chiamati stati del sistema e i test sono chiamati cambiamenti nei suoi stati.

Definiamo ora una catena di Markov utilizzando una nuova terminologia.

Una catena di Markov a tempo discreto è un circuito i cui stati cambiano in determinati istanti fissi.

Una catena di Markov a tempo continuo è una catena i cui stati cambiano in ogni istante casuale possibile nel tempo.

§2. Catena di Markov omogenea. Probabilità di transizione. Matrice di transizione

Definizione. Una catena di Markov si dice omogenea se la probabilità condizionata (transizione da stato a stato) non dipende dal numero di prove. Pertanto, invece di scrivere semplicemente .

Esempio 1. Passeggiata casuale. Sia presente una particella materiale su una linea retta in un punto con coordinate intere. In determinati momenti la particella subisce degli shock. Sotto l'influenza di una spinta, la particella si sposta con probabilità di un'unità a destra e con probabilità di un'unità a sinistra. È chiaro che la posizione (coordinata) di una particella dopo uno shock dipende da dove si trovava la particella dopo lo shock immediatamente precedente e non dipende da come si è spostata sotto l'influenza di altri shock precedenti.

Pertanto, una passeggiata casuale è un esempio di catena di Markov omogenea con tempo discreto.

La probabilità di transizione è la probabilità condizionata che dallo stato (in cui il sistema si è trovato a seguito di qualche test, indipendentemente dal numero) a seguito del test successivo il sistema si sposterà nello stato.

Pertanto, nella designazione, il primo indice indica il numero dello stato precedente e il secondo indica il numero dello stato successivo. Ad esempio, è la probabilità di transizione dal secondo stato al terzo.

Sia finito il numero degli stati e uguale a .

La matrice di transizione di un sistema è una matrice che contiene tutte le probabilità di transizione di questo sistema:

Poiché ogni riga della matrice contiene le probabilità di eventi (transizione dallo stesso stato a qualsiasi stato possibile) che formano un gruppo completo, la somma delle probabilità di questi eventi è uguale a uno. In altre parole, la somma delle probabilità di transizione di ciascuna riga della matrice di transizione è pari a uno:

Facciamo un esempio della matrice di transizione di un sistema che può trovarsi in tre stati; la transizione da stato a stato avviene secondo lo schema di una catena di Markov omogenea; le probabilità di transizione sono date dalla matrice:

Qui vediamo che se il sistema fosse in uno stato, allora dopo aver cambiato stato in un unico passaggio, rimarrà nello stesso stato con probabilità 0,5, rimarrà nello stesso stato con probabilità 0,5, entrerà nello stato con probabilità 0,2, quindi dopo la transizione potrebbe finire negli stati; non può spostarsi da uno stato all'altro. L'ultima riga della matrice ci mostra che da uno stato si passa a uno qualsiasi degli stati possibili con la stessa probabilità di 0,1.

Sulla base della matrice di transizione del sistema, è possibile costruire un cosiddetto grafico di stato del sistema; è anche chiamato grafico di stato etichettato. Ciò è utile per una rappresentazione visiva del circuito. Diamo un'occhiata all'ordine di costruzione dei grafici utilizzando un esempio.

Esempio 2. Utilizzando una data matrice di transizione, costruisci un grafico di stato.

Perché matrice del quarto ordine, quindi, di conseguenza, il sistema ha 4 stati possibili.

Il grafico non indica le probabilità che il sistema passi da uno stato allo stesso. Quando si considerano sistemi specifici, è conveniente costruire prima un grafico di stato, quindi determinare la probabilità di transizione del sistema da uno stato allo stesso (in base al requisito che la somma degli elementi delle righe della matrice sia uguale a uno), e quindi costruire una matrice di transizione del sistema.

§3. Uguaglianza di Markov

Definizione. Indichiamo con la probabilità che a seguito di passaggi (test) il sistema si sposti da uno stato all'altro . Ad esempio, è la probabilità di transizione in 10 passi dal secondo stato al quinto.

Sottolineiamo che a otteniamo le probabilità di transizione

Poniamoci un compito: conoscere le probabilità di transizione, trovare le probabilità del sistema di passare da uno stato all'altro gradualmente.

A questo scopo introduciamo in considerazione uno stato intermedio (tra e ). In altre parole, assumeremo che dallo stato iniziale per passi il sistema si sposterà ad uno stato intermedio con probabilità , dopodiché nei rimanenti passi dallo stato intermedio si sposterà allo stato finale con probabilità .

Usando la formula della probabilità totale, otteniamo

. (1)

Questa formula è chiamata uguaglianza di Markov.

Spiegazione. Introduciamo la seguente notazione:

– l'evento che ci interessa (a passi il sistema passerà dallo stato iniziale allo stato finale), quindi, ; − ipotesi (per passi il sistema si sposterà dallo stato iniziale a quello intermedio), quindi, − probabilità condizionata di accadimento, a condizione che l'ipotesi si sia verificata (per passi il sistema si sposterà dallo stato intermedio allo stato finale), Perciò,

Secondo la formula della probabilità totale,

()

Oppure nella notazione da noi adottata

che coincide con la formula di Markov (1).

Conoscendo tutte le probabilità di transizione, cioè conoscendo la matrice di transizione da stato a stato in un passaggio, è possibile trovare le probabilità di transizione da stato a stato in due passaggi, e quindi la matrice di transizione stessa; utilizzando una matrice nota, puoi trovare la matrice di transizione da stato a stato in tre passaggi, ecc.

Infatti, inserendo l'uguaglianza di Markov

catena di segni probabilità casuale

(2)

Quindi, utilizzando la formula (2) puoi trovare tutte le probabilità e, quindi, la matrice stessa. Poiché l'uso diretto della formula (2) risulta noioso e il calcolo matriciale porta all'obiettivo più velocemente, scriverò le relazioni derivanti da (2) in forma matriciale:

Inserendo la (1), otteniamo analogamente

Generalmente

Teorema 1. Per qualsiasi s, t

(3)

Prova. Calcoliamo la probabilità utilizzando la formula della probabilità totale (), mettendo

Dalle uguaglianze

Quindi dalle uguaglianze (4) e

otteniamo l'enunciato del teorema.

Definiamo la matrice. Nella notazione matriciale (3) ha la forma

Da allora dov'è la matrice delle probabilità di transizione. Dalla (5) segue

(6)

I risultati ottenuti nella teoria delle matrici consentono di utilizzare la formula (6) per calcolare e studiare il loro comportamento quando

Esempio 1. Matrice di transizione specificata Trova la matrice di transizione

Soluzione. Usiamo la formula

Moltiplicando le matrici otteniamo infine:

§4. Distribuzione stazionaria. Teorema della probabilità limite

La distribuzione di probabilità in un momento arbitrario può essere trovata utilizzando la formula della probabilità totale

(7)

Potrebbe risultare che non dipenda dal tempo. Chiamiamo distribuzione stazionaria vettore , soddisfacendo le condizioni

dove sono le probabilità di transizione.

Se in una catena di Markov quindi per qualsiasi

Questa affermazione segue per induzione da (7) e (8).

Presentiamo la formulazione del teorema sulle probabilità limite per un'importante classe di catene di Markov.

Teorema 1. Se per alcuni >0 tutti gli elementi della matrice sono positivi, allora per qualsiasi , for

, (9)

Dove distribuzione stazionaria con una costante che soddisfa la disuguaglianza 0< H <1.

Da allora secondo le condizioni del teorema, da qualsiasi stato puoi arrivare a qualsiasi stato nel tempo con una probabilità positiva. Le condizioni del teorema escludono catene in un certo senso periodiche.

Se le condizioni del Teorema 1 sono soddisfatte, allora la probabilità che il sistema si trovi in un certo stato limite non dipende dalla distribuzione iniziale. Infatti, dalle (9) e (7) segue che per qualsiasi distribuzione iniziale ,

Consideriamo alcuni esempi di catene di Markov per le quali le condizioni del Teorema 1 non sono soddisfatte. Non è difficile verificare che tali esempi siano esempi. Nell'esempio, le probabilità di transizione hanno dei limiti, ma questi limiti dipendono dallo stato iniziale. In particolare, quando

In altri esempi, gli intervalli di probabilità ovviamente non esistono.

Troviamo la distribuzione stazionaria nell'esempio 1. Dobbiamo trovare il vettore condizioni soddisfacenti (8):

;

Quindi esiste una distribuzione stazionaria, ma non tutti i vettori di coordinate sono positivi.

Per lo schema polinomiale sono state introdotte variabili casuali pari al numero di risultati di un dato tipo. Introduciamo quantità simili per le catene di Markov. Sia il numero di volte in cui il sistema entra nello stato nel tempo . Quindi la frequenza con cui il sistema colpisce lo Stato. Utilizzando le formule (9), possiamo dimostrare che quando si avvicina . Per fare ciò, è necessario ottenere formule asintotiche per e e utilizzare la disuguaglianza di Chebyshev. Ecco la derivazione della formula per . Rappresentiamolo nella forma

(10)

dove, se e altrimenti. Perché

quindi, utilizzando la proprietà dell'aspettativa matematica e della formula (9), otteniamo

In virtù del Teorema 1, il triplo termine a destra di questa uguaglianza è una somma parziale di una serie convergente. Mettendo , noi abbiamo

Perché il

Dalla formula (11), in particolare, risulta che

È inoltre possibile ottenere una formula da utilizzare per calcolare la varianza.

§5. Dimostrazione del teorema sulle probabilità limite in una catena di Markov

Dimostriamo innanzitutto due lemmi. Mettiamo

Lemma 1. Ci sono limiti per chiunque

Prova. Usando l'equazione (3) con otteniamo

Pertanto, le sequenze sono sia monotone che limitate. Ciò implica l’enunciato del Lemma 1.

Lemma 2. Se le condizioni del Teorema 2 sono soddisfatte, allora ci sono costanti , tale che

Per ogni

dove , significa somma di tutto ciò che è positivo, e somma di tutto il resto . Da qui

. (12)

Poiché nelle condizioni del Teorema 1 le probabilità di transizione per tutti , quindi per qualsiasi

E a causa del numero finito di stati

Valutiamo ora la differenza . Usando l'equazione (3) con , , otteniamo

Da qui, utilizzando (8)-(10), troviamo

Combinando questa relazione con la disuguaglianza (14), otteniamo l'enunciato del lemma.

Vai alla dimostrazione del teorema. Poiché le sequenze sono monotone, allora

0<. (15)

Da questo e dal Lemma 1 troviamo

Pertanto, quando ottieni e

La positività deriva dalla disuguaglianza (15). Passando al limite in e nell'equazione (3), otteniamo che soddisfa l'equazione (12). Il teorema è stato dimostrato.

§6. Applicazioni delle catene di Markov

Le catene di Markov servono come una buona introduzione alla teoria dei processi casuali, vale a dire la teoria delle successioni semplici di una famiglia di variabili casuali, solitamente dipendenti da un parametro, che nella maggior parte delle applicazioni svolge il ruolo del tempo. È destinato principalmente a descrivere completamente il comportamento sia a lungo termine che locale di un processo. Ecco alcune delle questioni più studiate a questo proposito.

Moto browniano e sue generalizzazioni: processi di diffusione e processi con incrementi indipendenti . La teoria dei processi casuali ha contribuito ad approfondire il collegamento tra la teoria della probabilità, la teoria degli operatori e la teoria delle equazioni differenziali, che, tra le altre cose, era importante per la fisica e altre applicazioni. Le applicazioni includono processi di interesse per la matematica attuariale (assicurativa), la teoria delle code, la genetica, il controllo del traffico, la teoria dei circuiti elettrici e la teoria dell'inventario.

Martingale . Questi processi preservano abbastanza proprietà delle catene di Markov da far sì che importanti teoremi ergodici rimangano validi per loro. Le martingale differiscono dalle catene di Markov in quanto quando lo stato attuale è noto, solo l'aspettativa matematica del futuro, ma non necessariamente la distribuzione di probabilità stessa, non dipende dal passato. Oltre ad essere un importante strumento di ricerca, la teoria della martingala ha arricchito la teoria dei processi casuali che si verificano nella statistica, nella teoria della fissione nucleare, nella genetica e nella teoria dell'informazione con nuovi teoremi limite.

Processi stazionari . Il più antico teorema ergodico conosciuto, come notato sopra, può essere interpretato come un risultato che descrive il comportamento limitante di un processo casuale stazionario. Un tale processo ha la proprietà che tutte le leggi probabilistiche che soddisfa rimangono invarianti rispetto agli spostamenti temporali. Il teorema ergodico, formulato inizialmente dai fisici come ipotesi, può essere rappresentato come l'affermazione che, in determinate condizioni, la media dell'insieme coincide con la media temporale. Ciò significa che la stessa informazione può essere ottenuta dall'osservazione a lungo termine di un sistema e dall'osservazione simultanea (e istantanea) di molte copie indipendenti dello stesso sistema. La legge dei grandi numeri non è altro che un caso particolare del teorema ergodico di Birkhoff. L'interpolazione e la previsione del comportamento dei processi gaussiani stazionari, intesi in senso lato, costituiscono un'importante generalizzazione della teoria classica dei minimi quadrati. La teoria dei processi stazionari è uno strumento di ricerca necessario in molti campi, ad esempio nella teoria della comunicazione, che si occupa dello studio e della realizzazione di sistemi che trasmettono messaggi in presenza di rumore o interferenze casuali.

I processi di Markov (processi senza effetti collaterali) svolgono un ruolo enorme nella modellazione dei sistemi di code (QS), nonché nella modellazione e nella scelta di una strategia per la gestione dei processi socioeconomici che si verificano nella società.

La catena di Markov può essere utilizzata anche per generare testi. Vengono forniti diversi testi come input, quindi viene costruita una catena di Markov con le probabilità che una parola segua l'altra e il testo risultante viene creato sulla base di questa catena. Il giocattolo risulta essere molto divertente!

Conclusione

Pertanto, nel nostro lavoro del corso parlavamo del circuito della catena di Markov. Abbiamo imparato in quali aree e come viene utilizzato, test indipendenti hanno dimostrato il teorema sulle probabilità limite in una catena di Markov, hanno fornito esempi per una catena di Markov tipica e omogenea, nonché per trovare la matrice di transizione.

Abbiamo visto che il progetto della catena di Markov è una generalizzazione diretta del progetto di test indipendente.

Elenco della letteratura usata

1. Chistyakov V.P. Corso di teoria della probabilità. 6a ed., riv. − San Pietroburgo: Casa editrice Lan, 2003. − 272 p. − (Libro di testo per le università. Letteratura speciale).

2. Gnedenko B.V. Corso di teoria della probabilità.

3. Gmurman V.E. Teoria della probabilità e statistica matematica.

4. Ventzel E.S. Teoria della probabilità e sue applicazioni ingegneristiche.

5. Kolmogorov A.N., Zhurbenko I.G., Prokhorov A.V. Introduzione alla teoria della probabilità. − Mosca-Izhevsk: Istituto di ricerca informatica, 2003, 188 pp.

6. Katz M. Probabilità e questioni correlate in fisica.

(Andrei Andreevich Markov (1856-1922) - matematico, accademico russo)

Definizione. Viene chiamato un processo che avviene in un sistema fisico Markovsky, se in qualsiasi momento la probabilità di qualsiasi stato del sistema in futuro dipende solo dallo stato del sistema nel momento attuale e non dipende da come il sistema è arrivato a questo stato.

Definizione. catena di Markov chiamata una sequenza di prove, in ciascuna delle quali solo una delle K eventi incompatibili Ai da tutto il gruppo. In questo caso, la probabilità condizionata Pij(S) cosa c'è dentro S-esimo test arriverà l'evento Ag a condizione che in ( S – 1 ) – l'evento si è verificato durante il test Ai, non dipende dai risultati dei test precedenti.

Le prove indipendenti sono un caso speciale di catena di Markov. Gli eventi vengono chiamati Stati del sistema e test - Cambiamenti negli stati del sistema.

In base alla natura dei cambiamenti negli stati, le catene di Markov possono essere divise in due gruppi.

Definizione. Catena di Markov a tempo discreto Si chiama circuito i cui stati cambiano in determinati istanti fissi nel tempo. Catena di Markov a tempo continuo Si chiama un circuito i cui stati possono cambiare in qualsiasi momento casuale nel tempo.

Definizione. Omogeneo Si chiama catena di Markov se la probabilità condizionata Pij transizione del sistema dallo Stato IO Nello stato J non dipende dal numero del test. Probabilità Pij chiamato Probabilità di transizione.

Supponiamo che il numero di stati sia finito e uguale K.

Quindi la matrice composta dalle probabilità di transizione condizionate sarà simile a:

Questa matrice si chiama Matrice di transizione del sistema.

Poiché ogni riga contiene le probabilità di eventi che formano un gruppo completo, è ovvio che la somma degli elementi di ogni riga della matrice è pari a uno.

Sulla base della matrice di transizione del sistema, si può costruire il cosiddetto Grafico dello stato del sistema, è anche chiamato Grafico di stato etichettato. Ciò è utile per una rappresentazione visiva del circuito. Diamo un'occhiata all'ordine di costruzione dei grafici utilizzando un esempio.

Esempio. Utilizzando una data matrice di transizione, costruisci un grafico di stato.

Poiché la matrice è del quarto ordine, il sistema ha rispettivamente 4 stati possibili.

Permettere Pij(N) – la probabilità che come risultato N test il sistema andrà dallo Stato IO in uno stato J, R – qualche stato intermedio tra gli stati IO E J. Probabilità di transizione da uno stato all'altro Pij(1) = Pij.

Poi la probabilità Pij(N) può essere trovato utilizzando una formula chiamata Uguaglianza di Markov:

Qui T– il numero di passaggi (prove) durante i quali il sistema è passato dallo stato IO Nello stato R.

In linea di principio, l'uguaglianza di Markov non è altro che una formula leggermente modificata per la probabilità totale.

Conoscere le probabilità di transizione (cioè conoscere la matrice di transizione P1), possiamo trovare le probabilità di transizione da uno stato all'altro in due passaggi Pij(2) , cioè matrice P2, sapendolo, trova la matrice P3, eccetera.

L'applicazione diretta della formula ottenuta sopra non è molto conveniente, quindi è possibile utilizzare le tecniche del calcolo matriciale (dopotutto, questa formula non è altro che una formula per moltiplicare due matrici).

Allora in forma generale possiamo scrivere:

In generale, questo fatto è solitamente formulato sotto forma di teorema, tuttavia la sua dimostrazione è abbastanza semplice, quindi non lo darò.

Esempio. Matrice di transizione specificata P1. Trova la matrice P3.

Definizione. Vengono chiamate matrici le cui somme degli elementi di tutte le righe sono uguali a uno Stocastico. Se per alcuni P tutti gli elementi della matrice Rp non sono uguali a zero, viene chiamata tale matrice di transizione Regolare.

In altre parole, le matrici di transizione regolari definiscono una catena di Markov attraverso la quale è possibile raggiungere ciascuno stato P passi da qualsiasi stato. Tali catene di Markov vengono anche chiamate Regolare.

Teorema. (teorema della probabilità limite) Sia data una catena di Markov regolare con n stati e P sia la sua matrice di probabilità di transizione. Allora esiste un limite ed una matrice P(¥ ) ha la forma:

Processo Markoviano- un processo casuale che si verifica nel sistema, che ha la proprietà: per ogni istante di tempo t 0, la probabilità di qualsiasi stato del sistema nel futuro (a t>t 0) dipende solo dal suo stato nel presente (a t = t 0) e non dipende da quando e come il sistema è arrivato a questo stato (cioè da come si è sviluppato il processo nel passato).

Nella pratica ci imbattiamo spesso in processi casuali che, con vari gradi di approssimazione, possono essere considerati markoviani.

Qualsiasi processo di Markov è descritto utilizzando probabilità di stato e probabilità di transizione.

Probabilità degli stati P k (t) di un processo di Markov sono le probabilità che il processo (sistema) casuale al tempo t sia nello stato S k:

Probabilità di transizione di un processo di Markov sono le probabilità di transizione di un processo (sistema) da uno stato all'altro:

Viene chiamato il processo di Markov omogeneo, se le probabilità di transizione per unità di tempo non dipendono da dove avviene la transizione sull'asse del tempo.

Il processo più semplice è catena di Markov– Processo casuale di Markov con tempo discreto e insieme finito discreto di stati.

Quando analizzate, le catene di Markov lo sono grafico di stato, su cui tutti gli stati della catena (sistema) e le probabilità diverse da zero sono contrassegnati in un unico passaggio.

Una catena di Markov può essere pensata come se un punto che rappresenta un sistema si muovesse casualmente attraverso un grafico di stato, trascinandosi da uno stato all'altro in un passo o rimanendo nello stesso stato per diversi passi.

Le probabilità di transizione di una catena di Markov in un passo sono scritte sotto forma di una matrice P=||P ij ||, che è chiamata matrice delle probabilità di transizione o semplicemente matrice di transizione.

Esempio: l'insieme degli stati degli studenti della specialità è il seguente:

S 1 - matricola;

S 2 – secondo anno…;

S 5 – Studente del 5° anno;

S 6 – specialista laureato in un'università;

S 7 – una persona che ha studiato all'università, ma non si è laureata.

Dallo stato S 1 entro un anno sono possibili transizioni allo stato S 2 con probabilità r 1 ; S 1 con probabilità q 1 e S 7 con probabilità p 1, e:

r1 +q1 +p1 =1.

Costruiamo un grafico di stato per questa catena di Markov e contrassegniamolo con probabilità di transizione (diverse da zero).

Creiamo una matrice di probabilità di transizione:

Le matrici di transizione hanno le seguenti proprietà:

Tutti i loro elementi sono non negativi;

Le loro somme di riga sono uguali a uno.

Le matrici con questa proprietà sono dette stocastiche.

Le matrici di transizione consentono di calcolare la probabilità di qualsiasi traiettoria della catena di Markov utilizzando il teorema della moltiplicazione della probabilità.

Per catene di Markov omogenee, le matrici di transizione non dipendono dal tempo.

Quando si studiano le catene di Markov, quelle di maggiore interesse sono:

Probabilità di transizione in m passi;

Distribuzione sugli stati al passo m→∞;

Tempo medio trascorso in un determinato stato;

Tempo medio per tornare in questo stato.

Consideriamo una catena di Markov omogenea con n stati. Per ottenere la probabilità di transizione dallo stato S i allo stato S j in m passi, secondo la formula della probabilità totale, si dovrebbero sommare i prodotti della probabilità di transizione dallo stato Si allo stato intermedio Sk in l passi per la probabilità di transizione da Sk a Sj nei rimanenti passi m-l, cioè .

Questa relazione vale per tutti i=1,..., n; j=1, …,n può essere rappresentato come un prodotto di matrici:

P(m)=P(l)*P(m-l).

Quindi abbiamo:

P(2)=P(1)*P(1)=P2

P(3)=P(2)*P(1)=P(1)*P(2)=P 3, ecc.

P(m)=P(m-1)*P(1)=P(1)*P(M-1)=Pm ,

che rende possibile trovare le probabilità di transizione tra stati in un numero qualsiasi di passaggi, conoscendo la matrice di transizione in un passaggio, vale a dire P ij (m) - un elemento della matrice P(m) è la probabilità di passare dallo stato S i per enunciare S j in m passi.

Esempio: Il tempo in una certa regione alterna pioggia e asciutto per lunghi periodi di tempo. Se piove, allora con probabilità 0,7 pioverà il giorno dopo; Se il tempo è secco in un determinato giorno, con una probabilità di 0,6 persisterà il giorno successivo. È noto che mercoledì il tempo è stato piovoso. Qual è la probabilità che venerdì prossimo piova?

Scriviamo tutti gli stati della catena di Markov in questo problema: D – tempo piovoso, C – tempo secco.

Costruiamo un grafico di stato:

Risposta: p 11 = p (D tallone | D avg) = 0,61.

I limiti di probabilità р 1 (m), р 2 (m),…, р n (m) per m→∞, se esistono, si chiamano probabilità limitanti degli stati.

Si può dimostrare il seguente teorema: se in una catena di Markov si può passare da + ogni stato (in un dato numero di passi) all'altro, allora le probabilità limite degli stati esistono e non dipendono dallo stato iniziale del sistema .

Pertanto, poiché m→∞, nel sistema si stabilisce un certo regime stazionario limitante, in cui ciascuno degli stati si verifica con una certa probabilità costante.

Il vettore p, composto da probabilità marginali, deve soddisfare la relazione: p=p*P.

Tempo medio trascorso nello stato S i per il tempo T è uguale a pi *T, dove p i - probabilità marginale dello stato S i . Tempo medio per tornare allo stato S i è uguale a .

Esempio.

Per molti problemi economici è necessario conoscere l'alternanza degli anni con determinati valori delle portate annuali dei fiumi. Naturalmente questa alternanza non può essere determinata in modo assolutamente preciso. Per determinare le probabilità di alternanza (transizione), dividiamo i flussi introducendo quattro gradazioni (stati del sistema): prima (flusso più basso), seconda, terza, quarta (flusso più alto). Per chiarezza, assumeremo che la prima gradazione non sia mai seguita dalla quarta, e la quarta dalla prima a causa dell'accumulo di umidità (nel terreno, nel serbatoio, ecc.). Le osservazioni hanno dimostrato che in una determinata regione sono possibili altre transizioni e:

a) dalla prima gradazione si può passare a ciascuna di quelle intermedie il doppio delle volte che alla prima, cioè

p11 =0,2; p12 =0,4; p13 =0,4; p14 =0;

b) dalla quarta gradazione i passaggi alla seconda e alla terza gradazione avvengono quattro e cinque volte più spesso dei ritorni come nella seconda, cioè

difficile, cioè

nel quarto, cioè

p41 =0; p42 =0,4; p43 =0,5; p44 =0,1;

c) dalla seconda alle altre gradazioni può essere solo meno frequente: nella prima - due volte meno, nella terza del 25%, nella quarta - quattro volte meno spesso del passaggio alla seconda, ad es.

p21 =0,2;p22 =0,4; p23 =0,3; p24 =0,1;

d) dal terzo grado, il passaggio al secondo grado è tanto probabile quanto il ritorno al terzo grado, e il passaggio al primo e al quarto grado è quattro volte meno probabile, cioè

p31 =0,1; p32 =0,4; p33 =0,4; p34 =0,1;

Costruiamo un grafico:

Creiamo una matrice di probabilità di transizione:

Troviamo il tempo medio tra gli anni di siccità e gli anni di acqua alta. Per fare ciò, è necessario trovare la distribuzione limite. Esiste perché la condizione del teorema è soddisfatta (la matrice P2 non contiene zero elementi, cioè in due passi si può passare da qualsiasi stato del sistema a qualsiasi altro).

Dove p4 =0,08; p3=; p2=; p1 =0,15

La frequenza di ritorno allo stato S i è pari a .

Di conseguenza, la frequenza degli anni secchi è in media 6,85, cioè 6-7 anni e anni piovosi 12.