tcs math – some mathematics of theoretical computer science

February 18, 2013

Talagrand’s Bernoulli Conjecture, resolved.

Filed under: Math — Tags: , , — James Lee @ 5:34 pm

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.

About these ads

5 Comments »

  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.

    Comment by aramharrow — February 18, 2013 @ 10:05 pm

  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.

    Comment by James Lee — February 18, 2013 @ 10:48 pm

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

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

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

    Comment by James Lee — February 25, 2013 @ 12:41 pm


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

The Shocking Blue Green Theme Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 57 other followers

%d bloggers like this: