Математические байки

А именно — возьмём случайно выбранную точку (x_1,...,x_n) на n-1-мерной единичной сфере. Посмотрим на первую координату, x_1. Её модуль — это и есть расстояние до экваториальной сферы, {x_1=0}.

А вот как чуть менее широко известно, многомерный арбуз состоит в основном из своего экватора. Из какого? Да из любого!

А именно: как совсем широко известно, стомерные арбузы покупать не стоит. Ибо состоят они в основном из кожуры: даже если толщина кожуры это 5% — доля съедобной части в арбузе будет 0.95^100 ~ e^{-5} ~ 0.0067.

(Прошу прощения — такой большой перерыв не планировался...) Так вот, во-вторых, тут неподалёку живут слова "концентрация меры".

Обещанные несколько слов: — Во-первых, у нас тут выше вырисовалась связка (всё связано со всем) "случайное блуждание—время перемешивания—спектр оператора Лапласа—изопериметрическое неравенство". Ну, почти вырисовалась — ещё нужно сказать, что за случайное блуждание как раз оператор Лапласа и отвечает, а за "бутылочные горлышки" отвечает изопериметрическое неравенство.

(Picture credit : A. Okounkov)

Кстати: можно пытаться брать не равновероятное — а как-то взвешенное распределение. Например, раз уж мы всё равно смотрим на эту картинку как на кубики — зафиксировать объём. Или (что приводит к очень близкому результату) — сказать, что пусть вероятность разбиения (то есть пирамидки из кубиков) пропорциональна параметру q в степени количество кубиков. (И тут опять начинается статистическая физика, exp(-\beta H) и всё такое). И получим мы, вместо теоремы о полярном круге — предельную форму угла кубического монокристалла:

(Каюсь, не помню, чья это иллюстрация — но не моя. У Кеньона есть похожая, но чуть-чуть в других цветах — http://www.math.brown.edu/~rkenyon/gallery/bppsim.gif )

Кстати — левая иллюстрация на обложке как раз на нашу тему, только я показать её забыл: это случайное разбиение, но на шестиугольной, а не на квадратной, решётке. Раскрашенное в три цвета — то есть выглядящее, как кубики, сложенные в углу комнаты. И я забыл сказать, что для этого случая тоже есть "теорема о полярном круге" —

И ещё два слова я ещё скажу, а пока, в качестве иллюстрации сложности — большая книга, которая так и называется: "Markov chains and mixing times" — https://pages.uoregon.edu/dlevin/MARKOV/markovmixing.pdf

Тогда случайное блуждание, начавшееся в 100-мерном кубе (например, в точке "все нули"), будет там блуждать как минимум до первого попадания в точку перехода в 200-мерный куб. Соответственно, на временах, заметно меньших 2^100 итераций, мы будем видеть только пренебрежимо малую (2^100 по сравнению с 2^200) долю вершин нашего графа. (А если 100 в этом примере мало — возьмём 1000, и можно будет написать "за всё время существования Вселенной".) Ну и, собственно, проблема явно видна — "перешейки". Вопрос только в том, что с ними делать.

Давайте возьмём два куба, один 100-мерный, другой 200-мерный. И соединим в них лишь одну вершину одного с одной вершиной другого. (Например, "все единицы" со "всеми единицами".)

То, что он может быть сильно нетривиальным, можно увидеть на примере того же многомерного куба. Скажем, понятно, что бессмысленно делать число итераций меньшее, чем диаметр графа — мы тогда просто не сумеем от любой вершины дойти до любой. Но оказывается, что иногда характерное "время перемешивания" (собственно, оно так и называется, "mixing time") — гораздо больше.

Вопрос из этой же серии — а сколько раз нужно перетасовывать колоду, чтобы порядок карт в ней можно было считать случайным? Народ вполне серьёзно этим вопросом занимался — и я тут ограничусь ссылкой на текст Американского Математического Общества: http://www.ams.org/publicoutreach/feature-column/fcarc-shuffle

И при взгляде на всё это должен появиться вопрос — а когда пора остановиться? _Сколько именно_ нужно ждать, чтобы можно было сказать, что да, мы получили что-то "почти случайное"?

6000-я: