Finding patterns in various-length binary sequences

I have a large number of binary sequences of different lengths (time-series of observations of the occurrence (1) and non-occurence (0) of some thing) and I am wondering how I could find patterns that are common to these sequences. What I am interested in is

• finding out whether the sequences are random in the sense that the thing occurring at one position is independent of its earlier (non-)occurrences

• finding something like typical contours, that is, one or several sequences that are representative for the set. To elaborate, from exploring the data it looks like there is often a) a string of 0s first, then a string of 1s and then some alternating 1s and 0s or b) some alternating and then a string of 1s. This is what I would somehow like to extract or show statistically, though I have no clear idea how.

So how can I say these sequences are not random and they tend to look a certain way? For the first question (test for randomness), what I have thought of so far is to test for auto-correlation, to treat the sequences as a random walk, to compare conditional probabilities or maybe to add the preceding n observations as predictors in a logistic regression (a factor, e.g. for n=2 with levels (0,0), (0,1), (1,0) or (1,1)). For pattern-finding, I could define a similarity/distance measure (maybe hamming distance or pearson correlation) between the sequences and then do clustering? The biggest problem with that is that I don't know how to handle different lengths of the sequences.

Any ideas? I hope this question isn't too broad. I've never had a similar problem and I'm not sure how to tackle it.

• You might want to try looking up Markov chains, and testing whether your sequences fit the model of a first- or second-order Markov process. From the way you've described them they probably don't, but it might at least be a starting point. – user2390246 May 16 at 13:16

For Question 1:

"So how can I say these sequences are not random and they tend to look a certain way? (test for randomness)"

You could use the binomial distribution. A binomial distribution is given by the product of multiple Bernoulli distributions, or trials. e.g. If you toss a fair coin 20 times (trials), how many times may it come up heads? $$X∼Binomial(n,p)$$

The Binomial probability of exactly $$X$$ successes from an experiment with $$n$$ independent trials when the probability of success in each trial is $$p$$. In your case:

• ($$n$$) trials = length of sequence.
• ($$X$$) successes = number of 1's observed in sequence.
• ($$p$$) probability of success = 0.5 aka random.

You can use the CDF to determine if your observed value of $$X$$ in each sequence is different from random at different confidence intervals. I actually set up a demo of this here.

For Question 2:

pattern-finding

Similarly, you could identify the number of k-length successes in your sequences and use the n-choose-k binomial coefficient to determine probability of observing these sequences by random chance.

Also, as you suggest you could explore clustering. Perhaps calculate some second order features such as: the average sequence length, average time between clusters of size k, cumulative 1's, exponential moving averages etc. It really depends on what you mean by pattern finding? Do you want to identify common sequences, if so then why not count the frequencies of k-length 1's and 0's or the time between these. Alternatively, if you want to predict these time series patterns the above listed features, lagged and a classification model may work.