Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I Correlation Limits without Probability

  1. Nov 5, 2016 #1

    Mentz114

    User Avatar
    Gold Member

    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 ?
     
  2. jcsd
  3. Nov 6, 2016 #2

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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).
     
  4. Nov 6, 2016 #3

    Mentz114

    User Avatar
    Gold Member

    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##.
     
  5. Nov 7, 2016 #4
    What is the precise definition of the correlation between 2 given sequences ?
     
  6. Nov 8, 2016 #5

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  7. Nov 8, 2016 #6
    Sorry, I don't know how I missed it, thanks.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Correlation Limits without Probability
  1. Probability without STD? (Replies: 13)

Loading...