For a metric space with a probability measure , the concentration function is , where is the metric neighbourhood of radius . A sequence exhibits concentration of measure if these functions tend to zero for every fixed positive radius. The metric scale is part of this definition.
A Lévy family of graphs consists of finite connected graphs with their uniform probability measures and graph distances divided by their diameters, whose concentration of measure functions vanish at every fixed positive normalized radius. Equivalently, every family occupying at least half the vertices has a radius- neighbourhood occupying a proportion tending to one, uniformly over such families. Harper theorem and binomial distribution tail bounds prove this for the hypercube graphs.
Equip with uniform probability measure and its nearest-neighbour graph distance divided by , for fixed positive . The set has at least half the vertices. Its radius- graph neighbourhood still omits a proportion tending to when . These grids therefore do not form a Lévy family of graphs.
Equip the Boolean hypercube with uniform probability measure and graph distance divided by its graph diameter. These spaces form a Lévy family of graphs. The vertex-isoperimetric inequality in the discrete cube reduces the complement of a positive-density set's radius- graph neighbourhood to a binomial distribution tail. For fixed density , Chebyshev's inequality puts a lower density quantile at least . After enlarging by , the omitted mass is at most , which tends to zero.
Articles by others on the same topic
Concentration of measure is a phenomenon in probability theory and statistics that describes how, in high-dimensional spaces, random variables that are distributed according to certain types of probability distributions tend to become increasingly concentrated around their expected values, with very little probability mass in the tails. In simpler terms, it suggests that as the dimension of a space increases, the measure (or "size") of sets that are far from the mean becomes very small compared to the measure of sets that are close to the mean.