\begin{slide}{violet}
\violet
\begin{center}
Markov Model
\end{center}
{\it first-order} Markov chain: 
next state probabilities depend only upon the
current state 

assume measured sequence of virtual cylinders visited
represents a Markov chain of some order, perhaps order 0 (independent) 

$vc(t) \in\{1,2,...,2181\}$: virtual cylinder accessed on $t^{th}$ request
\begin{eqnarray*}
N_j(t) & = & \left\{
\begin{array}{ll}
1 & \mbox{if $vc(t)$=$j$}\\
0 & \mbox{otherwise}
\end{array}
\right.\\
N_{ij}(t) & = & \left\{
\begin{array}{ll}
1 & \mbox{if $vc(t)$=$j$ and $vc(t-1)$=$i$}\\
0 & \mbox{otherwise}
\end{array}
\right.\\
\end{eqnarray*}
maximum likelihood estimators of $\pi_j$ and $\rho_{ij}$:\\ 
$$
\hat{\pi}_{j} = \sum_{t=1}^T N_j(t)/T 
$$
$$
\hat{\rho}_{ij}  = \sum_{t=2}^T N_{ij}(t)/\sum_{t=2}^T N_{i}(t-1)
$$
test:
$$
H_0: \rho_{ij} = \pi_j \quad \forall i,j \mbox{\quad (Markov chain is order 0)}
$$
versus the alternative
$$
H_1:\rho_{ij} \neq \pi_j \quad \forall i,j \mbox{\quad (Markov chain has order $\ge$ 1)}
$$
\quad\\
\quad\\
\quad\\
\[ \chi_0^2 = \sum_{i=1}^N \sum_{j=1}^N \sum_{t=2}^T
N_{i}(t-1) \ [ \hat{\rho}_{i j} - \hat{\pi}_{j} ]^2 \ / \ \hat{\pi}_{j} \]
has $\chi^2$ limiting distribution 
with $N(N-1)$ degrees of freedom.

result: reject $H_0$ at significance $<$ 0.001 


