Теория вероятностей - это, вне всякого сомнения, один из самых важных и богатых приложениями разделов современной математики. С помощью методов этой замечательной науки можно как оценивать классические вероятности выигрышных стратегий в азартных играх, так и решать весьма серьезные прикладные задачи, возникающие буквально в каждой области науки. В нашем курсе мы познакомим слушателей прежде всего с самыми основами предмета. И сделаем мы это в уникальном формате - иллюстрируя вероятностные объекты и методы на примерах решения с их помощью комбинаторных задач. Суть в том, что, конечно, в базовой вероятности много комбинаторики, и это все знают; мы же расскажем не только об этом, но и о том, как, наоборот, вероятностные методы позволяют работать с комбинаторными задачами. Это позволит нам впоследствии выйти на приложения вероятности в теории графов, случайных графов и, наконец, веб-графов и прочих сложных сетей. Также в рамках курса мы оторвемся от чисто комбинаторных интерпретаций и обсудим более общие вероятностные модели. Но интуиция все равно сохранится, и в этой комбинаторной подоплеке уникальность курса. Курс построен так, что будет по плечу даже тем, кто изучал математику последний раз только в школе. Тем не менее, так как для понимания курса необходимы знания основ комбинаторики, мы рекомендуем пройти наш курс по комбинаторике прежде чем прослушивать данный курс. Внутри курса также все просто – каждую неделю вас ждут видеолекции и проверочные задания, которые нужно выполнять в срок. В конце – итоговая проверочная работа. Студенты, которые набрали достаточное количество баллов, смогут получить сертификат.
Задача о трех случайных подмножествах
Loading...
En provenance du cours de Moscow Institute of Physics and Technology
Теория вероятностей для начинающих
342 notes
À partir de la leçon
Схема испытаний Бернулли
Схема испытаний Бернулли: множество элементарных исходов, успех и его вероятность, вероятность элементарного исхода. Классическая вероятность как частный случай. Подсчет вероятности события «произошло k успехов» в схеме испытаний Бернулли. Задача про случайный выбор двух множеств – нахождение вероятности пустого пересечения. Обобщение задачи о существовании правильной раскраски на произвольное число множеств. Теорема о существовании правильной раскраски.
Rencontrer les enseignants
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Максим Жуковскийпреподаватель
кафедра дискретной математики МФТИ
Давайте обсудим еще одну замечательную задачу на случайные
подмножества конечного множества.
Мы про нее побольше поговорим, потому что она имеет выход на вообще совершенно
содержательную современную науку.
Ну сначала, давайте все-таки задачу.
По-прежнему есть у нас множество, состоящее из n элементов, ну,
которое мы считаем просто отрезком натурального ряда от 1 до n.
Есть вероятность успеха p – некоторое число из отрезка [0,
1], и есть на сей раз три случайных подмножества этого множества,
которые мы обозначим A, B и C.
Три случайных подмножества, ну как обычно.
Каждый элемент вот из этого множества, независимо от остальных,
принадлежит множеству A, точно так же принадлежит множеству B,
точно так же принадлежит множеству C.
Все в совокупности независимо, никаких зависимостей тут нет и в помине.
И на сей раз предлагается найти вероятность того,
что выполнено вот такое вот свойство: A пересеченное
с B вложено или совпадает с C, то есть совпадать не запрещается,
вложено или совпадает с A объединенным с B.
Ну такое, казалось бы, совершенно загадочное свойство.
Но в задаче есть еще второй пункт: помимо того, чтобы найти эту вероятность,
предлагается придумать какую-то геометрическую интерпретацию тому событию,
вероятность которого здесь вычисляется.
Значит, давайте сперва вычислим вероятность, а потом действительно
придумаем геометрическую интерпретацию, она совершенно сходу не очевидна.
Так, ну чтобы посчитать вероятность,
нужно действовать стандартно: нужно представить наше множество A, B и C,
наше множество A, B и C как последовательности из единичек и ноликов.
Мы так уже делали неоднократно, так,
что-нибудь такое, что-нибудь такое – не важно.
Вот представили A, B и C как последовательности из единичек и ноликов,
я не утверждаю, что они именно такие, я их просто для примера так нарисовал.
А дальше совершенно стандартно, как и на лекции, как и в разборе аналогичной задачи
про m множеств, давайте смотреть на каждый из столбцов, которые здесь возникают.
Именно на каждый из столбцов.
По-прежнему, что означает рассмотрение, ну, например, первого столбца?
Оно означает понимание того, как первый элемент вот этого
множества входит или не входит в множество A, B или C.
Понятно, что если здесь стоит единица, то первый элемент входит в множество A,
если здесь стоит ноль, как в нашем примере, то первый элемент
входит в множество B, и вот здесь видно, что первый элемент в множество C...
ой, извините, не входит, конечно, в множество B,
а вот в множество C он как раз попадает.
Вот, и нам просто нужно понять, вот если,
например, имеет место такая ситуация,
противоречит это тому, что A пересеченное с B вложено или совпадает с C,
вложено или совпадает с A объединенное с B или никаких противоречий нету?
Значит если никаких противоречий нету, то да, мы говорим,
что вот такая ситуация допустима, а если есть, то говорим, что недопустима.
Ну давайте тупо, со всей занудностью, какая только возможна,
переберем все возможные ситуации, которые могут возникнуть.
Давайте считать вот в рамках этого первого столбца каким может быть первый столбец.
Постепенно будем рассуждать, каким может быть первый столбец.
Ну понятно, что всего возможностей для первого столбца восемь, потому что ровно
столько есть последовательностей длины 3, которые бы состояли из единиц и нулей.
Ну вот давайте все эти восемь ситуаций как-нибудь и
перечислим: что вот такая ситуация есть, давайте с одним ноликом,
например, вот так, вот так и вот так.
Дальше с двумя ноликами: 0, 0,
1, 0, 1, 0, 1, 0, 0.
Ну и, наконец, с тремя ноликами.
Я специально рисую запятые, чтобы вы не думали, будто бы эта таблица,
которая вот здесь вот нарисована.
Нет, это просто все варианты того как может выглядеть первый столбец
вот в этой будущей таблице: он может оказаться состоящим из сплошных единиц, в
результате случайных бросаний монетки, он может быть вот таким, таким и так далее.
Но вот спрашивается: если он такой,
то это как-нибудь противоречит вот этому свойству?
Или никаких противоречий нету?
Ну смотрите: первый элемент входит в каждое из множеств – входит в A,
входит в B, входит в C, раз первый столбец вдруг выглядит вот так вот.
Значит первый элемент входит в каждое из множеств.
Ну раз он входит в каждое из множеств, внимание,
значит он входит и в пересечение тоже.
Но он входит и в C.
Никаких противоречий.
Да, элемент входит в пересечение, входит в C, значит это никак не противоречит тому,
что в будущем, когда мы посмотрим на все столбцы, окажется, что A пересеченное с B,
действительно, вложено или совпадает с C.
Посмотрим на правую часть этого условия.
Ну если элемент входит в каждое из этих множеств,
то он тем более входит в объединение.
Но он, по счастью, входит, да впрочем это и не важно, входит сюда,
ясно что это опять никакого противоречия не составляет.
То есть вот эта ситуация вполне нам годится, она нам ничего не портит.
Да, так действительно может быть,
что первый элемент вошел в каждое из этих множеств.
Теперь давайте смотреть вот на эту интересную
ситуацию: а может ли быть вот так?
Смотрите, первый элемент не входит в множество A,
но при этом входит в B и в C,
не входит в A, но входит в B и в C.
В пересечение он тогда попадает,
если он не входит в A, но входит в B?
Ну ясно, что попадает, он есть в этом пересечении.
Но он, по счастью, есть и в C.
Поэтому в этом месте нет никакого противоречия.
Смотрим на правую часть этого условия: еще раз, он не входит в A,
но входит в B, значит в объединение он все-таки входит,
потому что хотя бы в одно из этих двух множеств он попал.
В объединении он есть, ну и в C он есть – опять никакого противоречия,
да, так может быть.
Никаких неприятностей не возникает.
Ну, друзья, значит, я думаю, что вы сами можете проверить,
что вот здесь тоже никаких противоречий нету.
Действительно в пересечении этого элемента нет,
но в C он есть и никакого противоречия, ну и точно так же можно посмотреть направо.
Здесь все в порядке.
Так.
Хорошо.
А вот так?
Может такое быть: 1, 1, 0?
Значит, 1, 1, 0 означает, что элемент входит в A, входит в B, но не входит в C.
А вот это уже интересней.
Смотрите, элемент входит в A и B, значит он попадает в их пересечение.
В смысле, он и там и там есть, он попадает в пересечение.
С другой стороны, этот столбец означает что его нет в C.
Но как же такое может быть, чтобы было вот это вложение, если нашелся,
ну скажем, первый элемент, который здесь есть, а здесь отсутствует?
Вложений не будет.
Вот эта ситуация вредоносная, ее нужно запретить.
Такого быть не может, чтобы первый элемент входил в A и B и не входил в C,
коль скоро мы знаем вот это вот условие.
То есть вот этому событию, которое мы изучаем,
вероятность которого мы хотим посчитать,
не благоприятствует попадание такого столбца на первую позицию в нашей таблице.
Такого столбца точно быть не может.
Давайте посмотрим вот на эту ситуацию: 0, 0, 1.
Так, элемента одновременно нету в множествах A и B,
поэтому он в пересечении тоже отсутствует, конечно.
С запасом отсутствует.
Но он есть в C – никаких противоречий с левой частью.
Так, с другой стороны его одновременно нету в A и B,
то есть его нету не только в пересечении, его и в объединении тоже нет.
Его нету в объединении, но он есть в множестве C.
А как такое может быть, чтобы элемент был в множестве C, отсутствовал в объединении,
и, тем не менее, C оказалось бы вложенным в A объединенное с B?
В нем есть элемент, которого нету здесь.
Так не бывает.
Вылетел, это придется запретить.
Ну а дальше, товарищи, я не буду нудить, сами проверите,
вот эти все случаи подходят.
Их не вычеркнуть.
Всего есть два вредных случая, только два.
Ну и что в итоге получается?
Это мы рассуждали про первый столбец.
Значит первый столбец, коль скоро выполнено это вот событие, вероятность
которого мы ищем, первый столбец может быть любым, кроме вот этих двух ситуаций.
Ну ведь то же самое, конечно же, верно и для второго столбца.
И для третьего, и для последнего, который у нас имеет номер n.
То есть давайте напишем: это значит, что нам нужно найти вероятность того,
что в каждом столбце, в каждом, давайте здесь продолжим,
столбце не...
вот так, и не вот так.
Как угодно, только не так.
Опять, как и в уже известных нам задачах, имеется полная независимость по столбцам.
Поэтому вероятность, которую мы теперь записали,
это энная степень вероятности того, ну, если хотите,
что в первом столбце нет вот этих двух вредных ситуаций.
Вероятность того, что в данном столбце, не важно, первом или каком,
но уже фиксированном, в данном столбце
не один один ноль и не ноль ноль один.
Это в энной степени, в виду независимости по столбцам.
С какой вероятностью в данном столбце все, что угодно, кроме вот вот вот этого.
Ну давайте из единицы просто вычтем
вероятность, что так и вычтем вероятность, что так.
Тогда, разумеется, мы получим вероятность того, что не так, и не так.
Но вероятность вот этого столбца — это p умножить на p умножить на q,
то есть p в квадрате q.
А вероятность вот этого столбца- это q умножить на q умножить на p.
То есть q в квадрате p.
Ну это все в энной степени.
И можно чуть-чуть еще причесать, для красоты.
Один давайте pq вынесем за скобки.
А в скобках у нас останется p+q.
p+q в энной степени.
Но p+q просто по определению равняется единице же, правда?
Тут у нас получится 1 минус pq в энной степени.
Все, вероятность найдена, основная задача решена.
Ну это, казалось бы, классно.
Но там предлагается еще понять, а что это все означает геометрически.
И вот для того, чтобы рассказать о том, что это означает геометрически,
ну придется некоторые усилия нам приложить.
Вообще что такое ‹‹геометрически››?
Давайте я вот отделю здесь полученный результат.
Вероятность найдена, тут уже больше делать нечего.
А нам хочется понять, что вот это вот свойство, А пересеченное с В, вложено в С,
вложено в А объединенное с В, означает с точки зрения геометрии.
Ну геометрия здесь, конечно, не совсем простая.
То есть нужно понимать, что речь идет не про обычную плоскость,
и даже не про обычное трехмерное пространство.
А речь идет про пространство размерности n.
Ну друзья, значит если те из вас,
кто не знают совсем многомерных пространств, сейчас отпадут,
мне, конечно, будет жалко, поэтому я постараюсь как-то внятно рассказывать.
Ну с другой стороны, что ж поделать.
По крайней мере до сюда было понятно, но катарсис настоящий — он возможен только в
случае, если вы вникнете в то, что здесь происходит.
Потому что из этого вырастает очень содержательная, красивая наука,
про которую я тоже постараюсь вот в рамках этих комментариев пару слов сказать.
Значит ну смотрите.
Давайте я напомню, что такое многомерное пространство.
В конце концов я думаю, что все это должны понимать уже в рамках нашего курса.
Ну и я все-таки напомню, что оно обозначается R в энной, и я его себе
представляю следующим образом: это просто множество всевозможных точек,
каждая из которых имеет n координат.
Полностью аналогично тому,
как устроена обычная плоскость или обычное трехмерное пространство.
Просто последовательность каких-то вещественных чисел,
которые при желании мы можем считать координатами этой точки.
Каждое икс итое- это просто какое-то вещественное число.
Фактически R в энной — это вот такое вот произведение,
декартово произведение n копий вещественной прямой.
Мы рассматриваем точки, которые состоят из вещественных чисел.
Вот.
Ну давайте обсудим вот какой вопрос: а как
померить угол в пространстве размерности n?
Или, вернее, даже не угол, а то, является он тупым, прямым или острым?
Вот как это сделать, например, на плоскости?
Есть три точки, х, z и y.
Вот у нас есть здесь какой-то уголок, и нам хочется понять,
этот уголок является тупым, прямым, или острым?
Как это можно сделать?
Ну наверное все зависит от того, какой знак имеет косинус этого угла.
То есть если косинус угла положительный, то, понятное дело, это угол острый.
Если косинус угла равен нулю, то, понятное дело, это угол прямой.
Если косинус угла отрицательный, то это угол тупой.
Ну а косинус, в свою очередь,
ну скажем на плоскости вычисляется с помощью скалярного произведения.
То есть ну реально он вычисляется так: надо взять скалярное произведение и
поделить на корень из произведения скалярных квадратов.
Это я думаю, что вы знаете.
Вот. Но корень из произведения
скалярных квадратов, который стоит в знаменателе — он все равно положительный.
Поэтому на знак его величина никак не влияет.
Короче говоря, достаточно вычислить скалярное произведение для того,
чтобы понять, какой знак у косинуса угла.
Какое только скалярное произведение?
Ну понятно, надо взять вот так: x минус z на y минус z.
Вот такое скалярное произведение.
И именно его знак будет отвечать за то,
является угол тупым, прямым или острым.
Вот.
Ну и, естественно, я хочу сказать,
что в произвольной размерности имеет место скалярное произведение икс на игрек.
Это есть по определению просто икс один игрек один
плюс и так далее плюс икс эн игрек эн,
в точности так же, как это устроено на плоскости и в пространстве размерности 3.
И если взять вот это вот скалярное произведение,
то оно будет обладать ровно тем же самым свойством, что на плоскости и,
соответственно, за величину (тупость, так сказать, прямизну и остроту угла)
будет отвечать знак вот такого скалярного произведения, понятого вот в этом смысле.
Все. Вот это вот такая вот минимальная
многомерная геометрия, минимальный экскурс, если хотите,
в многомерную геометрию, как посчитать углы между точками в пространстве.
Как осознать, тупые они, прямые или острые?
Просто вычислить вот такое вот скалярное произведение.
Ну вот.
Я утверждаю, что наше замечательное событие,
вероятность которого мы посчитали,
вот это вот событие (давайте я его в фигурные скобки возьму, как водится).
Это множество всех элементарных исходов, для которых это выполнено,
то есть множество всех троек A, B и С, которые обладают этим свойством,
вот это событие — оно просто равносильно, просто совпадает со следующим.
Не забывайте, что вот эти множества А, В и С, ведь они же
отлично интерпретируются с помощью векторов с координатами из нулей и единиц.
Да?
А — это какие-то там единички и нолики,
В- это какие-то там единички и нолики, и С- это какие-то там единички и нолики.
Мы ровно так вероятность считали.
Давайте считать, что вот это вот — это вектор х,
отвечающий множеству A, это — вектор х,
отвечающий множеству В, и это — вектор х, отвечающий множеству С.
Так вот.
Тогда событие, я утверждаю что тогда событие А,
пересеченное с В вложено в С вложено в А объединенное с В — оно равносильно тому,
что скалярное произведение х с индексом А минус
х с индексом С на х с индексом В минус х с индексом С,
вот такое вот скалярное произведение строго больше нуля.
Или сейчас, секунду, нет, почему строго больше?
Равняется.
Равняется.
Вообще замечательно.
Вот так вот.
То есть смотрите, что утверждается?
Утверждается, что вот это вот теоретико-множественное свойство,
вероятность которого мы долго-долго считали — ну в общем-то простое,
но очень загадочное.
Оно на самом деле геометрически очень осмысленное.
Это просто вероятность того,
что с вершинами в точках x с индексом А,
х с индексом С и х c индексом В образуется прямой угол.
Вот это вот — это в точности прямой угол.
Такая вот неожиданная, красивая геометрия.
Ну почему это так?
Почему это так — можно понять, рассматривая тот же самый перебор случаев,
с помощью которого мы только что нашли вероятность вот этого события.
То есть опять смотрим на первый столбец.
Я уж, с вашего позволения, заново выпишу все возможные ситуации.
Один один ноль ноль один один, так,
один ноль один ноль ноль один
один ноль ноль ноль один ноль и три
нуля выписал все возможные ситуации, как я уже один раз сегодня делал.
А дальше смотрю.
Вот такая ситуация может быть, если мы хотим,
чтобы скалярное произведение равнялось нулю?
Ну, действительно, 1 – 1, 1 – 1.
Вот это вот A, вот это B, вот это C, да?
(1 – 1) * (1 – 1) — это 0,
и это ничему не противоречит, такое слагаемое в нашем скалярном произведении,
— вот оно, скалярное произведение, — вполне может возникать: если мы хотим,
чтобы в итоге получился 0, слагаемое 0 ничему не противоречит.
Подчеркиваем.
Смотрим вот на эту ситуацию.
(1 – 0) * (1 – 0).
Хе, а вот это 1.
Шлеп, так не бывает.
(0 – 1) * (1 –1) — никаких проблем.
(1 – 1) — все, уже нулевое скалярное произведение в этом месте,
по крайней мере, никаких проблем.
Здесь (0 – 1), (0 –1).
Перемножаем, получаем 1: нельзя,
0 не получится в сумме, если хотя бы одно слагаемое 1.
(1 – 0) * (0 – 0) — пожалуйста, (0 – 0) * (1 – 0) — пожалуйста.
Ну, это, конечно, тоже пожалуйста.
Смотрите, ровно те же самые ситуации запрещены, что и здесь,
что и раньше, что и вот в этом свойстве, ровно те же самые.
Ну, раз ровно те же самые, значит, это в точности то же самое событие.
Тут есть маленькое замечание, конечно.
Я сказал, что наше теоретико-множественное свойство равносильно тому,
что вот эти векторы образуют прямой угол с вершиной в точке Xc.
Так-то оно так, но есть маленькая деталь.
Помните, наши множества, в принципе, могут совпадать?
Так устроена схема Бернулли, что A, B и C могут совпадать: могут там
какими-то парами совпадать, могут все совпадать, как повезет.
То есть вот эти векторы тоже могут быть совпадающими.
Конечно, если Xb совпадает с Xc, то, в таком строгом математическом смысле,
непонятно, что значит, прямой угол здесь образуется.
Ну я и не написал «прямой угол», я написал «скалярное произведение 0».
Ну, а если 2 вектора совпадают, то их разность нулевая,
и скалярное произведение, конечно же, равняется 0.
То есть говорить о прямизне угла, разумеется,
можно только в случае, если все эти векторы разные.
Ну с какой-то вероятностью они, очевидно, все разные, и в этом случае мы
действительно корректно говорим о том, что вот это теоретико-множественное свойство
геометрически равносильно тому, что здесь возникает прямой угол.
Ну и последнее, что я скажу, комментируя эту задачу,
— видите какое красивое геометрическое свойство,
— на самом деле вокруг этого есть очень хорошая, действительно, математика.
А именно: в 1961 году два замечательных
геометра Данцер и Грюнбаум занялись следующей задачей,
которую, на самом деле, предложил Эрдеш.
Ну кто такой Эрдеж, я, вроде, еще на лекциях рассказывал.
Значит, Данцер и Грюнбаум предложили такую замечательную задачу.
Вернее, Эрдеш предложил, а Данцер и Грюнбаум ею занимались.
Задача была такая.
Вот у нас есть в пространстве Rn некоторое множество точек,
назовем его X, и давайте считать,
что в этом множестве любые 3 точки образуют только остроугольные
треугольники: любой треугольник,
порожденный точками из множества X, остроугольный.
Спрашивается: может ли такое множество X содержать много точек,
может ли оно быть большим по мощности?
Ну то есть какова максимальная мощность такого множества X,
если мы предполагаем, что любой треугольник, порожденный точками из X,
имеет только острые углы, является остроугольным?
И Данцер с Грюнбаумом долго-долго строили там разные красивые геометрические
конструкции, в результате чего у них самое лучшее что получилось,
— это пример, состоящий из 2n – 1 элементов произвольной размерности.
То есть у них получилось в каждой размерности построить множество,
в котором, действительно, любой треугольник остроугольный,
и которое при этом содержит 2n – 1 точек.
Ну раз не получилось больше, а геометры
они действительно были очень хорошие, явных конструкций никак не находилось, ну,
они сказали: «наверное, это правильный ответ, наверное, больше не бывает,
наверное, вот этот вот максимум не превосходит 2n – 1».
Это была замечательная гипотеза Данцера и Грюнбаума,
и она продержалась целых 22 года,
покуда в 1983 году этой задачей Эрдеш сам ни
занялся совместно с другим замечательным венгерским математиком по фамилии Фюреди.
Эрдеш и Фюреди.
И совершенно неожиданно они
доказали, что бывают множества X в пространстве,
в которых любые 3 точки образуют остроугольный треугольник,
и которые, тем не менее, гораздо «жирнее», чем все примеры Данцера и Грюнбаума,
а именно: это множества, содержащие не меньше, чем вот столько точек,
2/√3 в n-ной степени.
То есть, смотрите, эта функция растет как экспонента, а эта функция растет линейно.
То есть у нас получается, что Эрдеш и Фюреди мало того что «проплющили» Данцера
и Грюнбаума, но «проплющили» еще с колоссальным запасом: экспонента
растет намного, намного быстрее, нежели линейная функция.
Единственный забавный факт состоит в том, что,
поскольку вот эта константа довольно маленькая, 2/√3, — конечно, да,
она возводится в n-ную степень, но это всего там 1,154 примерно,
здесь вот стоит 1,154, что-то такое, — но поскольку
это достаточно маленькое число, то лишь начиная с некоторого момента,
лишь начиная с некоторого достаточно большого n, вот это становится больше,
чем 2n – 1, а именно: нужно, чтобы n было не меньше, чем 35.
Вот начиная с размерности 35,
пример Эрдеша и Фюреди превосходит пример Данцера и Грюнбаума.
Ну дальше они начинают расходиться как экспонента по отношению к линейной
функции, то есть тут все замечательно.
И пафос в том, что Эрдеш и Фюреди не построили никакого примера,
они лишь доказали, что существует этот пример,
и сделали они это традиционным вероятностным методом.
У нас сейчас вот на данном этапе не хватает техники, для того чтобы в точности
воспроизвести доказательство Эрдеша и Фюреди, но вот та вероятность,
которую мы с вами сосчитали, по сути, служит единственным
содержательным основным ингредиентом, собственно, в доказательстве.
То есть доказательство очень простое, и когда мы с вами изучим, что такое
математическое ожидание, я вполне смогу его рассказать, оно, в общем-то, доступно.
Ну, что называется, учите теорию вероятности, это очень полезно.
Explorer notre catalogue
Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.
Coursera propose un accès universel à la meilleure formation au monde,
en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.
© 2019 Coursera Inc. Tous droits réservés.
