1.2 CONCENTRATION FUNCTIONS 3 feature that the concentration function of (1.4) does not depend on the dimension of the underlying state space R^ for the product measure 7 = r yk. Our third example will be discrete. Consider the n-dimensional discrete cube X = {0, l } n and equip X with the normalized Hamming metric d(x,y) = -Card({xi ^ y^i = 1,... ,n}), n x (#1,... iXn),y = (2/1,... ,yn) £ {05l}n- Let /x = /in be uniform (product) measure on {0, l } n defined by /JL(A) = 2~n Card (A) for every subset A of X. Iden- tifying the extremal sets A in X for which the infimum inf{/x(Ar) /x(A) | } is attained may be used to show here that c v ( r ) e " 2 n r 2 , r 0 , (1.5) where the concentration function aM for /x on {0, l } n equipped with the Hamming metric is defined as above. These first examples of concentration properties all follow from more refined isoperimetric inequalities. They will be detailed in the next chapter in which full proofs of the concentration (rather than isoperimetric) results will be presented. These examples will serve as guidelines for the further developments. They moti- vate and justify in particular the analysis of the concept of concentration function performed in the next section. 1.2 Concentration functions Motivated by the early examples of the preceding section, we introduce and for- malize the concept of concentration function of a probability measure on, say, a metric space. The concentration examples of Section 1.1 indeed rely on two main ingredients, a (probability) measure and a notion of (isoperimetric) enlargement with respect to which concentration is evaluated. Thus, let (X, d) be a metric space equipped with a probability measure /i on the Borel sets of (X, d) (a metric measure space in the sense of [Grom2]). The concentration function a^x,d^) (denoted more simply ai(_x», or even a^, when the metric d, or the underlying metric space (X, d), is implicit) is defined as *(*,*,/*)(r) = sup{l - fi(Ar) Ac X^{A) | } , r 0. (1.6) Here Ar {x G X d(x, A) r} is the (open) r-neighborhood of A (with respect to d). A concentration function is less than or equal to | . When (X, d) is bounded, the enlargements r 0 in (1.6) actually range up to the diameter Diam(X,d) sup {d(x,y)\x,y E X } of (X, d), the concentration function being 0 when r is larger than the diameter. This, however, will not usually be specified. In any case, the concentration function decreases to 0 as r 00. Indeed, fix a point x in X. Given 0 e | , choose r such that the measure of the complement of the ball B with center x and radius r is less than e. Then, any Borel set A such that JJL(A) \ intersects B. Hence A^r covers B and thus 1 n(A2r) ^ 1 M ( ^ ) e -
Previous Page Next Page