You can update Pearson correlation online, you cannot update online OP correlation coefficient.

Pearson and other correlation coefficients are linear, O(n), sorting would incur logiarithmic multiplier O(NlogN).

Thus, it is not computationally efficient.

To break ties randomly one has to have good random number generator, which is a problem in itself.

Finally, if you want to have differentiable version of this correlation coefficient, you will need to use sorting networks which are O(Nlog^2(N)).

But, it is a cool idea nevertheless, it brings up use of ranking in statistics and there are ties to other areas of the statistical science.

For example, it appears that you can more efficiently prune language models if you use rank metric than probability [1].

[1] https://aclanthology.org/P02-1023.pdf

Since it's rank-based, it would be nice to see a comparison to Spearman's correlation instead. It's very easy to find failure cases for Pearson, so the visualization is next to meaningless, IMO.

This new coefficient of correlation is really really awesome, and this visualization shows its value in such a beautifully simple presentation.

It would be great if someone who has Wikipedia edit privileges, can edit the Wikipedia article at [1] to describe/link how the Chatarjee's correlation coefficient solves many of the known limitation of Pearson's correlation coefficient. ;)

[1] https://en.wikipedia.org/wiki/Pearson_correlation_coefficien...

(especially second top-left diagram)

what kind of summer school was that?

That costs $47 (US). The archiv article is free.

Thanks for finding this article. I agree, these are important developments in particular because so many econometric models are now using machine learning without any distributional assumptions. Using correlation coefficients based on linearity is grossly insufficient.

jmount has an explanation elsewhere in this thread linking to https://win-vector.com/2021/12/26/how-to-read-sourav-chatter... which does a great job of explaining the intuition, but in a nutshell the normalization factor of 3 comes from the fact that if you select two random points between 0 and 1, the mean distance between will be 1/3 (which is pretty easy to write down and solve, boils down the the fact that a pyramid of height 1 that's 1x1 at the base has volume = 1/3).

Different coefficients help you look at different kinds of relationships. For example, Pearson's R tells you about linear relationships between variables -- it's closely tied to the covariance: "how useful is it to draw a line through these data points, and how accurate is interpolating likely to be?".

Spearman's correlation helps you understand monotonic/rank-order relationships between variables: "Is there a trend where increasing X tends to also increase Y?" (This way we can be just as good at measuring the existence of linear, logarithmic, or exponential relationships, although we can't tell them apart.)

Mutual information helps you understand how similar two collections of data are, in the sort of unstructured way that's useful in building decision trees. You could have high mutual information without any sort of linear or monotonic relationship at all. Thus it's more general while at the same time not telling you anything that would be helpful in building, for instance, a predictive multivariate linear model.

TLDR; More specific coefficients leverage assumptions about the structure of the data (eg linearity), which can help you construct optimal versions of models under those assumptions. Mutual information doesn't make any assumptions about the structure of the data so it won't feed into such a model, but it still has lots of applications!

MI is quite useful and widely used. It typically requires binning data though when distributions are unknown / empirically estimated. This approach is a rank-based score, more similar to Spearman correlation than Pearson. This allows for nonlinear relationships between the two variables.

A slightly critical review on the work van be seen here: https://academic.oup.com/biomet/advance-article/doi/10.1093/.... They argue that the older forms of rank correlation, namely D, R, and tau*, are superior. Nonetheless, it seems like a nice contribution to the stats literature, although I doubt the widespread use of correlation is going anywhere.

Instead of mutual information, can I recommend the Transfer Entropy?

https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.85...

https://en.wikipedia.org/wiki/Transfer_entropy

It is designed for time series, but can be adopted to a more general case. The advantage over MI is that with MI, you could only see that A and B are related, while TE can show that A dives B, but not the reverse.

In the article it is explained that the purpose of this coefficient is to estimate how much X is a function of Y [1](or how noisy this association is); in particular this coefficient is 1 iff X is a function of Y.

With MI (the article claims that) you can have a coefficient of 1 without X being a function of Y.

[1] this means that this coefficient is intentionally not symmetric.

I'm also interested in this, having tried and semi-successfully used mutual information for finding associations between multinomial variables. As an even more naive question, I find the actual selection of estimators bewildering. How do I know which estimator to use for mutual information? How do I know if my chosen estimator has converged or is doing a bad job on my data? Bringing it back to the topic at hand, does the estimator presented in the paper provide good estimates for a wider variety of cases than the mutual information plug-in estimator? If so I can see it might be nice for simplicity reasons alone. Can we have different estimators for this new correlation coefficient? Any ideas what that would look like?

Mutual information is not trivial or even possible to estimate in many practical situations as far as i know. Example applications in robotics or computer vision, where mutual information would be useful are segmentation and denoising of unordered 3d point data, for example.

Two things: 1. The result is asymptotical, i.e. holds as number of samples approach infinity.

2. The result is an "almost surely" result, i.e. in the collection of all possible infinite samples, the set of samples for which it fails has 0 measure. In non technical terms this means that it works for typical random samples and may not work for handpicked counterexamples.

In our particular case let f=Sha256. Then X must be discrete, i.e. a natural number. Now the particulars depend on the distribution on X, but the general idea is that since we have discrete values, the probability that we get an infinite sample where the values tend to infinity is 0. So we get that in a typical sample theres going to be an infinitude of x ties and furthermore most x values arent too large (in a way you can make precise), so the tie factors l_i dominate since there just arent that many distinct values encountered total. And so we get that the coefficient tends to 1.

No. If you have a good hash function, that means it's computationally infeasible to determine anything about x based only on y. It's not statistically impossible at all; "statistically" doesn't concern itself with computational difficulties.

This is similar to how, e.g., we generally assume that AES is unbreakable from a computational point of view, but if you want a statistically unbreakable cipher, your only (IINM) option is a one-time pad.

The summary says that it works if it is a measurable function [0], which is structure preserving. So sha256 would scramble the input too much for it to be detected here.

[0] https://en.m.wikipedia.org/wiki/Measurable_function

Simple: if in the whole sample, the same x always comes with the same y, then y is a function of x.

Example:

x1 = 1, y1 = 2

x2 = 1.1, y2 = 2

Here, y is a function of x, because if we know that x = 1, the we also know that y = 2. However, x is not a function of y, as we don't know what value x has given that y = 2.

I hope that made it more clear. Here, "function" simply means that every time we started with the same x, we also got the same y.

    > counterexample = tibble(x = 1:6, y = c(1.1,-1.2,1.3,-1.4,1.5,-1.6))
    > counterexample
    # A tibble: 6 × 2
          x     y
      <int> <dbl>
    1     1   1.1
    2     2  -1.2
    3     3   1.3
    4     4  -1.4
    5     5   1.5
    6     6  -1.6
    > XICOR::calculateXI(xvec = counterexample$x, yvec=counterexample$y)
    [1] -0.2857143
    > -0.2857143 == 1
    [1] FALSE

In Theorem 1.1, f is a function of random variables, which might be where you're confused.

> doesn't that mean y is a predictable function of x

Sort of: as function of real numbers, sha256 is just some deterministic function. But point is its output "looks like" a uniform random variable for any reasonable input distribution i.e. as a function of random variables the input and output variables should have 0 correlation

This works for hash function as hash function does not introduce uncertainty, i.e. Y = f(X), not Y = f(x) + random_noise. I just tested it:

https://ibb.co/nCXVSqB

Perhaps they mean continuous or differentiable functions (evident by the desire to put an order on the elements)

edit: was wrong about sha256