I am new to statistics and I have this problem to solve which has to do with Hoeffding bounds.
My teacher provided me this theorem:
(Hoeffding bounds) Let $x_{1}, x_{2}, \ldots, x_{n}$ be independent $\{0,1\}$-valued random variables with $\operatorname{Prob}\left(x_{i}=1\right)=p .$ Let $s=\sum_{i} x_{i}$ (equivalently, flip $n$ coins of bias $p$ and let $s$ be the total number of heads). For any $0 \leq \alpha \leq 1$ $$ \begin{aligned} &\operatorname{Prob}(s / n>p+\alpha) \leq e^{-2 n \alpha^{2}} \\ &\operatorname{Prob}(s / n<p-\alpha) \leq e^{-2 n \alpha^{2}} \end{aligned} $$
The problem is the following:
Consider an instance space $X$ consisting of integers $1$ to $1000$ and a target concept $c^\ast = \{x: 501 \leq x \leq 1000\}$. If your hypothesis class $\mathcal H$ is $\{h_j:\, h_j=\{x: j \leq x \leq 1000\}, j=1,\ldots,1000\}$, how large must the training set $S$ be to ensure that with probability $99\%$ any consistent hypothesis (training error 0) will have a true error less than $10\%$?
How do you advise me to proceed?