- #1
Mentz114
- 5,432
- 292
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.
[tex]
\begin{align*}
\overbrace{
\underbrace{1111111111...}_\text{count of 1s $=1_K$} \
\underbrace{0000000000...}_\text{count of 0s $=0_K$}
}^\text{length of K is $N=0_K+1_K$}
\end{align*}
[/tex]
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 ?
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.
[tex]
\begin{align*}
\overbrace{
\underbrace{1111111111...}_\text{count of 1s $=1_K$} \
\underbrace{0000000000...}_\text{count of 0s $=0_K$}
}^\text{length of K is $N=0_K+1_K$}
\end{align*}
[/tex]
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 ?