How does one define the concept of correlation between languages?

Is there any 'standard' measure of 'correlation' between two (possibly inf) sets of strings / an analogue of the concept in this setting?

Was thinking could use the algorithmic mutual information between their descriptions--maybe this works for languages with finite descriptions?

  • $\begingroup$ Various reasonable definitions are possible; I suggested one such in my answer. What is your ultimate motivation in asking this? $\endgroup$
    – Aryeh
    Nov 28, 2020 at 15:39

1 Answer 1


Your idea only works on languages with finite descriptions; here is an approach that's well defined for all languages, but it requires choosing some probability distribution $\mu$ on the set of all finite words, $\Sigma^*$. Assuming that you've chosen one, let $A$ and $B$ be your two languages. Let $X$ be the random variable corresponding to the event that a $\mu$-random word belongs to $A$, and define $Y$ analogously for $B$. Now you can define correlation between $A$ and $B$ as the correlation between $X$ and $Y$ in the classical sense: $$ cov(X,Y) = E[XY]-E[X]E[Y] = \sum_{x\in\Sigma^*}1[x\in A\cap B]\mu(x) - \sum_{x,y\in\Sigma^*}1[x\in A]1[y\in B]\mu(x)\mu(y) , $$ and $cor(X,Y)=\frac{cov(X,Y)}{\sigma_X\sigma_Y}$, where $$ \sigma_X^2 = \sum_{x\in\Sigma^*}1[x\in A]\mu(x) - \left( \sum_{x\in\Sigma^*}1[x\in A]\mu(x) \right)^2. $$

A reasonable choice of $\mu$ would be to let word length be distributed, say, geometrically (or any other distribution on the integers), and within each fixed word length, $\mu$ is uniform. But of course the "reasonableness" or usefulness of this definition will depend entirely on your purposes.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.