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$.

`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. $\endgroup$ – wolfies Feb 17 '14 at 11:54