Convex Bodies and Probability I

Version 1.2: I’ve added more detailed description of duality from a geometric, a mechanical, and an analytic viewpoint.

1. Introduction

This set of very informal notes on the geometry of convex bodies and its relation to the theory of probability is a personal attempt to simplify and organize for my own use a large portion of the theory of convex bodies. The guiding principle is that there are several measure or probability spaces that are naturally associated to convex bodies and that even well-known probabilistic constructions can yield surprising insights into the geometry of convex bodies.

In this first part my only aim is to list some natural constructions of probability spaces related to convex geometry.

2. Dramatis Personae

I’ll be working in a real vector space V of dimension n in which I’ll be careful not to impose any further structure such as a basis or an inner product.

The space of linear, real-valued functions on V (the dual vector space) will be denoted by V^*. Duality plays an important role in the theory. Physically speaking, passing between V and V^* (and we need some structure to do this) corresponds to passing between velocity and momentum. Recall that velocity is just kinematics, momentum is physics (you must take into account the properties of the medium and the moving object to convert velocity into momentum).

A star body is a compact set in V that contains a neighborhood of the origin and such that if a point x is in the body, the whole segment that joins x to the origin is contained in the body.

A convex body is a compact set in V that has non-empty interior and such that if x and y are in the body, then the whole segment that joins x and y is contained in the body.

Convex bodies that contains the origin in their interior are also a star bodies and so I’ll refer to them as star convex bodies.

Definition of the gauge function of a star body.
Given a star body S \subset V, its gauge function is the real-valued function on $V$ whose value at point v is the least non-negative number $lates t$ for which v belongs to the dilated set tS.

Note that when S is a convex body symmetric about the origin, then its gauge function is the norm whose unit ball is S.

The Grassmannian of k-planes in V—to be denoted by G_k(V)—is the set of all its k-dimensional linear subspaces. If we also consider an orientation in these subspaces, then I’ll talk of the Grassmannian of oriented k-planes, G_k^+(V). Mostly k will be either 1 or n-1 and for these values of k we can think of the Grassmannian of oriented k-planes as a sphere of dimension n-1.

3. Two basic constructions

A. Push-forward of measures, mass transfer, and induced probabilities

These three terms really represent the same idea: given a measure space X with measure \mu and a measurable map f from X to some measurable space Y, the push-forward of \mu by f is the measure whose value at some event U \subset Y is the measure of the pre-image event f^{-1}(U) in X. In probabilistic terms the push-forward measure is the probability induced on Y by the random variable f.

B. Duality

In contrast to the previous paragraph where we had three terms to denote one idea, here we only have one term to denote three (related) ideas. I’ll start with the most geometric and basic of the three:

Given a set S in a finite-dimensional vector space V, the dual of S is the set of all half-spaces that contain it.

Note that every half-space in V that contains the origin in its interior is uniquely given by a linear inequality of the form \xi \cdot x \leq 1, where \xi is a non-zero linear functional. In other words, the set of all half-spaces containing the origin their interior can be perfectly identified with the dual space V^* minus its origin.

Since star bodies, by definition, contain the origin in their interior, the set of half-spaces containing a star body S can be seen as a subset S^* \subset V^*. It is not hard to show that once we add the origin to S^*, which we will always do from now on, the resulting set is a star convex body.

It is not hard to see that the dual of S^*, now a subset of (V^*)^* = V, coincides with the convex hull of S. In the case S is a star convex body S(^*)^* = S, and this justifies the term “duality”.

The second idea comes from mechanics rather than geometry: if we recall that the usual definition of the kinetic energy of a particle of unit mass is one-half the square of the magnitude of its velocity, it makes perfect sense to define the kinetic energy in precisely this way when the magnitude of the velocity is measured by a (possibly asymmetric) norm associated to a convex body containing the origin in its interior

Definition of kinetic energy associated to a star
convex body K.
The kinetic energy of a particle of unit mass moving with velocity v is one-half the square of the gauge function of K evaluated at v.

Definition of the momentum of a particle.
Let K be a star convex body in V whose boundary is a smooth hypersurface and let L : V \rightarrow [0,\infty) be the kinetic energy associated to K. The momentum of a particle of unit mass moving with velocity v is the linear functional \xi : V \rightarrow \mathbb{R} whose value at a vector w is given by the derivative at t = 0 of the function t \mapsto L(v + tw). In other words the momentum of this particle is dL(v), the differential of L evaluated at v.

That looks a bit strange at first sight and it takes a while getting used to, but it’s the right thing to do. The map v \mapsto dL(v) taking V minus the origin to the dual space V^* (or taking velocity to momentum) is the Legendre transform.

The dual K^* in V^* of a star convex body K \subset V is its image under the Legendre transform. In other words, it is the set of momenta that correspond to velocities whose magnitudes do not exceed 1. This is exactly the same dual body we previously defined as the set of all half-spaces containing K.

The third idea comes for analysis and optimization: recall that a function f: V \rightarrow \mathbb{R} is said to be convex if

f((1-t) x + ty) \leq (1-t)f(x) + tf(y) (0 \leq t \leq 1).

Equivalently, f is convex if its epigraph

\{(x,s) \in V \times \mathbb{R}: f(x) \leq s \}

is a convex set in V \times \mathbb{R}. From a convex function f: V \rightarrow \mathbb{R} we can construct a convex function on f^* : V^* \rightarrow \mathbb{R} by setting

f^*(\xi) := \sup_{x \in V} \xi \cdot x - f(x).

The function f^* is usually called the conjugate function of f, but it is also called its Legendre transform, or its Legendre-Fenchel transform. As you may expect, (f^*)^* = f.

4. Probability spaces associated to star and convex bodies

Definition of the uniform probability measure.
Given a star or convex body S \subset V, we define the probability of an event U \subset S as the quotient of the volume of U by the volume of S. Volume is defined by any multiple of the Lebesgue (Haar) measure in V (the multiple is irrelevant since we are taking quotients).

The uniform probability measure is the simplest, most basic construction. Many other constructions are obtained by inducing (pushing forward) this probability onto other sample spaces by various natural maps.

Definition of the “solid-angle” measure.
Given a star body S \subset V we consider its boundary \partial S as sample space and define the probability of an event U \subset \partial S as the fraction of the volume of S contained in the solid cone formed by the union of all line segments joining the origin with the points of U.

In other words, the solid-angle measure is the probability on the boundary
of S induced from the uniform probability on S by the radial map S\setminus 0 \rightarrow \partial S.

For the next definition I will define the Gauss map as a map that takes a smooth (or smooth enough) oriented hypersurface M \subset V to the Grassmannian of oriented n-1 planes in V, G_{n-1}^+(V): a point x \in M is taken to the (n-1)-dimensional subspace that is parallel to the hyperplane tangent to M at x.

There is no need to use unit normal vectors and this usually complicates things because it introduces an Euclidean metric we don’t really need. I don’t want to go into a full explanation of the term “smooth enough”, but in some cases we may allow the Gauss map to be multiple-valued and this will not pose any problems. This happens, for example, when M is a convex hypersurface.

Definition of the cone-volume measure.
Given a convex body K \subset V containing the origin in its interior, we define a probability measure on the Grassmannian G_{n-1}^+(V) by first considering the solid angle measure on the boundary of K and then using the Gauss map to induce a probability measure on the Grassmannian.

It helps to see what this gives for a polytope. In this case the cone volume measure is atomic and each atom corresponds to a facet of the polytope. In fact, the atoms are the hyperplanes containing the facets of the polytope translated to the origin.

Here is a simple-looking problem that is still unsolved:

Open problem (E. Lutwak, D. Yang, and G. Zhang):
Given a probability measure on the Grassmannian G_{n-1}^+(V), when is it the cone-volume measure of a convex body?

When the convex body is symmetric about the origin and we can replace the Grassmannian of oriented planes by G_{n-1}(V) (also known as the dual projective space P(V^*)), this problem was solved only a couple of years ago: http://www.ams.org/journals/jams/2013-26-03/S0894-0347-2012-00741-3/

Definition of the dual uniform measure.
This will be the probability measure on K^* induced from the uniform probability measure on K by the Legendre transform.

Definition of the dual solid angle measure
This will be the probability measure induced on the boundary of K^* from the dual uniform measure by means of the radial map K^* \rightarrow \partial K^*. Alternatively, it is the measure induced from the solid angle measure by (the restriction of) the Legendre transform dL : \partial K \rightarrow \partial K^*.

Note that given any measure associated to a convex body containing the origin in its interior, it makes sense to look at the dual measure defined as its push-forward under the Legendre transform.

5. Measures with convexity properties

In Version 1.3 this will be short summary of the work of Prekopa and Borell on logarithmically concave measures, quasi-concave measures, and related notions. The idea being that it is not only interesting to work with measures associated to convex bodies, but that convex-geometric concepts arise naturally in probability and measure theory.

The Prékopa-Leindler inequality

This inequality is the workhorse of most of what follows and unfortunately it is usually stated in a strange way. However, although the inequality is really quite surprising, it can be presented very naturally as a reverse of Hölder’s inequalty that makes use of the geometry underlying the measure space (\mathbb{R}^n,dx).

To motivate the inequality recall that in (\mathbb{R}, dx) as in any other measure space we have the Cauchy-Schwarz inequality for real-valued square-integrable functions:

\int_{\mathbb{R}} f(x)g(x) \, dx \leq \left( \int_{\mathbb{R}} f(x)^2 \, dx\right)^{1/2} \left( \int_{\mathbb{R}} g(x)^2 \, dx \right)^{1/2}

However, (\mathbb{R}, dx) is a very particular measure space and we can dream that for some other “exotic” product f \star g we can have a reverse inequality

\int_{\mathbb{R}} f \star g (x) \, dx \geq \left( \int_{\mathbb{R}} f(x)^2 \, dx\right)^{1/2} \left( \int_{\mathbb{R}} g(x)^2 \, dx \right)^{1/2}

In its first and most basic version, the Prékopa-Leindler inequality says that this dream can become reality:

Given two bounded functions f,g : \mathbb{R}^n \rightarrow \mathbb{R}, define their sup-convolution

f \star g (t) := \sup \{f(x)g(y) : x + y = t \}.

Theorem (Prékopa). If f and g are two non-negative, square integrable functions on (\mathbb{R}, dx), then

\int_{\mathbb{R}} f \star g (x) \, dx \geq 2 \left( \int_{\mathbb{R}} f(x)^2 \, dx\right)^{1/2} \left( \int_{\mathbb{R}} g(x)^2 \, dx \right)^{1/2}.

This is already remarkable, but to me it is downright amazing that exactly the same product can be used to obtain reverse-versions of Hölder’s inequality in (\mathbb{R}^n,dx):

Theorem (Prékopa and Leindler). Let f and g be non-negative measurable functions on (\mathbb{R}^n, dx). If f^p is integrable and g^q is integrable for 1 < p < \infty and 1/p + 1/q = 1, then

\int_{\mathbb{R}^n} f \star g (x) \, dx \geq (p^n)^{1/p} (q^n)^{1/q} \left( \int_{\mathbb{R}^n} f(x)^p \, dx\right)^{1/p} \left( \int_{\mathbb{R}^n} g(x)^q \, dx \right)^{1/q}.

Recall that for these functions, Hölder’s inequality states that

\int_{\mathbb{R}^n} f(x) g(x) \, dx \leq \left( \int_{\mathbb{R}^n} f(x)^p \, dx\right)^{1/p} \left( \int_{\mathbb{R}^n} g(x)^q \, dx \right)^{1/q}.

Advertisements

Leave a comment

Filed under Uncategorized

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