Discrete probability (16 min)

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

Я хочу убедиться, что каждый из вас знаком с обозначениям,

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

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

Я дам ссылки на онлайн-ресурсы, где вы сможете немного про это почитать, и

И вы сможете освоить те основы

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

Вход в курс дела не должны вызвать особых трудностей. Итак,

давайте начнем с основ. Основной объект изучения - дискретное вероятностное пространство. Для нас

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

вероятностным пространством у нас будет множество из N бит потока. Это означает

множество всех строк, состоящих из 0 и 1 длины N. Вероятностное распределение, которое мы будем

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

(и которая принимает значения из интервала от 0 до 1). И единственное требование к этой функции -

чтобы сумма всех значений была равна 1. Ок? Это то, что по существу из себя представляет вероятностное

распределение. Мне бы хотелось привести два примера. Первый пример -

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

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

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

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

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

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

имеют нулевой вес. Т.к. наше вероятностное пространство конечно,

буквально только что думаете о функции p так же, как вектор. Так что думать о основном

Эта функция p мы буквально можно записать все это в значения. Это будет

вектор размерности 2 до N, справа, или два до n компонентов здесь, если наши

Вселенная – 01 к. н. И я просто хотел бы отметить, что когда я говорю, что два

распределения одинаковы, распределения над строками из 01 длины N, мы говорим,

что они равны, если их векторы, если вектор, которому соответствует одно распределение

в точности такое же, которому соотвествует другое

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

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

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

вероятностей всех элементов нашего множества. Ок? Это множество A мы назовем

событием, Ок? И в качестве примера, рассмотрим строки из N бит,

которые оканчиваются на 11. Ок? Другими словами мы рассматриваем строки длины N,

которые содержат только нули и единицы, и у этих строк

на конце 11, ок? Это и есть наше событие. Представим, что строки

распределены равномерно над множеством всех строк из 0 и 1 длины N. Как вы думаете

какова вероятность этого события? Каков суммарный вес всего события,

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

это вес равен 1/4, т.к. вероятность получить на конце две единицы

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

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

1/2 * 1/2 = 1/4. Ок. Следующее, что я

хотел бы отметить — неравенство Буля. Опять же это довольно стандартое неравенство в

дискретной вероятности. Предположим, что у нас есть два набора, два события, А1 и А2, такие что эти

два набора принадлежат нашему вероятностному пространству. Здесь этот круг обоначает все пространство. И

мы спрашиваем, какова вероятность того, что произойдет либо событие 1A, либо 2A?

Другими словами, мы рассматриваем объединение этих событий и вы можете легко убедиться,

что на самом деле вероятность объединения меньше суммы

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

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

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

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

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

их пересечение пусто, то мы получаем, равенство. Другими словами,

вероятность объединения равняется сумме вероятностей каждой из частей. Ок. Пока все хорошо. И

затем давайте рассмотрим пример приложения [неразборчиво]. Представим, что

у нас есть два события, одно событие, что последние два бита равны 11 и

другое - что первые два бита равны 11. Спрашивается,

какова вероятность того, что последние два бита или первые два бита

равны 11. Это на самом деле эту вероятность несложно вычислить

точно, но мы просто хотим использовать неравенство Буля, чтобы получить простое ограничение на эту величину, чтобы

вы почувствовали, что из себя представляет вероятность объединения

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

Каждое событие происходит с вероятностью 1/4 и поэтому требует сбалансированного

Установите, что вероятность союза составляет меньше половины. Ладно как я сказал, вы можете

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

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

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

Помните, что вы знаете, то же качество это то, что будет вид intuitvally

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

в основном, зависит от нашего вероятностное пространство на некоторое пространство

Некоторые другие указанные v и мы скажу, что случайная величина принимает значение в Сет в

Так вот простой пример вы себе снова у нас есть наши стандартные пространства

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

Подсчитывает количество в заданной строки настолько здесь y представляет собой строку длиной n.

И поэтому X Y будет просто подсчитать количество в строке ю. хорошо. Так что этот

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

любой случайной величины, поэтому любые функции, как это, вызывает распространение на Сет В

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

легко. По существу, вероятность точки V-это только вес всех

очков в вас которые сопоставить V. точка хорошо, так что мы смотрим на

вероятность этого события. И мы говорим, что вероятность события в основном

— вероятность этого события.
Хорошо, так что бы нотацию для этого

в основном, является вероятность того, что x равен вероятности против того, что X =-V

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

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

равномерное распределение и мы смотрим на случайная величина, которую мы определили

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

что x равен V [неразборчиво] и ноль в. н. Таким образом это простое вычисление чтобы показать

что это n выбрать v разделена в 2-n, и причина — это размер, вам

знаете, размер прообраз v-в основном, ну, все строки веса

v. хорошо сколько строк есть, которые v1's в них? Это в основном n выбрать

v строк и мы поделить на два до n потому что вес набора размера n

выбираем v под равномерное распределение n выбрать v разделена в 2-n. Таким образом,

Вот пример, случайная величина, которая принимает, которая создается, форму

распределение, более чем 01-n, но на самом деле принимает значения, за целые числа.

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

о рандомизированные алгоритмы. Таким образом lemme напоминаем, детерминированного алгоритма

в основном имеет один вход и имеет только один выход. Учитывая вклад

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

нотация здесь сказать что y вывода алгоритма a на ввод X. хорошо, так что теперь

Давайте обобщать это рандомизированные алгоритмы. Так что рандомизированных алгоритм,

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

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

N, хорошо? Так что по сути, рандомизированных алгоритм принимает, кроме того, поистине

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

года. Как только мы исправить р. Алгоритм полностью детерминировано. Другими словами,

даже x и R, есть только одна Y, которое выведет алгоритм. Но, мы будем

Посмотрите на набор всех возможных r под равномерное распределение. И в результате

учитывая вклад X, вывода algorith фактически случайной величины.

Ладно? Поэтому важно помнить, что рандомизированных алгоритм определяет случайное

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

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

алгоритм. И я хочу обозначить это случайная величина с этой смешной стрелки

нотация. Так что я скажу, стрелка, и над ним, R означает, что y является результат, является

случайная величина определена. Запустив алгоритм a на вход x с единой

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

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

входные, x, под случайный ключ шифрует k. Итак здесь у нас есть наша форма

переменная, которая в основном является случайным зашифрованный текст, созданный путем шифрования x

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

переменная. И последнее, что я хочу упомянуть, в самом деле, я часто использую эту

нотация. Это на самом деле очень удобно нотации, чтобы сказать что r

есть стрелки и r выше его из определенного набора. Это просто конечного Омега

Задайте. И это просто означает, просто выберите r равномерно случайно над Омега. Если вы

хотите быть точным, R — это случайная величина, то единой случайная величина над Омега.

Но действительно, все это означает [неразборчиво] равномерно из набора. Мы часто выбирают

ключей, как это. Мы скажем, K равномерно выбирается из множества всех ключевых

возможных ключей. Ладно, так что это очень удобно нотации. И наконец я хочу

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

нужно упомянуть о концепции независимости. Если вы не знакомы с

вероятностные независимость. Опять же, пожалуйста.
Прочитайте немного о нем. В

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

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

у нас есть два события a и B. Мы говорим, что они являются независимыми и в основном

вероятность их пересечение. Так что вероятность того, что оба они происходят. Это

Это, если вам нравится, это то же самое, как вероятность пересечение б. потому что оба

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

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

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

Если вы посмотрите на распределение, переменные определяют на Сет В, где они

Возьмите их значения, затем они независимыми на этом наборе. Другими словами,

событие, X = A не зависит от события Y = B для всех возможных a и B.

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

можно либо государства этой теоремы. Я надеюсь, что поможет объяснить что-то важное

в классе. Так в этом классе во всем мы будем использовать XOR функции

совсем немного. Помните XOR битов в основном добавление этих битов

по модулю два. Поэтому мы будем использовать XOR функцию совсем немного. И XOR функции

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

Это такой полезной, эта теорема это причина почему функция XOR так

полезные в криптографии. Поэтому позвольте мне объяснить, что теорема говорит. Теорема говорит:

также Предположим, что вы даете мне случайная величина а. Это является произвольным. Мне не волнует то, что он

это. Это может быть выбран [неразборчиво], но это случайная величина наборами 01 для

н. Поэтому он принимает значения, поэтому случайная величина a принимает значения в наборе 01 для

н. А теперь представьте, рассмотрим еще один случайная величина. X, что происходит с

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

Переменная а. Так x и являются независимой переменной. Тогда на самом деле вы посмотрите на x или

x, то эта переменная y определяется как ax или x-это на самом деле единообразной. Поэтому вид

магические свойства здесь это не имеет значения то, что, может быть все, что

распределение, вам нравится, если вы ex провозглашаются с единой случайная величина вы собираешься

получите единый случайной величины. Так что мы рода сгладить нарушений в и мы

просто получить чистый единообразных случайная величина, ex orating его с единой случайных

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

оказаться для любого закрыть один, иными словами Если у нас только один бит. Давайте посмотрим. Таким образом A —

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

их P0 и P1. Могут быть произвольно, [неразборчиво] выбранная. X — это униформы

случайная величина, поэтому в нем ноль, одно значений. А потому, что он является единой. Он имеет

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

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

пар и потому, что n и x независимых кандидатов, мы просто умножить их

вероятностей и мы можем выяснить, вероятности каждой точки в пространстве.

Так, например, вероятность того, что мы ноль, ноль просто собирается быть p ноль

свыше двух. Затем нулевому также будет быть p нулевой более двух. Один ноль собирается

быть p один за два. И один, один, woops, один из них, один будет p один за два как

хорошо. Ладно, я сделал всё я просто умножить. Например, один один, я

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

Какова вероятность того, что x над равен нулю, что этот y равен

ноль. Ну, существует два способа, x и x может быть нулевым. Один — если оба

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

вероятность того что они 're x более чем ноль – в основном, вы знаете, вероятность того, что

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

что является p1 за два. В настоящее время и вот, это в основном полтора раза PO + P1. Но

потому что P0 и P1 исходят от [неразборчиво] распределения, P0 + P1 равен одному и поэтому

Это половина. Итак какова вероятность того, что Y = 0 — половина? В

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

Мы хотели, чтобы доказать. Ладно так же, вы можете очень многое утверждают, точно так же

путь. [неразборчиво] для n бит и я надеюсь, мы рода продолжать использовать [неразборчиво]

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

что именно поэтому XR является такая полезная функция в криптографии. Ладно так как я

сказал: это очень быстро ускоренный курс.
Если части это было не ясно, она не

конец света. Я хочу быть Касаясь этой нотации, но я буду стараться

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

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

классу и веб-сайта. И вы можете просто прочитать немного больше об этих

концепции. Но это в основном конце краш курс и этот великий

вероятность. А затем, в следующем сегменте, мы начнем с фактическими

алгоритмы шифрования.