KL divergence between noisy strings with small hamming distance

Question

Let $x$ and $y$ be strings of length $n$ from a vocabulary of $m$ characters. Suppose that the hamming distance between $x$ and $y$ is $d$, and that $d << n$.

Let $X$ and $Y$ be noisy versions of $x$ and $y$, respectively, corrupted in the following way: each character is independently, with probability $p$, replaced with a character selected uniformly at random from $[m]$.

I computed the KL divergence between $X$ and $Y$ to be $$ D(X||Y) = d \log \left( \frac{m}{p} - m + 1 \right) \left( 1 - p \right) $$

To my surprise, this quantity does not depend on the string length $n$. I would have expected that $D(X||Y) \to 0$ if $d$ is fixed and $n \to \infty$.

Do you think I made a mistake in my computation, or is my result correct?

If the result is correct, is there any other information theoretic distance between probability distributions which would tend to zero as $n \to \infty$?

Answer 1

This is essentially a comment that got too long.

---

No, any useful notion of statistical distance will depend on $d$ but not $n$. Note that due to your noise model, the tuples $\{(X_i, Y_i)\}_{i \in [1:n]}$ are mutually independent. Further, for the indices $i$ where $x_i = y_i,$ the distributions of $X_i$ and $Y_i$ are the same. Ergo, these coordinates would simply be integrated out and not affect any distance. So, for instance, you have $$ D(P_X \|P_Y) = \sum_i D(P_{X_i} \| P_{Y_i}) = \sum_{i: x_i \neq y_i} D(P_{X_i}\|P_{Y_i})\\ = d D\left( (1-p)\mathbf{1}\{a = 0\} + \frac{p}{m} \| (1-p)\mathbf{1}\{a = 1\} + \frac{p}{m}\right),$$

which evaluates to your claim. The final equality again exploits symmetry of the distributions.

What will go to zero is normalised KL divergence $\frac{1}{n} D(P_X \|P_Y)$ (and indeed, any divergence appropriately normalised). The following statistical interpretation may help with intuition.

Recall that $D(P\|Q)$ controls the risk of a hypothesis test between $P$ and $Q$ for a tester that knows $P$ and $Q$. Your first result - that $D$ does not go to zero - is saying that if you let the tester look at the whole vector, then it will be able to exploit the $d$ differences to do hypothesis testing - this makes sense, the difference is constant and just because you have a longer string doesn't mean the tester is weaker - it knows where to look and just looks there. However, if the tester is only allowed to look at one random coordinate, then with high probability it will fail for long vectors. Note that effective KL divergence for this setting is $\frac{D}{n} = O(d/n)$.