Discrete probability (crash course, cont.) (14 min)

Дискретная вероятность(ускоренный курс, продолж.) (14 мин.)

В этой части мы рассмотрим еще несколько видов дискретных вероятностей.

Также я хочу напомнить всем, что если вы хотите получить больше информации по данной теме,

то вы можете найти ее в Вики-книге (ссылка указана выше). Для начала давайте

сделаем быстрое резюме того где мы находимся. Мы говорили что дискретная вероятность всегда определяется

через дискретное множество, которое мы обозначаем как U. Обычно для нас,

U будет множеством всех N-битных двоичных строк, которые мы обозначим как U={0;1}^n.

Распределение вероятностей P по данному множеству U является функцией,

которая распределяет на каждый элемент в этом множестве вес в интервале от нуля

до единицы, так что сумма всех весов всех элементов множества будет равна единице.

Теперь мы должны вспомнить о подмножестве множества U, называемого событием.

Мы говорили что вероятность события является суммой всех весов

всех элементов события, и также мы говорили что вероятность события есть вещественное

число в интервале от нуля до единицы. И я хотел бы напомнить всем, что

вероятность всего множества U равна единице, так как сумма всех его весов

равна еднице. Далее мы определили что такое случайная переменная. Формально

случайной переменнной является функция от множества по некоторым его наборам данных.

Но я хочу чтобы вы запомнили что случайная переменная принимает значения в некотором

множестве v. И на самом деле слуайная величина определяется распределением на этом множестве v.

Следующая концепция которую мы должны рассмотреть называется "независимость". И я

собираюсь очень кратко рассказать о ней. Если вы хотите узнать больше, пожалуйста посмотрите

ссылку указанную на первом слайде. Итак, мы говорим что два события А и В являются

независимыми друг от друга в том случае если вы знаете что событие А произошло, но это вам ни говорит

ничего о том произошло событие В или нет. Официально определяя "независимость"

мы говорим что вероятность и А и В, а точнее того что оба события произошли,

на самом деле равна произведению вероятности события А на вероятность события В.

Таким образом произведение вероятностей, в некотором смысле, отображает их сочетание, и

отражает тот факт что эти события являются независимыми. И, как я и говорил,

если вы хотите узнать больше о них, пожалуйста, посмотрите дополнительный материал.

То же самое можно сказать и про случайные переменные. Итак, предположим, что у нас есть две

случайных переменных Х и У. Они принимают значения в неком множестве V. Тогда мы говорим, что это случайные

переменные являются независимыми, если вероятность того что Х = а, и У = b равна

результату умножения этих двух вероятностей. В основном это означает, что даже если вы знаете,

что Х = а, то это ничего не говорит вам о значении переменной У. Хорошо, то,

что означает это умножение, и опять же, это свойство должно сохраняться для всех А и В в

области значений этих случайных переменных. Итак, еще раз, чтобы вы запомнили, если

вы не видели это раньше, очень короткий пример. Допустим, что мы смотрим на множество

двубитных строк: итк 0, 0, 0, 1, 1, 0, 1, 1. И пускай ми выбираем

случайно из этого множества. Хорошо, итак мы выбираем случайно один из четырех элементов

с равной вероятностью. Теперь давайте определим две случайных переменных. Х будет представлять

младший бит, который был згенерирован, и у будет старшим сгенерированым битом.

Итак, я утверждаю, что эти случайные переменные, Х и У, являются независимыми друг от

друга. И способ увидеть это интуитивно, это понять, что выбор r

равномерен для этих четырех элементов, и в принципе очень похож на подбрасывание монетки.

Подбросим монетку два раза. Первый бит отвечает первому броску монетки, а

второй бит - второму броску. И, конечно же,

существет четыре возможных варианта. Все четыре результата являются не менее вероятными. Воот почему

ми получаем равномерное распределение двубитных строк. Теперь, что касается наших переменных Х и У,

они независимы. На самом деле, если я скажу вам результаты первого броска, а именно скажу вам

значение младшего бита R, тоесть если я расскажу, как упала первая монета, ну понимаете, упала ли она орлом

или решкой. Это ничего не скаже вам о результате

второго броска. Вот почему интуитивно, вы, воозможно можно было бы ожидать что эти случайные

переменные независимы друг от друга. Но формально, мы должны были бы

доказать, что, для всех 0 1 пар, вероятностть х = 0 и у = 0, ч = 1 и у = 1, и

так далее, эти вероятности перемножаются. Давайте сделаем это для одной из наших пар. Итак,

давайте посмотрим на вероятность того, что х = 0 и у = 0. Ну вы видите,

что вероятностть того, что х = 0 и у = 0, точнее

вероятность того, что r = 00... и какова вероятность того что

r = 00? Ну, при равномерном распределении. она на самом деле равна

одной четвертой. Это для одного элементя из множества, она равна одной четвертой в этом случае.

И вот, на самом деле, эта вероятность - вероятность с умножением, так как,

опять же, вероятность того. что х = 0 (вероятность того что младший

бит R = 0) эта вероятность = одной второй, так как

существет только два таких элемента у которых младший бит равен нулю (10, 00)

Два из чтырех элементов дают вам вероятность - одна вторая, и аналогично для

вероятности, что У = 0, она так же равна одной второй. Итак, по сути вероятности

перемножены. Хорошо, так суть этой независимости (умножение вероятностей) и есть причина, по которой я

хотел показать ее вам, так как мы собираемся рассматривать важную особенность XOR, которую

мы будем использовать снова и снова. Итак, перед тем как мы поговорим о XOR, позвольте мне сделать очень

короткий обзор того, что же такое XOR. Итак, обычно, XOR двух бит означает сумирование

этих бит, по модуляру два (mod 2). Итак, просто для того, чтобы убедиться, чо все понимают это

одинаково, если у нас есть два бита, итак, 0, 0, 0, 1, 1, 0, 1, 1. Их XOR или истинная таблица

XOR"ов является просто сумированием по модуляру 2 (mod 2). Как вы можете увидеть 1+1 равно двум,

модулярным двум, что равняется нулю. Итого, это истинная таблица для XOR"ов, и

я всегда буду обозначать XOR как кружочек со знаком + внутри него. И тогда, когда я

захочу использовать XOR для биовых строк я буду использовать операцию модулярного суммирования по 2,

поразрядного. Итак, например, XOR этих двух строк равен 1 1 0, и я думаю

я дам вам возможность заполнить оставшиеся места для XOR"ов, просто чтобы убедиться что ми все понимаем это

одинаково. Итак, конечно, получается 1, 1, 0, 1. Итак, мы собираемся

делать много операций XOR в этом класе. На самом деле, существует классическая шутка, что

только думающие криптографы знают, как это сделать, просто проXOR"ить вещи друг с другом. Но я хочу

объяснить вам, почему мы видим XOR так часто в криптографии. Дело в том, что XOR

имеет очень важную особенность, и эта особенность заключается в следующем. Допустим, что

случайная переменная У случайно распределена на {0,1}^n. Так что мы не знаем ничего

про распределение У. Но теперь допустим, что мы имеем независимую случайную переменную,

которая, так получилось, является равномерно распределенной также по {0, 1}^n. Итак, это

очень важно, что Х является равномерной. N не зависит от У. Так что теперь, давайте, определим

случайную переменную, которая является результатом XOR между Х и У. Далее я утверждаю, что не важно с чего

начинается распределение У, это Z всегда будет равномерной, случайной

переменной. Итак, другими словами, если я возьму любое конкретное распределение и я

проXOR"ю его с независимой равномерно-случайно величиной, то что я получу в конце будет равномерно-

случайной переменной. Хорошо, и это опять является одной из ключевых особенностей, что делает XOR

очень полезной для шифрования. ИТак, данный факт на самом деле очень просто доказать,

Давайте просто пойдем вперед и сделаем это, давайте просто докажем это для одного бита, тоесть для n = 1.

Итак метод которым мы сделаем это - мы будем просто вписывать распределение вероятностей

для разных случайных величин. Так что давайте посмотрим, случайная переменная У. Итак,

случайная переменная может быть равна либо 0, либо 1. И давайте предположим, что Р0 это вероятность того,

что У = 0, и Р1 вероятность того, что перемення = 1. Хорошо, итак

это одна из наших таблиц. Похожим образом мы построим таблицу для переменной х.

Ну, переменная Х является намного более простой. Это единственная случайная переменная, так что

вероятность того, что она = 0, на самом деле равна 1/2. Вероятность того, что она = 1

также является одна вторая. Теперь давайте выпишем вероятность для объединения

распределений в... другими словами, давайте посмотрим какова вероятнность для разных и

общих значений У и Х. Другими словами, насколько вероятно, что У = 0,

и при этом Х =0, У =0 и Х = 1, У = 1 и Х = 0, и 1 1. Итак,

что мы делаем, так это просто, так как мы предполагаем что переменные являются независимыми, все что

мы должны сделать это перемножить вероятности. Таким образом вероятность того, что У = 0

является Р0, вероятность того, что Х = 0 - одна вторая. Так

соседство, при которм мы получаем 0 0 равно Р0 / 2. Аналогичным образом для пары 1 0

мы полчим Р0 деленное на два, для 1 0 мы получим Р1 деленное на два, и для пары 1 1

опять таки, вероятность того что у = 1 и х = 1, хорошо, это Р1 умноженное на

вероятность того, что х = 1 (которая равна 1/2), так что она равна Р1 поделить на два. Хорошо? Итак, эти

четыре.. эти вероятности для разных вариантов Х и У. Так что теперь давайте

проанализируем, какова вероятность того, что Z = 0? Ну, вероятность что

Z = 0 на самом деле такая же, как вероятность, что, давайте напишем это таким образом,

ХY = 00, или XY = 11. Это два возможных случая при которых Z = 0.

Так как Z это XOR (Х и У). Итак, на пересечении этих событий, так,

это выражение можно просто записать как сумму двух выражений, приведенных выше. Итак,

в общем, есть вероятность что ху = 00, а также вероятность того, что ху =

= 11. Так что теперь мы можем просто искать эти вероятности в нашей таблице. Так что

вероятность что ХУ = 00 это Р0/2 и

вероятность что ХУ = 11 это Р1/2. Итак, мы получаем Р0/2

+ Р1/2, но что мы делаем с ними, что мы знаем про Р0 и Р1? Ну,

это распределение вероятностей. Таким образом сумма Р0 и Р1 должна быть равна единице, итак,

эта дробь, тут, должна = одной второй. Р0 + Р1 = 1. Так что, итак, сумма этих

двух вероятностей будет равняться одной второй. В принципе, мы доказали что вероятность того,

что Z = 0 равна 1/2, таким образом вероятность того, что Z = 1

также равна 1/2. Итак Z это равномерная случайная переменная. Эта простая

теорема является главной причиной частого использования XOR в криптографии. Последнее, что я

хотел бы вам показать вдискретных вероятностях называется "Парадокс дней рождений" и

я собираюсь сделать это очень быстро, так как ми предполагаем вернуться к этому позже и поговорить

об этом более детально. Итак, парадокс дней рождений базируется на следующем:

Пускай я выбираю N случайных переменных в нашей вселенной U. Хорошо, и просто так произошло,

что эти переменные являются независимыми друг от друга. На самом деле они не должны

быть одинаковыми. Все что мы должны предположить, так это то что они распределены таким же образом.

Наиболее важная особенность, все же, та, что они независят друг от друга. Итак

теорема говорит, что если вы возьмете приблизительно квдратный корень из размера U елементов,

ми игнорируем 1,2 написанные здесь, на самом деле это не так уж и важно. Но если вы возьмете

квадратный корень от U елементов, то существует хороший шанс, что вы получите

два одинаковых элемента. Другими словами, если ваш образец примерно равен

нескольким квадратным корням, то очень вероятно, что двое элементов в образце будут

равными друг другу. И, кстати, я должен отметить, что эта перевернутая Е

просто означает "Существует". Тоесть существет такие разные I и J, при которых Ri равно

Rj. Итак, вот конкретный пример. Мы на самом деле увидим много, много примеров.

Допустим. что наша вселенная состоит из всех строк длинной в

128 бит. Так что U имеет гигантский размер, фактически он равен 2 в степени

128. Это очень, очень боольшой набор, но это так происходит, что если ваша выборка будет

размером приблизительно 2 в 64 степени, что приблизительно корень квадратный из U

то, очень вероятно, что двое из ваших элементов фактически будут одни и тем самым элементом.

Так почему это называется парадоксом? Ну, традиционно это описано с точки зрения

даты рождения людей. Так, можна подумать, что каждый из этих элементов являет собой

чье-то день рождение, и вопрос состоит в следующем: сколько людей должно собраться рядом,

чтобы как минимум у двоих из них день рождение было в один день? Итак, сделва простые подсчеты

вы можете увидеть, что 365 дней в году, так что вам необходимо около 1,2

умножить на корень квадратный из 365 людей, для вероятности того, что двое из них имеют

день рождения в один и тот же день, была больше 1/2. Это если не ошибаюсь, около 24, а это означает

что, если 24 случайных человека собираются вместе в одной комнате, то очень вероятно, что у двоих из них

фактически день рождения будет в один день. Вот почему эта теорема называется парадоксом, потому как 24

вроде как меньше, чем вы ожидаете. Что интересно, человеческие

дни рождения на самом деле не являются равномерно распределенными по всем 365 дням в году. Существует

на самом деле, предвзятое отношение к декабрю. Но, я думаю, это не относится к данному

обсуждению. Последнее, что я хотел бы сделать это просто показать вам парадокс дня

рождения немного более конкретно. ИТак, допустим. что вселенная состоит из около миллиона

оразцов, тогда вы можете увидеть, что когда мы берем около 1200 образцов, вероятность того

что мы получаем образцом тот же номер, один и тот же элемент два раза, состовляет приблизительно 1/2, но

вероятность взять один и тот же элемент два раза сходится очень быстро

к единице. Вы можете увидеть, что если мы возьмем 2200 элементов, то вероятность

что два из них одинаковы, уже состовляет 90%, и вы знаете, при 3000 элементов

она в основном = 1. Итак, это преобразование очень быстро приближается к единице, как только

оно выхоит за рамки розмера квадратного корня из U. Поэтому мы возвратимся назад

и будет изучать парадокс дней рождений более подробно позже, но сейчас я просто хотел

чтобы вы знали, что это такое. Так что это конец данного блока, и в

следующем блоке мы начнем ч нашего первого примера системы шифрования.