А вот как чуть менее широко известно, многомерный арбуз состоит в основном из своего экватора. Из какого? Да из любого!
А именно — возьмём случайно выбранную точку (x_1,...,x_n) на n-1-мерной единичной сфере.
Посмотрим на первую координату, x_1.
Её модуль — это и есть расстояние до экваториальной сферы, {x_1=0}.
Посмотрим на первую координату, x_1.
Её модуль — это и есть расстояние до экваториальной сферы, {x_1=0}.
Но поскольку сумма квадратов всех n координат равна единице,
x_1^2+...+x_n^2=1,
то "естественно ожидать", что на квадрат каждой координаты в среднем приходится по 1/n. То есть x_1 (который вообще-то принимает значения от -1 до 1) "обычно" будет иметь порядок 1/sqrt{n}.
x_1^2+...+x_n^2=1,
то "естественно ожидать", что на квадрат каждой координаты в среднем приходится по 1/n. То есть x_1 (который вообще-то принимает значения от -1 до 1) "обычно" будет иметь порядок 1/sqrt{n}.
И это таки да правда — и более того, при увеличении n распределение произведения \sqrt{n}*x_1 сходится к гауссову нормальному распределению N(0,1) — тому самому, которое самое замечательное в теории вероятностей, и сходимость к которому утверждает ЦПТ.
Наиболее простой способ это увидеть такой. Давайте возьмём n независимых, распределённых как N(0,1) случайных величин \xi_k. Тогда у каждой из них плотность это (1/sqrt{2π}) * exp(-x^2/2), а совместная плотность в R^n — это их произведение, то есть
1/(2π)^{n/2} * exp(-r^2/2), где r^2=x_1^2+...+x_n^2 — радиус.
1/(2π)^{n/2} * exp(-r^2/2), где r^2=x_1^2+...+x_n^2 — радиус.
Тогда это распределение сферически симметричное: плотность в R^n у него зависит только от расстояния до начала координат. Значит, если мы спроецируем выбранную таким образом точку на единичную сферу — получится равномерно распределённая точка на сфере. И её первая координата будет равна
x_1=\xi_1/r.
x_1=\xi_1/r.
Но r^2=x_1^2+...+x_n^2 — это сумма n _независимых_ одинаково распределённых случайных величин. И как нас учит закон больших чисел, r^2/n с очень большой вероятностью близко к математическому ожиданию любой из них — то есть к единице.
То есть r это "почти константа \sqrt{n}". Ну а исходная случайная величина \xi_1 была точно N(0,1).
Значит,
\sqrt{n}* x_1 = \xi_1 * (\sqrt{n}/r) —
почти N(0,1), и чем больше n, тем точнее это "почти".
Значит,
\sqrt{n}* x_1 = \xi_1 * (\sqrt{n}/r) —
почти N(0,1), и чем больше n, тем точнее это "почти".
Вернёмся теперь к словам "концентрация меры". А именно — пусть на n-мерной единичной сфере задана какая-то 1-липшицева функция f (то есть такая, что |f(x)-f(y)|<|x-y|) — как в примере выше мы рассматривали функцию f(x_1,...,x_n)=x_1.
Посмотрим на распределение её значений — на какой доле площади точек сферы она принимает какие значения. Оказывается (и это и есть эффект "концентрации меры"), что в основном эти значения очень сконцентрированы.
А именно — хоть (как, собственно, и для функции x_1) максимальное от минимального может отличаться на 2 (на диаметр сферы), на 95% площади принимаются значения, отличающиеся друг от друга на const/sqrt{n} (и на 99%, и на 99.9%, вопрос только в константе).
А именно — хоть (как, собственно, и для функции x_1) максимальное от минимального может отличаться на 2 (на диаметр сферы), на 95% площади принимаются значения, отличающиеся друг от друга на const/sqrt{n} (и на 99%, и на 99.9%, вопрос только в константе).
Так что мера получается сконцентрированной, с характерным разбросом порядка 1/\sqrt{n}.
Более того, функция x_1 оказывается, в каком-то смысле [я тут чуть-чуть привираю — но чуть ниже уточню], "самым разбросанным" примером.
Более того, функция x_1 оказывается, в каком-то смысле [я тут чуть-чуть привираю — но чуть ниже уточню], "самым разбросанным" примером.
Удивительным образом, увидеть это удаётся очень "дёшево". А именно — давайте возьмём медианное значение функции, ту поверхность уровня, которая делит сферу на две части равной площади.
И будем от него отходить вверх и вниз и смотреть, как "ужимаются" области {x: f(x)>a} и {x: f(x)<a} соответственно.
Поскольку функция 1-липшицева — скорость ужимания не меньше, чем площадь "поверхности уровня" {f(x)=a}. Потому что если мы возьмём \eps-окрестность этой поверхности — то значения в ней в силу 1-липшицевости не выходят за предел [a-\eps, a+\eps]. Так что при переходе от {f(x)>a} к {f(x)>a+\eps} мы, например, смотрящую "внутрь" часть этой \eps-окрестности теряем, а у неё объём это примерно площадь {f(x)=a}, умноженная на \eps ("площадь основания на высоту").
А площадь поверхности {f(x)=a} можно сравнить с отсекаемым ею объёмом {f(x)>a} — и изопериметрическое неравенство скажет, что нельзя отрезать "большой" объём маленькой площадью.
Так что — если мы знаем, как устроено изопериметрическое неравенство для многомерной сферы (чего я, формально говоря, не сказал, но скажу сейчас, что с этим всё хорошо), то мы сможем сказать, что отрезаемый объём будет убывать быстро.
Более того, на самом деле на сфере (что очень естественно) наибольший объём, который можно отрезать данной площадью, это "полярная шапка".
Поэтому самое медленное убывание, которое бывает, будет как раз для функции x_1. А для неё мы знаем, что даже она сконцентрирована с разбросом ~1/\sqrt{n}. Ура, победа!
[И это как раз то место, где я не сильно, но заметно, привираю, путая расстояния "в R^n" и "по поверхности сферы". Чтобы мои слова стали совсем правдой, нужно брать расстояния по поверхности, произнести слова "риманова метрика", и брать функцию arcsin x_1. Те, кого они не пугают — вот после этого всё совсем почти честно]
Математические байки
Так что — если мы знаем, как устроено изопериметрическое неравенство для многомерной сферы (чего я, формально говоря, не сказал, но скажу сейчас, что с этим всё хорошо), то мы сможем сказать, что отрезаемый объём будет убывать быстро.
С другой стороны, возвращаясь, — хоть рассуждение для разброса мы закончили, вместо явного счёта сказав, что "широта" arcsin x_1 это самая разбросанная функция — вообще-то нам достаточно было бы иметь "хорошее" изопериметрическое неравенство (какое максимальное отношение площади поверхности к ограничиваемому ей объёму). Нужно было только его получить/написать.
Константа, которую можно в нём поставить, называется константой Чигера —
https://en.wikipedia.org/wiki/Cheeger_constant#Definition (и, кстати, есть она и для графов — https://ru.wikipedia.org/wiki/Константа_Чигера_(теория_графов) )
https://en.wikipedia.org/wiki/Cheeger_constant#Definition (и, кстати, есть она и для графов — https://ru.wikipedia.org/wiki/Константа_Чигера_(теория_графов) )
Wikipedia
Cheeger constant
invariant of compact Riemannian manifolds M; the infimum (ranging over n−1-dimensional submanifold E dividing M into disjoint submanifolds A and B) of S(E)/min{V(A), V(B)}, where V denotes n-dimensional volume and S denotes n−1-dimensional area