%\subsection{Grafo delle transizioni}


Spesso si è soliti interpretare una catena di Markov del primo ordine con un grafo orientato. In quest'ottica, l'evento $[ q_t = S_i ]$ rappresenta il fatto che la catena si trova nello stato $S_i$ al tempo $t$, mentre l'evento $[q_t = S_j |q_{t-1} = S_i]$ è interpretato come la transizione
della catena dallo stato $S_i$ allo stato $S_j$. 
La costruzione del grafo avviene quindi seguendo le seguenti semplici istruzioni:
\begin{enumerate} 
\item ad ogni stato della catena si associa un nodo nel grafo;
\item per ogni coppia di nodi nel grafo, l'arco orientato tra il nodo corrispondente all'evento $[q_{t-1} = S_i]$ e quello corrispondente all'evento $[q_t = S_j]$ viene etichettato con il valore di probabilità $a_{ij} = \mathcal{P}[q_{t+1} = S_j |q_t = S_i]$.
\end{enumerate}

L'intero problema considerato può essere pertanto associato alla creazione di un grafo, in cui ogni nodo, come si è detto nell'introduzione, rappresenta una regione dello spazio, che per qualche motivo è da considerare distinta dalle altre. 
Essi sono determinati dall'analisi delle osservazioni, cioè dai dati provenienti dalle VCC, e sono raccolti in una opportuna struttura dati che è in grado di contenere le informazioni necessarie a descriverne il legame con gli altri. 
In particolare, per i fini voluti, è necessario tenere conto di quali sono gli stati ""futuri'' legati a uno stato ""presente'', cioè verso quali è possibile transitare da un certo nodo in analisi. 
Per avere una descrizione più completa dei dati, e quindi del comportamento del \emph{target} in movimento, si è deciso di tener conto anche degli stati ""passati'' legati ad ogni nodo, nonchè dell'informazione di permanenza nello stesso stato.

\begin{figure}[h]
	\begin{center}
	\includegraphics[width=0.6\textwidth]{pictures/Grafo}
	\end{center}
	\mycaption{Esempio di un grafo descrittivo di una catena di Markov, si notino come gli archi uscenti da ciascun nodo sommi a 1.}
	\label{fig:}
\end{figure}

Una volta creato il grafo, quindi la catena di Markov senza memoria (intendendo che per le transizioni non conta il passato ma solo lo stato presente) a partire dalle osservazioni, sarà eseguita un'ulteriore elaborazione considerando un po' di ""storia'' legata a ciascuno stato. 
In sostanza si guarda quali percorsi passato-presente-futuro lo interessano e si decide, secondo un qualche criterio da definirsi, se ha senso scindere tale stato in due sottostati per dare una descrizione più verosimile del comportamento dell'oggetto in movimento e della topologia della rete analizzata.




