Markov Process – Checking Memoryless Property in Markov Chains

markov-process

I suspect that a series of observed sequences are a Markov chain…

$$X=\left(\begin{array}{c c c c c c c}
A& C& D&D & B & A &C\\
B& A& A&C & A&D &A\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\
B& C& A&D & A & B & E\\
\end{array}\right)$$

However how could I check that they indeed respect the memoryless property of $$P(X_i=x_i|X_j=x_j)?$$

Or at the very least prove that they are Markov in nature? Note these are empirically observed sequences. Any thoughts?

EDIT

Just to add, the aim is to compare a predicted set of sequence from the observed ones. So we'd appreciate comments on as to how best to compare these.

First Order Transition matrix $$M_{ij}=\displaystyle \frac{x_ij}{\sum^mx_{ik}}$$ where m=A..E states

$$
M=\left(\begin{array}{c c c c c c c}
0.1834& 0.3077 & 0.0769& 0.1479 & 0.2840\\
0.4697& 0.1136 & 0.0076 & 0.2500 & 0.1591\\
0.1827& 0.2404& 0.2212 & 0.1923 & 0.1635\\
0.2378 & 0.1818& 0.0629& 0.3357 & 0.1818\\
0.2458 & 0.1788& 0.1173 & 0.1788 & 0.2793\end{array}\right)$$

Eigenvalues of M
$$E =\left(\begin{array}{c c c c c c c}
1.0000 & 0 & 0 & 0 & 0 \\
0 & -0.2283 & 0 & 0 & 0 \\
0 & 0 & 0.1344 & 0 & 0\\
0 & 0 & 0 & 0.1136 – 0.0430i & 0 \\
0 & 0 & 0 & 0 & 0.1136 + 0.0430i\\
\end{array}\right)$$

Eigenvectors of M
$$V =\left(\begin{array}{c c c c c c c}
0.4472& -0.5852 & -0.4219 & -0.2343 – 0.0421i & -0.2343 + 0.0421i\\
0.4472 & 0.7838 & -0.4211 & -0.4479 – 0.2723i & -0.4479 + 0.2723i\\
0.4472 & -0.2006 & 0.3725 & 0.6323 & 0.6323 \\
0.4472 & -0.0010 & 0.7089 & 0.2123 – 0.0908i & 0.2123 + 0.0908i\\
0.4472 & 0.0540 & 0.0589 & 0.2546 + 0.3881i & 0.2546 – 0.3881i\\
\end{array}\right)$$

Best Answer

I wonder if the following would give a valid Pearson $\chi^2$ test for proportions as follows.

Estimate the one-step transition probabilities -- you've done that.
Obtain the two-step model probabilities: $$ \hat p_{U,V} = {\rm Prob}[X_{i+2}=U|X_i=V] = \sum_{W\in\{A,B,C,D\}} {\rm Prob}[X_{i+2}=U|X_{i+1}=W]{\rm Prob}[X_{i+1}=W|X_i=V] $$
Obtain the two-step empirical probabilities $$\tilde p_{U,V} = \frac{\sum_i \# X_i = V, X_{i+2} = U}{\sum_i \# X_i = V}$$
Form Pearson test statistic $$T_V = \# \{X_i = V\} \sum_U \frac{(\hat p_{U,V} - \tilde p_{U,V})^2}{\hat p_{U,V}}, \quad T=T_A + T_B + T_C + T_D$$

It is tempting for me to think that each $T_U \sim \chi^2_3$, so that the total $T\sim \chi^2_{12}$. However, I am not entirely sure of that, and would appreciate your thoughts on this. I am not likewise not co sertain about whether one needs to be paranoid about independence, and would want to split the sample in halves to estimate $\hat p$ and $\bar p$.

Related Solutions

Solved – Estimating Markov transition probabilities from sequence data

Please, check the comments above. Here is a quick implementation in R.

x <- c(1,2,1,1,3,4,4,1,2,4,1,4,3,4,4,4,3,1,3,2,3,3,3,4,2,2,3)
p <- matrix(nrow = 4, ncol = 4, 0)
for (t in 1:(length(x) - 1)) p[x[t], x[t + 1]] <- p[x[t], x[t + 1]] + 1
for (i in 1:4) p[i, ] <- p[i, ] / sum(p[i, ])

Results:

> p
          [,1]      [,2]      [,3]      [,4]
[1,] 0.1666667 0.3333333 0.3333333 0.1666667
[2,] 0.2000000 0.2000000 0.4000000 0.2000000
[3,] 0.1428571 0.1428571 0.2857143 0.4285714
[4,] 0.2500000 0.1250000 0.2500000 0.3750000

A (probably dumb) implementation in MATLAB (which I have never used, so I don't know if this is going to work. I've just googled "declare vector matrix MATLAB" to get the syntax):

x = [ 1, 2, 1, 1, 3, 4, 4, 1, 2, 4, 1, 4, 3, 4, 4, 4, 3, 1, 3, 2, 3, 3, 3, 4, 2, 2, 3 ]
n = length(x) - 1
p = zeros(4,4)
for t = 1:n
  p(x(t), x(t + 1)) = p(x(t), x(t + 1)) + 1
end
for i = 1:4
  p(i, :) = p(i, :) / sum(p(i, :))
end

Chi-Squared Test – Using $\chi^2$ to Compare Two Markov Transition Matrices

It looks as though you would like to use the Pearson $\chi^2$ test to assess whether a sample $x_1,...,x_n$ that is taken from a first-order chain with transition probabilities given by $M$ is well fit by the second order chain with transition probabilities given by $M^2$.

The notation you are using is a little confusing only because it seems to imply matrix multiplication. What I understand you to mean is that if I collapse transition probabilities in $M^2$ then I'll get the transition probabilities given in $M$.

Is the $\chi^2$ test appropriate here?

It depends on what you are testing. But, I think in your case that the idea is good.

The form of the $\chi^2$ test should be a bit different. For example, see the Wikipedia entry on Pearson's chi-squared test. If the expected values are denoted $E_\alpha$ and the observed values $O_\alpha$, the form of the test should be $$X^2 =\sum_\alpha \frac{\left(O_\alpha - E_\alpha\right)^2}{E_\alpha}.$$

Now, we need to think of the second-order chain in its flattened first-order form. That is, the matrix of transition probabilities consists of the bigram transition probabilities.

If we let $f_{ij}$ be the frequencies of observed bigram transitions taken from the sample $x_1,...,x_n$, $f_{i}$ the observed frequencies of bigrams, and $p_{ij}$ the second-order transition probabilities given in $M^2$, then we can calculate the Pearson $\chi^2$ statistic $$X^2 = \sum_{ij} \frac{\left(f_{ij} - f_{i}p_{ij}\right)^2}{ f_{i}p_{ij}},$$ and per Billingsley (1960) $$X^2 \sim \chi^2_{d-s},$$ where $d$ is the number of positive entries in the transition matrix $M^2$ and $s$ is the number of unique bigrams.

This gives an evaluation of how well the distribution $M^2$ fits the data $x_1,...,x_n$.

Billingsley credits Bartlett (1951) with this result, so as usual these days we are looking at material that has been developed some time ago! Billingsley also notes that the usual $\chi^2$ test on values from a Markov chain may be interpreted as a test for independent sampling given that the sampling is derived from a first-order Markov chain.

MS Bartlett (1951) The frequency goodness of fit test for probability chains. Proc. Camb. Phil. Soc. 47: 86--95.

P Billingsley (1960) Statistical methods in Markov chains. Technical Report P-2092. The RAND Corporation.

Best Answer

Related Solutions

Solved – Estimating Markov transition probabilities from sequence data

Chi-Squared Test – Using $\chi^2$ to Compare Two Markov Transition Matrices

Related Question