0
$\begingroup$

I have two binary sequence and wanted to test if there is a similar patterns between the two. This is a completely new topic for me. Are there ways to define distribution of a binary sequence (distribution of 1, for example)? And how to check if the two sequence are similar?

$\endgroup$
3
  • 1
    $\begingroup$ Start with bitwise XOR $\endgroup$
    – Aksakal
    Mar 3 '15 at 21:32
  • $\begingroup$ Thank you. Could you please be a little more specific? $\endgroup$
    – bankrip
    Mar 3 '15 at 21:56
  • $\begingroup$ Say, you have two sequences of equal length: 1001 and 0001, then the bitwise XOR operation will give 1000, sum the bits you get 1. That's the difference. Compare it to 1001 and 0110, you get XOR 1111, the sum of bits is 4, i.e. for bits are different. $\endgroup$
    – Aksakal
    Mar 3 '15 at 21:59
3
$\begingroup$

As Aksakal says, start with the bitwise Exclusive OR. A standard name for what he is proposing is finding the Hamming distance -- the number of places where the sequences differ -- between the two sequences. It is easy to show that if the sequences are chosen at random (all $2^n$ are equally likely to be chosen), then the expected value of the Hamming distance is $\frac n2$. Thus, if the Hamming distance is close to $\frac n2$, the sequences are quite different. If the Hamming distance is close to $0$, the sequences are very similar. If the Hamming distance is close to $n$, the sequences are almost complementary to each other: flipping all the bits in one gives you a sequence that is very close (in the Hamming metric) to the other. If the Hamming distance is exactly $n$, the sequences are complementary, for example, $1001$ and $0110$ in Aksakal's example.

There can be other measures of similarity that people can think of. For example, $10111001$ and $01011100$ of length $8$ have Hamming distance $6$, but the latter has the trailing subsequence $1011100$ which is just the leading subsequence of the former. So, this is a "similarity" that is of interest in several applications (especially in engineering which is where I am coming from). Look for literature on Hamming autocorrelation and crosscorrelation of sequences.

$\endgroup$
1
  • 1
    $\begingroup$ @bankrip, also consider this sequence 1010 and 0101. This would have hamming distance 4, as per Dilip's answer, but some could say the sequences are very similar. For instance, 1010 is a mirror image of 0101. Also, the simple one bit circular shift would produce 0101 from 1010 etc. It's important to figure out what does similar mean. $\endgroup$
    – Aksakal
    Mar 4 '15 at 15:00
1
$\begingroup$

you need to first define in what terms you want to assess the similarities. For instance, you can think of the sequence $i$ of length $N_i$ being sampled from a binomial (with parameter $p_i$); here the comparison can simply be a comparison of $p_1$ and $p_2$. You can approximate them with normal (mean = $N*p*(1-p)$ and do T-test. Another way can can be to look at higher order statistics (e.g., entropy) and compare the two sequences in that term ... As you see, depending on the problem you want to solve, the comparison can have different meanings.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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