Talagrand’s Bernoulli Conjecture, resolved.

Apparently, Bednorz and Latała have solved Talagrand’s \$5,000 Bernoulli Conjecture. The conjecture concerns the supremum of a Bernoulli process.

Consider a finite subset ${T \subseteq \ell^2}$ and define the value

$\displaystyle b(T) = \mathbb{E} \max_{t \in T} \sum_{i \geq 1} \varepsilon_i t_i\,,$

where ${\varepsilon_1, \varepsilon_2, \ldots}$ are i.i.d. random ${\pm 1}$. This looks somewhat similar to the corresponding value

$\displaystyle g(T) = \mathbb{E} \max_{t \in T} \sum_{i \geq 1} g_i t_i\,,$

where ${g_1, g_2, \ldots}$ are i.i.d. standard normal random variables. But while ${g(T)}$ can be characterized (up to universal constant factors) by the Fernique-Talagrand majorizing measures theory, no similar control was known for ${b(T)}$. One stark difference between the two cases is that ${g(T)}$ depends only on the distance geometry of ${T}$, i.e. ${g(A(T))=g(T)}$ whenever ${A}$ is an affine isometry. On the other hand, ${b(T)}$ can depend heavily on the coordinate structure of ${T}$.

There are two basic ways to prove an upper bound on ${b(T)}$. One is via the trivial bound

$\displaystyle b(T) \leq \max_{t \in T} \|t\|_1\,. \ \ \ \ \ (1)$

The other uses the fact that the tails of Gaussians are “fatter” than those of Bernoullis.

$\displaystyle b(T) \leq \sqrt{\frac{\pi}{2}} g(T)\,. \ \ \ \ \ (2)$

This can be proved easily using Jensen’s inequality.

Talagrand’s Bernoulli conjecture is that ${b(T)}$ can be characterized by these two upper bounds.

Bernoulli conjecture: There exists a constant ${C > 0}$ such that for every ${T \subseteq \ell^2}$, there are two subsets ${T_1, T_2 \subseteq \ell^2}$ such that

$\displaystyle T \subseteq T_1 + T_2 = \{ t_1 + t_2 : t_1 \in T_1, t_2 \in T_2 \}\,,$

and

$\displaystyle g(T_1) + \sup_{t \in T_2} \|t\|_1 \leq C b(T)\,.$

Note that this is a “characterization” because given such sets ${T_1}$ and ${T_2}$, equations (1) and (2) imply

$\displaystyle b(T) \leq \sqrt{\frac{\pi}{2}} g(T_1) + \sup_{t \in T_2} \|t\|_1\,.$

The set ${T_1}$ controls the “Gaussian” part of the Bernoulli process, while the set ${T_2}$ controls the part that is heavily dependent on the coordinate structure.

This beautiful problem finally appears to have met a solution. While I don’t know of any applications yet in TCS, it does feel like something powerful and relevant.

5 thoughts on “Talagrand’s Bernoulli Conjecture, resolved.”

1. Are there any applications of this that are known?

And do you think this is a stepping stone towards some more general result, perhaps for E_{alpha} max_{t in T} sum_i alpha_i t_i with {alpha_i} drawn from some more general distribution? i.e. Is there a sense in which the Gaussian and the coordinate-dependent part somehow always capture everything? Probably this is a really naive question.

2. Aram, the truth is I don’t know of any major applications. There are a couple of minor applications in functional analysis. I also have no idea what the proof looks like, so its hard to comment on how it generalizes.

I assume you are asking about {alpha_i} which are (at least) independent. In that case, it certainly works for any family of bounded random variables. But consider a family of n i.i.d. exponential random variables. Then the expected maximum is ~ log n and neither of the bounds (1) or (2) hold, so one needs a different way of controlling the process.

3. Rafał says:

The case of exponential i.i. d. varaibles and a more general setting – sums of nonnegative r.vs with logarithmically concave tails is aslo resolved – see Latała and Lochowski, Moment and tail estimates for multidimensional chaos generated by positive random variables with logarithmically concave tails. Stochastic inequalities and applications, 77–92,
Progr. Probab., 56, Birkhäuser, Basel, 2003.

4. Re g(A(T)) = g(T): surely, g(T) as defined is not invariant to scaling…

5. Sorry, I meant affine isometry. I fixed it.