Understanding the Vapnik and Chervonenkis Theorem I am currently studying VC theory and have question to better understand the main theorems inside. I hope that someone who deeply understands it might be willing to give me some intuition on how to use it. Here is the theorem:
Let $Z$ be a class of sets and z are sets from that class ($z \in Z$) . Then:
$$P(\underset{z \in Z}{sup}\vert P_{n}(z) - P(z) \vert \ge \epsilon) \leq 8 \cdot s_{n} (z) e^{-n \epsilon^{2} /32}$$
where $s_{n} (z)$ is the shattering number of z, $P_{n}(z)= \frac{1}{n} \sum_{i=1}^{n} I(X_{i} \in z)$
With Sauer's theorem, we can "substitute" $s_{n} (z)$ with $(n+1)^{d}$, where d is the VC dimension of Z. 
So far so good. Now I apply this theorem to the most practical example that I can come up with in relation to statistics (probably someone of you has another one? I would be happy to study it! ):
Let's assume $Z = \{ (- \infty , t]: t \in \mathbb{R}\}$, so we are looking at all sets that a cdf evaluates at each position of a cdf. As one can easily check by just drawing it down, the VC-dimension d of Z is $d(Z) = 2$. In this particular case, I think we can interpret P(z) as the true cdf's value at a particular position t, and $P_{n}(z)$ as the empirical cdf's value at a particular value of z. Now let's further assume that we repeatedly draw random variables $X_{i}$ from any distribution, say we do this $n = 1000$ times (because for example we have 1000 obervations in a data set, for which we are trying to fit a theoretical cdf to estimate the true cdf). Furthermore, we want the the empirical probability not be further away than $\epsilon = 0.01$, since we believe everything else would be unacceptable for our estimated cdf. Then by the given theorem, we have that
$$P(\underset{z \in Z}{sup}\vert P_{n}(z) - P(z) \vert \ge 0.01) \leq 8 \cdot (1000+1)^{2} e^{-1000 \cdot 0.01^{2} /32} \approx 8*10^6$$
This doesn't help us at all. Only for very large numbers of n, say $n=10^8$, we get $1.5 \cdot 10^{-19}$, which is a very strong statement, but for $n=10^7$ we get some value of the right hand side $\ge 1$ which doesn't help again. 
So what's the implication of this? A class with $d=2$ is already so complex that we need enormous amounts of data point to get reasonable statements from the theorem above?
Let's assume that for $n=1000$, the right-side would have been evaluated to some small value (e.g. by choosing $\epsilon$ larger), say the right hand side is 0.05. What is then the implication of the supremum statement? Does this mean, that looking at the largest "gap" between the true cdf and the empirical cdf, it is no larger than 0.01 with a probability that is larger or equal than 0.95? 
Probably someone of you can give me a better example or ressource where I can read more.
Thank you guys for your help!
 A: Note that the VC-dimension of $Z$ (which you defined) is actually 1:
No set of two elements $x < y$ can be shattered,
since any $z \in Z$ that contains $y$ will also contain $x$.
You have observed that error probability given by the VC inequality
drops very fast, from $> 1$ at $n = 10^6$ to $< 10^{-5}$ at $n = 10^7$.
This simply tells you that the VC inequality will not promise you that
$10^6$ samples is enough, but $10^7$ samples is enough with high probability.
One explanation of why the VC inequality doesn't give any guarantee
in this case for $n = 10^6$ is that the VC inequality holds for general
range spaces and is not optimized for your example.
In fact, for your specific $Z$, the
DKW inequality,
which holds only when approximating the CDF,
would tell you that you need just $60\,000$ samples
to approximate the CDF within 0.01 with high probability.
A quick manual way of solving for $n$ in the VC inequality
given $\epsilon$ and some error probability $\delta$
is to iteratively insert the $n$ from the previous iteration
in $(n + 1)^d$ and solving for $n$ in the exponent.
This gives, for the $i$th iteration,
$$
n_i = \ln (8 (n_{i-1} + 1)^d / \delta) / (\epsilon^2 / 32) - 2
$$
Inserting $d = 1$, $\epsilon = 0.01$, $\delta = 10^{-5}$, $n_0 = 0$ and computing $n_{16}$ in this way yields
$$n \approx 9490616$$
as the solution to
$$\delta = 8 (n+1)^d e^{-n \epsilon^2 / 32}$$
The following bit of Python code implements this 16-fold iteration:
from math import log
t = lambda f: lambda x: f(f(x))
n = lambda ε, δ, d: t(t)(t)(lambda n: (log(8 * (n+1)**d / δ)/(ε**2 / 32)) - 2)(0)
print(n(0.01, 1e-5, 1))  # prints 9490615.980437638

