Bounding random process

Question

Def $\{X_t\}_{t\in T}$ is called Lipschitz for metric $d$ on $T$ if there exists a random variable $C$ such that $$|X_t-X_s|\leq Cd(t,s),\text{ for all }t,s\in T.$$

Lemma Suppose $\{X_t\}_{t\in T}$ is a Lipschitz process and is $\sigma^2$-subgaussian for every $T$. Then $$E[\sup_{t\in T}X_t]\leq \inf_{\epsilon>0}\{\epsilon E[C]+\sqrt{2\sigma^2\log N(T,d,\epsilon)}$$

To prove the lemma, we split $X_t$ into two parts, i.e. $$\sup_{t\in T}X_t\leq \sup_{t\in T}\{X_t-X_{\pi(t)}\}+\sup_{t\in T}X_{\pi(t)}$$ then take expectation we have $$E[\sup_{t\in T}X_t]\leq \epsilon E[C]+\sqrt{2\sigma^2\log|N|}$$

I am a bit confused on the applicability of this lemma on random process that its $E[\sup X_t]$ is negative.

In the proof, we use the Lipschitz bound to control $\sup_{t\in T}\{X_t-X_{\pi(t)}\}\leq Cd(t,\pi(t))$. Clearly, this bound $Cd(t,\pi(t))$ is non-negative, thus the the resulting bound $ \inf_{\epsilon>0}\{\epsilon E[C]+\sqrt{2\sigma^2\log N(T,d,\epsilon)}$ in the lemma is also non-negative.

But, what if the expectation of sup of random process is negative? Then the bound given by the lemma is very loose.

For example, I guess this process $\sum_{i=1}^n(-100+w_i)\sin(\theta_i)$ where $w_i$ is iid standard gaussian would have negative expectation of supreme.

Am I misunderstood something on this lemma?

Answer 1

$\newcommand\ep\epsilon\newcommand\si\sigma\newcommand\td{\tilde d}$You wrote: "I am a bit confused on the applicability of this lemma on random process that its $E[\sup X_t]$ is negative."

One way to use this result, whether $E\sup_{t\in T} X_t$ is negative or not, is as follows. We have

$$E\sup_{t\in T}X_t\le \inf_{\ep>0}\big\{\ep EC+\sqrt{2\si^2\ln N(T,d,\ep)}\big\} \tag{10}\label{10} $$ given that $$|X_t-X_s|\le Cd(t,s)\text{ for all }(t,s)\in T\times T. \tag{20}\label{20}$$

Here $N(T,d,\ep)$ is the smallest number of balls of radius $\ep$ in metric $d$ needed to cover the set $T$, and $C>0$ is a random variable.

By appropriately truncating the $X_t$'s and $d$ (or by going through the proof of this highlighted result), here we may allow $d$ to be a generalized metric -- such that $d(t,s)$ may take the value $\infty$ for some $(t,s)\in T\times T$.

Let a set $S$ be a copy of the set $T$ disjoint from $T$, so that we have a bijection $f$ from $S$ onto $T$. For all $u\in U:=T\cup S$, let $$Y_u:=\begin{cases} X_u&\text{ if }u\in T, \\ -X_{f(u)}&\text{ if }u\in S. \end{cases} $$ Then $$\sup_{u\in U}Y_u=\max\Big(\sup_{u\in T}X_u,\sup_{u\in S}(-X_{f(u)})\Big) \\ =\max\Big(\sup_{t\in T}X_t,\sup_{t\in T}(-X_t)\Big) =\sup_{t\in T}|X_t|. \tag{30}\label{30} $$ Extend the generalized metric $d$ on $T\times T$ to the generalized metric $\td$ on $U\times U$ by the formula $$\td(u,v):=\begin{cases} d(u,v)&\text{ if }(u,v)\in T\times T, \\ d(f(u),f(v))&\text{ if }(u,v)\in S\times S, \\ \infty&\text{ otherwise }. \end{cases} $$ Then $|Y_u-Y_v|\le C\td(u,v)\text{ for all }(u,v)\in U\times U$; cf. \eqref{20}. So, by the highlighted result, $$E\sup_{u\in U}Y_u\le \inf_{\ep>0}\big\{\ep EC+\sqrt{2\si^2\ln N(U,\td,\ep)}\big\}. \tag{40}\label{40}$$

But $N(U,\td,\ep)\le2N(T,d,\ep)$ for real $\ep>0$. So, by \eqref{30} and \eqref{40}, $$E\sup_{t\in T}|X_t|\le \inf_{\ep>0}\big\{\ep EC+\sqrt{2\si^2\ln (2N(T,d,\ep))}\big\}. $$