Determine whether two binary sequences are correlated 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)


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.
