# how to define "correlation" between languages?

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?

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

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.