Теория вероятностей - это, вне всякого сомнения, один из самых важных и богатых приложениями разделов современной математики. С помощью методов этой замечательной науки можно как оценивать классические вероятности выигрышных стратегий в азартных играх, так и решать весьма серьезные прикладные задачи, возникающие буквально в каждой области науки. В нашем курсе мы познакомим слушателей прежде всего с самыми основами предмета. И сделаем мы это в уникальном формате - иллюстрируя вероятностные объекты и методы на примерах решения с их помощью комбинаторных задач. Суть в том, что, конечно, в базовой вероятности много комбинаторики, и это все знают; мы же расскажем не только об этом, но и о том, как, наоборот, вероятностные методы позволяют работать с комбинаторными задачами. Это позволит нам впоследствии выйти на приложения вероятности в теории графов, случайных графов и, наконец, веб-графов и прочих сложных сетей. Также в рамках курса мы оторвемся от чисто комбинаторных интерпретаций и обсудим более общие вероятностные модели. Но интуиция все равно сохранится, и в этой комбинаторной подоплеке уникальность курса. Курс построен так, что будет по плечу даже тем, кто изучал математику последний раз только в школе. Тем не менее, так как для понимания курса необходимы знания основ комбинаторики, мы рекомендуем пройти наш курс по комбинаторике прежде чем прослушивать данный курс. Внутри курса также все просто – каждую неделю вас ждут видеолекции и проверочные задания, которые нужно выполнять в срок. В конце – итоговая проверочная работа. Студенты, которые набрали достаточное количество баллов, смогут получить сертификат.
Вероятностный метод в задаче о нахождении минимального числа пустых треугольников
Loading...
Del curso dictado por Moscow Institute of Physics and Technology
Теория вероятностей для начинающих
342 calificaciones
De la lección
Бесконечные вероятностные пространства
Задача о встрече. Геометрическая вероятность. Парадокс Бертрана. Бесконечное множество элементарных исходов. Колмогоровская аксиоматика.
Conoce a los instructores
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Максим Жуковскийпреподаватель
кафедра дискретной математики МФТИ
Конечно, можно пытаться как-то явно сконструировать такое множество, то есть
прямо там пытаться в координатах описать точки этого множества и потом доказывать,
что в этом множестве пустых треугольников не больше, чем нужная нам величина.
Но вот это, представьте себе, работает очень плохо.
А гораздо лучше работает вероятностный метод.
Что значит вероятностный метод?
Опять вот, возвращаясь к нашим, к нашим раскраскам гиперграфам.
Там нам нужно было доказывать существование какой-то раскраски.
И мы брали случайную раскраску и доказывали, что это случайная
раскраска с положительной вероятностью обладает нужным нам свойством.
Ну значит и здесь, наверное,
нужно взять случайное подмножество из n точек на плоскости и доказывать,
что с положительной вероятностью в этом случайном подмножестве не больше,
чем нужное нам количество пустых треугольников.
Ну уж насколько маленьким сможем взять a при этом, настолько и хорошо.
То есть нам нужно вроде бы как случайное множество
из n точек.
Хе, но это ведь совсем не понятно что значит.
Даже случайная хорда могла быть определена по-разному,
а что такое случайное множество из n точек?
Тоже не понятно.
Можно, например, взять квадрат со стороной 1 на плоскости,
с которого мы сегодня начинали: Коля, Вася, встреча, да?
Можно взять квадрат на плоскости, и из него как-нибудь там независимо,
скажем, согласно геометрической вероятности извлечь n случайных точек.
Это, конечно, можно.
После чего надо будет считать вероятность того,
что в этом случайном множестве не слишком много пустых треугольников, и если эта
вероятность окажется положительной, то мы докажем существование такого X мощности n,
в котором не больше, чем нужное нам количество пустых треугольников.
А можно взять вместо круга, ой, извините, квадрата, например, круг на плоскости.
И в нем, согласно геометрической вероятности, выбирать случайные точки.
Вот оказывается, что все искусство получения наилучшей оценки для
вот этого a оно именно к тому и сводится: как правильно определить случайность.
То есть откуда эти случайные точки выбирать так, чтобы потом с наибольшей
вероятностью, с наиболее, так сказать, положительной вероятностью,
– наша-то цель доказать, что вероятность положительная – вот так, чтобы
потом с наибольшей вероятностью, чтобы она все-таки оказалась положительной,
с наибольшей вероятностью пустых треугольников было бы поменьше.
Количество пустых треугольников было бы как можно меньше.
Это целое искусство – правильно определить случайность множества X,
состоящего из n точек.
Давайте я не буду вдаваться в подробности доказательства, потому что оно там требует
довольных хитрых рассужений с подсчетом каких-то интегралов,
не хочу вам морочить голову, но саму конструкцию нарисую.
Одну из лучших, которая дает в итоге одну из лучших оценок для величины a.
Конструкция такая.
Берем такую, что называется, расческу, условно говоря.
Здесь 1, дальше 2,
3, и так далее, вот здесь n.
И это все отрезочки длины единица.
Вот берем такую,
Бог знает откуда, с какого потолка взявшуюся конструкцию,
но вот это именно и есть искусство выбора геометрической вероятности правильной.
Дальше, берем случайную точку x1 на первом зубце «расчески»,
берем случайную точку x2, естественно независимо от x1,
на втором зубце «расчески», дальше случайную точку x3 и,
наконец, случайную точку xn на последнем зубце.
Вот получается такой набор из n случайных точек.
Давайте X большое – это и будет {x1, ..., xn}.
Набор из n случайных точек, он, естественно, случаен сам по себе.
Вероятность попадания этого конкретного набора внутрь какого-то набора
подмножеств зубцов «расчески» тоже легко посчитать.
Но вот оказывается, что если теперь в таком определении случайности
множества из n точек на плоскости посчитать вероятность того,
что в X не больше ну,
скажем, 2,1n²
пустых треугольников, то вот она окажется положительной.
То есть существует действительно конкретное множество точек,
расположенных каждая по отдельности на своем зубце «расчески», такое,
что в этом множестве точек не больше чем 2,1n² пустых треугольников.
Ну я здесь написал 2,1 потому,
что на самом деле я с таким же успехом могу здесь написать 2,01,
2,001, и каждый раз вероятность будет больше нуля.
Но чего я не могу сделать, это заменить вот это число в точности двойкой.
То есть если в рамках этой конструкции попытаться заменить каждое из вот
этих чисел просто ровно двойкой, тогда ничего не получится.
То есть можно сказать так: если мы фиксируем произвольное ε положительное и
хотим, чтобы в случайном множестве X, которое мы выбрали с помощью вот такой вот
геометрической вероятности, было не больше,
чем (2 + ε) на n² пустых треугольников, то вот эта вероятность больше нуля.
Ну и значит такой X существует.
Но убрать ε, заменить его на ноль все-таки в этом рассуждении нам не удается.
Это не означает, что не существует более хитрого определения случайного множества,
которое даст лучший результат, но вот в рамках этого рассуждения,
если его провести до конца, вот получается такая штука.
Так, товарищи.
Но в чем пафос-то?
А пафос вот в чем.
Видите, максимальное количество пустых треугольников – это C из n по 3.
Но эта величина, которая, как мы знаем, ведет себя примерно как n³/6.
То есть максимальное количество пустых треугольников – это величина порядка n³.
А минимальное количество пустых треугольников – это величина, которая,
как мы видим, заведомо не превосходит чего-то порядка n²,
то есть гораздо меньше.
Но это еще не пафос.
Дело в том, что есть следующая теорема, которую я тоже не собираюсь здесь
доказывать, она не имеет отношения к нашей вероятностной тематике.
Вот эта имела, а эта не имеет.
Но мне просто хочется,
чтобы вы уж до конца представляли себе ситуацию с этой наукой.
А ситуация такая.
Оказывается, что f(n) ≥ (1 – ε) * n².
Это тоже можно доказать.
То есть не бывает на плоскости множества из n точек,
не бывает на плоскости множества из n точек, в которых было бы меньше,
чем столько пустых треугольников.
Иными словами, вот этот результат почти точный.
Он всего лишь в 2 плюс какая-то мелочь раз отличается от нижней оценки.
Вот эта вероятностная технология,
правильный выбор случайностей позволяет практически точно отыскать величину f(n).
Ну и вот сейчас проблема состоит в том,
чтобы найти прямо асимптотику для этого f(n).
То есть все-таки хочется найти правильную константу.
Придумали более хитрые конструкции, нежели та, которую я сейчас описал.
Известны оценки что-то типа 1,6 * n²,
но по прежнему все-таки зазор в константу раз присутствует,
и вот люди не знают, как это аккуратно посчитать.
То есть тут есть до сих весьма интересная и полезная нужная деятельность.
Такая вот забавная наука.
Explora nuestro catálogo
Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.
Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.
© 2019 Coursera Inc. Todos los derechos reservados.
