Lesson 5

It turns out that for \(d=\frac{n}{4}\), the code can be of exponential size!

Theorem. There exists a set of \(e^{n/16}\) binary strings of length \(n\) such that any pair is at Hamming distance at least \(n/4\) from each other.

Proof. We construct the required code randomly: generate \(e^{n/16}\) random strings (by generating all bits of each string independently).

The expected distance between two random strings is \(n/2\). Indeed, let \(\alpha\) be the distance between two random strings \(a\) and \(b\). Then, \[\alpha=\chi_{[a_1 \neq b_1]}+\dotsb+\chi_{[a_n \neq b_n]},\] where \(\chi_{[a_i \neq b_i]}\) is an indicator random variable of an event “\(a\) and \(b\) differ in the \(i\)-th bit”. Clearly, \[\operatorname{E}[\chi_{[a_i \neq b_i]}]=\Pr[\chi_{[a_i \neq b_i]}=1]=\Pr[a_{i} \neq b_{i}]=\frac{1}{2}.\] Hence, \(\operatorname{E}[\alpha]=n/2\).

Then, by Chernoff, \[\Pr\left[\alpha \le \frac{n}{4}\right] =\Pr\left[\alpha \le \operatorname{E}[\alpha] - \frac{n}{4}\right]\le e^{-\frac{2}{n}\frac{n^2}{16}}=e^{-\frac{n}{8}}\]

By the union bound, the probability that any pair of \(k=e^{n/16}\) random strings lies at distance at most \(n/4\), is at most \[\binom{k}{2}e^{-\frac{n}{8}}<k^{2}e^{-\frac{n}{8}}=e^{\frac{n}{8}}e^{-\frac{n}{8}}=1.\]◼