Undergrad Correlation Limits without Probability

[Mentz114]

I'm reposting this piece of logic because my earlier attempts to get it across failed - nobody got what I was saying.

This is about binary sequences like $010110100111001001...$.
All we need to know about a particular sequence is its length, $N$ and the number of 1's it contains. The logic applies to all permutations of any given sequence.
<br /> \begin{align*}<br /> \overbrace{<br /> \underbrace{1111111111...}_\text{count of 1s $=1_K$} \<br /> \underbrace{0000000000...}_\text{count of 0s $=0_K$}<br /> }^\text{length of K is $N=0_K+1_K$}<br /> \end{align*}<br />
The question is - given two sequences labelled A and B with 1 counts of $1_A$ and $1_B$, what is the maximum correlation possible between any permutations of A and B ? The answer is obviously $\pm1$. But this extreme can only be reached by a small subset of all sequences, the remainder having limits $|\rho_M|<1$.

The comparison of two sequences means arranging then in two rows and counting the coincidences 0,0 and 1,1 denoted by $S_{AB}$. The number of anti-coincidences $A_{AB}$ is obviously $N-S_{AB}$. Finally, the correlation between A and B is defined in terms of coincidence counts as $\mathcal{C}_{AB}= (S_{AB}-A_{AB})/(S_{AB}+A_{AB})=(2S_{AB}-N)/N$ which is in $[-1,1]$.

So far everything is definitions and notation. Now comes the crucial ansatz

If $1_A<1_B$ then the maximum number of 1,1 coincidences is $1_A$ and the maximum number of 0,0 coincidences is $0_B=N-1_B$ and the maximum number of symmetric coincidences possible is $S_{AB}= 1_A+0_B = 1_A-1_B +N$ .

Putting this into the correlation gives $1-\frac{2(1_B-1_A)}{N} \le 1$. This can only be 1 if $1_A=1_B$. In all other cases the extreme cannot be achieved because there will be anti-coincidences and coincidences.

Is there a fault in the logic ? I suspect this could be more elegantly reasoned

Has anyone got a reference to something similar ?

 

[andrewkirk]

You appear to be implicitly assuming that both sequences have the same length. I will maintain that assumption.
If $1_A=1_B$ then by sorting both sequences in descending order we see that the sorted sequences are identical, as the first $1_A$ elements of both are 1 and the next $N-1_A$ elements of both are 0. So all pairs match.

Assume WLOG that $1_A\leq 1_B$ and let $1_B-1_A=h$. Then if both sequences are sorted in descending order we have:

• the first $1_A$ elements matching as (1,1), where the first number indicates the $A$ value and the second the $B$ value
  
• the next $h$ elements mismatching as (0,1)
• the last $N-1_B=N-1_A-h$ elements matching as (0,0)

So $S_{AB}=N-h,A_{AB}=h$ and the correlation statistic is $1-2h/N$. Since $0\leq h\leq N$, this statistic is in $[-1,1]$ and it is 1 iff $h=0$ (in which case the two sorted strings are identical) and -1 iff $h=N$ (in which case string $A$ is all 0s and string $B$ is all 1s).

 

[Mentz114]

You appear to be implicitly assuming that both sequences have the same length. I will maintain that assumption.
If $1_A=1_B$ then by sorting both sequences in descending order we see that the sorted sequences are identical, as the first $1_A$ elements of both are 1 and the next $N-1_A$ elements of both are 0. So all pairs match.

Assume WLOG that $1_A\leq 1_B$ and let $1_B-1_A=h$. Then if both sequences are sorted in descending order we have:

• the first $1_A$ elements matching as (1,1), where the first number indicates the $A$ value and the second the $B$ value
  
• the next $h$ elements mismatching as (0,1)
• the last $N-1_B=N-1_A-h$ elements matching as (0,0)

So $S_{AB}=N-h,A_{AB}=h$ and the correlation statistic is $1-2h/N$. Since $0\leq h\leq N$, this statistic is in $[-1,1]$ and it is 1 iff $h=0$ (in which case the two sorted strings are identical) and -1 iff $h=N$ (in which case string $A$ is all 0s and string $B$ is all 1s).

Yes the sequences being compared have the same length. I agree with your derivation. It looks a bit shorter than mine.
A more general expression for the maximum correlation is
$-1\le 1-\frac{2|1_B-1_A|}{N}\le 1$ which is symmetric under interchange of A and B and does not require the assumption $1_A<1_B$.

 

[Igael]

What is the precise definition of the correlation between 2 given sequences ?

 

[andrewkirk]

The OP defines what they want the term to mean in this context at the end of their 4th paragraph. It is different from the usual meaning of correlation.

 

[Igael]

Sorry, I don't know how I missed it, thanks.