Determine whether two binary sequences are correlated

Question

I have two arrays of 2048 binary values (1 and 0) and I'd like to find out if their content can be considered correlated. I'd like to have less than 1:1000000 chance of a false positive in determining the correlation.

I'm looking for a percentage number as well as a formula.

We can assume the binary values to have been generated by uniform random variables that may or may not be independent. The task is to find out whether they are independent or correlated. I assume with 2048 values, they can be considered uncorrelated if around 50% values are different. But they will never be exactly 50% different because they are random values. They may be 49% different and we may still be quite confident that there is no correlation.

Note: The only value I have as input for the algorithm is the number of positions that are different (denoted popcount(A xor B) in the example).

Let X=popcount(A xor Y)/2048 with A and B independent uniform random variables. I think X would form a Gauss distribution around 0.5 and its standard deviation would probably be the main ingredient of the answer, I think.

Example 1:

Pattern A          100111010101010111111111
Pattern B          100101010001000111111101
A xor B            000010000100010000000010
popcount(A xor B)  4
In percentage      4/24=16.7%
Interpretation     Correlated (only 4 positions differ) 

Example 2:

Pattern A          100111010101010111111111
Pattern B          001100110001000100101101
A xor B            101011100100010011010010
popcount(A xor B)  11
In percentage      11/24=45.8%
Interpretation     Not Correlated (nearly 50% different)

Answer 1

Assuming that the binary values in each sequence can be regarded as $i.i.d.$ Bernoulli random variables with $p=1/2$ (equal probability for 0 and 1), then the quantity popcount(A xor B) is simply a Binomial variate with mean $n/2$ and variance $n/4$ (under the hypothesis of no correlation).

So, to get your desired false positive rate of $10^{-6}$, find the upper and lower quantiles of the Binomial distribution with that tail probabililty. With your parameters ($p=1/2$ , $n=2048$) those are $913$ and $1135$, or $44.6\%$ and $55.4\%$ in percentage terms (you can find functions that calculate this in many common libraries or even online).

Since $n$ in your case is large enough you can equivalently use a normal approximation for the Binomial distribution and calculate the quantiles via

$$ \frac{1}{2} \pm \frac{\Phi^{-1}(10^{-6}/2)}{2\sqrt{n}} $$

Where $\Phi$ is the normal CDF.

Notice the assumption of $i.i.d.$ - I'm guessing that this is what you intended to mean in your question, although you didn't describe it clearly enough. If that assumption doesn't hold things get much more complicated (as you can see from whuber's answer) and you won't be able to make meaningful conclusions based only on the single quantity $X$.

Lastly, your use of the terms independence and correlation is a bit confusing - when you say that "The task is to find out whether they are independent or correlated", it sounds like you refer to "independent" as being equivalent to "not correlated". While this is true for a pair of binary variables, it is generally not the case.

Answer 2

You describe two reasonably long sequences $(X_i)$ and $(Y_i)$ of binary values and, with due caution, do not assume independence. Let's parse the possible meanings of that.

Uncorrelated sequences

First, if the $(X_i)$ are independent and the $(Y_i)$ are independent (and therefore uncorrelated), your problem comes down to assessing the sequence of independent variables $(X_i,Y_i).$ These variables have four possible values $(0,0),$ $(0,1),$ $(1,0),$ and $(1,1).$ The $2\times 2$ contingency table summarizes all the relevant information (it is a sufficient statistic for the data):

$$\begin{array}{l|cc|l} & Y=0 & Y=1 & \text{Total}\\ \hline X=0 & n_{00} & n_{01} & n_{0\cdot}\\ X=1 & n_{10} & n_{11} & n_{1\cdot}\\ \hline \text{Total} & n_{\cdot 0} & n_{\cdot 1} & n \end{array}$$

The cell values $n_{ij}$ count how many of the pairs equal $(i,j).$

If you don't make any assumptions about the rate at which each variable will produce $1$s, you can estimate that rate from the counts. The estimated rate for $X$ is $\hat p_X=n_{1\cdot}/n$ and the estimated rate for $Y$ is $\hat p_Y=n_{\cdot 1}/n.$ Otherwise, let $p_X$ be your assumed (or stipulated) rate for $X$ and $p_Y$ your rate for $Y.$ The analysis of the table is the same whether you put hats on $p_X$ and $p_Y$ or not.

If $X$ and $Y$ are independent (your null hypothesis), the rate in each cell ought to be the product of the corresponding rates times the total $n.$ Writing $\hat q_x = 1-\hat p_X$ and $\hat q_Y = 1-\hat p_Y$ for the rates of zeros gives the expected values $e_{ij},$

$$\begin{array}{l|cc|l} & Y=0 & Y=1 & \text{Total}\\ \hline X=0 & n \hat q_X \hat q_Y & n \hat q_X \hat p_Y & n \hat q_X\\ X=1 & n \hat p_X \hat q_Y & n \hat p_X \hat p_Y & n \hat p_X\\ \hline \text{Total} & n \hat q_Y & n \hat p_Y & n \end{array}$$

Given $n$ and your estimates $\hat p_X$ and $\hat p_Y,$ this table is determined by any single value in its cells. This leads to zillions of mathematically equivalent statistics you can use to express how much the data contingency table differs from this table of expectations: the odds ratio; the $\phi$ coefficient (which can range from $-1$ to $1$ and thereby satisfy your request for a "correlation"); Cramér's $V$; the contingency coefficient $C$; the tetrachoric correlation coefficient; asymmetric and symmetric $\lambda$ coefficients (also suitable as unsigned correlations); Theil's $U$ (another candidate for correlation); Cohen's $\kappa$; various formulas in terms of "true" and "false" "positives" and "negatives;" etc., etc.

One of the most useful statistics, though, is the $\chi^2$ (Chi-square) statistic. It is obtained from the residuals $n_{ij} - e_{ij}:$ you square each residual, divide that result by the expectation $e_{ij},$ and sum the values:

$$\chi^2 = \sum_{i=0}^1 \sum_{j=0}^1 \frac{\left(n_{ij} - e_{ij}\right)^2}{e_{ij}}.$$

When the $X$ and $Y$ sequences are independent, this value should be around $1$ (when you estimate the rates) with a standard deviation of $\sqrt 2;$ or around $3$ with a standard deviation of $\sqrt 6$ when you don't estimate the rates. Provided all four expected values are sufficiently large (usually $5$ is good enough), $\chi^2$ closely follows the chi-squared distribution with $1$ (or $3$) degrees of freedom. Large values of $\chi^2$ evidently indicate there are one or more large discrepancies between observed and expected frequencies and thereby provide evidence against the independence hypothesis. The chi-squared distribution can be used to produce p-values.

Correlated sequences

This is trickier. Intuitively, when one (or both) of the sequences $X$ and $Y$ is not independent, that will manifest in serial correlation. With positive serial correlation, a value tends to persist for a while before the other value appears. The patterns in the first example of the question exhibit this tendency at the end where long runs of ones appear. These runs can accidentally produce greater discrepancies (larger chi-squared statistics) than one might otherwise suppose.

To show that this matters, I generated two such sequences of length $n=2048$ many times. In the first case, each value was followed by the same value with a probability of $\rho = 0.05.$ These sequences tend to alternate zeros and ones. I did this again with $\rho = 0.5$ (random sequences) and $\rho=0.95$ (strong positive serial correlation). These histograms summarize the values of the resulting chi-squared statistics.

The middle panel, for the uncorrelated case, gives exactly what we would expect: the histogram closely approximates the $\chi^2(1)$ distribution plotted by the red curve. The other panels show how the statistics tend to be hugely greater than expected (the values are shown on a log scale, after all).

One way to cope with this is a "circular bootstrap." Basically, we rotate the arrays relative to each other, thereby matching $X_i$ with $Y_{i+h \mod n}$ when rotating by a lag of $h.$ This is a way of breaking the association between $X$ and $Y$ (via the rotation) without destroying the correlations internal to $X$ and $Y.$ The collection of all resulting chi-squared statistics (omitting, perhaps, small values of $h,$ which might not completely eliminate the effects of serial correlation) gives us a sense of what their values ought to be when there is no association between $X$ and $Y.$ This is theoretically justified for sufficiently long sequences.

The next figure shows the results of bootstrapping two binary $(X,Y)$ datasets of length 2048.) At the left, $X$ and $Y$ were independently generated with high serial correlation ($\rho=0.95$). This is the bootstrap distribution under the null hypothesis $H_0.$ At the right, $X$ was slightly modified by forcing it to agree with $Y$ with a chance of $10\%$ at each position. This randomly changed it at $120$ out of the $2048$ positions, creating a statistical dependence between $X$ and $Y$ corresponding to an alternate hypothesis $H_A.$

The p-values are given by the proportion of bootstrap results with larger (more discrepant) chi-squared values. The independent data have (in this example) a p-value of $0.91,$ not at all statistically significant. The dependent data have a p-value of $0.048,$ which many would consider significant.

This example thereby demonstrates that this chi-squared "circular bootstrap" can be effective at assessing and testing the independence of binary sequences $X$ and $Y$ especially when each sequence might be serially correlated.

This bootstrapping is easier than it might look. Here, for example, is the R code used to produce the previous figure. The omit argument is the minimum number of lags $h$ to leave off at both ends of the rotation. It will thereby output n - 2*omit bootstrap statistics.

chisq.boot <- function(x, y, omit=0, stat=chisq.binary) {
  h <- seq_along(y)[seq(omit+1, length(y)-omit)]
  sapply(h, function(i) {stat(c(x[-seq_len(i)], x[seq_len(i)]), y)})
}

It refers to a function stat to compute the statistic you are using to compare $X$ to $Y.$ The function used here by default is the chi-squared statistic explained in the first half of this post.

chisq.binary <- function(x, y) {
  n <- tabulate(x + 2*y + 1, 4)
  n.x <- n[2] + n[4]
  n.y <- n[3] + n[4]
  n.. <- sum(n)
  e <- c(outer(c(n.. - n.x, n.x), c(n.. - n.y, n.y))) / n..
  sum((n - e)^2 / e)
}

Answer 3

You can compute correlation between vectors/matrices as their dot product scaled by their magnitude (norm). Geometrically, this represents the cosine of the angle formed between them. Ie: $\text{corr}(\mathbf{X},\mathbf{Y}) = \frac{\left< \mathbf{X}, \mathbf{Y} \right>_F}{\| \mathbf{X} \|_F \| \mathbf{Y} \|_F }$ where the inner product between matrices (from which the norm follows) is the Frobenius norm, that is the $\ell_2$ norm over the matrice viewed as a vector : $\text{vec}(\mathbf{X})$.