3
$\begingroup$

This is a problem I'm having reading Arora & Barak's book, page 378-379. They define:

For two words $x, y \in \{0, 1\}^m$, the fractional Hamming distance of $x$ and $y$ is equal to the fraction of bits on which they differ, i.e. $\frac{1}{m} \cdot |\{i : x_i \neq y_i\}|$, where the $x_i$ refers to the $i$-th bit of $x$ (same for $y_i$).

Now, in the proof of Lemma 18.9, they use the fact that

for every string $y_i$ of $m$ bits, the number of strings that are of distance at most $\delta$ to it is ${m \choose \lceil \delta m \rceil}$

meaning that there are ${m \choose \lceil \delta m \rceil}$ words that disagree on not more than a $\delta$ fraction of bits.

But, I can't convince myself of that. Suppose for simplicity that $y_i = 0000 \ldots 000$. Here are the words that are of distance at most $\delta m$: all the words that have exactly one $1$, or two, or three, up to $\lfloor \delta m \rfloor$ of bits set to $1$. Thus I rather think that this number is

$$ \sum_{k = 1}^{\lfloor \delta m \rfloor} {m \choose k} $$

Can anyone explain?

$\endgroup$
  • 2
    $\begingroup$ you are correct, it looks like a mistake. $\endgroup$ – Ran G. Dec 23 '15 at 17:23
2
$\begingroup$

That's an inaccuracy. If $\delta < 1/2$ is constant then it is the case that $\sum_{k=0}^{\delta m} \binom{m}{k} = O\left(\binom{m}{\delta m}\right)$, since the binomial coefficients increase very fast until they finally level out around the central binomial coefficient. The hidden constant depends on $\delta$. (When $\delta$ is close to $1/2$ this doesn't hold: for example, $\sum_{k=0}^{m/2} \binom{m}{k} = 2^{m-1}$ for even $m$, while $\binom{m}{m/2} = \Theta\left(\frac{2^m}{\sqrt{m}}\right)$.)

At any rate, what they are interested in really is the estimate $\sum_{k=0}^{\delta m} \binom{m}{k} \leq (1-\epsilon) 2^{H(\delta)m}$, which holds for every $\epsilon > 0$ and large enough $m$ (depending on $\epsilon,\delta$).

$\endgroup$
  • $\begingroup$ Thanks for the answer. I get the idea. Do you, by any chance, have an idea on how to prove the two assertions you mention (that $\sum_{k = 0}^{\delta m} {m \choose k} = O( {m \choose k} )$ and the last estimate) ? Not asking for the details, just the idea if you have it. Otherwise that's fine. $\endgroup$ – Manuel Lafond Dec 24 '15 at 1:55
  • $\begingroup$ @ManuelLafond Take a look at their appendix or the Wikipedia article on binomial coefficients. $\endgroup$ – Yuval Filmus Dec 24 '15 at 9:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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