# Tight lower bound for expected maximum of K sums of T Rademacher random variables

For each $j \in \{1, \ldots, K\}$, let $(\varepsilon_{j,t})_{t=1}^T$ be an independent sequence of iid Rademacher random variables (i.e. taking values $\pm 1$ with equal probability). What is the best lower bound on the expected maximum of the Rademacher sums

\begin{align*} \mathbb{E} \max_{j = 1, \ldots, K} \sum_{t=1}^T \varepsilon_{j,t} . \end{align*}

The result needs to hold for every $K, T \geq 1$ (no asymptotics allowed).

The best I have been able to do so far is

\begin{align*} \frac{1}{L} \min \left\{ \sqrt{2 T \log(K)}, 2 T \right\} , \end{align*}

where $L$ is a universal constant. I am only interested in the regime when $\sqrt{2 T \log(K)} \leq 2 T$. The above lower bound follows by applying Talagrand's Sudakov minoration for Bernoulli processes result (see Theorem 4.2.4 in Talagrand's book "Generic chaining") to a Bernoulli process with a very simple index set, all coefficients being are $0$ or $1$.

This solution is still not totally satisfying for two reasons. It seems overly sophisticated for what should be a simpler problem. Also, we do not have an explicit numerical constant for $L$, and the presumably-computable value of $L$ from Talagrand's result will likely be much larger than what we could obtain for this very special Bernoulli process. From numerical experiments, I expect the best possible lower bound to be

\begin{align*} \frac{1}{2} \sqrt{T \ln(K)} . \end{align*}

Update:

After further experimentation by explicitly computing the expectation (using the CDF of the maximum of K iid Binomial($1/2$, $T$) random variables, it appears the lower bound should be closer to $\frac{1}{\sqrt{2}} \sqrt{T \ln(\ln(T)) \ln(K)}$. In the plots below, this bound is "BoundLogLog". I also include the simpler bound $\sqrt{T \ln(K)}$ (with constant $1$), referred to as "BoundSimple" below.

In the plot below, $K = 100$ and $T$ varies from $100$ to $10^4$, with samples in increments of $100$.

In the next plot, $K = 1000$ and $T$ varies from $1000$ to $10^5$, with samples in increments of $1000$.

I will post more plots later where $T$ is fixed and we vary $K$.

-
Solution confusion: OP wrote: "I expect the best possible lower bound to be $$\frac{1}{2} \sqrt{T \log(K)}$$." ... Unfortunately, this does not seem remotely close to the exact theoretical solution. Why not put up a plot showing your calculated (theoretical or Monte Carlo approximation of the) exact solution (as k and T vary), and comparing it to your proposed best possible lower bound. – wolfies Feb 17 '14 at 11:54
I have added some plots as you suggested, varying T for fixed K. I will add more plots soon varying K for fixed T. I agree that the originally suggested bound is not close to theoretically optimal in that even the rate seems wrong. I suspect that there is a missing $\sqrt{\ln(ln(T))}$ factor, although I do not see how to theoretically prove this. – niche Feb 18 '14 at 13:21