Processo markoviano: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
fix vari |
|||
| (167 versioni intermedie di 84 utenti non mostrate) | |||
Riga 1:
[[File:Markovkate_01.svg|thumb|Un diagramma rappresentante un processo markoviano a due stati, etichettati con A ed E. Ogni numero rappresenta la probabilità del processo di cambiare da uno stato all'altro e la freccia rappresenta la direzione di tale cambiamento. Per esempio, se il processo si trova nello stato A, allora la probabilità di rimanervi è 0.6, mentre la probabilità di passare allo stato E è di 0.4.]]
Si definisce '''processo stocastico markoviano''' (o '''di Markov'''), un [[processo stocastico|processo aleatorio]] in cui la [[probabilità di transizione]] che determina il passaggio a uno [[stato di sistema]] dipende solo dallo stato del sistema immediatamente precedente ([[proprietà di Markov]]) e non da come si è giunti a questo stato.<ref>{{Cita web|url=https://en.oxforddictionaries.com/definition/us/markov_chain|titolo=Markov chain {{!}} Definition of Markov chain in US English by Oxford Dictionaries|sito=Oxford Dictionaries {{!}} English|accesso=2018-11-27|dataarchivio=15 dicembre 2017|urlarchivio=https://web.archive.org/web/20171215001435/https://en.oxforddictionaries.com/definition/us/markov_chain|urlmorto=sì}}</ref> Viceversa si dice processo non markoviano un processo aleatorio per cui non vale la proprietà di Markov. Prende il nome dal [[matematico]] [[Russia|russo]] [[Andrej Andreevič Markov (1856)|Andrej Andreevič Markov]] che per primo ne sviluppò la teoria. Modelli di tipo markoviano vengono utilizzati nella progettazione di [[reti di telecomunicazioni]]: la [[teoria delle code]] che ne consegue trova applicazione in molti ambiti, dalla fila agli sportelli ai [[Pacchetto (reti)|pacchetti]] dati in coda in un [[router]].
Un processo di Markov può essere descritto per mezzo dell'enunciazione della [[proprietà di Markov]], o condizione di "assenza di memoria", che può essere scritta come
:<math> P\big(X(t_{n+1})= x_{n+1}\big|X(t_n)= x_n, X(t_{n-1})= x_{n-1}, \ldots, X(t_0)= x_0\big) = P\big(X(t_{n+1})= x_{n+1}\big|X(t_n)=x_n\big).</math>
== Catene di Markov ==
[[File:AAMarkov.jpg|thumb|Il matematico russo [[Andrey Markov]]]]
Una '''catena di Markov''' è un processo di Markov con [[stato di sistema|spazio degli stati]] discreto, quindi è un [[processo stocastico]] che assume valori in uno spazio discreto e che gode della [[proprietà di Markov]]. L'insieme <math>S</math> di spazio degli stati può essere finito o infinito numerabile. Nel primo caso si parla di catena di Markov a stati finiti. Una catena di Markov può essere tempo-continua o tempo-discreta, in base all'insieme <math>T</math> di appartenenza della variabile tempo (continuo o discreto).
Formalmente una catena di Markov è un processo stocastico Markoviano caratterizzato da un parametro <math>t_i \in T</math>, da un insieme <math>S</math> di stati e da una [[Probabilità di transizione|funzione probabilità di transizione]]
:
Essendo un processo Markoviano, <math>P</math> gode della [[proprietà di Markov]]:
:<math>P(X(t_{n+1})= x_{n+1}|X(t_n)= x_n, X(t_{n-1})= x_{n-1}, \ldots, X(t_0)= x_0) = P(X(t_{n+1})= x_{n+1}|X(t_n)=x_n).</math>
Nel caso di catena di Markov a ''tempo discreto,'' cioè con l'insieme <math>T</math> discreto, la notazione si semplifica:
:<math>P(X_{n+1}=x_{n+1}|X_n, X_{n-1}, \ldots, X_0) = P(X_{n+1}=x_{n+1}|X_n).</math>
=== Catene di Markov omogenee ===
Una catena di Markov omogenea è un processo markoviano in cui la probabilità di transizione al tempo <math>t_i</math> non dipende dal tempo stesso, ma soltanto dallo stato del sistema al tempo immediatamente precedente <math>S(t_{i-1})</math>. In altre parole, la probabilità di transizione è indipendente dall'origine dell'asse dei tempi e quindi dipende soltanto dalla distanza tra i due istanti temporali.
Per le catene omogenee vale la condizione
:<math>P(X_{n+1}=x|X_n=y) = P(X_{n}=x|X_{n-1}=y).</math>
Più in generale si dimostra che in una catena di Markov omogenea la probabilità di transizione da uno stato a un altro in <math>n</math> passi è costante nel tempo:
:<math>P(X_{i+n}=x|X_i=y) = P(X_{i-1+n}=x|X_{i-1}=y), \qquad \forall i = 1,2,\ldots</math>
I sistemi reali che possono essere modellati con catene di Markov omogenee sono rari: è sufficiente pensare al sistema "tempo atmosferico" per capire come la probabilità di transizione da uno stato (per esempio "sole") a un altro stato (per esempio "pioggia") dipende dalla stagione, quindi non è possibile modellare questo sistema come catena di Markov omogenea. Tuttavia restringendo l'analisi del sistema a un determinato intervallo di tempo si può considerare il comportamento omogeneo: in questo caso l'intervallo di tempo potrebbe essere una singola stagione.
=== Matrice di transizione ===
{{vedi anche|Matrice di transizione}}
Una catena di Markov omogenea a stati finiti in cui l'insieme <math>S</math> degli stati del sistema è finito e ha <math>N</math> elementi può essere rappresentata mediante una matrice di transizione <math>A \in \mathbb{R}^{N \times N}</math> e un vettore di probabilità iniziale <math>\tilde{\pi}_0 \in \mathbb{R}^N</math>.
Gli elementi di <math>A</math> rappresentano le probabilità di transizione tra gli stati della catena: una catena che si trova nello stato <math>i</math> ha probabilità <math>a_{ij}</math> di passare allo stato <math>j</math> nel passo immediatamente successivo. In particolare gli elementi <math>a_{ii}</math> sulla [[diagonale principale]] di <math>A</math> indicano le probabilità di rimanere nello stesso stato <math>i</math>. Il vettore <math>\tilde{\pi}_0</math> definisce le probabilità che inizialmente la catena di Markov si trovi in ciascuno degli <math>N</math> stati. Una catena di Markov omogenea è univocamente definita dalla coppia <math>(A,\tilde{\pi}_0)</math>.
Se al tempo <math>t_0</math> ha la distribuzione di probabilità <math>\tilde{\pi}_0</math> allora le probabilità <math>\tilde{\pi}_n</math> che a un tempo <math>t_n</math> il sistema si trovi in ciascuno degli <math>N</math> stati sono date dal vettore così definito:
:<math>(\tilde{\pi}_n)^T=(\tilde{\pi}_0)^T\cdot A^n,</math>
dove <math>(\tilde{\pi}_n)^T</math> indica la trasposta del vettore <math> \tilde{\pi}_n</math>.
Dalla [[Probabilità#Definizione assiomatica|definizione assiomatica della probabilità]] discendono le seguenti proprietà per la matrice <math>A</math>:
* <math>a_{ij} \ge 0,\qquad \forall i,j \in \{1\ldots N \};</math>
* <math>\sum_{j=1}^{N} a_{ij} = 1,\qquad \forall i \in \{1\ldots N \}.</math>
La seconda proprietà equivale a richiedere che la somma degli elementi su ciascuna riga sia uguale a 1, nel qual caso la matrice si dice anche [[Matrice stocastica|stocastica]].
Per esempio, <math>A</math> e <math>\tilde{\pi}_0</math> possono essere i seguenti:
:<math>A =\begin{pmatrix}
0,3&0,5&0,2\\
0,1&0,8&0,1\\
0,5&0,5&0
\end{pmatrix}, \qquad \tilde{\pi}_0 =
\begin{pmatrix}
0,4\\0,3\\0,3
\end{pmatrix}.</math>
Nel caso di una ''catena di Markov omogenea a stati discreti'' si può adottare la notazione sintetica:
:<math> P^{(n)}_{ij} \equiv P \left( X_{m+n}=s_j|X_{m}=s_i \right)= P \left( X_{n}=s_j|X_{0}=s_i \right),</math>
dove <math>(n)</math> non è un esponente bensì un indice.
Si ha quindi <math>(\tilde{\pi}_n)_j=\sum_{i \in S} (\tilde{\pi}_0)_i(P^{(n)})_{ij}</math>.
Si hanno le seguenti proprietà:
*<math>P_{ij} \ge 0, \qquad \forall i,j \in S;</math>
*<math>\sum_{j \in S} P_{ij} =1.</math>
=== Catene di Markov aperiodiche ===
Il '''periodo''' di uno stato <math>s_i \in S</math> di una ''catena di Markov a stati discreti,'' con <math>S</math> finito o infinito numerabile, è definito come il minimo numero di passi temporali affinché vi sia una probabilità diversa da zero di tornare sullo stesso stato, partendo dallo stato <math>s_i</math> al tempo <math>t_m</math>. Formalmente il periodo <math>d(s_i)</math> è definito come segue:
:<math>d(s_i,t_m)=\mathrm{MCD}\{n \ge 1 : P\left(X_{m+n}=s_i|X_m=s_i \right) > 0\},</math>
dove <math>\mathrm{MCD}</math> indica il [[massimo comune divisore]].
Nel caso di una ''catena di Markov omogenea a stati finiti'' con numero di stati <math>N</math>, rappresentabile quindi con una matrice <math>A \in \mathbb{R}^N</math>, si può riformulare la definizione così:
:<math> d(s_i)=\mathrm{MCD}\{n \ge 1: (A^n)_{ii}>0 \}.</math>
Lo stato <math>s_i</math> è detto aperiodico se il suo periodo è uguale a 1.
Una catena di Markov è detta aperiodica se tutti i suoi stati sono aperiodici, altrimenti è detta periodica.
=== Catene di Markov irriducibili ===
Una catena di Markov a stati discreti è detta irriducibile se partendo da ogni stato <math>s_i</math> c'è una probabilità maggiore di zero di raggiungere ogni altro stato <math>s_j</math>. Formalmente una catena di Markov è irriducibile se:
:<math>\forall s_i,s_j \in S, \forall m \in \mathbb{N}, \exists n \in \mathbb{N} : P\left(X_{m+n}=s_j|X_m=s_i\right)>0.</math>
=== Stati ricorrenti positivi ===
Sia
:<math>T_i = \begin{cases}
\min\{n\ge 1 : X_n = s_i\} & \text{se } X_n = s_i \text{ per qualche } n \ge 1, \\
+\infty & \text{altrimenti},
\end{cases}</math>
lo stato <math>s_i \in S</math> si dice ricorrente positivo se <math>E(T_i| X_0=s_i)=\mu_i < + \infty.</math>
Se una catena è irriducibile e un suo stato è ricorrente positivo allora tutti i suoi stati sono ricorrenti positivi, in tale caso la catena si dice ricorrente positiva.
=== Distribuzioni stazionarie ===
Data una catena di Markov omogenea a stati discreti, una sua distribuzione stazionaria di probabilità, detta anche distribuzione di equilibrio, <math>\pi=\{\pi_1 \ldots \pi_n \ldots \}</math> è una [[misura di probabilità|distribuzione discreta di probabilità]] che soddisfa le seguenti:
* <math>\pi_i \ge 0,\qquad \forall i \in S;</math>
* <math>\sum_{i \in S} \pi_i = 1;</math>
* <math>\sum_{i \in S} \pi_iP_{ij} = \pi_j,\qquad\forall j \in S.</math>
Informalmente una distribuzione stazionaria è una distribuzione di probabilità che si mantiene costante all'evolversi nel tempo della catena di Markov.
L'importanza delle distribuzioni stazionarie per le catene di Markov omogenee a stati discreti è data dai seguenti teoremi:
*Il teorema di esistenza e unicità afferma che data una catena di Markov omogenea a stati discreti con probabilità di transizione <math>P_{ij}</math> e spazio degli stati <math>S</math>, se la catena di Markov è irriducibile e ricorrente positiva allora esiste un'unica distribuzione stazionaria <math>\pi</math> per la catena di Markov.
*Il teorema della convergenza afferma che data una catena di Markov omogenea a stati discreti con probabilità di transizione <math>P_{ij}</math> e spazio degli stati <math>S</math>, se la catena di Markov è irriducibile, aperiodica e ricorrente positiva allora la distribuzione di probabilità <math>\tilde{\pi}_n</math> al tempo <math>t_n</math>, converge alla distribuzione stazionaria <math>\pi</math> per ogni distribuzione iniziale di probabilità <math>\tilde{\pi}_0</math> scelta. Si ha cioè
::<math>\lim_{n \to \infty}\sum_{i \in S}(\tilde{\pi}_0)_i(P^{(n)})_{ij} = \pi_j,\qquad \forall \tilde{\pi}_0, \forall i,j \in S.</math>
La convergenza di una catena di Markov a una distribuzione stazionaria e la possibilità di costruire una catena con una distribuzione stazionaria scelta sono alla base del funzionamento dell'[[algoritmo di Metropolis-Hastings]].
=== Catene di Markov ergodiche ===
{{vedi anche|Teoria ergodica}}
Una catena di Markov si definisce ergodica se e solo se per ogni istante iniziale <math>t_0</math> e per ogni condizione iniziale di probabilità <math>\tilde{\pi}(t_0)</math> esiste ed è indipendente da <math>t_0</math> e da <math>\tilde{\pi}(t_0)</math> il limite della probabilità per tempi infiniti
:<math> P=\lim_{t \to \infty}\tilde{\pi}(t).</math>
== Applicazioni ==
[[File:PageRank-hi-res.png|thumb|Schematizzazione del sistema PageRank]]
* Molti algoritmi di [[Link Analysis Ranking]] si basano sulla teoria di processi markoviani. Ad esempio il [[PageRank]] [[inferenza statistica|inferito]] da [[Google]] si basa sulla frequenza a posteriori di transizione degli utenti da un [[sito web]] A a un sito B tramite i [[collegamento ipertestuale|link]] che da A conducono a B e non sul semplice numero e tipo di collegamenti da A a B, in modo da rispecchiare la popolarità del legame per gli utenti e non l'importanza per il creatore del sito. Cioè la frequenza di un sito è un valore nell'intervallo [0,1] corrispondente alla quantità media di tempo spesa sul sito da un gran numero di utenti dopo un tempo abbastanza elevato: la frequenza, opportunamente riscalata, costituisce il Page Rank del sito. Dato che la frequenza di transizione approssima la probabilità di transizione si può stimare la distribuzione stazionaria di probabilità della catena di Markov formata da tutti i siti web, costruendo una [[matrice di transizione]].
* Fa uso di modelli statistici markoviani anche un filone di [[modellistica matematica|modellistica]] del [[linguaggio naturale]]. Ad esempio nell'ambito della [[sintesi vocale]] lo [[CSELT]] è stato tra i precursori di questo filone, in particolare per la [[lingua italiana]] e le [[lingue latine]].<ref name="CSELT">Billi, R., Canavesio, F., Ciaramella, A., & Nebbia, L. (1994, September). Interactive voice technology at work: The CSELT experience. In Interactive Voice Technology for Telecommunications Applications, 1994., Second IEEE Workshop on (pp. 43-48). IEEE.</ref>
* Diversi algoritmi previsionali in ambito economico, finanziario e di [[dinamica dei sistemi]] fanno uso dei processi markoviani.
Anche gran parte della modellistica di serie temporali in finanza si basa su processi stocastici generati da catene di Markov.
== Software ==
* In [[R (software)|R]], una libreria abbastanza completa è il pacchetto markovchain<ref>{{Cita pubblicazione|nome=Giorgio Alfredo|cognome=Spedicato [aut|data=2019-08-26|titolo=markovchain: Easy Handling Discrete Time Markov Chains|accesso=2019-09-13|url=https://cran.r-project.org/package=markovchain|cognome2=cre|nome3=Tae Seung|cognome3=Kang}}</ref>
* Una lista di pacchetti [[Python]] può essere trovata qui<ref>{{Cita web|url=https://martin-thoma.com/python-markov-chain-packages/|titolo=Python Markov Chain Packages|autore=Martin Thoma|sito=Martin Thoma|lingua=en|accesso=2019-09-13|urlmorto=sì|dataarchivio=24 marzo 2023|urlarchivio=https://web.archive.org/web/20230324040908/https://martin-thoma.com/python-markov-chain-packages/}}</ref>
* ''[[Mathematica]]'' ha sviluppato funzionalità [[ad hoc]] per le catene di Markov, a partire dalla versione 9.
== Note ==
<references />
==Bibliografia==
* {{en}} Olle Häggström (2002), ''Finite Markov Chains and Algorithmic Applications'', Cambridge University Press, ISBN 0-521-81357-3
== Voci correlate ==
* [[Processo stocastico]]
* [[Variabile casuale]]
* [[
* [[
* [[Modello di Markov nascosto]]
* [[Algoritmo di Metropolis-Hastings]]
* [[N-gramma]]
* [[Teoria ergodica]]
* [[Vacancy chain]]
== Altri progetti ==
{{interprogetto|preposizione=sul}}
== Collegamenti esterni ==
* {{Collegamenti esterni}}
* {{FOLDOC|Markov chain|Markov chain}}
{{Probabilità}}
{{Controllo di autorità}}
{{Portale|matematica}}
[[Categoria:Processi stocastici]]
| |||