\documentclass[12pt,letterpaper]{article}

\author{Augusto Del Zotto}
\title{Esercizi 5,6,7 Catene di Markov}

\usepackage[english,italian]{babel}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}

\begin{document}
\maketitle
\paragraph{Esercizio 5}
Determinare tutte le misure di probabilità invarianti della seguente matrice di transizione: \[ Q=\begin{pmatrix} 
\frac{1}{2} & 0&\frac{1}{2} \\
 0 &\frac{1}{2} &\frac{1}{2} \\
 \frac{1}{2} & \frac{1}{2} &0
\end{pmatrix} \]
\begin{proof}
Sia $\mu = \left( a,b,c \right)$ una misura di probabilità invariante per Q, allora $\mu Q=\mu $ e $a+b+c=1$.
Da cui il sistema \begin{align*} 
&\left\{
		\begin{aligned}
		\frac{1}{2} a +\frac{1}{2} c = a \\
        \frac{1}{2} b + \frac{1}{2} c = b \\
        \frac{1}{2} a + \frac{1}{2} b = c \\
        a+b+c= 1
        \end{aligned}
		\right.
\end{align*} 
la cui soluzione è unica ed è $\mu = \left(\frac{1}{3},\frac{1}{3},\frac{1}{3} \right)$
\end{proof}

\paragraph{Esercizio 6}
Si consideri la seguente catena di Markov a due stadi con matrice di transizione: \[ Q=\begin{pmatrix} 
1-\alpha & \alpha \\
\beta & 1- \beta \\
\end{pmatrix} \]
con $\alpha ,\beta \in \left[0,1 \right]$.
Determinare $Q^{(n)}(1,1) $ per ogni $n \in \mathbb{N}$.
\begin{proof}
Suppongo che gli stati siano $S= \{ 1,2 \}$
Ricordando che vale $Q^{(n)} = Q^n$ dove $Q^n$ indica la potenza n-esima della matrice Q, non resta che calcolare $Q^n (1,1)$ in funzione di n
\begin{align*}
Q^n(1,1) &= \sum_{h=1}^{2}{Q(h,1)Q^{n-1}(1,h)} =\\
&= Q(1,1)Q^{n-1}(1,1) + Q(2,1)Q^{n-1}(1,2) =\\
&=\left( 1-\alpha \right) Q^{n-1}(1,1) + \beta Q^{n-1}(1,2) 
\end{align*}
Poiché Q è stocastica, lo sono anche le $Q^k$  $\forall k \in \mathbb{N}$, in particolare \[Q^k(1,1) +Q^{k}(1,2)= 1 \]
sostituendo quindi ottengo \[ Q^n(1,1)=\left( 1- \alpha \right)Q^{n-1}(1,1) + \beta \left( 1- Q^{n-1}(1,1) \right) \]
da cui si ricava la seguente successione per ricorsione, dove $Q^n(1,1)= a_n $:
\begin{align*} 
&\left\{
		\begin{aligned}
		a_1 &= 1 - \alpha \\
		a_n &= \left(  1- \alpha - \beta \right) a_{n-1} + \beta
        \end{aligned}
		\right.
\end{align*} 
Esplicitando infine il termine n-esimo in funzione di n si ottiene \[a_n = Q^n(1,1) = \left(  1- \alpha \right)\left(  1- \alpha - \beta \right)^{n-1} + \beta \left( \frac{\left(  1- \alpha - \beta \right)^{n-1} -1}{\left(  1- \alpha - \beta \right) -1} \right)  \]
\end{proof}

\paragraph{Esercizio 7}
Riassumendo il testo ci sono N ceppi di un virus, che ha probabilità $\alpha$ di cambiare ceppo dopo ogni replicazione e di scegliere un secondo ceppo in maniera equiprobabile tra gli altri.
Si chiede la probabilità che il ceppo originario (generazione 0) coincida con il ceppo della n-esima generazione.
\begin{proof}
Come nell'esercizio precedente schematizzo il problema come un catena di Markov a N stadi (i vari ceppi). \\
Dalle ipotesi si ha che $Q(i,i)=1-\alpha$ per ogni $i \in \{1,\dots ,N\}$ in quanto la probabilità di cambiare ceppo è $\alpha$.\\
Inoltre si ha che $Q(i,j)=\frac{ \alpha}{N-1}$ per ogni $i\neq j \in \{1,\dots ,N\}$ poiché la scelta di un nuovo ceppo è equiprobabile.\\
La matrice di transizione risulta quindi essere:
\[ Q= \begin{pmatrix}
1-\alpha & \frac{ \alpha}{N-1} & \dots &\dots & \frac{ \alpha}{N-1} \\
\frac{ \alpha}{N-1} & 1-\alpha & \frac{ \alpha}{N-1}& \dots & \frac{ \alpha}{N-1} \\
\vdots & \ddots & \ddots & \ddots & \vdots \\
\vdots & & \ddots &\ddots & \vdots \\
\vdots & &  & \ddots & \frac{ \alpha}{N-1}\\
 \frac{ \alpha}{N-1} & \dots & \dots & \frac{ \alpha}{N-1} & 1-\alpha 
\end{pmatrix} \]
Poiché i vari stadi sono indistinguibili uno dall'altro e hanno tutti le stesse caratteristiche posso dedurre che $\forall n \in \mathbb{N}$ 
\[Q^n(1,1)= Q^n(2,2)=\dots=Q^n(N-1,N-1) = Q^n(N,N) \]
Analogamente a prima ottengo quindi:
\begin{align*}
Q^n(i,i)&= \sum_{h=1}^{N}{Q(h,i)Q^{n-1}(i,h)} = \\
&=(1-\alpha)Q^{n-1}(i,i) +\sum_{h\neq i,h=1}^{N}{Q(h,i)Q^{n-1}(i,h)} = \\
&=(1-\alpha)Q^{n-1}(i,i) +\frac{ \alpha}{N-1} \sum_{h\neq i,h=1}^{N}{Q^{n-1}(i,h)} = \\
&=(1-\alpha)Q^{n-1}(i,i) +\frac{ \alpha}{N-1} \left(1-Q^{n-1}(i,i)\right) = \\
&=\frac{ \alpha}{N-1} + Q^{n-1}(i,i)\left(1-\alpha - \frac{ \alpha}{N-1} \right) =\\
&=\frac{ \alpha}{N-1} + Q^{n-1}(i,i)\left(1-\alpha\frac{N}{N-1} \right)
\end{align*}
Risolvendo la ricorrenza come prima si ottiene:
\[Q^n(i,i)=(1-\alpha)\left(1-\alpha\frac{N}{N-1} \right)^{n-1} + \frac{ \alpha}{N-1} \left(\frac{\left(1-\alpha\frac{N}{N-1} \right)^{n-1} -1}{\left(1-\alpha\frac{N}{N-1} \right) -1} \right) \]
\end{proof}

\end{document}
