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