Return to Revisions

The phenomenon of concentration of measure produces many examples wherein a randomly chosen object has an unexpected property with high probability. A classical example is the Johnson-Lindenstrauss lemma, which asserts that given any small number $\epsilon$, integers $N >> n >> k$, and $k$ points in $\mathbb{R}^N$, a randomly chosen linear map $\mathbb{R}^N \to \mathbb{R}^n$ will distort the pairwise distances between the $k$ points by no more than a factor of $1-\epsilon$ with very high probability.