Теория вероятностей - это, вне всякого сомнения, один из самых важных и богатых приложениями разделов современной математики. С помощью методов этой замечательной науки можно как оценивать классические вероятности выигрышных стратегий в азартных играх, так и решать весьма серьезные прикладные задачи, возникающие буквально в каждой области науки. В нашем курсе мы познакомим слушателей прежде всего с самыми основами предмета. И сделаем мы это в уникальном формате - иллюстрируя вероятностные объекты и методы на примерах решения с их помощью комбинаторных задач. Суть в том, что, конечно, в базовой вероятности много комбинаторики, и это все знают; мы же расскажем не только об этом, но и о том, как, наоборот, вероятностные методы позволяют работать с комбинаторными задачами. Это позволит нам впоследствии выйти на приложения вероятности в теории графов, случайных графов и, наконец, веб-графов и прочих сложных сетей. Также в рамках курса мы оторвемся от чисто комбинаторных интерпретаций и обсудим более общие вероятностные модели. Но интуиция все равно сохранится, и в этой комбинаторной подоплеке уникальность курса. Курс построен так, что будет по плечу даже тем, кто изучал математику последний раз только в школе. Тем не менее, так как для понимания курса необходимы знания основ комбинаторики, мы рекомендуем пройти наш курс по комбинаторике прежде чем прослушивать данный курс. Внутри курса также все просто – каждую неделю вас ждут видеолекции и проверочные задания, которые нужно выполнять в срок. В конце – итоговая проверочная работа. Студенты, которые набрали достаточное количество баллов, смогут получить сертификат.
Задача о пользователе социальной сети
Loading...
Из курса от партнера Moscow Institute of Physics and Technology
Теория вероятностей для начинающих
307 оценки
Из урока
Схема испытаний Бернулли
Схема испытаний Бернулли: множество элементарных исходов, успех и его вероятность, вероятность элементарного исхода. Классическая вероятность как частный случай. Подсчет вероятности события «произошло k успехов» в схеме испытаний Бернулли. Задача про случайный выбор двух множеств – нахождение вероятности пустого пересечения. Обобщение задачи о существовании правильной раскраски на произвольное число множеств. Теорема о существовании правильной раскраски.
Познакомьтесь с преподавателями
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Максим Жуковскийпреподаватель
кафедра дискретной математики МФТИ
Давайте, друзья разберем задачу на сочетание условной вероятности и
схемы испытаний Бернулли.
Ну такую, в каком-то смысле, жизненную, конечно, не вполне, ну уж...
Ладно, значит, постановка такая: пользователь социальной сети...
Ну давайте это все запишем.
Пользователь социальной сети,
давайте считать, что имеет всего 7 друзей по числу дней в неделю.
Значит, мне так удобнее будет.
Имеет 7 друзей.
Если кого-то смущает такое маленькое количество, ну вы не переживайте,
мы просто рассматриваем конкретных семерых друзей,
и вот именно о них пойдет речь в задаче.
Так вот он имеет каких-то конкретных семерых друзей и каждый день он
просматривает стену одного из своих вот этих вот семерых друзей.
Каждый день — ровно одного.
Так у него заведено.
...он просматривает
стену одного из них.
При этом делает он это с одной и той же вероятностью для каждого из друзей.
То есть, ну в общем, с вероятностью 1/7 он просматривает стену первого друга,
с вероятностью 1/7 — второго, ну и так далее вплоть до последнего седьмого друга.
Друзья, естественно, разные.
Вот.
Давайте обозначим буковкой ν первую неделю,
номер первой недели.
Давайте так: ν — номер первой недели,
когда наш пользователь,
вот этот самый товарищ, — давайте я напишу просто «он» —
просмотрит стены всех своих друзей.
...стены всех своих друзей.
Сейчас я еще раз повторю, как устроен процесс.
Ну, если хотите, процесс начинается так: в какой-то понедельник
он случайным образом просматривает стену одного из семерых друзей.
Потом наступает вторник, он снова случайным образом, независимо от того, как
он это сделал в понедельник, просматривает стену одного из семерых друзей.
То же самое делает в среду, то же самое — в четверг и так вплоть до воскресенья.
Вот если на этой первой неделе, действуя таким образом,
он не преуспел в просмотре всех стен, тогда мы считаем, что вот ну не повезло.
И наступает следующая неделя, на которой снова в понедельник он смотрит какого-то
случайного, во вторник — кого-то случайного и так вплоть до воскресенья.
И если опять в течение вот этих 7-ми дней
ему не удалось просмотреть все 7 стен — ну значит не судьба.
Вот если удалось, тогда ν = 2.
Ну и так далее, то есть ν — это номер первой недели,
в которую ему удалось просмотреть всех семерых своих друзей.
Давайте рассмотрим на самом деле два даже пункта этой задачи.
Во-первых, давайте считать, что известно,
что в первые две недели он не преуспел.
В первые две недели нашлись какие-то друзья,
которых он все-таки просмотреть не сумел при таком случайном процессе просмотра.
В первые две недели он, ну давайте, не преуспел.
Спрашивается: какова вот в этих условиях, коль скоро это известно,
какова вероятность того, что он преуспеет на третью неделю?
То есть, на самом деле, я вот здесь черточку не рисую, но смысл в том,
что мы хотим посчитать условную вероятность.
Вероятность того, что ν = 3, что он преуспеет на третьей неделе при условии,
что на первых двух преуспеяние не достигнуто.
Вот.
Ну и пункт б).
Давайте еще одну такую же задачу сделаем.
Это вероятность того, что ν = 3 при условии, что ν — нечетное число.
Вот здесь я уже явно нарисовал черточку, но,
повторяю, и в пункте а) и в пункте б) на самом деле присутствует черта.
То есть, строго говоря, здесь надо было написать: вероятность того,
что ν = 3 при условии, что в первые две недели он не преуспел.
Так. Ну а здесь вот, что ν = 3 при условии,
что ν — нечетное.
Ну давайте начнем с пункта а).
Введем какие-нибудь обозначения, наверное.
Давайте через A обозначим, собственно,
интересующее нас событие, состоящее в том, что ν = 3 (первая неделя,
когда он преуспел), а B — ну это то условие, которое известно.
То есть нас интересует условная вероятность A при условии B.
B — это событие, состоящее в том, что в первые две недели наш пользователь не
сумел просмотреть стены всех своих друзей.
Повторяю, в первую неделю не сумел и во вторую неделю не сумел.
Суммарно, может быть, у него и получилось.
Но мы об этом не говорим.
Ну понятное дело, что, как всегда, условная вероятность — это, конечно,
вероятность пересечения событий поделить на вероятность условия.
Ну дальше...
Что такое пересечение событий?
С какой вероятностью случится то, что в третью неделю он преуспел,
а в первые две не преуспел?
Давайте рассмотрим для того, чтобы посчитать эту вероятность,
такую понятную совершенно схему испытаний Бернулли.
Каждое испытание Бернулли соответствует номеру очередной недели,
в течение которой он пытается преуспеть.
Вот в слове «преуспеть» уже видно, заложен какой-то успех, правда?
Как в схеме испытаний Бернулли.
Поэтому испытания — это просто недели.
И «успех» (преуспеяние) состоит в том,
что на очередном испытании, то есть в течение очередной недели,
товарищу таки удалось просмотреть все стены.
Давайте, как водится в схеме испытаний Бернулли,
буковкой p обозначим вероятность успеха и, собственно, ее сосчитаем.
То есть с какой вероятностью в рамках очередной недели нашему
пользователю удастся просмотреть все стены.
Ну понятно, как эта вероятность устроена.
Всего существует 7 в 7-ой степени вариантов, которые могут, в принципе,
реализоваться, потому что каждый день он может просмотреть любого из своих друзей.
Значит, по обычному комбинаторому правилу умножения, у нас получается 7 в
7-ой всевозможных вариантов, как он может просматривать стены в течение недели.
Вот.
А преуспеяние происходит из них только в случаях,
когда он просматривает всех, но при этом, бог его знает, в каком порядке.
То есть он может на первый день просмотреть стену первого друга,
на второй — второго и так далее, на седьмой – седьмого; а может в каком-то
другом порядке: скажем, на первый день — седьмого, на второй — шестого, на третий —
пятого, на седьмой — первого, то есть в совершенно противоположном порядке.
Короче, понятно,
что нашему успеху благоприятствуют ровно те варианты просмотров,
при которых мы просто имеем перестановку на множестве из 7-ми элементов.
Всего есть 7!
способов так сделать,
чтобы в течение недели просмотреть всех семерых своих товарищей.
Ну можно, если угодно, подсократить и написать: 6!
поделить на 7 в 6-ой степени.
Принципиально это, понятное дело, не меняет ничего,
но вот так чуть-чуть покороче как бы считать.
Вот. Это вероятность успеха — вероятность того,
что в течение очередной недели наш пользователь
увидит в каком-нибудь порядке стены всех своих друзей.
Это вероятность успеха.
Что же у нас, спрашивается, вот здесь?
Что такое вероятность A, пересеченного с B?
Ну это вероятность того, что на первых двух неделях в нашей
вот такой вот схеме испытаний Бернулли произошли неудачи,
а на третью неделю случился успех.
Ну неудача у нас случается с вероятностью (1 – p).
Поскольку неудача нас преследовала — вернее, не нас,
а вот этого товарища — преследовала дважды подряд, то мы пишем (1 – p)².
Все просмотры, понятное дело, осуществляются независимо.
Ну а дальше то, что все-таки ν = 3 означает,
что на третьей неделе случился успех, и он случился с вероятностью p.
Ну и теперь нам нужно поделить это на вероятность события B,
которое по-прежнему состоит в том, что в первые две недели
товарищ не преуспевал.
В первые две недели товарищ не преуспевал.
Ну, вроде бы, совершенно понятно,
с какой вероятностью он не преуспевал в первые две недели.
Значит, что просто надо поделить вот так,
и ответ получен.
Тут, в общем,
большого дела-то нету.
Так.
Ну давайте посмотрим пункт б).
Он, наверное, чуть более интересен.
Нам нужно как-то посчитать условную вероятность того, что ν = 3,
при условии, что ν нечетно.
Но опять мы можем ввести обозначение A — это ν = 3.
B — это ν нечётно, и вероятность их пересечения.
Ой, извините, условная вероятность A при условии B — это вероятность их
пересечения, поделённая на вероятность условия, как и прежде.
Ну пересечение, событие, состоящее в том,
что ν = 3 и в том, что ν — нечетное, это, конечно, первое из них.
То есть фактически это вероятность A, поделенная на вероятность B.
Таким образом, нам нужно посчитать каждую из этих вероятностей.
Но вероятность A мы фактически считали, вот она у нас здесь присутствует,
это вероятность того, что на первых двух неделях случилась неприятность,
и он всех не просмотрел.
То есть (1 − p) в квадрате, ну а на третью неделю все-таки
случилась удача, успех, и ему удалось просмотреть всех своих друзей.
Вероятность B — это несколько более интересно,
потому что схема-то Бернулли у нас бесконечная.
Фактически процесс может продолжаться сколько угодно долго, сколь угодно долго.
Значит, давайте попробуем, что такое вероятность того, что B нечётно?
Ну просто разобьем событие B на кусочки.
ν нечётно, это означает, что либо ν = 1,
либо ν = 3, либо ν = 5, и так далее, в общем-то, до бесконечности.
Каждое нечётное число нам вполне в этом месте благоприятствует.
Но вероятность того, что ν = 1, то есть,
что он сразу преуспел, ну эта вероятность, конечно, = p.
Преуспел, и слава богу.
Дальше есть ν = 3, это (1 − p)² * p Мы это уже считали.
Дальше есть случай, когда ν = 5.
Ну это означает, что первые 4 недели случалась неприятность,
(1 − p) в 4-ой, ну а на 5-ю неделю случилась удача.
Ну, +, в общем-то, ...,.
Дальше будет (1 − p) в 6-ой степени * p, ну и, ..., до бесконечности.
Ну давайте это как-нибудь перепишем.
У нас получается (1 − p)² * p, поделить...
Здесь мы p вынесем за скобку, а в скобках останется сумма
такой бесконечной геометрической прогрессии: 1
+ (1 − p)² + (1 − p) в 4-ой,
+ ,..., до бесконечности.
Такая бесконечно убывающая геометрическая прогрессия, которую, я надеюсь,
со школы все умеют считать.
(1 − p)² сохраняем,
p у нас уничтожилось благополучно.
Так...
Ну и давайте посмотрим, чему эта сумма равняется?
Сумма эта равняется вот чему.
Надо 1 поделить...
ну давайте я вот здесь прям так и напишу: 1 / на
разность, из 1 вычитается величина знаменателя этой прогрессии.
Это геометрическая прогрессия, у неё знаменатель: (1 − p)².
Каждый раз тут на (1 − p)² мы умножаем.
Вот, значит, это (1 − p)²,
знаменатель геометрической прогрессии, он оказывается здесь после знака «−».
Ну поскольку мы что-то делим на 1, делённое на что-то, то то,
на что делится знаменатель, оно перескакивает в числитель.
То есть у нас в итоге получается вот так: (1 − p)²,
− (1 − p) в 4-ой степени.
И вот это вот — ответ во втором пункте.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
