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.
 A: 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.
A: Randomness of the sequences is a well studied problem as it is connectedd with the encryption standards, the National Institute of Standards and Technologies (NIST) has a publication and 131 pages book of such methods, check them out:
https://www.nist.gov/publications/statistical-test-suite-random-and-pseudorandom-number-generators-cryptographic-0
https://nvlpubs.nist.gov/nistpubs/legacy/sp/nistspecialpublication800-22r1a.pdf
More methods were also developed and target more pattern-like search:

*

*https://www.researchgate.net/publication/220240814_A_Randomness_Test_Based_on_T-Complexity - see also their references,

*compression tests: If you try to compress a truly random string, compression algorithms won't find any patterns and the resulting file will have very similar size to the original.

You can cluster such sequences by several techniques:

*

*first, the compression method mentioned above can work like a meassure of similarity, where you compress each sequence separately and together. If the two files match, their compressed size will be the same as the individuals. With less shared patterns, the sizes will differ. See e.g., https://ksvi.mff.cuni.cz/~mraz/bioinf/BioAlg11-4c.pdf  .

*Bioinformatitians in general have bunch of algorithms for comparison and clustering of the sequences as they cluster DNA sequences, see e.g., https://bioinformaticshome.com/bioinformatics_tutorials/sequence_alignment/introduction_to_sequence_comparison.html .

*Classical sequence/string comparison tools are available (Hamming distance, Levensthein distance, Damerau-Levensthein distance, see more here https://en.wikipedia.org/wiki/String_metric ), these could be handy.

*Time-series approach: https://en.wikipedia.org/wiki/Dynamic_time_warping and more.

I hope some of these can help
