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 
and define the value
where 
are i.i.d. random 
. This looks somewhat similar to the corresponding value
where 
are i.i.d. standard normal random variables. But while 
can be characterized (up to universal constant factors) by the Fernique-Talagrand majorizing measures theory, no similar control was known for 
. One stark difference between the two cases is that depends only on the distance geometry of 
, i.e. 
whenever 
is an affine isometry. On the other hand, can depend heavily on the coordinate structure of .
There are two basic ways to prove an upper bound on . One is via the trivial bound
The other uses the fact that the tails of Gaussians are “fatter” than those of Bernoullis.
This can be proved easily using Jensen’s inequality.
Talagrand’s Bernoulli conjecture is that can be characterized by these two upper bounds.
Bernoulli conjecture: There exists a constant 
such that for every , there are two subsets 
such that
and
Note that this is a “characterization” because given such sets 
and 
, equations (1) and (2) imply
The set controls the “Gaussian” part of the Bernoulli process, while the set 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.
Like this:
Like Loading...
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.
Comment by aramharrow — February 18, 2013 @ 10:05 pm
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.
Comment by James Lee — February 18, 2013 @ 10:48 pm
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.
Comment by Rafał — February 20, 2013 @ 1:10 am
Re g(A(T)) = g(T): surely, g(T) as defined is not invariant to scaling…
Comment by Amit C — February 25, 2013 @ 6:42 am
Sorry, I meant affine isometry. I fixed it.
Comment by James Lee — February 25, 2013 @ 12:41 pm