数学基础-各种界

Gilbert-Varshamov Bound

Let $d>1$. There is a subset $\mathcal{V}$​ of the $d$-dimensional hypercube $\mathcal{H}_d=\{-1,1\}^d$ of size $|\mathcal{V}|\le \exp(d/8)$ such that the $\ell_1$-distance

$$\left\|v-v^{\prime}\right\|_{1}=2 \sum_{j=1}^{d} 1\left\{v_{j} \neq v_{j}^{\prime}\right\} \geq \frac{d}{2}$$

for all $v \not= v’$ with $v,v’\in \mathcal{V}$.​

参考资料：《Chapter2 Minimax lower bounds: the Fano and Le Cam methods》by John Duchi.