I wondered if anyone could give me some advice on this problem?

I need to compare one sequence of (mutually exclusive) states against another (of the same length) to say if they match or not. For example:



Each sequence is actually about 3600 items long and there are 17 symbols (states). The data are categorical labels, with no order in the symbols, so I can’t use a Kolmogorov-Smirnov (K-S) test. (The data are not numeric, I can’t form a cumulative mass distribution.) A simple term-by-term comparison, using scores of match=1, nomatch=0, could give a relative measure, but how then to assess significance? Chi-squared test? The sequence is actually a time-series, so it would be nice to somehow use the information contained in the order?

Is there a statistical procedure to do this comparison?

Alternatively, I could, with significant loss of information, summarize each sequence by calculating the frequencies of each of the (in reality 17) states: For example, assuming 4 states: seq#, a#, b#, c#, d#

seq1, 6, 3, 4, 4

seq2, 7, 3, 5, 2

This data can be plotted on a bar chart – but not a histogram. Again, I can’t use a K-S test, because the 4 states are categorical labels, not numeric, let alone continuous.
The states are mutually exclusive. I believe a Chi-squared test would give an overall measure of the match and whether it was significant?

What I really won’t though is to compare the raw sequences.

I have over 200 pairs of sequences to compare.


Further details: Apologies - I tried to reduce the amount of verbage! As part of my PhD research I observed classroom lessons and collected data on who did what and when. Then I developed an agent-based simulation of the lessons. Now I need to compare the simulation output to the empirical data in order to calibrate and eventually validate the simulation. The sequences are sequences of activity states, every second for about an hour, for each student and for the teacher. I am trying to get my head around how to say that a simulated student is close enough to the empirical student, in terms of their behaviour, their sequence of activity states. I have calculated simple comparisons of various summary performance indicator means (e.g. time in productive states), but the results of two completely different lessons can give almost the same aggregated value. Greater resolution is needed: hence my interest in comparing sequences of activity states.

  • $\begingroup$ If you provide these kinds of contextual information, we can give you better advice. $\endgroup$ Oct 16, 2018 at 14:22
  • $\begingroup$ Is your goal to create some sort of a distance metric between the two strings? If so, you could create a 2d table looking vaguely like a confusion matrix and define some kind of a loss function that rewards the diagonals and penalizes everything else. If you have a well-defined statistical model, why don't you use the model evidence to assess/compare between your models? $\endgroup$
    – adityar
    Oct 16, 2018 at 15:24
  • $\begingroup$ Thanks @InfProbSciX. Yes, a distance metric. That's an interesting idea to create a loss function. I had wondered how best to extract a quantitative measure from a confusion matrix. I'm learning. As for a well-defined statistical model, there isn't one! This whole project has been exploratory, identifying relevant activity states and student and teacher attributes, trying to use attributes and event history to predict what people might do next. $\endgroup$ Oct 16, 2018 at 15:51
  • $\begingroup$ Even a transition matrix would count as a well defined model. Aren't you simulating values somehow? If you can express the model probability law, you'd be able to find the likelihood or the evidence. By the way - when I said 2d table, I meant having labels "a", "b", "c", "d", ... etc. on both sides, so in your example, you'd have a 4x4 matrix - it'd add to the flexibility if you did wanna create some kind of a loss specific to your scenario (e.g. maybe you care more about certain transitions than others) $\endgroup$
    – adityar
    Oct 16, 2018 at 15:54
  • $\begingroup$ Thanks. Yes, I got what you meant about the confusion table: 17x17 for real. Good idea about weighting the more important states. I have 17x17 state transition matrices for classes and lessons, but for students there isn't enough data. I had resigned myself to having a state 'vector' for each student (as posted) that is just a summary of the % time spent in each state, then comparing the simulated and empirical vectors. Because this is a stochastic simulation I need to do, say, 100 replications and somehow use a mean STM. I've been looking a methods to compare matrices - any thoughts? $\endgroup$ Oct 16, 2018 at 16:18

1 Answer 1


Your intuition is correct that you should compare the raw sequences rather than e.g. comparing the counts of the number of times each state appears, because aaabbb is likely to be quite different behavior from bbaaab.

However, significance isn't helpful because you want to examine the degree of association between the simulation and the data. Very weak association could be significant, and very strong association could be non-significant, depending on your sample size and the power of the test you use.

A simple term-by-term comparison, using scores of match=1, nomatch=0, could give a relative measure

This is a good way to start. The greater the proportion of matches, the greater the association. It's wise to compare this proportion to the proportion of times that the real student was in his most common state, in order to get a sense of what proportions are actually good. 97% accuracy might sound good, but if the real student is in a single state 98% of the time, it's really bad—your simulation is worse than a trivial model that predicts the most common state every time.

  • $\begingroup$ Thanks @Kodiologist. I thought term-by-term might be too simplistic and sacrifice so information contained in the sequence? Is there a way to use the order of states as well? (I am reading a paper right now: A Similarity Measure for Sequences of Categorical Data Based on the Ordering of Common Elements). Agreed I need to check the percentages: a simple model that says the student is in the 'expected' state (i.e. just 1 of the 17 states) is overall correct for 80% of the time (for some students it's 99%, others as low as 66%). Thanks again. I'm going to see if I get any other suggestions. $\endgroup$ Oct 16, 2018 at 16:05
  • $\begingroup$ But you are indeed using the order of states if you compare them term-by-term. The behavior records ab and ba would have 0% agreement under this metric. Or do you mean there's an order of some kind among the 17 possible states? $\endgroup$ Oct 16, 2018 at 16:22
  • $\begingroup$ Yes, probably I'm talking rubbish. There's no order in the state labels. What I meant was that term-by-term comparisons can be done in any order of the terms and give the same result? I was just hoping there was an established test statistic, like Chi-squared or Fisher's exact test, only using more detailed data than state frequencies, that I could use and nobody would find fault with! Thanks again. If you have more ideas I'd appreciate hearing them. $\endgroup$ Oct 16, 2018 at 16:40
  • $\begingroup$ "What I meant was that term-by-term comparisons can be done in any order of the terms and give the same result?" — Yes; for example, the agreement between baa and caa and the agreement between aab and aac are both 2/3. This is desirable, unless you have an a priori greater interest in some timepoints than others, or something like that. $\endgroup$ Oct 16, 2018 at 17:05
  • $\begingroup$ "I was just hoping there was an established test statistic, like Chi-squared or Fisher's exact test" — Test statistics are usually only good for significance tests, and see my answer above regarding significance. Remember, in statistics, a fancier method isn't always a better one. The method should fit the question to be answered. $\endgroup$ Oct 16, 2018 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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