Markov chain between between days N-3, N-2, and N-1 and N

Question

Suppose that whether or not a web server is in a fully operational mode at a specific day N depends on previous conditions of the server through the last three days only, i.e., days N-1, N-2 and N-3. Show how the performance of this web server can be analysed using a Markov chain. How many states are needed for the Markov chain?

Answer 1

Let $X_N$ the state of the web server at $N^{\text{th}}$ day. It can be either $0$ (not fully operational) or $1$ (fully operational) thus 2 states are needed: $0$ and $1$. Since $X_N$ depends only on $X_{N-1},\dots,X_{N-3}$, this gives a Markov chain of order 3. (see here)

If you want to obtain a Markov chain $Y_N$ of order 1 (i.e. where the distribution of $Y_N|Y_1,\dots,Y_{N-1}$ depends only on $Y_{N-1}$, you can define $Y_{N} := (X_N,X_{N-1},X_{N-2})$ which has 8 possible states, these states being the elements of $\{0;1\}^3$ and check that for all $k = (k_1,k_2,k_3), k' = (k'_1,k'_2,k'_3)\in\{0;1\}^3 $: \begin{eqnarray}\Bbb P(Y_N=k|Y_{N-1}=k') &= \Bbb P(X_N = k_1, X_{N-1} = k_2, X_{N-2} = k_3| X_{N-1} = k'_1, X_{N-2} = k'_2, X_{N-3} = k'_3)\\ & = \Bbb P(X_N = k_1 | X_{N-1} = k_2, X_{N-2} = k_3, X_{N-1} = k'_1, X_{N-2} = k'_2, X_{N-3} = k'_3)\times \Bbb P(X_{N-1} = k_2,X_{N-2} = k_3| X_{N-1} = k'_1, X_{N-2} = k'_2, X_{N-3} = k'_3)\end{eqnarray} (using the formula $\Bbb P(A\cap B|C) = \Bbb P(A|B\cap C)\times \Bbb P(B|C)$).

Of course, if $(k_2,k_3) \neq (k'_1,k'_2)$, this is $0$. Otherwise, we obtain:

\begin{eqnarray}\Bbb P(Y_N=k|Y_{N-1}=k') &= \Bbb P(X_N = k_1 | X_{N-1} = k_2, X_{N-2} = k_3, X_{N-3} = k'_3)\times \Bbb P(X_{N-1} = k_2,X_{N-2} = k_3| X_{N-1} = k_2, X_{N-2} = k_3, X_{N-3} = k'_3) \end{eqnarray}

Now, on the RHS, the 1st probability can be seen as $$\Bbb P(X_N = k_1 | X_{N-1} = k_2, X_{N-2} = k_3, X_{N-3} = k'_3, X_{N-4} = x,\dots, X_0 = x_0)$$ since the state $X_N$ depends only on the states at times $N-1,N-2,N-3$.

The 2nd probability on the RHS can be decomposed using the same formula $\Bbb P(A\cap B|C) = \Bbb P(A|B\cap C)\times \Bbb P(B|C)$ and you can thus conclude (...) that $Y_N$ is a Markov chain of order 1.