Математические байки
Ir al canal en Telegram
Рассказы про разную математику. Архив: http://dev.mccme.ru/~merzon/mirror/mathtabletalks/
Mostrar más4 358
Suscriptores
-124 horas
+67 días
+3630 días
Archivo de publicaciones
4 358
Кстати — если рисовать гистограмму того, сколько операций было произведено в такое-то время в таком-то месте, то тоже получается красивая картина:
4 358
Начальный и конечный момент времени это начальное и итоговое расположение чемоданов, у которых графики — прямые. А в промежуточные моменты времени видны эллипсы — а синим показаны полученные уже тогда (11 лет назад, препринт ещё 2006-го — https://arxiv.org/abs/math/0609538v1 ) оценки.
4 358
А что будет в другие моменты времени? Естественно считать параметром t долю от общего числа N выполненных операций; и вот картинка опять же из их работы —
4 358
Явно проглядывает круг — но при этом плотность ближе к краям, так, как если бы это была равномерная мера на сфере в трёхмерном пространстве (x,y,z) — которую спроецировали на плоскость (x,y).
4 358
А ещё можно посмотреть на то, как будут устроены графики перестановок (при фиксированном моменте времени, какой чемодан на каком месте стоит). Вот, к примеру (опять из той же статьи) график перестановки, которая наблюдается после половины всех операций:
4 358
Тут выделена траектория, по которой движется чемодан номер 3, и отмечены места, где мы выполняли нашу операцию. Но пока ничего красивого не видно; это потому что n у ещё маленькое!
А вот такая у них получается красивая картина, если взять n=2000, и нарисовать (в соответствующем масштабе по осям) траектории отдельных чемоданов —
4 358
Так вот — давайте посмотрим на случайно выбранную сортировку, когда n достаточно большое. Вот, взятый из статьи Angel, Holroyd, Romik, Virag, "Random Sorting Networks" ( https://www.sciencedirect.com/science/article/pii/S0001870807001545 ) пример для n=6:
4 358
Как выбрать равновероятно — отдельная красивая история: их столько же, сколько способов получить диаграмму Юнга в форме равнобедренного прямоугольного треугольника, добавляя к пустой диаграмме по одной клетке за раз. (Это называется Edelman-Greene's bijection.) Но туда мы сейчас не пойдём.
4 358
С другой стороны, число способов отсортировать чемоданы ровно за это число операций больше одного. Из простейшего — можно запустить сортировку "пузырьком" начиная с 1, можно, начиная с n, можно их чередовать, но даже это только начало. А на самом деле их очень и очень много. И да, вы правильно догадались — давайте из них выберем один равновероятным образом.
