Abbiamo due tennisti, che indicherò con le lettere maiuscole P e Q, che nel corso di un gioco sono arrivati ad una situazione di parità o deuce. Se chiamo $p$ e $q$ le rispettive probabilità di segnare un punto (ovviamente $p,q>0\ \land\ p+q=1$), quanti punti in media dovranno essere giocati affinché il gioco termini?
La situazione può essere rappresentata da questa figura. Se chiamo $n$ il numero di punti da giocare prima che il gioco termini e $\overline n$ il numero medio di questi punti, avrò una probabilità $p^2$ che sia $n=2$, una probabilità $q^2$ che sia $n=2$ e una probabilità $2pq$ che in media sia $n=\overline n+2$. Posso dunque scrivere: $\overline n=2p^2+2q^2+2pq(\overline n+2)$. Risolvendo per $\overline n$ ottengo $\overline n=2\ \dfrac{p^2+2pq+q^2}{1-2pq}=\dfrac2{p^2+q^2}$ dove ho tenuto conto del fatto che $p^2+2pq+q^2=(p+q)^2=1$. Si ha il massimo per $\overline n$ quando $p=q=1/2$ e allora $\overline n=4$. Quanto maggiore è la differenza in valore assoluto fra $p$ e $q$, tanto più $\overline n$ si avvicina a $2$.
La situazione può essere rappresentata da questa figura. Se chiamo $n$ il numero di punti da giocare prima che il gioco termini e $\overline n$ il numero medio di questi punti, avrò una probabilità $p^2$ che sia $n=2$, una probabilità $q^2$ che sia $n=2$ e una probabilità $2pq$ che in media sia $n=\overline n+2$. Posso dunque scrivere: $\overline n=2p^2+2q^2+2pq(\overline n+2)$. Risolvendo per $\overline n$ ottengo $\overline n=2\ \dfrac{p^2+2pq+q^2}{1-2pq}=\dfrac2{p^2+q^2}$ dove ho tenuto conto del fatto che $p^2+2pq+q^2=(p+q)^2=1$. Si ha il massimo per $\overline n$ quando $p=q=1/2$ e allora $\overline n=4$. Quanto maggiore è la differenza in valore assoluto fra $p$ e $q$, tanto più $\overline n$ si avvicina a $2$.
E… se volessi sapere qualcosa di più? ad esempio qual è la probabilità che il gioco si chiuda in $4$, $6$, $8$, eccetera punti? Qual è la varianza? E quali sono le probabilità che sia P o Q a vincere? Possiamo utilizzare le matrici di Markov.
Se la matrice $\mathbf M$ rappresenta le probabilità di transizione da uno stato ad un altro dopo un passo, la matrice $\mathbf M^n$ rappresenta le probabilità di transizione da uno stato ad un altro dopo $n$ passi. Ad esempio nel caso che stiamo esaminando $$\mathbf M^2=\left( \begin{array}{ccccc} 2pq & 0 & 0 & p^2 & q^2 \\ 0 & pq & q^2 & p & 0 \\ 0 & p^2 & pq & 0 & q \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{array} \right )$$dove, ad esempio, riconosciamo nella prima riga che se partiamo da una situazione di parità, dopo due punti giocati c’è una probabilità $2pq$ di essere ancora in parità, una probabilità $p^2$ che abbia vinto P ed una probabilità $q^2$ che abbia vinto Q, come peraltro avevamo già dedotto in precedenza.
In questo caso specifico vi sono due stati particolari, “VP” e “VQ” che sono detti stati assorbenti. Uno stato assorbente ha la caratteristica che, in un certo senso, da esso non si può scappare e, una volta giunti, vi si rimane per sempre. Nella matrice di Markov uno stato assorbente è associato ad un $1$ sulla diagonale, il che implica che gli altri elementi della riga corrispondente allo stato assorbente saranno tutti pari a $0$. Inoltre, sempre nel caso che stiamo esaminando, si può dire che abbiamo una catena assorbente di Markov, in quanto da ogni stato non assorbente, tecnicamente stato transitorio, è possibile, con un numero finito di passi, raggiungere ogni stato assorbente. Una matrice di Markov corrispondente ad una catena assorbente, con $t$ stati transitori e $r$ stati assorbenti è esprimibile in questa forma canonica se ordiniamo gli stati mettendo prima gli stati transitori e poi quelli assorbenti:$$\mathbf M=\left( \begin{array}{cc} \mathbf Q & \mathbf R\\ \mathbf 0 & \mathbf I_r \end{array} \right )$$dove $\mathbf Q$ è una matrice quadrata $t\times t$ che descrive le probabilità di passare da uno stato transitorio ad un altro, $\mathbf R$ è una matrice $t\times r$ che descrive le probabilità di passare da uno stato transitorio ad uno assorbente, $\mathbf 0$ è una matrice $r\times t$ i cui elementi sono tutti pari a $0$ e $\mathbf I_r$ è la matrice identità $r\times r$, ovvero una matrice quadrata con gli elementi sulla diagonale pari a $1$ e tutti gli altri elementi pari a $0$. Nel nostro caso$$\mathbf Q=\left( \begin{array}{ccc} 0 & p & q \\ q & 0 & 0 \\ p & 0 & 0 \end{array} \right ), \ \mathbf R=\left( \begin{array}{cc} 0 & 0 \\ p & 0 \\ 0 & q \end{array} \right ),\ \mathbf 0=\left(\begin{array}{ccc} 0 & 0 & 0 \\ 0 & 0 & 0 \end{array}\right),\ \mathbf I_r=\mathbf I_2=\left(\begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array}\right)\ .$$
Con un semplice ragionamento sulla proprietà della moltiplicazione fra matrici si può dimostrare che in generale$$\mathbf M^n=\left( \begin{array}{cc} \mathbf Q^n & *\\ \mathbf 0 & \mathbf I_r \end{array} \right )$$dove l’asterisco $*$ indica una matrice $t\times r$ che dipende da $\mathbf Q$, da $\mathbf R$ e da $n$. La matrice $\mathbf Q^n$ indica quindi le probabilità di passaggio da uno stato transitorio ad un altro dopo $n$ passi.
Una importante proprietà della matrice $\mathbf Q$, nel caso di una catena assorbente di Markov, è che $\displaystyle{\lim_{n\to\infty}\mathbf Q^n=\mathbf 0}$ (dove in questo caso $\mathbf 0$ è una matrice $t\times t$ con tutti gli elementi pari a $0$). Infatti, per ogni stato transitorio $s_i$ per ipotesi è possibile raggiungere uno stato assorbente. Chiamiamo $m_i$ il minimo numero di passi necessario per passare dallo stato $s_i$ ad uno stato assorbente, ovvero affinché lo stato $s_i$ venga assorbito. Nel nostro caso abbiamo $m_1=2$, $m_2=1$ e $m_3=1$. Chiamiamo $p_i$ la probabilità che dallo stato $s_i$ non venga raggiunto uno stato assorbente in $m_i$ passi. Nel nostro caso $p_1=2pq$, $p_2=1-p$ e $p_3=1-q$. Chiamiamo ora $m$ il valore maggiore degli $m_i$ (nel nostro caso $m=2$) e $p$ il valore maggiore delle $p_i$ (nel nostro caso dipende dai valori di $p$ e $q$). In ogni caso deve essere $p<1$, in quanto, se non fosse così, vi sarebbe uno stato transitorio $s_i$ con $p_i=1$ e che quindi non avrebbe possibilità di raggiungere uno stato assorbente, contrariamente alle ipotesi iniziali. Ora, la probabilità che da un qualsiasi stato transitorio non venga raggiunto uno stato assorbente in $m$ passi è minore o uguale a $p$, in $2m$ passi è minore di $p^2$, in generale dopo $n\cdot m$ passi è minore di $p^n$. Poiché $p<1$ queste probabilità tendono a $0$. Poiché la probabilità che uno stato non venga assorbito decresce all’aumentare del numero di passi si ha $\displaystyle{\lim_{n\to\infty}\mathbf Q^n=\mathbf 0}$.
Attraverso questo teorema appena dimostrato si può dimostrare l’esistenza della matrice fondamentale $\mathbf N=(\mathbf I-\mathbf Q)^{-1}$ ($\mathbf I$ è la matrice identità delle stesse dimensioni di $\mathbf Q$). Sia infatti $\mathbf v$ un vettore tale che $(\mathbf I-\mathbf Q)\mathbf v=\mathbf 0$. Si ha allora $\mathbf v=\mathbf Q \mathbf v$ e, iterando, $\mathbf v=\mathbf Q^n \mathbf v$. Poiché $\displaystyle{\lim_{n\to\infty}\mathbf Q^n=\mathbf 0}$ deve essere anche $\mathbf v=\mathbf 0$. L’unica combinazione lineare nulla delle colonne di $(\mathbf I-\mathbf Q)$ è la combinazione lineare banale e quindi la matrice è invertibile. Consideriamo inoltre questa identità: $$\mathbf I -\mathbf Q^{n+1}=(\mathbf I-\mathbf Q)(\mathbf I + \mathbf Q+\mathbf Q^2+\ldots+\mathbf Q^n)$$ e moltiplichiamo a sinistra entrambi i membri per $\mathbf N=(\mathbf I-\mathbf Q)^{-1}$: otteniamo$$\mathbf N(\mathbf I - \mathbf Q^{n+1})=\mathbf I + \mathbf Q+\mathbf Q^2+\ldots+\mathbf Q^n\ .$$Facendo tendere $n$ a infinito otteniamo $$\mathbf N=\mathbf I + \mathbf Q+\mathbf Q^2+\ldots\ = \sum_{n=0}^\infty \mathbf Q^n\ .$$Nel nostro caso$$\mathbf N=\frac1{p^2+q^2}\left(\begin{array}{ccc} 1 & p & q \\ q & 1-pq & q^2 \\ p & p^2 & 1-pq \end{array}\right)\ . $$Vediamo ora quale significato attribuire agli elementi di $\mathbf N$. Indico con $q^{(k)}_{i,j}$ l’elemento della riga $i$ e colonna $j$ di $\mathbf Q^k$ (se $k=0$ si ha $\mathbf Q^0=\mathbf I$ e $q^{(0)}_{i,j}=\delta_{ij}$ dove $\delta$ è il simbolo di Kronecker). e con $n_{i,j}$ l’analogo elemento di $\mathbf N$. Fissati $i$ e $j$, $q^{(k)}_{i,j}$ indica la probabilità che un processo iniziato nello stato $i$ si trovi nello stato $j$ dopo $k$ passi. Il numero atteso di volte che un processo iniziato nello stato $i$ si trovi nello stato $j$ entro i primi $n$ passi è invece $E^{(n)}_{i,j}=q^{(0)}_{i,j}+q^{(1)}_{i,j}+\ldots+q^{(n)}_{i,j}$. Facendo tendere $n$ a infinito otteniamo una importantissima proprietà di $\mathbf N$: il numero atteso di volte che un processo iniziato nello stato $i$ si trovi nello stato $j$ prima di essere assorbito è: $$E_{i,j}=q^{(0)}_{i,j}+q^{(1)}_{i,j}+\ldots=\sum_{k=0}^\infty q^{(k)}_{i,j}=n_{i,j}\ .$$Nel nostro caso, partendo da una situazione di deuce, in media il sistema passerà mediamente per $\dfrac1{p^2+q^2}$ volte per uno stato di deuce (compreso quello iniziale), per $\dfrac p{p^2+q^2}$ volte per uno stato di “vantaggio per P” e per $\dfrac q{p^2+q^2}$ volte per uno stato di “vantaggio per Q”. Questo ci permette di calcolare il numero atteso di punti che devono essere giocati prima che il gioco venga assegnato a P o a Q: $$\overline n=\dfrac1{p^2+q^2}+\dfrac p{p^2+q^2}+\dfrac q{p^2+q^2}=\dfrac{1+p+q}{p^2+q^2}=\dfrac2{p^2+q^2}$$ come avevamo trovato all’inizio.
In generale, la somma degli elementi della riga $i$ di $\mathbf N$ dà il numero atteso di passi affinché un processo cominciato nello stato $s_i$ venga assorbito. Definendo il vettore colonna $\mathbf 1$ come il vettore formato da $t$ elementi tutti uguali a $1$, allora il vettore $\mathbf a=\mathbf N \mathbf 1$ ha come elementi $a_i$ il numero atteso di passi prima che il processo cominciato nello stato $s_i$ venga assorbito.
Possiamo chiederci quale sia la probabilità $b_{i,j}$ che un processo cominciato nello stato transitorio $s_i$ si concluda nello stato assorbente $s_j$. Essa corrisponde all’elemento $(i,j)$ della matrice $t\times r$ $\mathbf B=\mathbf N \mathbf R\ $. Infatti indicando con $r_{i,j}$ gli elementi della matrice $\mathbf R$ si ha:$$b_{i,j}=\sum_{n=0}^\infty \sum_{k=1}^t q_{i,k}^{(n)}r_{k,j}=\sum_{k=1}^t \sum_{n=0}^\infty q_{i,k}^{(n)}r_{k,j}=\sum_{k=1}^t n_{i,k} r_{k,j}=(\mathbf N \mathbf R)_{i,j}\ .$$Nel nostro caso$$\mathbf B=\frac1{p^2+q^2}\left(\begin{array}{ccc} 1 & p & q \\ q & 1-pq & q^2 \\ p & p^2 & 1-pq \end{array}\right) \left( \begin{array}{cc} 0 & 0 \\ p & 0 \\ 0 & q \end{array} \right)=\frac1{p^2+q^2}\left( \begin{array}{cc} p^2 & q^2 \\ p-p^2q & q^3 \\ p^3 & q-pq^2\end{array}\right) $$da cui ricaviamo immediatamente che le probabilità di vittoria per P e Q, partendo da una situazione di parità, sono rispettivamente $\dfrac{p^2}{p^2+q^2}$ e $\dfrac{q^2}{p^2+q^2}$.
Si può dimostrare che la varianza del numero di passi prima dell’assorbimento, partendo dallo stato transitorio $s_i$ è l’elemento $i$ del vettore $(2\mathbf N-\mathbf I)\mathbf a-\mathbf a_{sq}$ dove $\mathbf a_{sq}$ è il prodotto di Hadamard di $\mathbf a$ con sé stesso, ovvero è il vettore che ha per elementi i quadrati degli elementi di $\mathbf a$. Nel nostro caso, semplificando e ricordando che $p+q=1$ si ha $(2\mathbf N-\mathbf I)\mathbf a-\mathbf a_{sq}=\dfrac{4pq}{({p^2+q^2})^2}(2\quad 1+2q\quad 1+2p)^\intercal$.
Si può dimostrare inoltre che la probabilità di visitare lo stato transitorio $s_j$ partendo dallo stato transitorio $s_i$ è l’elemento $(i,j)$ della matrice $\mathbf H=(\mathbf N-\mathbf I)(\mathbf N_{dg})^{-1}$ dove $\mathbf N_{dg}$ è la matrice $\mathbf N$ dove tutti gli elementi fuori dalla diagonale sono stati sostituiti da $0$. Nel nostro caso$$\mathbf H=\left(\begin{array}{ccc} 2pq & \dfrac p{1-pq} & \dfrac q{1-pq} \\ q & \dfrac{pq}{1-pq} & \dfrac{q^2}{1-pq}\\ p & \dfrac{p^2}{1-pq} & \dfrac{pq}{1-pq}\end{array}\right ) .$$
Se vogliamo calcolare probabilità specifiche, ad esempio la probabilità che il giocatore P vinca dopo quattro punti, dobbiamo tornare alla matrice $\mathbf M$ e alle sue potenze. Per poterle calcolare in modo agevole è conveniente diagonalizzare, se possibile, la matrice $\mathbf M$. Nel nostro caso $\mathbf M$ è diagonalizzabile e si ha $\mathbf V^{-1} \mathbf M \mathbf V=\mathbf D$ dove $$\mathbf V=\left(\begin{array}{ccccc} \frac{q^2}{p^2+q^2} & \frac{p^2}{p^2+q^2} & 0 & -\sqrt\frac{2q}{p} & \sqrt\frac{2q}{p} \\ \frac{q^3}{p^2+q^2} & \frac{p(1-pq)}{p^2+q^2} & -\frac{q}{p} & \frac{q}{p} & \frac{q}{p} \\ \frac{q(1-pq)}{p^2+q^2} & \frac{p^3}{p^2+q^2} & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \end{array} \right ),\ \mathbf D=\left(\begin{array}{ccccc} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & -\sqrt{2pq} & 0 \\ 0 & 0 & 0 & 0 & \sqrt{2pq}\end{array}\right )$$e si ha allora $\mathbf M=\mathbf V\mathbf D\mathbf V^{-1}$ e $\mathbf M^n=\mathbf V\mathbf D^n\mathbf V^{-1}$. Ora però non ci interessa tutta la matrice $\mathbf M^n$ ma ci interessano solo il quarto ed il quinto elemento della prima riga. Si ha $$\begin{array}{lc}\mathbf M^n_{1,4}=\dfrac{4 p^2- (2 p q)^{n/2} p \left[2 p \left(1+(-1)^n\right)+ \sqrt{2p/q}\left(1-(-1)^n\right) \right]}{4 \left(p^2+q^2\right)} & \textrm{ e} \\ \mathbf M^n_{1,5}=\dfrac{4 q^2- (2 p q)^{n/2} q \left[2 q \left(1+(-1)^n\right)+ \sqrt{2q/p}\left(1-(-1)^n\right) \right]}{4 \left(p^2+q^2\right)}\ . & \end{array}$$Per entrambi gli elementi della matrice si ha $\mathbf M^{2k}_{1,i}=\mathbf M^{2k+1}_{1,i}\ \forall k \in \mathbb N$, ovvero all’aumentare dell’esponente gli elementi cambiano valore solo dal passaggio da un valore dispari ad uno pari, infatti se calcoliamo $\mathbf M^{n}_{1,i}-\mathbf M^{n-1}_{1,i}$ possiamo raccogliere un fattore comune $1+(-1)^n$ che si annulla se $n$ è dispari. Tutto questo è legato al fatto che il gioco si può concludere solo dopo un numero pari di punti.
La probabilità che il giocatore P vinca dopo $n$ punti è $\mathbf M^n_{1,4}-\mathbf M^{n-1}_{1,4}$, la probabilità che il gioco si concluda dopo $n$ punti è $\mathbf M^n_{1,4}+\mathbf M^n_{1,5}-\left(\mathbf M^{n-1}_{1,4}+\mathbf M^{n-1}_{1,5}\right)$.
 |
| probabilità che il giocatore P vinca dopo $n$ punti |
 |
| probabilità che il gioco termini dopo $n$ punti |
Post
0 commenti:
Posta un commento