И её в каких-то случаях получается проконтролировать — и как только мы знаем, что она большая, это и гарантирует концентрацию меры (а также большое первое собственное значение оператора Лапласа и потому "быстрое" расползание случайного блуждания).

Кстати. Из всё того же многомерного гауссового распределения хорошо получается формула для площади поверхности единичной сферы (и объёма единичного шара) в n-мерном пространстве.

Потому что — давайте рассмотрим его плотность в R^n. Только, для простоты счёта, растянем всё в корень из двойки раз. Тогда плотность по одной координате будет просто e^{-x^2}, делённой (нормировка на интеграл 1) на корень из π.

А совместная —
\rho(x_1,\dots,x_n) = \frac{1}{\sqrt{π}^n} \exp(-x_1^2-\dots-x_n^2),

Эта плотность сферически симметрична. И интеграл от неё равен 1 (это же плотность вероятностного распределения). Но давайте его найдём "в сферических координатах" — а точнее, просто порежем всё пространство на "сферические слои".
Если мы возьмём разницу шаров с радиусами r и r+dr, то её объём примерно равен c_n r^{n-1} dr, где c_n — площадь поверхности единичной сферы в R^n.

А подынтегральная функция на таком слое равна
π^{-n/2} exp(-r^2). Поэтому интеграл от плотности равен интегралу от c_n r^{n-1}* π^{-n/2} exp(-r^2) dr,

А сделав в этом интеграле замену R=r^2, и вынеся константу, мы получим как раз ту самую гамма-функцию Эйлера, которая обобщает факториал:

Ну вот мы и получили (раз интеграл должен равняться единице), что
c_n Г(n/2) /(2 π^{n/2}) = 1,
откуда
c_n = (2 π^{n/2}) / Г(n/2).

А объём единичного шара, соответственно, в n раз меньше (можно сказать, "потому что пирамида из центра", а можно проинтегрировать r^{n-1} и получить r^n/n):

И вот в этом виде — "π в степени n/2, поделить на n/2 факториал" — я эту формулу когда-то давно узнал, и доказывал индукцией по отдельности для чётных и для нечётных n.
А рассуждение с гауссовой плотностью (объясняющее, почему чётные и нечётные n так хорошо объединились в одну формулу) узнал только гораздо позднее...

Ну и в завершение — вспомнил я эту формулу тут совершенно не случайно. Потому что если мы захотим посмотреть, как устроено изопериметрическое неравенство на единичной сфере в R^n — какое наименьшее отношение площади к отсекаемому ею объёму (считая, что отсекается та часть, которая меньше половины сферы), то не очень сложно поверить, что это будет как раз отношением для экватора.

А тогда оно равно c_{n-1}/(c_n/2). То есть мы видим отношение гамма-функций в точках, отличающихся на (1/2). Но раз Г(m+1)=mГ(m), то очень естественно ожидать, что отношение Г(m+1/2) и Г(m) будет вести себя, как корень из m.

Ну и, соответственно, изопериметрическая константа для n-мерной сферы ведёт себя, как корень из n/2 (ибо там половинный аргумент).

Что как раз и соответствует тому, что x_1 имеет разброс порядка 1/sqrt{n} (у соответствующего дифференциального уравнения решением будет экспонента с изопериметрической константой в показателе).

Начиная рассказ про асимптотическую комбинаторику, я надеялся ацтекский бриллиант проскочить быстро, и перейти к другим красивым картинкам, а в результате там надолго застрял. Так что давайте я волевым решением перейду к другому, менее известному примеру — Random Sorting Networks. А потом вернусь и доскажу остальное.

Итак, Random Sorting Networks. Допустим, что у нас в ряд выстроено n тяжёлых чемоданов. Но мы вдруг обнаружили, что нужно их переставить в обратном порядке. А единственная операция, которая нам доступна, это взять два соседних чемодана, и поменять их местами.

Сколько нам понадобится операций? Несложно видеть, что минимум n(n-1)/2, число беспорядков.
Потому что в лучшем случае каждая операция уменьшает число беспорядков на 1 — ну а отсортировать за такое число действий можно, например, "пузырьком".

С другой стороны, число способов отсортировать чемоданы ровно за это число операций больше одного. Из простейшего — можно запустить сортировку "пузырьком" начиная с 1, можно, начиная с n, можно их чередовать, но даже это только начало. А на самом деле их очень и очень много. И да, вы правильно догадались — давайте из них выберем один равновероятным образом.