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.


I'm solving the exact same exercise on Vershynin. The problem is actually much simpler.

Some hint:

$\epsilon_k=\epsilon_\kappa/2^{k-\kappa}\le diam(T)/2^{k-\kappa}.$

You will likely need the following elementary calculation

$$\sum_{k=1}^\infty (\frac{1}{2})^k \sqrt{k}\le \sum_{k=1}^\infty (\frac{1}{2})^k k=2.$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.