Show entropy bound unit simplex

198 Views Asked by At

Let $\mathcal{S}_d$ be the $d$-dimensional unit simplex. Then for the norm $||x||_1 = \sum_i |x_i|$ and $0 < \varepsilon \leq 1$, $$N(\varepsilon, \mathcal{S}_d, ||\cdot||_1) \leq \left(\frac{5}{\varepsilon}\right)^{d-1}.$$ Prove this.

I have difficulty starting the proof. The unit simplex $\mathcal{S}_d$ is defined as $$\mathcal{S}_d = \left\{(x_1, ..., x_d) \in \mathbb{R}^d: x_i \geq 0 \text{ for all $i$}, \sum_{i=1}^d x_i = 1\right\}.$$

Now for the covering number: $$N(\varepsilon, \mathcal{S}_d, ||\cdot||_1) = \inf\left\{n \in \mathbb{N}: \exists x^1, ..., x^n \in \mathcal{S}_d: \mathcal{S}_d \subset \bigcup_{i=1}^n B_{\varepsilon}(x^i) \right\},$$ where $$B_{\varepsilon}(x^i) = \{x^* \in \mathcal{S}_d: ||x^i - x^*||_1 < \varepsilon\}.$$

I don't know how to show that the covering number is below $(5/\varepsilon)^{d-1}$.

Anyone who can help me?

Thanks in advance!