I'm trying to figure out how to estimate, given a transition matrix for a stream of distinct things, what the p-value is that the underlying stream is memoryless. In order to simplify the problem, I'm constraining my view of the world somewhat so that the alternative hypothesis is "the next item depends on the previous item". I'm okay with implicitly assuming that streams with more exotic dependencies between items in the stream are impossible.


Consider a random stream of integers in the range $\{1, \cdots, n \}$, let's call it $X$ .

If it is the case that the entries in $X$ are independent and drawn from a particular distribution $P$, then the transition matrix $T$ would have constant rows, since the previous state is irrelevant.

$$ \left[ \begin{array}{ccc} p_1 && p_1 && p_1 \\ p_2 && p_2 && p_2 \\ p_3 && p_3 && p_3 \end{array} \right] \left( \begin{array}{c} x_1 \\ x_2 \\ x_3 \end{array} \right) $$


For the sake of example, here's a bad test statistic I've come up with on the spot that probably doesn't have the right behavior but does serve to illustrate the goal.

Let $w$ be the sum of the variances of the individual rows of the matrix divided by their mean squared, since that would be zero if the rows are constant. It also normalizes for the number of rows and how probable each of the items are to begin with.

$$ w \stackrel{df}{=} \sum_{i=0}^n \frac{\mathrm{Var}(A_{i*})}{\mathop{(\mathbb{E}}A_{i*})^2} $$

If I have an empirical estimate of $T$, computed by tallying frequencies, and then compare that with a distribution for $w$ (possibly parameterized for the number of items in the matrix), I can get back a p-value.

I don't know what the distribution would be, but I'm okay with computing an EDF and using that to get the p-value instead of a closed form solution.

  • +1 Welcome to our site, Greg! I suspect a standard $\chi^2$ test might make short work of this; if not, a slight generalization (use a GLM) will do. Is there some reason you are not considering those standard approaches? Perhaps I misunderstand your data or how you are estimating the transition matrix. – whuber Nov 8 at 20:25
  • Hello. In short, it's because I don't really know the standard approaches very well or why they are standard. I'd like the distribution for the test statistic to (ideally) not depend on how common each of the states are within $P$ . Maybe doing a $\chi^2$ on each of the rows would work, but I'm not sure how to combine the results or how to interpret what I've done by combining them. I'm basically trying to figure out how to pick a statistic from first principles that maximizes my ability to distinguish a "0-memory-stream" and a "1-memory-stream". – Gregory Nisbet Nov 8 at 20:39

It turns out there's a simple answer based on comparing the row-wise entropy of the rows of the "empirical transition matrix" $T$ and the "empirical frequency vector" $\vec{f}$ .

$$ \Lambda = \frac{\exp(kH'(T))}{\exp(kH(\vec{f}))} $$

In the above example $H'$ is the row-wise entropy, defined below.

The proof below mostly works, but I think it needs a clear argument for why ignoring elements with probability zero is okay.


In order to solve the problem as originally stated where $H_0$ is a model where the elements of the stream are independent and $H_a$ is "the model depends on the previous state", we can set this up as a likelihood ratio test. By the Neyman-Pearson lemma, this gives us the most powerful such test.

Let the models in $H_0$ be parameterized by $\vec{p}$ which is a vector in $[0, 1]^n$ where the elements sum to 1. Let $\vec{v}$ be the vector of length $k$ from the observations from the string. Let $\vec{f}$ be a vector of length $n$ recording the observed frequencies of each observation in $\vec{v}$ .

Let $L_0$ be the likelihood associated with the champion model.

$$ L_0 = \max_{\vec{p}} \prod_{i=1}^{k} \vec{p}_{\vec{v}\,[1]} $$

Let's rearrange the product so our index ranges over outcomes rather than observations

$$ L_0 = \max_{\vec{p}} \prod_{i=1}^{n} \vec{p}_{i}^{(k\vec{f}_i)} $$

Compute the logarithm

$$ \log L_0 = (k) \max_{\vec{p}} \sum_{i=1}^n \vec{f}_i \log (\vec{p}_i) $$

The dot product $\vec{f} \cdot log(\vec{p})$ is the negative of the cross entropy. The cross entropy is minimzed by picking $\vec{p} = \vec{f}$.

so, now we have a closed form.

$$ \log L_0 = (k) \vec{f} \cdot \log(\vec{f}) = -kH(\vec{f}) $$

Let $L_a$ be the likelihood associated with the champion alternate model. Let $Q$ be the transition matrix we're picking. Let $T$ be the empirical tally matrix with each row normalized to have unit sum.

There's a small detail to handle with the first element, since it isn't transitioned to from another state. The proper thing to do would probably be to sample from the limiting distribution of $Q$ , so that our alternative models are still penalized in some way for "being surprised at" the first observation. However, for the sake of expedience, I'll say that an alternative model can freely pick the starting element, making its contribution to the likelihood $1$ . The first element is thus a freebie.

$$ L_a = \max_Q \prod_{i=2}^k Q_{(\vec{v}[i-1],\, \vec{v}[i])} $$

This product can be rearranged into a double product over $\{1 \cdots n \}$ .

$$ L_a = \max_Q \prod_{i=1}^n \prod_{j=1}^n Q_{(i,j)} ^ {kT_{(i,j)}} $$

Take the log as before

$$ \log L_a = (k) \max_Q \sum_{i=1}^n \sum_{j=1}^n (T_{(i,j)}) \log(Q_{(i,j)}) $$

So, now we have to be careful, each row of $Q$ has unit sum, so we'll define the row-wise entropy $H'(T)$ as the sum of the entropy of the rows in $T$ .

$$ H'(T) \stackrel{df}{=} \sum H(T_{(i, \cdot)}) $$

so then, by applying the same argument about minimizing the cross-entropy as before and noting that $H'$ is linear, we get

$$ \log L_a = -kH'(T) $$

Which makes the likelihood ratio is

$$ \Lambda = \frac{\exp(kH'(T))}{\exp(kH(\vec{f}))} $$

And then our chosen p-value cutoff can be applied to $\Lambda$ directly.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.