Самая длинная возрастающая подпоследовательность

УТОЧНЕНИЯ/ИСПРАВЛЕНИЯ: В теореме о предельной форме вероятность должна стремиться к 1, а не к 0. Технически случайная матрица, показанная в видео, является матрицей GOE (с вещественными элементами), а не матрицей GUE (с комплексными элементами). Распределение Трейси-Уидома, которое здесь обсуждается, соответствует GUE, а не GOE, но я обнаружил, что матрица комплексных чисел не так приятна для глаз, поэтому я немного схитрил с анимацией. Не все задачи оптимизации над независимым случайным шумом, как ожидается, будут иметь флуктуации Трейси-Уидома, но многие модели, в которых, как ожидается, такие флуктуации будут, можно сформулировать как задачи оптимизации. -------------------------------------------------------------------- Это видео предполагает, что зритель прошёл курс теории вероятностей. Надеюсь, что и без этого предварительного условия оно будет достаточно понятным и интересным, но для краткости мне пришлось принять как данность многие концепции, обычно изучаемые в подобных курсах. Подробнее см. в книге Дэна Ромика «Удивительная математика длиннейших возрастающих подпоследовательностей». Обложка этой книги использована в видео с разрешения автора. Это видео снято Виласом Винстейном, музыка — Аранкой Грушковой. Оно входит в третью рубрику Summer of Math Exposition (#SoME3). -------------------------------------------------------------------- Главы: 0:00 Введение 1:36 Эвристика 6:21 Идея доказательства 13:18 Флуктуации 16:14 Заключение