# Dudley's integral inequality: tail bound

This is problem 8.1.7 in Vershynin's High Dimensional Probability book.

Let $$(X_t)_{t\in T}$$ be a random process indexed by a metric space $$(T,d)$$ with sub-gaussian increments(i.e. $$||X_t-X_s||_{\psi_2} \leq Kd(s,t)$$ for all $$s,t\in T$$). Then for every $$u\geq 0$$, the event

$$\sup_{t,s\in T} |X_t-X_s| \leq CK \left( \int_0^\infty \sqrt{\log\mathcal{N}(T,d,\epsilon)} d\epsilon + u \text{diam}(T) \right)$$

with probability $$1-2\exp(u^2)$$ where $$C$$ is just some absolute constant.

If we assume $$T$$ is second countable then we may prove it just for the case when $$T$$ is finite by applying dominated convergence theorem and apply a limit argument. Furthermore, the tail bound is trivially true when $$T$$ is unbounded so assume $$\text{diam}(T)<\infty$$. With these assumptions, lets move on to the issues I'm having proving the result.

To prove this result we are given the following hints. Define $$\epsilon_k=2^{-k}$$ and $$T_k$$ is an $$\epsilon_k$$ covering of with cardinality $$|T_k|=\mathcal{N}(T,d,\epsilon_k)$$. Then if $$t\in T$$ we define $$\pi_k(t)\in T_k$$ to be the closest element in $$T_k$$ to $$t_0$$ for some fixed element $$t_0$$. In particular we can show that

$$\sup_{t\in T} (X_{\pi_k(t)}-X_{\pi_{k-1}(t)}) \leq CK\epsilon_{k-1}(\sqrt{\log|T_k|}+z)$$

with probability at least $$1-2\exp(-z^2)$$. So proving this was fairly straight forward. The next hint was to prove a bound for

$$\sup_{t\in T} |X_t-X_{t_0}| \leq CK \left( \int_0^\infty \sqrt{\log\mathcal{N}(T,d,\epsilon)} d\epsilon + u \text{diam}(T) \right)$$

using the previous result. We note that we can write

$$\int_0^\infty \sqrt{\log\mathcal{N}(T,d,\epsilon)} d\epsilon + u \text{diam}(T) = \int_0^{\text{diam}(T)}\left( \sqrt{\log\mathcal{N}(T,d,\epsilon)} + u \right) d\epsilon$$

Since $$T$$ is finite there exists a $$\kappa_0, K_0 \in \mathbb{Z}$$ such that $$T_{\kappa_0} = \{t_0\}$$ and $$T_{K_0} = T$$. So we can write

$$\int_0^{\text{diam}(T)}\left( \sqrt{\log\mathcal{N}(T,d,\epsilon)} + u \right) d\epsilon \sim \sum_{k\geq{\kappa_0+1}} \epsilon_{k-1}\left( \sqrt{\log\mathcal{N}(T,d,\epsilon_k)} + u \right)$$

Next we form the chain and note that $$\pi_{k_0}(t) = t_0$$ and $$\pi_{K_0}(t)=t$$ so we have

$$\sup_{t\in T}|X_t-X_{t_0}|\leq \sum_{k=\kappa_0+1}^{K_0} \sup_{t\in T}|X_{\pi_k(t)}-X_{\pi_{k-1}(t)}|$$

If we let

$$\sup_{t\in T}|X_t-X_{t_0}|\geq CK\sum_{k=\kappa_0+1}^{K_0}\epsilon_{k-1}\left( \sqrt{\log\mathcal{N}(T,d,\epsilon_k)} + z_k \right)$$

be our event $$E$$ then from a union bound we have

$$P(E) \leq 2\sum_{k=\kappa_0+1}^{K_0}\exp(-z_k^2)$$

Vershynin then suggests we choose $$z_k=u+\sqrt{k-\kappa_0}$$. If we plug this into our sum we get $$2\sum_{k=\kappa_0+1}^{K_0}\exp(-z_k^2) \leq \exp(-u^2)$$

So, in particular, we have that by another union bound that

$$\sup_{s,t\in T}|X_s-X_{t}|\geq 2CK\sum_{k=\kappa_0+1}^{K_0}\epsilon_{k-1}\left( \sqrt{\log\mathcal{N}(T,d,\epsilon_k)} + u + \sqrt{k-\kappa_0} \right)$$

Has probability less than $$2\exp(-u^2)$$

Which is almost a larger event than the original one were proving. My only issue is how to absorb the additional term $$\sum_{k=\kappa_0+1}^{K_0} \epsilon_{k-1} \sqrt{k-\kappa_0}$$. If I can deal with that I have what I wanted to prove because

$$2CK\int_0^\infty \sqrt{\log\mathcal{N}(T,d,\epsilon)} d\epsilon + u \text{diam}(T) \geq C' 2CK\sum_{k=\kappa_0+1}^{K_0}\epsilon_{k-1}\left( \sqrt{\log\mathcal{N}(T,d,\epsilon_k)} + u \right)$$

I think this term was actually smaller than some $$M$$, because as k goes from $$\kappa_0+1$$ to $$K_0$$, the term $$\epsilon_{k-1}$$ drops exponential fast and $$\sqrt{k-\kappa_0}$$ grows much slower than that. Try to apply Able's to see the series actually converge, hence this partial sum is bounded by some constant M. And then by choose a $$C$$ large enough you can simply drop this constant $$M$$. I was just in this chapter today, and THIS MIGHT BE WRONG because I was trying to see the answer which has lead me here. Just let me know if you agree or not.
$$\epsilon_k=\epsilon_\kappa/2^{k-\kappa}\le diam(T)/2^{k-\kappa}.$$
$$\sum_{k=1}^\infty (\frac{1}{2})^k \sqrt{k}\le \sum_{k=1}^\infty (\frac{1}{2})^k k=2.$$