Домівка > Перекладені, Теорія ймовірностей > Як відрізнити випадкову послідовність від псевдовипадкової.

Як відрізнити випадкову послідовність від псевдовипадкової.

Прожилки

Чи була послідовність з H та T наведена нижче згенерована підкиданням збалансованої монети 100 разів чи її хтось набрав на клавіатурі в манері, що нагадує випадкову?

HTTTHTHTTHTTHTHTHTHT

TTTHHTHHTHTHTTHHHTHT

HHTHHTTTHHHTHTTHHHHT

THTTHHTHTHTHTHTTHTHH

HTTHHHTHTHHHTHTHHHTH

Тут напевне і не скажеш. Однак. Ця послідовність має характерну рису, яка притаманна для “випадкових” послідовностей згенерованих людьми і незвичайна для насправді випадкових послідовностей: а саме, тут немає тривалих прожилок з H або T. Насправді, жоден символ не з’являється більш як чотири рази поспіль. Наскільки це правдоподібно? Якщо ми підкинемо збалансовану монету 100 разів, яка ймовірність то, що ми не матимемо п’ять аверсів підряд?

Від імовірнісної проблеми проблеми до лічильної.

Простір вибірок для цього досліду є {H, T}^{100}; що є, множиною всіх послідовностей з H і T завдовжки 100 символів. Якщо ми все робимо чесно і монета збалансована, тоді всі 2^{100} послідовностей рівноймовірні. Отже, нам лише потрібно порахувати кількість послідовностей без прожилок з п’яти аверсів, бо ймовірність, що 100 символьна випадкова послідовність не має таких прожилок є:

Pr(sequence\ has\ no\ \mathrm{HHHHH}) = \frac{\#sequences\ with\ no\ \mathrm{HHHHH}}{2^{100}}

Це звичайна ситуація. Ми звели ймовірнісну проблему до лічильної проблеми. На жаль, у нас немає надії розв’язати лічильну проблему прямим обчисленням. Комп’ютер не можу розглянути усі 2^{100} послідовностей H і T, слідкуючи скільком з них бракне прожилок з п’яти аверсів. Але, є й добра звістка, напрацьовано великий лантух математичних трюків для розв’язання лічильних проблем. В нашому випадку, ми використовуватимемо рекурентне рівняння. Підхід рекурентного рівняння має два етапи:
1. Розв’язати деякі маленькі проблеми.
2. Розв’язати n-ю проблему, використовуючи попередні розв’язки.

Етап 1: Розв’язати малі проблеми

Нехай S_n буде множиною послідовностей довжини n, які складені з H і T, які не мають прожилок з п’яти аверсів. Наша кінцева мета обчислити |S_{100}|. Але поки що, давайте обчислимо S_n для деяких дуже маленьких n:

    |S_1| = 2 (H та T)
    |S_2| = 4 (HH, HT, TH та TT)
    |S_3| = 8
    |S_4| = 16
    |S_5| = 31 (HHHHH)

Це наші базові випадки.

Етап 2: Розв’язати n-ю проблему, використовуючи попередні розв’язки

Ми можемо класифікувати послідовності в S_n у п’ять груп:
1. Послідовності, що закінчуються з T.
2. Послідовності, що закінчуються з TH.
3. Послідовності, що закінчуються з THH.
4. Послідовності, що закінчуються з THHH.
5. Послідовності, що закінчуються з THHHH.

Кожна послідовність у S_n потрапляє в одну з цих груп. Отже, розмір S_n це сума розмірів цих п’яти груп.

Як багато послідовностей у першій групі? Тобто, як багато послідовностей у S_n закінчуються на T? Попередні n - 1 символів у таких послідовностях не можуть містити прожилок з п’яти аверсів. Отже, ці n - 1 символів утворюють послідовність S_{n-1}. З іншого боку, додавання T у кінець послідовності в S_{n-1} переводить її в S_n. Таким чином, кількість послідовностей у першій групі дорівнює |S_{n-1}|.

Як багато послідовностей у другій групі? Міркуючи як і перед цим, попередні n-2 символи в кожній такій послідовності повинні формувати S_{n-2}. З іншого боку, додавання TH до будь-якої послідовності з S_{n-2} переводить її до другої групи S_n. Отже, всього |S_{n-2}| послідовностей у другій групі.

Подібне обгрунтування дає, що кількість послідовностей у третій групі становить |S_{n-3}|, у четвертій |S_{n-4}| і кількість у п’ятій є |S_{n-5}|. Таким чином, маємо:

    |S_n| = |S_{n-1}| + |S_{n-2}| + |S_{n-3}| + |S_{n-4}| + |S_{n-5}|, (n > 5)

Це рекурентне рівняння виражає розв’язок для великої проблеми (S_n) у термінах розв’язків для менших проблем (S_{n-1}, S_{n-2}, \dots).

Комбінуючи наші базові випадки і рекурентне рівняння, ми можемо обчислити |S_6|, |S_7|, \dots доки не досягнемо |S_{100}|.

    |S_6| = |S_5| + |S_4| + |S_3| + |S_2| + |S_1| = 31 + 16 + 8 + 4 + 2 + 1 = 62
    |S_7| = |S_6| + |S_5| + |S_4| + |S_3| + |S_2| = 62 + 31 + 16 + 8 + 4 + 2 = 123
    |S_8| = \dots

Обчислення S_{100} все ще вимагає близько 500 додавань, але це вже по силам комп’ютеру. Отже результат такий:

Pr(sequence\ has\ no\ \mathrm{HHHHH}) = 0.193\dots

З цього, чотири з п’яти послідовностей зі 100 підкидань монети містять прожилку з п’яти аверсів. За симетрією, ми також знаємо, що чотири з п’яти послідовностей містять п’ять реверсів. Якщо припустити, що ці дві події майже незалежні, тоді лише приблизно одна випадкова послідовність з двадцяти п’яти не містить прожилки з п’яти аверсів або реверсів. Це спостерігається в послідовності наведеній на початку статті. Напевне, ця послідовність підроблена натисканням на клавіатурі “випадкових” клавіш!

Mathematics for Computer Science
MIT Course Number: 6.042J / 18.062J
Advertisements
  1. Коментарів ще немає.
  1. No trackbacks yet.

Залишити відповідь

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

Лого WordPress.com

Ви коментуєте, використовуючи свій обліковий запис WordPress.com. Log Out / Змінити )

Twitter picture

Ви коментуєте, використовуючи свій обліковий запис Twitter. Log Out / Змінити )

Facebook photo

Ви коментуєте, використовуючи свій обліковий запис Facebook. Log Out / Змінити )

Google+ photo

Ви коментуєте, використовуючи свій обліковий запис Google+. Log Out / Змінити )

З’єднання з %s

%d блогерам подобається це: