Varshamov-Gilbert, question about proof with probabilistic method

54 Views Asked by At

Let $d \in \mathbb{N}$ such that $d \equiv 0 \pmod{4}$, and take $S_1, \dots, S_d \sim Bernoulli(0, 1)$.

Define for $v \in \{0,1\}^d$ the ball $B(v, d/2) = \{w \in \{0,1\}^d : \|v - w\|_1 \leq d/2\}$.

At p.144 of the lecture notes of John Duchi, in the proof of the Varshamov-Gilbert bound, the following is stated:

$$2^{-d} B(v, d/2) = \mathbf{P}(S_1 + S_2 + \dots + S_d \leq d/4)$$

A quick computation gives me (from the CDF of a Binomial distribution)

$$\mathbf{P}(S_1 + S_2 + \dots + S_d \leq d/4) = \sum_{i=0}^{d/4} {d \choose i} (1/2)^i (1 - 1/2)^{d-i} = 2^{-d} \sum_{i=0}^{d/4} {d \choose i}$$

Which looks more to me like $B(v, d/4)$ instead of $B(v, d/2)$. What am I missing ?