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

Дискретні ймовірності (прискорений курс, продовж.) (14 хв.)

У цьому сегменті ми будемо продовжувати розглядати ще кілька інструментів дискретних

ймовірністей, і я хочу нагадати всім, що якщо ви хочете прочитати більше про це,

Існує більше інформації у wiki книги статті, зв'язаній тут. Тому по-перше

Давайтешвидко подивимость де ми знаходимося. Ми говорили, що дискретні ймовірності

завжди визначено скінченною множиною(набором), який ми збираємося позначати як U і, як правило, для

нас, U буде набором всіх n-біт двійкових рядків, які ми позначимо як

{0,1}^n. Отже, розподіл ймовірності Р у цьому всесвіті U являє собою

функцію, яка призначає кожному елементу у Всесвіті вагу в інтервалі від нуля

до одиниці, таку, що якщо ми просумуємо вагу всіх цих елементів, сума, в основному сума буде наближатися

до одиниці. Також ми говорили, що підмножина Всесвіту називається подією, і

ми сказали, що ймовірність події є, в основному, сумою всіх ваг

всіх елементів події і ми сказали, що ймовірністю події є деякі реальні

числа в інтервалі від 0 до 1, І я хотів би нагадати всім - в основному

Імовірність всього Всесвіту = 1, сума

всіх ваг наближається до одиниці. Потім ми визначимо, що випадкова змінна є формально,

випадкова змінна є функцією від Всесвіту з деякими іншими множинами, але

те, що я хочу щоб ви запам'ятали, це те що випадкова змінна приймає значення у деякій

множині V, й по суті, випадкова змінна визначає розподіл на цій множині V.

Наступне поняття, що нам неоюхідно називається "Незалежність", І я дуже коротко

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

подивіться на статтю в wiki-книги. Але по суті ми сказати, що дві події, A і B є

незалежними одна від одної тоді, коли якщо ви знаєте, що подія А відбувається, це нічого не говорить

вам про те відбувається подія B чи ні. Формально, шлях яким ми визначаємо

незалежність - це ми говоримо, що ймовірність А і B, а саме, що обидві

події сталися, якщо фактично = ймовірность події A * ймовірність

події В. Отже множення, в деякому розумінні, факт того що ймовірності перемножено одна з

одною, підкреслює той факт, що ці події незалежні, і як я вже сказав, якщо

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

Тепер те ж саме можна сказати і про випадкові змінні. Так, припустимо, що у нас є дві випадкових

змінні x та y. Вони приймають значення у деякій множині v. Тоді ми кажемо, що ці випадкові

змінні є незалежними якщо ймовірність що x = а, та y = b дорівнює

результату множення цих двох ймовірностей.
В основному це означає, навіть якщо ви

знаете, що x = а, це не говорить вам нічого про значення у. Добре, те,

що означає це множення, і знову ця властивість повинна зберігатися для всіх А та В в

просторі значеннь цих випадкових змінних. Отже, ще раз, щоб ви запам'ятали, якщо

Ви бачили це раніше, дуже короткий приклад. Припустимо, що ми дивимося на множину

двохбітних рядків: так, нуль, нуль, нуль, один, один нуль і, один, один, І нехай, ми

обираємо випадково, з цієї множини. Добре, отже ми випадково обраємо один з цих чотирьох елементів

з рівною ймовірністю. Тепер давайте визначимо дві випадкові змінні. X буде являти собою

найменш значимий біт, що був згенерований, і y буде значущім бітом.

Ітак, я стверджую, що ці випадкові змінні, x та y, є незалежним одна від

одної. І спосіб побачити це інтуїтивно, це зрозуміти, що вибір r

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

Підкинемо монету двічі. Перший біт відповідає за підсумками першого

кидка і другий біт відповідає підсумкам другого кидка. І, звичайно

Існують чотири можливі результати. Всі чотири результати є не менш імовірними. Ось чому

Ми отримуємо рівномірний розподіл двобітних рядків. Тепер що до наших змінних Х та У,

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

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

або решкою. Це нічого не говорить вам про результат

другого кидка. Ось чому інтуїтивно, ви, можливо, можна було б очікувати що ці випадкові

змінні незалежні одна від одної. Але формально, ми повинні були б

довести, що, для всіх 01 пар, ймовірність, x = 0 і y = 0, x = 1, y = 1, і

так далі, ці ймовірності перемножуються. Давайте зробимо це для однієї з цих пар. Отже,

Давайте подивимося на ймовірність того, що x = 0, і y = 0. Ну, ви бачите

що ймовірність того, що x дорівнює нулю, і y дорівнює нулю в основному

ймовірність, що r = 00... І яка ймовірніть того, що

r = 00? Ну, на рівномірному розподілі, вона насправді рівна

одній четвертій. Це для одного елементу з множини, яка рівна одній четвертій, в цьому випадку.

І ось так, насправді, ця ймовірність - ймовірність з множеннім, оскільки,

знову, ймовірність того, що x дорівнює нулю (ймовірність того, що молодший значущий

біт R дорівнює нулю) Ця ймовірність є рівною одній другій, так як

існує лише два таких елементи, у яких молодший значущий біт рівен нулю (10, 00)

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

ймовірність, що У дорівнює нулю, вона також рівна одній другій, отже по суті ймовірності

перемножені. Гаразд, так ось, ця суть незалежності (множення ймовірностей) і є причиною, по якій я хотів

показати її вам, тому що ми збираємося розглядати важливу властивість XOR, яку

Ми будемо використовувати знову і знову. Отже, перш ніж ми говоримо про XOR, дозвольте мені зробити дуже

короткий огляд того, що таке XOR. Так, звичайно, XOR двох бітів означає додавання

цих бітів, модульно по двійці. Отже, просто для того, щоб переконатися, що всі розуміють

однаково, якщо у нас є два біти, так 0, 0, 0, 1, 1, 0, 1 , 1. Їх XOR або істинна таблиця

XOR'ів в основному є просто додаванням по модулю два (mod 2). Як ви можете бачити, 1 + 1 = двум,

модулярним двум, що рівно нулю. Отож, це справжня таблиця для XOR'ів, і

Я завжди буду позначити XOR, як коло з знаком + у середині, І тоді, коли я

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

порозрядного. Так, наприклад, було б XOR цих двох рядків буде - 110, і я думаю

Я дам вам заповнити залишок на XORs, просто щоб переконатися, що ми всі однаково це

розуміємо. Так, звичайно, виходить один, один, нуль, один. Отож, ми збираємося

робити багато операцій XOR в цьому класі. Справді, існує класичної жарт, що

тільки думаючі криптографи знають, як це зробити, просто зXOR'ьте речі разом. Але я хочу

пояснити вам, чому ми бачимо XOR так часто в криптографії. В основному, XOR

має дуже важливу властивість, і властивість полягає в наступному. Припустимо, що

випадкова змінна У довільно розподілена від 01 до n. Так що ми не знаємо нічого

про розподіл У. Але тепер, припустимо, що ми маємо незалежну випадкову

змінну, яка, так сталося, є рівномірно розподіленою також від 01 до n. Так, це

дуже важливо, що x є рівномірна. N незалежних від y. Так що тепер, давайте визначимо

випадкову змінну, яка є результатом XOR'у Х та Y. Далі я стверджую, що не важливо з чого

починається розподіл У, це z завжди буде рівномірною, випадковою

змінною. Так, іншими словами, якщо я візьму довільний навмисний розподіл і я

проXOR'ю його з незалежною рівномірно-випадковою змінною, те що я отримаю в кінці буде рівномірно-

випадковою змінною. Гаразд, і це знову є однією з ключових властивостей, що робить XOR

дуже корисною для шифрування. Так що, цей факт насправді дуже просто довести,

Давайте просто йти вперед і робити це, давайте просто доведемо це для одного біту, тобто для n = 1. Добре

так що шлях, яким ми зробимо це - ми будемо просто виписувати розподіли ймовірностей

для різних випадкових величин. Так що давайте подивимося, випадкова змінна y. Отже,

випадкова змінна може бути рівна або нулю або одиниці.
І давайте припустимо, що P0 це ймовірність

що У = 0 і P1, є ймовірність того, що змінна = 1. Гаразд, отже

Це одна з наших таблиць. Аналогічним чином, ми будемо мати таблицю для змінної x.

Ну, змінна x є набагато простішою. Це єдина випадкова змінна. Так що

ймовірність того, що вона = 0, є насправді одна друга. Ймовірність того, що вона = 1

також є саме одна друга. Тепер давайте випишемо ймовірності для об'єднання

розподілів в, іншими словами, давайте подивимося яка імовірність, для на

різних, спільні значення y та x. Іншими словами, наскільки вірогідно, що y = 0,

і x = 0. (Y=0, і x = 1). Y = 1 і x = 0, та 1, 1. Отже,

що ми робимо це, просто, тому що ми припускаємо, що змінні є незалежними, все, що

ми повинні зробити це перемножити ймовірності. Таким чином ймовірність що y

дорівнює нулю є Р0. Імовірність того, що x дорівнює нулю є одна друга. Так

сусідство, при якому ми отримаємо 0 0 рівно Р0поділити на два. Аналогічним чином для пари 1 0

ми отримаємо Р0 поділити на два, для 1 0 ми отримаємо P1 на два, та для 1 1,

знову ж таки, ймовірність того що y = 1, і x =1, добре, це P1 помножити на

Імовірність того, що x = 1, яка рівна одній другій, отже це рівно P1 поділеному на два. Добре? Так, ці

чотири, це ймовірності для різних варіантів Х та У. Так що тепер давайте

Проаналізуємо, яка ймовірність того, що z дорівнює нулю? Ну, ймовірність що

z = 0, насправді така сама, як ймовірність що, давайте напишемо це таким чином,

XY = 00. Або xy = 11. Це два можливих випадки при яких z = 0.

Так як Z це XOR між X та Y. Тепер, неперетинні ці події, так, це

вираз можна просто записати як сума двох виразів, наведені вище. Так

в основному, є ймовірність, що ХУ = 00, а також ймовірність що ХУ

= до одинадцяти. Так що тепер ми може просто шукати ці ймовірності в нашій таблиці. Так що

ймовірність що ХУ дорівнює 00 є просто Р0 / 2, та

імовірність що ХУ дорівнює 1 1 просто Р1 навпіл. Отже, ми отримуємо P0/2 +

+ P1/2, але що ми знаємо, що ми знаємо про P0 та P1? Ну,

це розподіл імовірностей. Таким чином, P0 + P1 повинні дорівнювати одиниці, і отже,

цей дріб, тут, повинні = одній другій. P0 + P1 = 1. Так що, отже, сума цих

двух ймовірностей буде рівна одній другій. У принципі, ми довели, що ймовірність того,

що Z = 0 є 1/2, таким чином ймовірність того, що Z = 1

також рівна одній другій. Отжє Z це рівномірна випадкова змінна. Так ця проста

теорема є головною причиною, чому ХOR так часто використовується у картографії. Останнє, що я

хочу вам показати з дискретної ймовірности це те, що називається "парадокс днів народження" та

Я збираюся зробити це дуже швидко, тому що ми маємо намір повернутися до цього пізніше і говорити

про це в більш докладно. Так, парадокс днів народжень складається з наступного:

Припустимо, що я вибираю N випадкових змінних у нашому всесвіті U. Добре, і просто так сталося

що ці змінні є незалежними одна від одної. Вони насправді не повинні

бути однаковими. Все, що ми повинні припустити це, що вони розподілені таким же чином.

Найбільш важлива властивість, однак, що вони незалежні одна від одної. Так що

Теорема говорить, що якщо ви вибираєте приблизно квадратний корінь з розміру в U елементів,

Ми ігноруємо 1,2 написані тут, це насправді не такважливо. Але якщо ви обираєте

квадратний корінь з розміру U елементів, то в основному існує хороший шанс, що

є два однакових елемента. Іншими словами, якщо ваш зразок приблизно рівен

кільком квадраним кореням, то цілком можливо, що двоє з ваших зразків будуть

дорівнювати один одному. І до речі, я повинен відзначити, що оця перевенута E

просто означає "існує". Тобто існують такі різні I та J, при яких Ri є рівною

Rj. Отже, ось конкретний приклад.
Ми насправді побачимо багато, багато разів.

Припустимо, що наш всесвіт складається з усіх рядків довжиною в

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

128. Це дуже, дуже великий набір, але це так відбувається, якщо ваш зразок буде

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

тоді, дуже ймовірно, що два з ваших зразка фактично будуть одним і тим самим зразком (єквівалентним).

Так чому це називається парадокс? Ну, традиційно описано з точки зору

дати народження людей. Так, можна подумати, що кожен з цих зразків являє собою

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

щоб було принаймні двоє людей, з однаковим днем народження? Ітак, зробив прості підрахунки

ви можете бачити, що є 365 днів у році, так що вам буде потрібно близько 1,2

помножити на квадратний корінь з 365 людей, для ймовірність того, що двоє з них мають

день народження в один і той самий днь, була більше 1/2. Це якщо не помиляюся, близько 24, а це означає

що, якщо 24 випадкових людей збираються разом в кімнаті, то дуже ймовірно, що двоє з них

фактично будуть мати день народження в той самий день. Ось чому вона називається парадокс, тому що 24

нібито це менше значення, ніж ви очікуєте. Що цікаво, людські

дні народження не є насправді рівномірно розподіленими через усі 365 днів на рік. Існує насправді

упереджене ставлення до грудня. >> Але, я думаю, це не, це не відноситься до данного

обговорення. >> Останнє, що я хотів зробити це просто показати вам парадокс дня

народження трохи більш конкретно. Отже, припустимо, що всесвіт складається з близько мільйона

зразків, тоді ви можете побачити, що коли ми беремо приблизно 1200 зразків, ймовірність того

що ми отримуємо зразком той же номер, одного й того ж елемента двічі становить приблизно половину, але

ймовірністьвзяти тей самий номер два рази фактично сходиться дуже

швидко до одного. Ви можете побачити, що якщо ми візьмемо 2200 елементів, то ймовірність

що два з цих елементів однакові, вже становить 90 відсотків, і ви знаєте, при 3000 елементів

вона в основному = одиниці. Так це перетворення дуже швидко наближається до одного, як тільки

він виходить за рамки розміру квадратний корінь з всесвіту. Тому ми повертаємось

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

хотів, щоб ви знали, що це таке. Так що це кінець цього сегмента, і в

наступному сегменті, ми почнемо з нашого першого прикладу шифрувальної системи.