Un appunto sulla notazione: nella letteratura scientifica in lingua inglese vige la convenzione di scrivere le matrici di transizione in riga
$V=\begin{pmatrix} 1-p & p \\ q & 1-q \end{pmatrix}$
Questa è una matrice stocastica destra (la somma di ogni riga dà $1$). È altresì possibile (io lo faccio continuamente) scrivere le matrici di transizione in colonna
$M=\begin{pmatrix} 1 - p & q \\ p & 1 - q \end{pmatrix}$
ottenendo una matrice stocastica sinistra (la somma di ogni colonna dà $1$).
Nella convenzione destra la transizione viene ottenuta moltiplicando a destra un vettore riga (ovviamente, un vettore stocastico per il quale la somma delle componenti è $1$ e ogni componente contiene la probabilità di trovarsi nel corrispondente stato del processo)
$m_{i+1}^\text{T}=m_i^\text{T}\,V$
A me viene molto più naturale usare la convenzione sinistra nella quale la transizione è ottenuta moltiplicando a sinistra un vettore (stocastico) colonna
$v_{i+1}=Mv_i$
cioè
$\begin{pmatrix} x_{i+1} \\ y_{i+1} \end{pmatrix}=\begin{pmatrix} 1-p & q \\ p & 1-q \end{pmatrix}\begin{pmatrix} x_i\\y_i \end{pmatrix}$
come si fa in Algebra Lineare
$\left\{\begin{array}{cC} x^\prime=\left(1-p\right)x+qy \\ y^\prime=px+\left(1-q\right)y\end{array}\right.$
Finché si tratta di valori numerici non c’è molta differenza ma quando facciamo algebra tutti quei vettori colonna trasposti rompono le scatole. E servono trasposti perché i vettori riga sono di difficile lettura, per esempio
$\begin{pmatrix}x \\ 1-x\end{pmatrix}^\text{T}=\begin{pmatrix}x & 1-x\end{pmatrix}$
Ciò detto, prendiamo in considerazione il caso generale di un processo stocastico con due stati, $\text{S}$ (Markov è in spiaggia) e $\text{A}$ (Markov è in albergo).
- VacanzaDiMarkov.01.640x320.png (25.41 KiB) Visto 62967 volte
La probabilità di passare da $\text{S}$ ad $\text{A}$ sia $p$; la probabilità di passare da $\text{A}$ a $\text{S}$ sia $q$. La matrice (stocastica sinistra) di transizione sarà
$M=\begin{pmatrix} 1-p & q \\ p & 1-q \end{pmatrix}$
Quando Markov è in spiaggia il vettore stocastico è
$v_\text{S}=\begin{pmatrix}1\\0\end{pmatrix}$
mentre quando Markov è in albergo il vettore stocastico è
$v_\text{A}=\begin{pmatrix}0\\1\end{pmatrix}$
Al tempo zero Markov è in spiaggia quindi
$v_0=v_\text{S}=\begin{pmatrix}1\\0\end{pmatrix}$
La prima transizione avviene dopo un’ora: il vettore stocastico
$v_1=Mv_0=\begin{pmatrix} 1-p & q \\ p & 1-q \end{pmatrix}\begin{pmatrix}1\\0\end{pmatrix}=\begin{pmatrix}1-p\\p\end{pmatrix}$
contiene le probabilità di occupazione dei due stati nell’ora successiva; il vettore stocastico
$v_2=Mv_1=\begin{pmatrix} 1-p & q \\ p & 1-q \end{pmatrix}\begin{pmatrix}1-p\\p\end{pmatrix}=\begin{pmatrix}1-p\left(2-p-q\right)\\ p\left(2-p-q\right)\end{pmatrix}$
contiene le probabilità di occupazione dei due stati dopo due ore e così via.
Naturalmente
$v_2=Mv_1=M^2 v_0$
e, in generale,
$v_r=M^r v_0$
Il problema diventa quello di calcolare la potenza di una matrice quadrata.
Sfruttiamo il fatto che la potenza di una matrice diagonale è la matrice diagonale delle potenze dato che
$\begin{pmatrix}a&0\\0&b\end{pmatrix}^1=\begin{pmatrix}a^1&0\\0&b^1\end{pmatrix}$
e che, se è vero che
$\begin{pmatrix}a&0\\0&b\end{pmatrix}^n=\begin{pmatrix}a^n&0\\0&b^n\end{pmatrix}$
allora
$\begin{pmatrix}a&0\\0&b\end{pmatrix}^{n+1}= \begin{pmatrix}a&0\\0&b\end{pmatrix}^n\begin{pmatrix}a&0\\0&b\end{pmatrix}=\begin{pmatrix}a^n&0\\0&b^n\end{pmatrix}\begin{pmatrix}a&0\\0&b\end{pmatrix}=\begin{pmatrix}a^n\cdot a+0\cdot 0&a^n\cdot 0+0\cdot b\\0\cdot a+b^n\cdot 0&0\cdot 0+b^n\cdot b\end{pmatrix}=\begin{pmatrix}a^{n+1} & 0\\0 & b^{n+1}\end{pmatrix}$
Se la matrice $M$ è diagonalizzabile allora esistono due matrici, l’una l’inversa dell’altra tali che
$\Lambda=S^{-1} MS$
dove $\Lambda$ è una matrice diagonale (le matrici $\Lambda$ e $M$ vengono definite matrici simili).
La potenza di $M$ si troverà rovesciando la similitudine
$M^r=S\Lambda^r S^{-1}$
Come facciamo la diagonalizzazione? Scriviamo l’equazione caratteristica della matrice
$\left|M-\lambda I\right|=\left|\begin{pmatrix}1-p & q\\p & 1-q\end{pmatrix}-\lambda\begin{pmatrix}1 & 0\\0 & 1\end{pmatrix}\right|=\begin{vmatrix}1-p-\lambda & q \\ p & 1 - q-\lambda\end{vmatrix}=0$
cioè
$\lambda^2-\left(2-p-q\right)\lambda+1-p-q=0$
Le soluzioni di questa equazione sono gli “autovalori” della matrice: in questo caso
$\lambda_{1,2}=\left\{\begin{array}{lC}1-p-q \\1\end{array}\right.$
Ora che abbiamo gli autovalori li usiamo per trovare gli “autovettori” cioè dei vettori per cui
$\left(M-\lambda_k I\right)v_k=0$
Nel nostro caso
$\left\{\begin{array}{lC}\left(1-p-\lambda_k\right)\,v_{k,1}+q\,v_{k,2}=0 \\p\,v_{k,1}+\left(1-p-\lambda_k\right)\,v_{k,2}=0\end{array}\right.$
o, in forma matriciale,
$\begin{pmatrix}1-p-\lambda_k & q \\ p & 1-q-\lambda_k\end{pmatrix}\begin{pmatrix}v_{k,1}\\v_{k,2}\end{pmatrix}=\begin{pmatrix}0\\0\end{pmatrix}$
Sostituendo i valori di $\lambda$ troviamo
$\lambda=1-p-q\qquad\Longrightarrow\qquad\begin{pmatrix}q & q\\p & p\end{pmatrix}\begin{pmatrix}-1\\1\end{pmatrix}=\begin{pmatrix}0\\0\end{pmatrix}$
e
$\lambda=1\qquad\Longrightarrow\qquad\begin{pmatrix}-p & q\\p & -q\end{pmatrix}\begin{pmatrix}q\\p\end{pmatrix}=\begin{pmatrix}0\\0\end{pmatrix}$
Concateniamo i due vettori colonna per ottenere la matrice degli autovettori
$S=\begin{pmatrix}-1 & q\\1 & p\end{pmatrix}$
e troviamo la sua inversa
$\displaystyle S^{-1}=\frac1{p+q}\begin{pmatrix}-p & q\\1 & 1\end{pmatrix}$
Applichiamo la similitudine e troviamo
$\Lambda=S^{-1}MS=\begin{pmatrix}\left(1-p-q\right) & 0\\0 & 1\end{pmatrix}$
cioè
$\Lambda=\text{diag}\lambda=\begin{pmatrix}\lambda_1 & 0\\0 & \lambda_2\end{pmatrix}$
Ed è sempre così, non serve trovare $\Lambda$ mediante la similitudine: le matrici $S$ e $S^{-1}$ ci servono per rovesciare la similitudine
$M^r=S\Lambda^r S^{-1}=S\begin{pmatrix}(1-p-q)^r & 0\\0 & 1\end{pmatrix} S^{-1}=\begin{pmatrix}\displaystyle\frac{q+p(1-p-q)^r}{p+q} & \displaystyle\frac{q+q(1-p-q)^r}{p+q}\\\displaystyle\frac{p-p(1-p-q)^r}{p+q} & \displaystyle\frac{p-q(1-p-q)^r}{p+q}\end{pmatrix}$
Ora, abbiamo che, per $0\leq|1-p-q|<1$,
$\displaystyle\lim_{r\to\infty}(1-p-q)^r=0$
quindi, al crescere di $r$, la matrice si stabilizza
$\displaystyle\lim_{r\to\infty}M^r=\begin{pmatrix}\displaystyle\frac{q}{p+q} & \displaystyle\frac{q}{p+q}\\\displaystyle\frac{p}{p+q} & \displaystyle\frac{p}{p+q}\end{pmatrix}$
e arriva rappresentare uno stato stazionario.
Per trovare il vettore e la matrice dello stato stazionario non è necessaria tutta questa analisi: basta porre
$\begin{pmatrix}1-p & q\\p & 1-q\end{pmatrix}\begin{pmatrix}t\\1-t\end{pmatrix}=\begin{pmatrix}t\\1-t\end{pmatrix}$
Dalla prima equazione
$(1-p)t+q(1-t)=t$
ricaviamo facilmente
$\displaystyle t=\frac{q}{p+q}$
da cui segue
$\displaystyle 1-t=\frac{p}{p+q}$
La convergenza verso lo stato stazionario è, in generale, molto veloce per via dell’esponenziale $(1-p-q)^r$: in $100$ ore il vettore stocastico dello stato stazionario
$v_\infty=\begin{pmatrix}\displaystyle\frac{q}{p+q}\\\displaystyle\frac{p}{p+q}\end{pmatrix}$
rappresenta molto bene l’occupazione dei due stati.
Se vogliamo sapere qual è la probabilità di essere in $\text{S}$(piaggia) dopo $r$ spostamenti, partendo da $\text{S}$ avremo
$v_r=\begin{pmatrix}\displaystyle\frac{q+p(1-p-q)^r}{p+q} & \displaystyle\frac{q+q(1-p-q)^r}{p+q}\\\displaystyle\frac{p-p(1-p-q)^r}{p+q} & \displaystyle\frac{p-q(1-p-q)^r}{p+q}\end{pmatrix}\begin{pmatrix}1\\0\end{pmatrix}=\begin{pmatrix}\displaystyle\frac{q+p(1-p-q)^r}{p+q} \\\displaystyle\frac{p-p(1-p-q)^r}{p+q}\end{pmatrix}$
quindi
$\displaystyle\frac{q+p(1-p-q)^r}{p+q}$
mentre, partendo da $\text{A}$, avremo
$v_r=\begin{pmatrix}\displaystyle\frac{q+p(1-p-q)^r}{p+q} & \displaystyle\frac{q+q(1-p-q)^r}{p+q}\\\displaystyle\frac{p-p(1-p-q)^r}{p+q} & \displaystyle\frac{p-q(1-p-q)^r}{p+q}\end{pmatrix}\begin{pmatrix}0\\1\end{pmatrix}=\begin{pmatrix}\displaystyle\frac{q+q(1-p-q)^r}{p+q} \\\displaystyle\frac{p-q(1-p-q)^r}{p+q}\end{pmatrix}$
quindi
$\displaystyle\frac{q+q(1-p-q)^r}{p+q}$
Nel caso specifico, con $p=2/5$, $q=1/5$ e $r\in\{2,\,3,\,10\}$
$\displaystyle\frac{33}{75}\approx 0,44\qquad\frac{141}{375}\approx 0,38\qquad\frac{9767673}{29296875}\approx 0,33$
e
$\displaystyle\frac{29}{75}\approx 0,39\qquad\frac{133}{375}\approx 0,35\qquad\frac{9766649}{29296875}\approx 0,33$
