# Distribution of Maximum of Sum of Sum of Gaussians

Let $X_i$ be a sequence of i.i.d. standard normal random variables. Let $Y_i=\sum_{k=1}^iX_k$ and $Z_i=\sum_{k=1}^iY_k$. I am interested in upper and lower bounds for $P(\sup_{1\leq i\leq m}|X_i|\leq c)$, $P(\sup_{1\leq i\leq m}|Y_i|\leq c)$ and $P(\sup_{1\leq i\leq m}|Z_i|\leq c)$. I managed to figure out the first two, and for the second one I got bounds of something like $1-\mbox{const}\times e^{-c^2/n}$ by considering $P(|B_t|\geq c)$ and using the reflection principle for $\tau=\inf_{t\leq m}\{t: \ |B_t|\geq c)\}$.

The problem is, the same trick doesn't quite work when figuring out the $P(\sup_{1\leq i\leq m}|Z_i|\leq c)$. In fact, the best I could do was write $Z_{n+1}=Z_n+B_{n+1}$ where $B$ is a standard Brownian motion. Maybe this can become a stochastic differential equation? But, it feels intractable unless I'm missing something. I was wondering how one might get good upper and lower bounds for the supremum over $Z_i$? Maybe I'm thinking too hard and there's an easier way which doesn't resort to Brownian motion.

Any help would be greatly appreciated!

-
I assume you mean $Z_i = \sum_{k=1}^i Y_k$, not $Z_i = \sum_{k=1}^i Y_i$ – Robert Israel Feb 28 '12 at 22:00
Your bound for $P(\sup_{1\le i\le m} |Y_i| \le c)$ is not good as $m \to \infty$ for fixed $c$: it should go to $0$ exponentially in $m$. Note that if any $|X_k| > 2 c$, then $\max(|Y_{k-1}|, |Y_k|) > c$. Similarly, if any $|X_k| > 4c$, then $\max(|Z_{k-2}|,|Z_{k-1}|,|Z_k|) > c$. So these should also go to $0$ exponentially in $m$. – Robert Israel Feb 28 '12 at 22:21
Corrected. Thanks! – Alex R. Feb 29 '12 at 0:53

Maybe you find this useful. This paper by Charles. E. Clark http://www.eecs.berkeley.edu/~alanmi/research/timing/papers/clark1961.pdf gives a way to approximate the maximum of a finite set of correlated normal variables $Y_1,\ldots,Y_n$ by a normal variable itself.

Namely, if $Y_1\sim N(\mu_1,\sigma_1)$, $Y_2\sim N(\mu_2,\sigma_2)$ are normal variables with correlation $\rho$ denote $$a^2 = \sigma_1^2 + \sigma_2^2 -2\sigma_1\sigma_2\rho\ ,\\ \alpha = (\mu_1-\mu_2)/a\ .$$ The first and second order of the maximum $W = \max(Y_1,Y_2)$ are given by $$\nu_1 = \mu_1\Phi(\alpha) + \mu_2\Phi(-\alpha) + a\varphi(\alpha)\ , \\ \nu_2 = (\mu_1^2+\sigma_1^2)\Phi(\alpha) + (\mu_1^2+\sigma_1^2)\Phi(-\alpha) + (\mu_1+\mu_2)a\varphi(\alpha)\ ,$$ where $\Phi$ is the standard normal cdf and $\varphi$ the standard normal density. Using this it is possible to define a normal variable $\widetilde{W}\sim N(\nu_1,(\nu_2-\nu_1)^2)$ that approximates the maximum of $Y_1$ and $Y_2$. You can obtain then an approximation of $\max(Y_1,Y_2,Y_3)$ using the correlation $$\rho(W,Y_3) = \sigma_1\rho_1\Phi(\alpha) + \sigma_2\rho_2\Phi(-\alpha)/(\nu_2 - \nu_1)^{1/2}$$ where $\rho_1=\rho(Y_1,Y_3)$ and $\rho_2=\rho(Y_2,Y_3)$. This can be done recursvely but the general recurrence is a little bit more tricky since you need the correlations $\rho(W_j,Y_i)$ for $i\geq j+2$ at every step being $$W_j \approx \max(Y_1,\ldots,Y_{j+1})\ .$$ The approximation is good enough for many numerical purposes and it may be good as well to obtain the bounds that you require.

But I feel that maybe you are right and the answer is simpler than all that.

-

This may be overkill, but: Fernique's theorem says that for any Gaussian measure $\mu$ on a separable Banach space $(X, \|\cdot\|)$, there are constants $C,\epsilon$ such that $\mu(\{ x : \|x\| > t\}) \le Ce^{-\epsilon t^2}$. (You can find a proof at Theorem 4.10 of these lecture notes of mine.) $(Z_1, \dots, Z_m)$ is a Gaussian random vector (being a linear transformation of $(X_1, \dots, X_m)$), hence its law $\mu$ is a Gaussian measure on $\mathbb{R}^m$. If we let $X$ be $\mathbb{R}^m$ equipped with its $\ell^\infty$ norm, then Fernique's theorem says that $$P(\max_{1 \le i \le m} |Z_i| > t) \le C e^{-\epsilon t^2}.$$

If you want more explicit control over the constants, you may have to do more work.

-