Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Определение 3.1 (Классическое определение вероятности). Допустим, что в ходе эксперимента извлекается одна из п — равновероятных точек и что
Глава 3. Теория вероятностей и теория информации
95
в результате каждого эксперимента обязательно извлекается одна точка. Обозначим через т количество точек, принадлежащих событию Е. Тогда вероятностью события Е называется число ^. Эта вероятность обозначается следующим образом:
РгоВД = —.
п
Пример 3.2. В примере 3.1 вероятности таковы.
2. РгоЪ[?2] = 1.
3. РгоЦЯз] = ^-. ?
Определение 3.2 (Статистическое определение вероятности). Допустим, что при одинаковых условиях проводятся п экспериментов, в которых р. раз происходит событие. Если при достаточно больших значениях п величина ? становится и остается устойчивой, то говорят, что событие Е происходит с вероятностью
РтоЫЕ] ~ ^.
п
В разделе 3.5.3 мы увидим, что при некоторых интуитивных предположениях определение 3.2 можно вывести из теоремы, которая является следствием закона больших чисел.
3.3 Свойства
1. Поле вероятностей само по себе является достоверным событием (sure event). Например, S = {ОРЕЛ, РЕШКА}. Тогда
Prob[S] = 1.
2. Обозначим через О событие, не содержащее ни одной точки (т.е. событие, которое никогда не происходит, например, черные бубны). Это событие называется невозможным (impossible event). Вероятность невозможного события равна нулю.
Prob[0] = 0.
3. Вероятность любого события удовлетворяет неравенству
0 < Prob[0] < 1.
96
Часть II. Математические основы
4. Если Е С F, то говорят, что событие Е влечет событие F, и
Prob[F] ^ Prob[F].
5. Обозначим через Ё = S\F событие, дополнительное (complementary) по отношению к событию Е. Тогда
Prob[F] + Prob[F] = 1.
3.4 Основные вычисления
Обозначим через Е U F сумму событий Е и F (происходит одно из двух событий), а через EHF — произведение событий F и F (происходят оба события).
3.4.1 Правила сложения
1. Prob[F U F] = Prob[?] + Prob[F] - Prob[F П F].
2. Если Е П F = О, говорят, что события Е и F являются взаимно исключающими, или несовместными, и
Prob[F U F] = Prob[F] + Prob[F].
п
3. Если U Ei = S и Ei П Ej = 0(г ф j), то
г=1
?РгоЬ[?У = 1.
i=i
Пример 3.3. Покажем, что
Prob[? U F] = Prob[F] + Prob[F П Ё]. (3.4.1)
Поскольку E\jF = ELi[FnE), где события Е и F П Ё являются взаимно | исключающими, равенство (3.4.1) является следствием правила 2. ?
Определение 3.3 (Условная вероятность). Пусть Е и F — два события, причем событие Е имеет ненулевую вероятность. Вероятность события F при условии, что произошло событие Е, называется условной вероятностью события F при условии события Е и вычисляется по формуле
^ , r^i^ ProblEnF]
Глава 3. Теория вероятностей и теория информации
97
Пример 3.4. Рассмотрим семьи с двумя детьми. Обозначим буквами д (girl) и Ь (boy) пол ребенка (девочка и мальчик соответственно), причем первая буква обозначает пол старшего ребенка. Существует четыре возможности дд, gb, Ьд и ЬЬ. Эти точки образуют поле вероятностей S. Вероятность извлечь каждую из этих точек из поля вероятностей равна \. Обозначим через Е событие "в семье есть девочка", а через F — событие "в семье есть две девочки". Чему равна вероятность события F при условии, что произошло событие Е (т.е. Prob[F|.E])?
Событие EnF представляет собой точку дд, поэтому Prob[.E П F] = Поскольку событие Е состоит из точек дд, дЬ или Ьд, Prob[.E П F] = |. Следовательно, по определению 3.3 Prob[F|.E] = |. Действительно, в одной трети случаев в семьях, имеющих двух детей, одна из которых — девочка, оба ребенка являются девочками. ?
Определение 3.4 (Независимые события). События Е и F называются независимыми, тогда и только тогда, когда
Prob[F|?] = Prob[F].
3.4.2 Правила умножения
1. РтоЦЕ nF] = Prob[F|?] х Prob[?] = Prob[?|F] x Prob[F].
2. Если события E и F являются независимыми, то
Prob[? П F] — Prob[E] x Prob[F].
Пример 3.5. Вернемся к примеру 3.1. Предположим, что события Е\ и Eq, являются независимыми. Их вероятности равны ^ и \ соответственно (пример 3.2). Поскольку эти события независимы, применяя второе правило умножения, получаем, что вероятность их одновременной реализации (из колоды извлекается туз красной масти) равна ?
3.4.3 Закон полной вероятности
Закон полной вероятности (law of total probability) выражается следующей теоремой.
п
Теорема 3.1. Если (J Ei = S и Ei П Ej = О (г ф j), mo для любого события Е t=i
п
Prob [А] = J^Prob [А | Ei] Prob [Et].
г=1
98
Часть II. Математические основы
Доказательство. Поскольку
п
А = АГ\Б = \J{ADEi),
i=l
где А П Ei и А П Ej (г ф j) являются взаимно исключающими, вероятность суммы событий в правой части равенства можно вычислить по второму правилу сложения вероятностей, причем вероятность каждого слагаемого вычисляется по первому правилу умножения. о
Закон полной вероятности весьма полезен. Мы будем часто применять его при вычислении (или оценке) условной вероятности события А при взаимоисключающих событиях (как правило, при событиях Е и Ё). Полезность этой формулы объясняется тем, что часто легче оценить условные вероятности Prob [j4|Z?j], чем непосредственно вычислять вероятность РгоЬ[Л].
