3
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – user2390246
    May 16, 2019 at 13:16
  • $\begingroup$ See this stored search $\endgroup$
    – kjetil b halvorsen ♦
    Aug 21, 2020 at 16:15
  • 1
    $\begingroup$ Christian Adam, I encountered this question on the home page (although I can not see an edit or other reason that bumped it up) and wondering whether you are still active on this topic. There might already be several other questions that relate to this question. I am not sure about trying to figure this out as I am not sure what your underlying problem is and whether you can explain it. $\endgroup$
    – Sextus Empiricus
    May 2, 2022 at 13:46
  • 1
    $\begingroup$ @SextusEmpiricus, I am not working on this anymore, but still interested. My problem was similar to this: I analyze posts on reddit. Each post I split into words and then code each word as 1, if it starts with a vowel, or 0 otherwise. So now I have a collection of binary sequences of varying length. And I want to know if there is some structure to them, in particular a) are any clusters and b) can I predict a given 1 or 0 based on its context. One sequence might have length 6 (111000) and another length 20 (11111111110000000000), but structurally they are similar. But how would I find out? $\endgroup$
    – Christian Adam
    May 15, 2022 at 20:52

2 Answers 2

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ It is unclear how your solution for case 1 is working. $\endgroup$
    – Sextus Empiricus
    May 2, 2022 at 13:47
0
$\begingroup$

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:

You can cluster such sequences by several techniques:

I hope some of these can help

Improve this answer
$\endgroup$

Your Answer

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

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