# Distribution of binary sequences?

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?

• Start with bitwise XOR Mar 3 '15 at 21:32
• Thank you. Could you please be a little more specific? Mar 3 '15 at 21:56
• 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. Mar 3 '15 at 21:59

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.
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.