# Comparing noisy data sequences to estimate the likelihood of them being produced by different instances of an identical Markov process

(Prompted to some extent by the answers already given by Shane and Srikant, I've rewritten this to try to clarify what I'm getting at, if only to myself.)

Suppose we have several similar systems, each with behaviour that approximates a continuous time Markov process. That is, there are some number of discrete states the system can be in and associated probabilities of transitioning from one state to another at any instant, depending solely on the current state. For now, consider the processes to be stationary, ie the transition probabilities do not change over time, and unaffected by seasonality or other external considerations.

Unfortunately, we cannot measure the state of any system directly, but have instead to measure a proxy quantity, which varies with state but is not discrete and is subject to various sources of noise and error.

The principal question is this:

Q1: Given two data sequences produced independently from two such systems, how can we decide whether the underlying Markov processes are the same?

Now, it may be that the best way to approach this is as two separate problems:

1. Convert the imperfect proxy sequence into an idealised time series of (categorical) states
2. Determine whether the state sequences correspond

On the other hand, such a separation might involve discarding some information from the data in step 1 (eg, about its variability) that would be useful in step 2. Which leads to:

Q2: Does it make sense to decompose the problem in this way or is it better to compare the proxy data directly?

If such a decomposition does make sense, that opens up a whole other issue about how to do the idealisation, but that's definitely a question for another day.

Shane, below, mentions goodness-of-fit and distributional tests such as Anderson-Darling, and that seems like a promising approach. But I'd like to check I'm understanding the idea correctly.

Given sufficient samples in a sequence, we would expect the proportion of time spent in each state to tend to the stationary distribution. So one could test the distributions of occupancies in the two sequences for similarity. (I have the vague sense a two-sample Kolmogorov-Smirnov might suit for this, but please set me right about that.)

The thing is, I'm not sure how good this can be as evidence. If the distributions are very different, that seems like a reasonable strike against the underlying processes being the same, but what if they're very similar? Can we draw conclusions in that direction?

Q3: Does a good fit of occupancy distributions tell us anything useful?

It seems like there could be an infinite number of processes that will tend to the same stationary distribution. I think this is very unlikely in practice, and that different systems will tend to have distinctly different behaviour, but still it's worth considering.

Finally, we will often have a model of the underlying process that we are looking for, although it may not be perfect. So we could compare each sequence with the expected behaviour of the model, instead of with each other. We may also have more than two sequences to test.

Q4: Is it better to compare multiple sequences to a single model, even an approximate one, or are we better off comparing data directly?

• I was interested in using a Kolmogorov-Smirnov test for a similar purpose. As far as I can tell, there is no variant on a K-S test that's appropriate for comparing time series. (I am very, very far from being an expert on such things, however.)
– Mars
Feb 23, 2015 at 20:31

You can perhaps use a hidden markov model (HMM). I know that there is a R package that estimates HMMs but cannot recall its name right now.

A few thoughts:

1. Can you not just use a goodness-of-fit test? Choose a distribution and compare both samples. Or use a qqplot. You may want to do this with returns (i.e. changes) instead of the original series, since this is often easier to model. There are also relative distribution functions (see, for instance, the reldist package).
2. You could look at whether the two series are cointegrated (use the Johansen test). This is available in the urca package (and related book).
3. There many multivariate time series models such as VAR that could be applied to model the dependencies (see the vars package).
4. You could trying using a copula, which is used for dependence modeling, and is available in the copula package.

If the noise is serious concern, then try using a filter on the data before analyzing it.

• Thanks for the suggestions. I'll have to look into them in more detail, but one thing that occurs immediately is that the series do not share a time frame, so cointegration and VAR are probably not relevant. I've edited the question to try to clarify this, apologies for being misleading before. Noise filtering brings up some other issues, but those are for another question and another day! Aug 20, 2010 at 17:44
• Ok. Well, looking at the distributions may be the way to go. You can also try a distribution test such as Anderson–Darling (as in this question: stats.stackexchange.com/questions/1645/…). Aug 20, 2010 at 18:01