Дискретная вероятность

Видеолекцию "Дискретная вероятность (крэш-курс)" профессора Дэна Боне (Стэнфордский Университет) в рамках курса по криптографии можно найти здесь:
https://class.coursera.org/crypto/lecture/11

Ниже приведен перевод титров к этой лекции. Тэгом [слайд] я обозначаю содержание слайдов (здесь могут быть вопросы, формулы, картинки, пояснения и т.п.), которые профессор приводит по ходу лекции для наглядности материала.



Дополнительная информация: http://en.wikibooks.org/wiki/High_School_Mathematics_Extensions/Discrete_Probability

Приступим. На протяжении всего курса, мы будем использовать некоторые понятия и обозначения, встречаемые в теории вероятности. Я хотел убедиться, что все знакомы с этими обозначениями, поэтому я проведу ускоренный вводный курс в дискретную вероятность. Даже если вы не знакомы с тем, что я скажу здесь, это не катастрофа. Я дам вам ссылку на интернет-ресурс, где вы сможете почитать про эту вещь чуть более подробно. И сможете ознакомиться с тем, что мы будем использовать из дискретной вероятности. В основном, мы будем использовать условные обозначения. И они являются вполне несложными, чтобы понять и узнать о чем идет речь. Итак, начнем с основ.

[слайд] U: конечное множество, т.е. $U = \{0,1\}^n$ [слайд]

А именно, дискретное поле вероятностей (discreet probability space). И для нас, оно просто будет конечным множеством, которое я буду обозначать через U. Чаще всего, мы будем использовать множество всех n-битных строк как наше поле вероятностей. Это такое поле, которое включает в себя все строки, состоящие из символов 0 и 1, длины n.

[слайд]
Определение. Распределение вероятности P над U - это функция $P:U \longrightarrow [0,1]$, такая
что $\sum\limits_{x \in U}P(x) = 1$
[слайд]

А тогда распределение вероятности (probability distribution) (мы будем обозначать его через Р) над этим множеством бит - есть всего лишь функция, которая присваивает каждому элементу x принадлежащему U значение-вес, лежащее в интервале от 0 до 1. И единственным требованием является то, что сумма всех весов равна 1. Окей? Так, а какие виды распределений вероятности существуют. Для этого я хотел бы привести два примера.

[слайд] 1. Равномерное распределение:
для любых $x \in U: P(x) = 1/|U|$ [слайд]

Первым примером является равномерное распределение (uniform distribution), где каждый элемент в поле вероятностей имеет равный вес. Т.е. каждый элемент в поле вероятностей распределяется равномерно. В общем, если взять выборку из этого распределения, то увидим, что вероятность появления каждого элемента в пространстве - равновероятная.

[слайд] 2. Точечное распределение для x0:
$P(x_0) = 1,$ а для любых $x \neq x_0: P(x) = 0$ [слайд]

И второй пример распределения, который я хотел бы упомянуть, - точечное распределение (point distribution). В этом распределении вся масса вероятностей сосредоточены в одной точке x0, а все остальные точки по сути имеют нулевую массу. Потому что наше поле вероятностей конечно.

[слайд] Вектор распределения для множества из трех бит:
(Р(000), Р(001), Р(010), Р(011),… Р(111)) [слайд]

Вы можете воспринимать функцию P буквально, как вектор. Так что, функцию Р можно представить как запись всех его значений. Его размерность будет 2 в степени n, или, в нашем случае 2 в степени n компонентов, состоящих из 0 и 1 длиной n. Я просто хотел сказать, что когда говорю, что два распределения равны - два распределения, состоящих из 0 и 1 длиной n - это значит, что и векторы равны, где вектор, соответствующий одному распределению, идентичен вектору, соответствующий другому распределению. И тогда мы скажем, что два распределения одинаковы. Окей. До сих пор все ясно.

[слайд]
Множество А называют событием, если:
$A \subseteq U: Pr[A] = \sum\limits_{x \in A} P(x) \in [0,1]$
[слайд]

А сейчас еще несколько обозначений. По существу, если вы возьмете какое-либо подмножество A из U, то чтобы определить его вероятность Pr[A], надо просуммировать вероятности всех элементов этого подмножества. Окей. Таким образом, это подмножество А называют событием (event), понятно?

[слайд] Пример:
событие A = {для любых x из {0,1}n, таких, что младшие два разряда lsb2(x)=11}
для равномерного распределения {0,1}n: вероятность события Pr[A] = 1/4
[слайд]

Предположим, что мы смотрим на строки длиной n, как вы уже знаете, состоящих из 0 и 1. И эти строки заканчиваются парой цифр – 11, окей? Это наше событие. А теперь представьте, что мы смотрим на равномерное распределение, состоящее из 0 и 1 длиной n - {0,1}n. Как вы думаете, какая вероятность нашего события? Она равна весу всего целого события под равномерным распределением. Ну, я думаю, все знают, что ответ будет 1/4, потому что вероятность получения в последних двух битах значения 11, в принципе, было бы равно половине вероятности для одного последнего бита. Вероятность последнего бита 1/2. А для второго бита уже будет половина 1/2. И равно 1/4.

[слайд]
Обозначим через $A_1 \cup A_2$ сумму событий $A_1$ и $A_2$ (происходит одно из двух событий).
Тогда вероятность $Pr[A_1 \cup A_2] \le Pr[A_1] + Pr[A_2]$
Обозначим через $A_1 \cap A_2$ произведение событий $A_1$ и $A_2$ (происходят оба события).
Если $A_1 \cap A_2 = 0$ (события не пересекаются), тогда $Pr[A_1 \cup A_2] = Pr[A_1] + Pr[A_2]$
image00.jpg
[слайд]

Хорошо. Следующая вещь, которую я хотел бы упомянуть, называется неравенством Буля (известное как union bound). И снова рассмотрим это неравенство в рамках дискретной вероятности. Итак, пусть у нас есть два множества, два события, A1 и A2. И эти два множества лежат внутри нашего большого множества U (профессор показывает на большой круг, внутри которого лежат А1 и А2). И мы спросим, какая вероятность того, что произойдет либо событие А1, либо событие А2? Другими словами. Нам нужно объединение этих событий, и легко можно заметить, что на самом деле вероятность объединения меньше, чем сумма отдельных вероятностей. Единственная причина, почему у нас нет равенства в том, что, когда мы смотрим на сумму отдельных вероятностей, мы понимаем, что где-то мы суммируем дважды. Вероятность пересечения (такое событие, где события A1 и A2 произошли одновременно) дает двойную сумму, и поэтому мы не получим равенства, а только не равенство. Мне, наверное, следует отметить, что если события разобщенные, другими словами, они не пересекаются, то мы действительно получаем равенство: одно объединение равно сумме двух вероятностей событий. Окей.

[слайд] Пример:
Cобытие A1 = {для любых x из {0,1}n, таких, что младшие два разряда lsb2(x)=11}
Cобытие A2 = {для любых x из {0,1}n, таких, что старшие два разряда msb2(x)=11}
Тогда вероятность суммы событий Pr[lsb2(x)=11 или msb2(x)=11] = $Pr[A_1 \cup A_2] \le \frac{1}{4} + \frac{1}{4} = \frac{1}{2}$
[слайд]

Далее. Теперь мы можем привести пример объединения событий. Итак, представьте, определим два события: одно событие заключается в том, что последние два бита станут равны 11 и другое события, где первые два бита станут равны 11. И мы спросим, какая вероятность того, что либо произойдет событие, где последние биты будут равны 11, либо событие, где первые биты будут равны 11. По сути, нам нужно получить вероятность объединения двух событий. Которая меньше, чем сумма вероятностей каждого. Т.к. каждое событие происходит с вероятностью 1/4 и, следовательно, их сумма равна 1/2. Вариант решения такой: вероятность объединения двух событий 1) меньше, чем сумма 1/4 + 1/4 (есть пересечение событий) или 2) равно этой сумме 1/2 (нет пересечения событий - точное значение вероятности). Окей. Переходим к случайной величине.

[слайд]
Определение. Случайная величина Х - это функция $X:U \longrightarrow V$
Пример: $X = \{0,1\}^n \longrightarrow {0,1,...,n}; X(y) =$ Считаем_число_единиц$(y), y \in [0,1]^n$
Вероятность точки v - $Pr[X=v] := Pr[X^{-1}(v)]$
Для $v \in \{0,1,...,n\}: Pr[X=v] = (n$ выбранных $v) / 2^n$
image01.jpg
[слайд]

Итак, случайная величина - это функция отображения нашего поля вероятностей U на другое поле, дадим ему имя V, и будем говорить, что случайная величина принимает числовые значения из этого множества V. Простой пример. Представьте, у нас есть стандартное поле вероятностей, состоящее из множества всех v-строк, и мы хотим определить случайную величину, которая подсчитывает число единиц в данной строке y длиной n. И функция Х(y) просто подсчитывает число единиц в бинарной строке y. Окей. Так что, эта переменная, эта случайная величина принимает значения от 0 до n. Теперь, по сути, любая случайная величина, как и любая функция, наподобие вышеописанной - порождает распределение на множестве V, на множестве, где она принимает значения. И распределение определяется очень легко. Вот так: вероятность точки v - это как раз вес всех точек, что, так случилось, попали в точку v. Окей, рассмотрим вероятность этого события. И мы говорим, что вероятность этого события в принципе - это вероятность этого события здесь. Окей, обозначим эту вероятность как X=v. Вероятность того, что Х=v, как мы сказали выше, равна вероятности этого события здесь. И, опять же, приведу короткий пример. Пусть у нас есть равномерное распределение, и мы смотрим на случайную величину, которую мы определили ранее, как случайная величина здесь. И мой вопрос к вам, чему равна вероятность Pr[X=v] для v $\in$ {0,1,…,n}? Простой расчет показывает, что вероятность равна (n выбранных v) поделенная на 2 в степени n, и причиной этого является количество всех строк с весом v. Так вот, сколько строк имеют значение v? Ответ - n строк со значением v. А почему мы делим на 2 в степени n? Потому что вес множества n строк со значением v подходит под равномерное распределение и поэтому мы делим на 2 в степени n. Поэтому, в этом примере, случайная величина, которая принимает значения, при его создании, из равномерного распределения от 0,1, до n - на самом деле принимает значения конкретных целых чисел. Окей. Теперь, когда мы понимаем, что такое случайные величины, мы можем поговорить о рандомизированных алгоритмах.

[слайд]
Детерминированный алгоритм: $y \leftarrow A(x)$
Рандомизированный алгоритм: $y \leftarrow A(x;r)$ выходное значение - это случайная величина
$y \stackrel{R}{\leftarrow} A(x)$
image02.jpg
[слайд]

Так, напомню вам, что детерминированный алгоритм - это по сути процесс, который имеет один вход и только один выход. Берем заданные входные данные и выдаем рассчитанный по алгоритму результат. Обозначим, что y является выходом алгоритма А с входными данными x.

А теперь дадим понятие рандомизированного алгоритма. Итак, рандомизированный алгоритм, как и прежде, принимает на входе, как вы знаете, заданное значение - нормальное. Но также на входе принимает и случайные строки. Обозначим случайную строку как R, равномерно распределенную от 0,1 до n, окей?

По сути, рандомизированный алгоритм принимает «по-настоящему» равномерно распределенную строку в качестве входных данных. Алгоритм является полностью детеминированным до тех пор, пока мы фиксируем R. Другими словами, при фиксированных x и R, есть только одно выводимое значение y. Но мы собираемся рассмотреть множество всех возможных R в соответствии с равномерным распределением. И как результат, имея на входе постоянную x, на выходе алгоритма на самом деле будем иметь случайную величину. Окей? Поэтому важно помнить, что рандомизированный алгоритм определяет случайную величину как возможное множество выходов алгоритма. Так что, используя один входной параметр x, вы видите, что на самом деле мы получаем целое распределение возможных выходов алгоритма (профессор на слайде отмечает одну точку x и множество точек выхода алгоритма A(x)). И я буду обозначать эту случайную величину вот такой забавной стрелкой с буквой R над ней. И стрелка с R над ней означает, что y – это случайная величина, выходной параметр алгоритма. y – результат алгоритма A с входными параметрами: значением x и с равномерно распределенной случайной строкой R. Итак, давайте рассмотрим небольшой пример. Так вот, у нас есть входные параметры. Теперь представьте алгоритм, который шифрует входное значение х случайным ключом k. Итак, мы получаем равномерно распределенную величину, которая представляет собой случайный шифротекст, созданный при шифровании х с помощью случайного ключа k, выбранного из поля ключей. Окей? Итак, мы рассмотрели пример случайной величины.

[слайд]
$r \stackrel{R}{\leftarrow} Omega$
[слайд]

Последнее, о чем я хочу упомянуть. На самом деле, я часто использую это обозначение. Это действительно очень удобное обозначение – стрелка и R над ней – выборка из определенного множества. Здесь *Omega* - конечное множество. Смысл обозначения - просто выбрать R, случайно и равновероятно из множества Omega. Если быть более точными, R является случайной величиной, равномерной случайной величиной из Omega. Мы часто будем выбирать ключи, как в приведенном примере. И мы будем говорить, что ключ k выбирается равновероятно из множества всех возможных ключей. Окей, так что это очень удобное обозначение.

И, наконец, я хотел бы рассказать о XOR функции. Но чтобы сделать это я просто вкратце должен упомянуть о понятии независимости. Если вы не знакомы с вероятностной независимостью, то почитайте немного об этом (ссылка на онлайн материал доступна).

[слайд]
Определение. События A и B независимы, если Pr[A и B] = Pr[A] * Pr[B]
[слайд]

Итак, у нас есть два события А и В. Мы будем говорить, что они независимы, т.е. будем говорить о их вероятности пересечения - вероятность того, что оба события произойдут. Если хотите, это тоже самое, что вероятность события А пересекается с вероятностью события B. Вероятность того, что оба события произойдут, равна произведению их индивидуальных вероятностей. Итак, определив независимые события, мы можем определить независимые случайные величины.

[слайд]
Определение. Случайные величины $X,Y:U \longrightarrow V$ независимы, если для всех $a,b \in V:$ Pr[X=a и Y=b] = Pr[X=a] * Pr[Y=b]
[слайд]

Если вы посмотрите на распределение величин на множестве V, где они берут свои значения, то заметим, что они независимы на этом множестве. Другими словами, события, X=a не зависит от события Y=b для всех возможных a и b. Итак, вот что значит для двух величин быть независимыми.

А теперь мы можем вывести своего рода теорему. Я надеюсь, она поможет объяснить что-то важное для всего курса обучения. Так как на протяжении всего курса, мы будем использовать функцию XOR много раз.

[слайд]
Теорема. А - случайная величина из $\{0,1\}^n$, X независимая равновероятная величина из $\{0,1\}^n$.
Тогда Y = А XOR X – это тоже равновероятная величина из $\{0,1\}^n$
[слайд]

Вспоминаем, операция XOR – это сложение бит по модулю два. И XOR на самом деле обладает важным свойством, которое объясняется в этой теореме. И эта теорема, фактически, является причиной, почему XOR функция так полезна в криптографии. Позвольте мне объяснить, о чем говорит теорема. Ну, предположим, что вы дали мне случайную величину A. Произвольно выбранную. Мне все равно, что это такое. Это случайная величина из множества {0,1}n. Поэтому она принимает значения, т.е. случайная величина А принимает значения из множества {0,1}n. А теперь, представьте себе, мы рассмотрим еще одну случайную величину X, которая, так случилось, равновероятна на множестве {0,1}n. И что еще более важно, X не зависит от A. Т.е. X и А являются независимыми величинами. Тогда посмотрев на A XOR X, на переменную Y, которая определяется как A XOR X, заметим, что Y на самом деле будет равновероятной. И магия здесь в том, что А может иметь любое распределение, но если вы XORите его с равномерно распределенной (равновероятной) случайной величиной, то вы получите равномерно распределенную (равновероятную) случайную величину. Т.е. мы как бы сглаживаем неровности А, и просто получаем ровную равновероятную случайную величину Y, всего лишь поXORив А с равновероятной случайной величиной.

Давайте получим это очень простое доказательство. Для доказательства достаточно взять просто один бит. Посмотрим. Итак, А может принимать значение: ноль или один. И их вероятности назовем P0 и P1. Произвольно выбранная величина X – это равновероятная случайная величина, она также принимает ноль и один. Но т.к. она равновероятная, то вероятность нуля и единицы равна 1/2.

Итак, теперь посмотрим на совместном распределении A и X. Итоговое распределение будет состоять из четырех возможных вариантов, а т.к. А и Х являются независимыми, мы просто перемножим их вероятности, чтобы выяснить вероятность каждого события. Так, например, вероятность события 0-0 просто будет P0 / 2. Для события 0-1 также будет P0 / 2. Для 1-0 будет Р1/2, а для 1-1 также Р1/2. Окей, все, что я сделал, я просто перемножил вероятности. Например, для 1-1 я умножил Р1 на 1/2 и получил Р1/2.

Теперь нам надо вычислить вероятность того, что Pr[Y=0]. Ну, есть два способа, когда A XOR X = 0. Один из них, когда A=0 и X=0, и наоборот, когда A=1 и X=1. И тогда

Pr[Y=0] = Pr[A=0 и X=0] + Pr[A=1 и X=1] = P0/2 + P1/2 = 1/2 * (P0 + P1)

Но поскольку P0 + P1 = 1, и

Pr[Y=0] = 1/2

Окей, вероятность, что Y=0 составляет 1/2. Вероятность того, что Y=1 также равна 1/2, и поэтому Y будет равновероятной случайной величиной, и это то, что мы хотели доказать. Окей, точно таким же образом это утверждение можно получить для XOR N-бит. Я надеюсь, что вы вернетесь к этой теореме, чтобы обдумать и понять, почему XOR является такой полезной функцией в криптографии.

Хорошо, как я уже сказал, это крэш-курс по дискретной вероятности. Если что-то из вышеприведенного материала было не ясно – не беда. Я собираюсь ссылаться на эти обозначения, но я всегда попытаюсь объяснить как мы их используем. Для тех, кто хочет узнать больше о дискретной вероятности, есть ресурс в Интернете, который я указал в предисловии к классу и веб-сайт, где можно немного больше почитать об этих понятиях. На этом крэш-курс закончен, а в следующих лекциях, мы начнем с реальных алгоритмов шифрования.

Пока не указано иное, содержимое этой страницы распространяется по лицензии Creative Commons Attribution-ShareAlike 3.0 License