Эрдёш и вероятностный метод: как доказать существование с помощью случая
У Пола Эрдёша не было дома, не было работы в обычном смысле и почти не было имущества. Он провёл жизнь, переезжая между университетами с чемоданом, появляясь на пороге у коллеги со словами «мой мозг открыт» и оставляя после себя поток теорем и нерешённых задач, над которыми математики работают и сегодня. Среди всего им созданного одна идея выделяется тем, что изменила сам способ доказательства. Она называется вероятностным методом, и в её основе лежит ход, который звучит почти как жульничество: доказать, что нечто существует, отказавшись это построить.
Вопрос: когда порядок неизбежен?
Начнём с простой на вид головоломки. На вечеринке из шести человек любые двое либо друзья, либо незнакомцы. Оказывается, что среди любых шести человек всегда можно найти трёх, которые все взаимно друзья, или трёх, которые все взаимно незнакомцы. Порядок вынуждает себя появиться. Раздел математики, изучающий, когда это обязано происходить, называется теорией Рамсея, и он привязывает к вопросу число.
Теорема Рамсея гарантирует, что эти числа существуют, но не говорит, насколько они велики. Естественное продолжение таково: насколько большой может стать группа, всё ещё избегая любого одноцветного скопления размера k? Ответить на это значит доказать, что такая хитрая раскраска существует. И именно здесь построение её вручную становится безнадёжным, потому что число возможных раскрасок астрономично.
Ход Эрдёша: не строй, а считай
Озарение Эрдёша в 1947 году состояло в том, чтобы перестать пытаться спроектировать хорошую раскраску и вместо этого раскрашивать совершенно случайно, а затем дать арифметике сделать работу. Рассуждение достаточно короткое, чтобы проследить его целиком.
Раскрась каждую связь подбрасыванием монеты
Возьмите n человек и рассмотрите полную сеть, где каждая пара соединена ребром. Раскрасьте каждое ребро независимо и случайно, в красный или синий, каждый с вероятностью одна вторая. Никакой хитрости, никакого замысла. Просто честная монета для каждого отдельного ребра.
Измерь, насколько вероятно, что одна группа одноцветна
Зафиксируйте любой конкретный набор из k человек. Среди них есть C(k,2) рёбер, то есть k(k-1)/2 связей. Чтобы все эти рёбра имели один цвет, маловероятно: вероятность равна 2 × (1/2)^C(k,2), поскольку цветов два и каждое из C(k,2) подбрасываний монеты должно совпасть. Назовём это малое число p.
Сложи ожидаемое число плохих групп
Существует C(n,k) различных групп из k человек, о которых надо беспокоиться. По линейности математического ожидания ожидаемое число полностью одноцветных групп это просто количество групп, умноженное на вероятность для каждой: C(n,k) × 2 × (1/2)^C(k,2). Это единственное выражение в среднем описывает, сколько одноцветных скоплений будет содержать случайная раскраска.
Если среднее меньше 1, безупречная раскраска обязана существовать
Теперь выберите n примерно равным 2^(k/2). При таком выборе ожидаемое число выше оказывается меньше 1. Но количество реальных одноцветных групп это целое число, и если среднее по всем раскраскам меньше 1, то хотя бы одна раскраска обязана дать 0. У этой раскраски вообще нет одноцветной группы размера k. Следовательно, R(k,k) больше n, который равен примерно 2^(k/2).
Перечитайте этот последний шаг, потому что в нём вся магия. Мы так и не произвели хорошую раскраску. Мы её так и не описали. Мы показали, что средняя раскраска настолько близка к безупречной, что идеальная вынуждена существовать где-то в этой куче. Доказательство вручает вам уверенность в конкретном объекте, не указывая ни на один объект в отдельности.
Почему это было революционно
До Эрдёша доказать, что нечто существует, почти всегда означало это построить или хотя бы описать процедуру, которая это сделает. Вероятностный метод сломал это ожидание. Он установил, что сама случайность может служить доказательством: если случайная попытка удаётся с любой вероятностью выше нуля, успех возможен, и точка.
Этот неконструктивный оттенок ставит рассуждение в один ряд с самыми изящными результатами математики. Диагональный аргумент Кантора тоже доказывает существование нечто, числа, отсутствующего в любом списке, через чистую логическую силу, а не явное построение. Оба разделяют эту тихую, почти тревожащую мощь: вывод герметичен, хотя он так и не показывает вам то, что обещает. Случайность здесь покоится на тех же основаниях, что разобраны в статье интуитивное понимание вероятности, где идея математического ожидания, движитель третьего шага, выстраивается с нуля.
Проблемы Эрдёша и их момент с ИИ
Эрдёш не только доказывал теоремы. Он ставил задачи, сотни задач, часто прилагая небольшие денежные призы, которые варьировались от нескольких долларов за каверзное упражнение до тысяч за вопрос, который он считал по-настоящему глубоким. Многие из этих задач до сих пор открыты, и они тщательно каталогизированы и поддерживаются на erdosproblems.com.
Дзен этого
Вероятностный метод прекрасен по той же причине, по какой прекрасен хороший фокус: вы следите за каждым шагом, не можете найти место, где вас обманули, и всё же результат по-прежнему кажется невозможным. Никакой ловкости рук. Математическое ожидание действительно меньше единицы, и целое число, меньшее собственного среднего, действительно обязано где-то опуститься до нуля. Уверенность полна, построение отсутствует, и оба этих факта истинны одновременно.
Вот непреходящий урок, который оставил после себя Эрдёш. Существование и построение это не одно и то же. Иногда самый чистый способ узнать, что идеальный объект где-то там, это доказать, что средний объект почти идеален, и дать разнице сделать остальное. Ради другого результата, где одна строка связывает воедино идеи, кажущиеся несвязанными, тождество Эйлера предлагает противоположный род красоты: там, где Эрдёш вызывает существование из подсчёта, Эйлер пригвождает одно точное и неизбежное число.
Частые вопросы
- Что такое вероятностный метод?
- Это способ доказать, что объект с некоторым свойством существует, не строя этот объект напрямую. Вы создаёте случайную версию искомого, показываете, что вероятность наличия нужного свойства больше нуля, и заключаете, что хотя бы один такой объект обязан существовать. Пол Эрдёш первым развил этот приём, и сегодня это центральный инструмент комбинаторики и информатики.
- Что Эрдёш доказал с его помощью?
- Его знаковый результат 1947 года дал нижнюю границу для чисел Рамсея: он показал, что диагональное число Рамсея R(k,k) больше, чем 2^(k/2). Проще говоря, существуют способы раскрасить связи в большой сети двумя цветами так, чтобы ни одна большая группа не была соединена целиком одним цветом. Он доказал, что такие раскраски существуют, ни разу не предъявив ни одной, просто посчитав.
- Как можно доказать, что нечто существует, не построив это?
- С помощью средних значений. Если выбрать объект случайно и вычислить ожидаемое число дефектов в нём, и это ожидаемое число окажется меньше 1, то хотя бы один объект из набора обязан иметь ноль дефектов. Случайный выбор со средним числом дефектов меньше единицы гарантирует, что идеальный пример где-то лежит в коллекции, хотя рассуждение и не указывает, какой именно.
- Что такое число Рамсея?
- Число Рамсея R(k,k) это наименьший размер группы, который вынуждает порядок появиться при любом расположении. Конкретно, R(k,k) это наименьшее число людей, при котором, как ни раздели каждую пару на друзей или незнакомцев, гарантированно найдётся группа из k человек, все взаимно друзья или все взаимно незнакомцы. Теорема Рамсея утверждает, что эти числа существуют; метод Эрдёша показывает, что они растут очень быстро.
- Почему вероятностный метод важен сегодня?
- Он превратил случайность в технику доказательства, и эта идея теперь пронизывает комбинаторику, проектирование алгоритмов, теорию кодирования и теоретическую информатику. Многие результаты о сетях и алгоритмах до сих пор доказываются тем, что случайная конструкция работает с положительной вероятностью. Метод также объясняет, почему значительная часть собственных задач Эрдёша остаётся активными целями исследований.
Понравилось разбираться?
Math Zen превращает такую интуицию в ежедневную практику: адаптивные задачи по 24 темам математики.
