# How Data Compression relates to Estimating Distribution?

I recently read this paper Mahoney, 1999. And encountered this line,

optimal compression of a probabilistic language L with unknown distribution (such as English) using an estimated distribution M (an encoding of length −log2 M(x) bits for each string x) is M = L, by the discrete channel capacity theorem.

Can you please explain what this means and what is the relation between data compression and estimation of distribution?

Suppose that we have a random source $$X$$, and we wish to encode many independent samples $$x_1,\ldots,x_n$$ taken from $$X$$. An compression scheme is an algorithm that converts $$n$$ samples of $$X$$ to a binary string in a reversible way. Shannon showed that the optimal compression scheme produces binary strings of length roughly $$nH(X)$$, where $$H(X)$$ is the entropy of $$X$$.
In practice, we may have access to $$X$$ but might not know its distribution exactly. What we can do is to estimate its distribution as $$Y$$, and then use an optimal compression for $$Y$$. This will produce binary strings of length roughly $$n(H(X) + D(X\|Y))$$, where $$D(X\|Y)$$ is the Kullback–Leibler divergence (called cross-entropy by Mahoney). We have $$D(X\|Y) \geq 0$$, with equality only when $$Y = X$$. Thus optimal compression requires knowing the distribution of the source exactly.