3.3: Перетасування карт

Перетасування карт

Значна частина цього розділу базується на статті Бреда Манна, ²⁸ років, яка є експозицією статті Девіда Байєра та Персі Діаконіса. ²⁹

Рябні перетасовки

Враховуючи колоду\(n\) карт, скільки разів ми повинні перетасувати її, щоб зробити її «випадковою»? Звичайно, відповідь залежить від методу перетасування, який використовується і що ми маємо на увазі під «випадковим». Почнемо вивчення цього питання з розгляду стандартної моделі для перетасовки.

Ми починаємо з колоди\(n\) карт, які ми будемо вважати, що позначені в порядку зростання цілими числами від 1 до\(n\). Рябна перетасовка складається з розрізу колоди на дві стопки та чергування двох стопок. Наприклад, якщо\(n = 6\), початкове замовлення є\((1, 2, 3, 4, 5, 6)\), і розріз може відбутися між картами 2 і 3. Це дає початок двом стекам, а саме\((1, 2)\) і\((3, 4, 5, 6)\). Вони чергуються, щоб сформувати нове впорядкування колоди. Наприклад, ці два стеки можуть сформувати замовлення\((1, 3, 4, 2, 5, 6)\). Для того щоб обговорити такі перетасування, нам потрібно призначити розподіл ймовірностей набору всіх можливих перетасовок. Існує кілька розумних способів, за допомогою яких це можна зробити. Ми наведемо кілька різних стратегій присвоєння, і покажемо, що вони рівнозначні. (Це не означає, що це призначення є єдиним розумним.) Спочатку присвоюємо\(b(n, 1/2, k)\) біноміальну ймовірність тому випадку, якщо розріз\(k\) відбувається після карти. Далі припускаємо, що всі можливі переплетення, з огляду на розріз, однаково вірогідні. Таким чином, щоб завершити присвоєння ймовірностей, нам потрібно визначити кількість можливих переплетення двох стопок карт, з\(k\) і\(n-k\) карт відповідно.

Ми починаємо з написання другого стека в рядку, з пробілами між кожною парою послідовних карт і з пробілами на початку і в кінці (так що є\(n-k+1\) пробіли). Ми вибираємо, із заміною,\(k\) ці пробіли та розміщуємо картки з першої стопки у вибрані пробіли. Це можна зробити в

\[ n \choose{k} \]

способи. Таким чином, ймовірність заданого чергування повинна бути

\[{1\over{ n\choose{k} }}.\]

Далі зауважимо, що якщо нове замовлення не є упорядкуванням ідентичності, це результат унікальної пари, що перемежовується. Якщо нове замовлення є ідентичністю, це результат будь-якої з пар, що\(n+1\) перемежовуються.

Визначено a в порядку максимальної підпослідовності послідовних цілих чисел у порядку зростання. Наприклад, в упорядкуванні\[(2, 3, 5, 1, 4, 7, 6)\ ,\] є 4 зростаючі послідовності; вони є\((1)\),\((2, 3, 4)\),\((5, 6)\), і\((7)\). Легко помітити, що впорядкування є результатом перетасування, застосованого до упорядкування ідентичності, якщо і лише тоді, коли воно має не більше двох зростаючих послідовностей. (Якщо впорядкування має дві зростаючі послідовності, то ці зростаючі послідовності відповідають двом стекам, викликаним розрізом, а якщо впорядкування має одну зростаючу послідовність, то це впорядкування ідентичності.) Таким чином, вибірковий простір замовлень, отриманий шляхом застосування рятувального перетасування до упорядкування ідентичності, природно описується як сукупність усіх порядків з щонайменше двома зростаючими послідовностями.

Тепер легко призначити розподіл ймовірностей для цього простору вибірки. Кожному впорядкуванню з двома зростаючими послідовностями присвоюється значення

\[ \frac{b(n, 1/2, k)}{n \choose{k}} = \frac{1}{2^n},\]

і упорядкуванню ідентичності присвоюється значення

\[{n+1}\over{2^n} .\]

Є ще один спосіб перегляду рятувального перетасовки. Ми можемо собі уявити, починаючи з колоди, розрізаної на два стопки, як і раніше, з тим же присвоєнням ймовірностей, що і раніше, тобто біноміальний розподіл. Після того, як у нас є два стопки, ми беремо карти, по черзі, з нижньої частини двох стопок, і кладемо їх на одну стопку. Якщо є\(k_1\) і\(k_2\) карти, відповідно, в двох стопках в якийсь момент цього процесу, то робимо припущення, що ймовірність того, що наступна карта, яку потрібно взяти, виходить з заданого стека пропорційна поточного розміру стека. Це означає, що ймовірність того, що ми візьмемо наступну карту з першого стека, дорівнює.

\[{k_1}\over{k_1 + k_2} ,\]

і відповідна ймовірність для другого стека

\[{k_2}\over{k_1 + k_2} .\]

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

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

\[{k_i}\over{k_1 + k_2}} ,\]

де\(i = 1\) або\(2\), і знаменник кожного множника дорівнює кількості карт, які залишилося вибрати. Таким чином, знаменник ймовірності справедливий\(n!\). У той момент, коли вибирається карта зі стопки, яка має в ній\(i\) карти, чисельник відповідного коефіцієнта ймовірності є\(i\), а кількість карт в цій стопці зменшується на 1. Таким чином, чисельник бачиться бути\(k!(n-k)!\), так як всі карти в обох стопках в кінцевому підсумку вибираються. Тому цей процес привласнює ймовірність\[ {1\over{ n\choose{k} } }\]

до кожного можливого чергуванню.

Тепер перейдемо до питання про те, що відбувається, коли ми рятуємо перетасовки\(s\) раз. Повинно бути зрозуміло, що якщо ми почнемо з упорядкування ідентичності, ми отримаємо впорядкування з щонайбільше\(2^s\) зростаючими послідовностями, оскільки перетасовка створює не більше двох зростаючих послідовностей з кожної зростаючої послідовності в початковому порядку. Насправді, неважко помітити, що кожне таке замовлення є результатом\(s\) перетасовок. Тоді виникає питання, скільки способів може виникнути впорядкування з\(r\) зростаючими послідовностями, застосовуючи\(s\) рятувальні перетасовки до упорядкування ідентичності? Для того щоб відповісти на це питання, переходимо до ідеї\(a\) -shuffle.

\(a\)-Перетасовки

Існує кілька способів візуалізації\(a\) -shuffle. Один із способів - уявити істота з\(a\) руками, якому дається колода карт для перетасування. Істота природним чином розрізає колоду на\(a\) стопки, а потім розбиває їх разом. (Уявіть, що!) Таким чином, звичайна рядова перетасовка - це 2-перетасовка. Як і у випадку зі звичайним 2-shuffle, ми дозволяємо деяким стекам мати 0 карт. Інший спосіб візуалізувати\(a\) -shuffle - думати про його зворотному, який називається\(a\) -unshuffle. Ця ідея описана в доведенні наступної теореми.

Тепер ми покажемо, що\(a\) -shuffle з подальшим\(b\) -shuffle еквівалентно\(ab\) -shuffle. Це означає, зокрема, що\(s\) рябні перетасовки послідовно еквівалентні одному\(2^s\) -shuffle. Ця еквівалентність робиться точною наступною теоремою.

[thm 3.3.1]\(b\) Дозволяти\(a\) і бути двома натуральними числами. \(S_{a,b}\)Дозволяти множиною всіх впорядкованих пар, у яких перший запис є\(a\) -shuffle, а другий запис -\(b\) shuffle. \(S_{ab}\)Дозволяти бути набором всіх\(ab\) -shuffles. Тоді існує відповідність 1-1 між\(S_{a,b}\) і\(S_{ab}\) з наступним властивістю. Припустимо, що\((T_1, T_2)\) відповідає\(T_3\). Якщо\(T_1\) застосовується до замовлення особи, і\(T_2\) застосовується до отриманого замовлення, то остаточне замовлення таке ж, як замовлення, яке отримується шляхом звернення\(T_3\) до замовлення особи. Найпростіший спосіб описати необхідну відповідність - через ідею unshuffle. \(a\)-unshuffle починається з колоди\(n\) карт. По черзі карти беруться з верхньої частини колоди і розміщуються, з однаковою ймовірністю, на дно будь-якої з\(a\) стопок, де стопки маркуються від 0 до\(a-1\). Після того, як всі карти були розподілені, ми об'єднуємо стеки, щоб сформувати один стек, розміщуючи стек\(i\) поверх стека\(i+1\), для\(0 \le i \le a-1\). Легко помітити, що якщо почати з колоди, існує точно один спосіб вирізати колоду, щоб отримати\(a\) стеки, створені за допомогою\(a\) -unshuffle, і з цими\(a\) стеками є точно один спосіб перемежування їх, щоб отримати колоду в тому порядку, в якому вона була до unshuffle було виконано. Таким чином, цей\(a\) -unshuffle відповідає унікальному\(a\) -shuffle, а цей\(a\) -shuffle є зворотним оригіналу\(a\) -unshuffle.

Якщо застосувати\(ab\) -unshuffle\(U_3\) до колоди, ми отримуємо набір\(ab\) стеків, які потім об'єднуються, щоб сформувати один стек. Ми позначимо ці стеки впорядкованими парами цілих чисел, де перша координата знаходиться між 0 і\(a-1\), а друга координата знаходиться між 0 і\(b-1\). Потім маркуємо кожну картку етикеткою її стопки. Кількість можливих етикеток є\(ab\), як потрібно. Використовуючи це маркування, ми можемо описати, як знайти\(b\) -unshuffle та\(a\) -unshuffle, так що якщо ці два unshuffle застосовуються в такому порядку до колоди, ми отримуємо той самий набір\(ab\) стеків, який був отриманий за допомогою\(ab\) -unshuffle.

Щоб отримати\(b\) -unshuffle\(U_2\), ми сортуємо колоду на\(b\) стопки, при\(i\) цьому стопка містить всі карти з другою координатою\(i\), для\(0 \le i \le b-1\). Потім ці штабелі з'єднуються, утворюючи одну стопку. \(a\)-unshuffle\(U_1\) протікає таким же чином, за винятком того, що використовуються перші координати міток. Отримані\(a\) штабелі потім з'єднують, утворюючи одну стопку.

Наведений вище опис показує, що карти, що закінчуються зверху, є всі ті, що позначені\((0, 0)\). За ними слідують ті, що позначені\((0, 1),\ (0, 2),\)\(\ \ldots,\ (0, b - 1),\ (1, 0),\ (1,1),\ldots,\ (a-1, b-1)\). Крім того, відносний порядок будь-якої пари карток з однаковими мітками ніколи не змінюється. Але це точно так само, як і\(ab\) -unshuffle, якщо на початку такого unshuffle ми маркуємо кожну з карт однією з міток\((0, 0),\ (0, 1),\ \ldots,\ (0, b-1),\ (1, 0),\ (1,1),\ \ldots,\ (a-1, b-1)\). На цьому доказ завершено.

На малюнку [рис. 3.14] ми показуємо мітки для 2-unshuffle колоди з 10 картами. Є 4 карти з міткою 0 і 6 карт з міткою 1, тому якщо виконується 2-unshuffle, то в першому стосі буде 4 карти, а другий стек - 6 карт. Коли це unshuffle виконується, колода закінчується в порядку ідентичності.

На малюнку [рис. 3.15] ми показуємо мітки для 4-unshuffle тієї ж колоди (оскільки використовуються чотири мітки). Цю цифру також можна розглядати як приклад пари 2-unshuffle, як описано в доказі вище. Перший 2-unshuffle використовуватиме другу координату міток для визначення стеків. У цьому випадку дві стопки містять карти, значення яких

\[\{5, 1, 6, 2, 7\} {\rm and} \{8, 9, 3, 4, 10\}.\]

Після виконання цього 2-unshuffle колода знаходиться в порядку, показаному на малюнку [рис. 3.14], як повинен перевірити читач. Якщо ми хочемо виконати 4-unshuffle на колоді, використовуючи показані мітки, ми сортуємо карти лексикографічно, отримуючи чотири стопки

\[\{1, 2\},\ \{3, 4\},\ \{5, 6, 7\},\ {\rm and}\ \{8, 9, 10\}.\]

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

Теорема 3.3.2

Якщо\(D\) будь-яке впорядкування, яке є результатом застосування\(a\) -shuffle, а потім\(b\) -shuffle до упорядкування ідентичності, то ймовірність, що призначається\(D\) цією парою операцій, така ж, як ймовірність, що присвоюється процесом застосування\(ab\) -\(D\) перетасувати до замовлення ідентичності. Викликати простір зразка\(a\) -shuffles\(S_a\). Якщо позначити стеки цілими числами від\(0\) до\(a-1\), то кожна пара, що перемежовується, тобто shuffle, відповідає рівно одному\(n\) -значному базовому\(a\) цілому числу, де\(i\) й цифра в ціле число - це стопка, членом якої є\(i\) й карта. Таким чином, кількість пар, що перемежовуються, дорівнює числу\(n\) -digit базових\(a\) цілих чисел, що є\(a^n\). Звичайно, не всі ці пари призводять до різних порядків. Кількість пар, що ведуть до заданого замовлення, буде розглянуто далі. Для наших цілей досить вказати, що саме пари виріз-чергуються визначають присвоєння ймовірності.

Попередня теорема показує, що існує відповідність 1-1 між\(S_{a,b}\) і\(S_{ab}\). Крім того, відповідні елементи дають однаковий порядок при застосуванні до замовлення особи. Враховуючи будь-яке впорядкування\(D\), нехай\(m_1\) буде кількість елементів, з\(S_{a,b}\) яких, при застосуванні до упорядкування посвідчення особи, результат\(D\). \(m_2\)Дозволяти кількість елементів, з\(S_{ab}\) яких, при застосуванні до упорядкування ідентичності, результат\(D\). Попередня теорема має на увазі це\(m_1 = m_2\). Таким чином, обидві множини присвоюють ймовірність

\[

ParseError: EOF expected (click for details)

Callstack:
    at (Статистика/Теорія_ймовірностей/Книга:_Вступна_ймовірність_(Grinstead_і_Snell)/03:_Комбінаторика/3.03:_Перетасування_карт), /content/body/div/div[2]/div/p[3]/span/span, line 1, column 4

\]

до\(D\). На цьому доказ завершено.

Зв'язок з проблемою Дня Народження

Є ще один момент, який можна зробити стосовно міток, наданих карткам шляхом послідовних unshuffles. Припустимо, що ми 2-unshuffle\(n\) -card колоду, поки мітки на картах не будуть різними. Легко помітити, що цей процес виробляє кожну перестановку з однаковою ймовірністю, тобто це випадковий процес. Щоб переконатися в цьому, зауважте, що якщо мітки стають різними на\(s\) 2-й unshuffle, то можна думати про цю послідовність 2-unshuffle як одну\(2^s\) -unshuffle, в якій всі стеки, визначені unshuffle, мають не більше однієї карти в них (пам'ятайте, стеки відповідають міткам). Якщо в кожній стопці є не більше однієї карти, то дано будь-які дві карти в колоді, однаково ймовірно, що перша карта має нижчу або вищу мітку, ніж друга. Таким чином, кожне можливе замовлення однаково ймовірно буде результатом цього\(2^s\) -unshuffle.

\(T\)Дозволяти випадкова величина, яка підраховує кількість 2-unshuffles, поки всі мітки не будуть різними. Можна думати про те\(T\), як дати міру того, скільки часу потрібно в процесі розшарування, поки не буде досягнута випадковість. Оскільки перетасування та розшарування є оберненими процесами,\(T\) також вимірюється кількість перетасовок, необхідних для досягнення випадковості. Припустимо, що у нас є колода\(n\) -card, і ми просимо\(P(T \le s)\). Це дорівнює\(1 - P(T > s)\). Але\(T > s\) якщо і тільки якщо це так, що не всі мітки після\(s\) 2-unshuffles є відмінними. Це просто проблема дня народження; ми запитуємо ймовірність того, що принаймні дві людини мають однаковий день народження, враховуючи, що у нас є\(n\) люди і\(2^s\) можливі дні народження. Використовуючи нашу формулу з Прикладу [іспит 3.3], ми знаходимо, що

\[P(T > s) = 1 - {2^s \choose n} \frac{n!}{2^{sn}}.\]

У розділі [chp 6] ми визначимо середнє значення випадкової величини. Використовуючи цю ідею та вищевказане рівняння, можна обчислити середнє значення випадкової величини\(T\) (див. Вправа [сек. 6.1]. [Вище 6.1.42]). Наприклад, якщо\(n = 52\), то середнє значення\(T\) становить близько 11,7. Це означає, що в середньому для того, щоб процес вважався випадковим, потрібно близько 12 рядових перетасовок.

Вирізати-перемежування пар і замовлень

Як було зазначено в доведенні теореми [thm 3.3.2], не всі пари, що перемежовуються, ведуть до різних порядків. Однак існує легка формула, яка дає кількість таких пар, які призводять до заданого впорядкування.

[thm 3.3.3] Якщо впорядкування довжини\(n\) має\(r\) зростаючі послідовності, то кількість пар перерізування-чергування під\(a\) -shuffle порядку ідентичності, що призводить до впорядкування, дорівнює

\[ { n + a - r \choose{n} }.\]

Щоб зрозуміти, чому це правда, нам потрібно підрахувати кількість способів, за допомогою яких може бути виконано розріз у\(a\) -shuffle, що призведе до заданого впорядкування з\(r\) зростаючими послідовностями. Ми можемо ігнорувати переплетення, оскільки після того, як було зроблено розріз, щонайменше одне переплетення призведе до заданого замовлення. Оскільки задане впорядкування має\(r\) зростаючі\(r-1\) послідовності, визначаються точки поділу в розрізі. Решта точки\(a - 1 - (r - 1) = a - r\) поділу можна розмістити в будь-якому місці. Кількість місць, щоб поставити ці залишкові точки поділу дорівнює\(n+1\) (це кількість пробілів між послідовними парами карт, включаючи позиції на початку і кінці колоди). Ці місця вибираються з дозволеним повторенням, тому кількість способів зробити цей вибір

\[{n + a - r \choose{a-r}} = {n + a - r \choose{n}} .\]

Зокрема, це означає, що якщо\(D\) це впорядкування, яке є результатом застосування\(a\) -shuffle до упорядкування ідентичності, і якщо\(D\) має\(r\) зростаючі послідовності, то ймовірність, що\(D\) присвоюється цим процесом

\[{ {n + a - r\choose{n}} \over{a^n}}.\]

На цьому доказ завершено.

Наведена вище теорема показує, що істотна інформація про ймовірність, присвоєну впорядкуванню під\(a\) -shuffle, - це лише кількість зростаючих послідовностей у впорядкуванні. Таким чином, якщо ми визначимо кількість порядків, які містять точно\(r\) зростаючі послідовності, для кожного\(r\) між 1 і\(n\), то ми визначимо функцію розподілу випадкової величини, яка полягає у застосуванні випадкового\(a\) -shuffle до впорядкування ідентичності.

Число порядків\(\{1, 2, \ldots, n\}\) з\(r\) зростаючими послідовностями позначається\(A(n, r)\), і називається номером Ейлера. Існує багато способів обчислити значення цих чисел; наступна теорема дає один рекурсивний метод, який випливає відразу з того, що ми вже знаємо про\(a\) -shuffles.

[thm 3.3.4] Нехай\(a\) і\(n\) бути додатними цілими числами. Тоді

\[a^n = \sum_{r = 1}^a {n + a - r \choose{n} } A(n, r). \]

Таким чином,

\[A(n, a) = a^n - \sum_{r = 1}^{a-1} { n + a - r \choose{n} }A(n, r) \]

Крім того,

\[A(n, 1) = 1\]

Друге рівняння може бути використано для обчислення значень чисел Ейлера, і випливає відразу з Рівняння [eq 3.6]. Останнє рівняння є наслідком того, що єдиним впорядкуванням\(\{1, 2, \ldots, n\}\) з однією зростаючою послідовністю є впорядкування ідентичності. Таким чином, залишається довести рівняння [ур. 3.6]. Розраховувати набір\(a\) -shuffles колоди з\(n\) картами ми будемо двома способами. По-перше, ми знаємо, що існують\(a^n\) такі перетасовки (це було відзначено в доведенні теореми [thm 3.3.2]). Але є\(A(n, r)\) порядки\(\{1, 2, \ldots, n\}\) з\(r\) зростаючими послідовностями, і теорема [thm 3.3.3] стверджує, що для кожного такого впорядкування є саме

\[{ n+a-r \choose n}\]

вирізати-чергуються пари, які призводять до впорядкування. Тому права частина Equation [eq 3.6] підраховує набір\(a\) -shuffles колоди\(n\) -карт. На цьому доказ завершено.

Випадкові замовлення та випадкові процеси

Тепер перейдемо до другого питання, яке було задано на початку цього розділу: Що ми маємо на увазі під «випадковим» впорядкуванням? Дещо вводить в оману думати про те, що даний порядок є випадковим або не випадковим. Якщо ми хочемо вибрати випадкове замовлення з безлічі всіх замовлень, ми маємо на увазі\(\{1, 2, \ldots, n\}\), що ми хочемо, щоб кожне замовлення було обрано з тією ж ймовірністю, тобто будь-яке замовлення є таким же «випадковим», як і будь-яке інше.

Слово «випадковий» дійсно слід використовувати для опису процесу. Ми скажемо, що процес, який виробляє об'єкт з (кінцевого) набору об'єктів, є випадковим процесом, якщо кожен об'єкт у множині виробляється з однаковою ймовірністю процесом. У нинішній ситуації об'єкти є порядками, а процес, який виробляє ці об'єкти, є процесом перетасування. Легко побачити, що no\(a\) -shuffle - це дійсно випадковий процес, оскільки якщо\(T_1\) і\(T_2\) є двома порядками з різною кількістю зростаючих послідовностей, то вони виробляються за допомогою\(a\) -shuffle, застосованого до упорядкування ідентичності, з різними ймовірностями.

Зміна відстані

Замість того, щоб вимагати, щоб послідовність перетасовок дала процес, який є випадковим, ми визначимо міру, яка описує, наскільки далеко заданий процес знаходиться від випадкового процесу. \(X\)Дозволяти бути будь-який процес, який виробляє впорядкування\(\{1, 2, \ldots, n\}\). \(f_X(\pi)\)Визначте ймовірність, що\(X\) виробляє замовлення\(\pi\). (Таким чином,\(X\) може розглядатися як випадкова величина з функцією розподілу\(f\).) \(\Omega_n\)Дозволяти бути безлічі всіх порядків\(\{1, 2, \ldots, n\}\). Нарешті, нехай\(u(\pi) = 1/|\Omega_n|\) для всіх\(\pi \in \Omega_n\). Функція\(u\) є розподільною функцією процесу, який виробляє замовлення і який є випадковим. Для кожного замовлення\(\pi \in \Omega_n\) кількість\[|f_X(\pi) - u(\pi)|\] - це різниця між фактичними та бажаними ймовірностями, які\(X\) виробляють\(\pi\). Якщо ми підсумовуємо це протягом усіх\(\pi\) порядків і називаємо цю суму\(S\), ми бачимо, що\(S = 0\) якщо і тільки якщо\(X\) є випадковим, а в іншому випадку\(S\) є позитивним. Легко показати, що максимальне значення\(S\) дорівнює 2, тому ми помножимо суму на\(1/2\) так, щоб значення потрапляло в інтервал\([0, 1]\). Таким чином, отримаємо наступну суму як формулу для між двома процесами:\[\parallel f_X - u \parallel = {1\over 2}\sum_{\pi \in \Omega_n} |f_X(\pi) - u(\pi)| .\]

Тепер застосуємо цю ідею до випадку перетасування. Ми дозволяємо\(X\) бути процесом\(s\) послідовних перетасовок, застосованих до упорядкування ідентичності. Ми знаємо, що також можна думати\(X\) як про одне\(2^s\) -shuffle. Ми також знаємо, що\(f_X\) є постійною на множині всіх порядків з\(r\) зростаючими послідовностями, де\(r\) є будь-яке натуральне число. Нарешті, ми знаємо значення\(f_X\) на замовлення з\(r\) зростаючими послідовностями, і ми знаємо, скільки таких замовлень існує. Таким чином, в даному конкретному випадку ми маємо

\[\parallel f_X - u \parallel = {1\over 2}\sum_{r=1}^n A(n, r) \biggl| {2^s + n - r\choose{n}}/2^{ns} - {1\over{n!}}\biggr| \]

Оскільки ця сума має лише\(n\) суми, її легко обчислити для середніх значень розміру\(n\). Для\(n = 52\), отримаємо список значень, наведених в таблиці [табл. 3.12].

Відстань до випадкового процесу.

1	1
2	1
3	1
4	0.9999995334
5	0,923 7329294
6	0.613 5495966
7	0.3340609995
8	0,167 158 6419
9	0.0854 2019 34
10	0.0429455489
11	0.0215023760
12	0.0107548935
13	0.0053779101
14	0.0026890130

Щоб допомогти зрозуміти ці дані, вони наведені в графічному вигляді на малюнку [рис. 3.13]. Програма VariationList виробляє дані, наведені як в таблиці [таблиця 3.12], так і на малюнку [рис. 3.13]. Один бачить, що поки не відбулося 5 перетасовок, вихід\(X\) дуже далекий від випадкового. Після 5 перетасовок відстань від випадкового процесу по суті зменшується вдвічі кожного разу, коли відбувається перетасування.

З огляду на функції розподілу\(f_X(\pi)\) і,\(u(\pi)\) як зазначено вище, існує інший спосіб перегляду варіації відстані\(\parallel f_X - u\parallel\). З огляду на будь-яку подію\(T\) (яка є підмножиною\(S_n\)), ми можемо обчислити її ймовірність як під процесом, так\(X\) і під рівномірним процесом. Наприклад, ми можемо собі уявити, що\(T\) являє собою набір всіх перестановок, в яких перший гравець в грі в покер на 7 гравців роздається стрит-флеш (п'ять послідовних карт в одній масті). Цікаво розглянути, наскільки ймовірність цієї події після певної кількості перетасовок відрізняється від ймовірності цієї події, якщо всі перестановки однаково ймовірні. Цю різницю можна вважати описом того, наскільки близький процес до випадкового процесу щодо події\(T\).\(X\)

Тепер розглянемо\(T\) таку подію, щоб абсолютна величина різниці між цими двома ймовірностями була якомога більшою. Можна показати, що ця абсолютна величина є варіаційною відстанню між процесом\(X\) і рівномірним процесом. (Читача просять довести цей факт у Вправі [exer 3.3.4].)

Ми щойно бачили, що для колоди з 52 карт варіативна відстань між процесом перетасування 7 та випадковим процесом приблизно\(.334\). Цікаво знайти\(T\) таку подію, щоб різниця між ймовірностями, які виробляють два процеси,\(T\) близька до\(.334\). Подія з цим властивістю можна описати в плані гри під назвою New Age Solitaire.

Пасьянс «Новий вік»

Цю гру придумав Пітер Дойл. У неї грають стандартною колодою з 52 карт. Роздаємо карти лицьовою стороною вгору, по одній за раз, на стопку скидання. Якщо зустрінеться туз, скажімо туз сердець, ми використовуємо його, щоб почати серцю купу. Кожна купа мастей повинна бути побудована по порядку, від туза до короля, використовуючи тільки згодом роздані карти. Після того, як ми роздали всі карти, ми забираємо стопку скидання і продовжуємо. Ми визначаємо костюми Інь як Серця та Клуби, а Ян - діамантами та Піками. Гра закінчується, коли обидві палі костюмів Інь були завершені, або обидві палі костюмів Ян були завершені. Зрозуміло, що якщо впорядкування колоди проводиться випадковим процесом, то ймовірність того, що палі костюма Інь завершені першими, дорівнює рівно 1/2.

Тепер припустимо, що ми купуємо нову колоду карт, ламаємо печатку на упаковці, і рятуємо колоду 7 разів. Якщо хтось спробує це, то виявляє, що костюми Інь виграють близько 75% часу. Це на 25% більше, ніж ми б отримали, якби колода була в дійсно випадковому порядку. Це відхилення досить близьке до теоретичного максимуму\(33.4\)%, отриманого вище.

Чому костюми Інь виграють так часто? У новій колоді карт, масті знаходяться в наступному порядку, зверху вниз: туз через короля сердець, туз через короля треф, король через туз діамантів, і король через туз пік. Зверніть увагу, що якби карти взагалі не перетасовувалися, то стопки масті Інь були б завершені на першому проході, перш ніж будь-які карти масті Ян будуть навіть помічені. Якби ми продовжували грати в гру, поки палі костюма Ян не будуть завершені, для цього знадобиться 13 проходів через колоду. Таким чином, можна помітити, що в новій колоді костюми Інь знаходяться в найбільш вигідному порядку, а костюми Ян - в найменш вигідному порядку. Під 7 рябів-перетасовками відносна перевага костюмів Інь над костюмами Ян певною мірою зберігається.

Вправа\(\PageIndex{1}\)

Враховуючи будь-яке впорядкування\(\sigma\)\(\{1, 2, \ldots, n\}\)\(\sigma^{-1}\), ми можемо визначити, зворотне впорядкування\(\sigma\), щоб бути порядком, в якому\(i\) й елемент є позицією, зайнятою\(i\) в\(\sigma\). Наприклад, якщо\(\sigma = (1, 3, 5, 2, 4, 7, 6)\), то\(\sigma^{-1} = (1, 4, 2, 5, 3, 7, 6)\). (Якщо хтось розглядає ці порядки як перестановки, то\(\sigma^{-1}\) є зворотним\(\sigma\).)

A виникає між двома позиціями в упорядкуванні, якщо ліву позицію займає більше число, ніж права позиція. Зручно буде сказати, що кожне замовлення має падіння після останньої позиції. У наведеному вище прикладі\(\sigma^{-1}\) має чотири падіння. Вони виникають після другої, четвертої, шостої і сьомої позицій. Доведіть, що кількість зростаючих послідовностей в порядку\(\sigma\) дорівнює кількості падінь в\(\sigma^{-1}\).

Відповідь

Додайте сюди текст відповіді, і він автоматично буде прихований, якщо на сторінці активний шаблон «AutoNum».

Вправа\(\PageIndex{2}\)

Покажіть, що якщо ми почнемо з упорядкування ідентичності\(\{1, 2, \ldots, n\}\), то ймовірність того, що\(a\) -shuffle призводить до впорядкування з точно\(r\) зростаючими послідовностями дорівнює\[

ParseError: EOF expected (click for details)

Callstack:
    at (Статистика/Теорія_ймовірностей/Книга:_Вступна_ймовірність_(Grinstead_і_Snell)/03:_Комбінаторика/3.03:_Перетасування_карт), /content/body/div/div[7]/div[2]/p[2]/span[4]/span, line 1, column 10

A(n, r) ,\] для\(1 \le r \le a\).

Відповідь

Додайте сюди текст відповіді, і він автоматично буде прихований, якщо на сторінці активний шаблон «AutoNum».

Вправа\(\PageIndex{3}\)

Нехай\(D\) буде колода\(n\) карт. Ми бачили, що існують\(a^n\)\(a\) -перетасування\(D\). Кодування множини\(a\) -unshuffles було дано в доведенні теореми [thm 3.3.1]. Тепер ми дамо кодування\(a\) -shuffles, яке відповідає кодуванню\(a\) -unshuffles. \(S\)Дозволяти множина всіх\(n\) -кортежів цілих чисел, кожен між 0 і\(a-1\). \(M = (m_1, m_2, \ldots, m_n)\)Дозволяти бути будь-яким елементом\(S\). \(n_i\)Дозволяти число\(i\) в\(M\), для\(0 \le i \le a-1\). Припустимо, що ми починаємо з колоди в зростаючому порядку (тобто карти нумеруються від 1 до\(n\)). Ми маркуємо перші\(n_0\) картки з 0, наступні\(n_1\) карти з 1 і т.д. потім\(a\) -shuffle, що відповідає\(M\) є перетасування, що призводить до порядку, в якому карти з маркуванням\(i\) поміщаються в позиції,\(M\) що містять етикетку\(i\) . Картки з однаковою міткою розміщуються в цих положеннях в порядку збільшення їх кількості. Наприклад, якщо\(n = 6\) і\(a = 3\), нехай\(M = (1, 0, 2, 2, 0, 2)\). Потім\(n_0 = 2,\ n_1 = 1,\) і\(n_2 = 3\). Таким чином, ми позначити карти 1 і 2 з 0, карти 3 з 1, і карти 4, 5 і 6 з 2. Потім карти 1 і 2 поміщаються в позиції 2 і 5, карта 3 поміщається в положення 1, а карти 4, 5 і 6 поміщаються в позиції 3, 4 і 6, в результаті чого відбувається впорядкування\((3, 1, 4, 5, 2, 6)\).

1. Використовуючи це кодування, показати, що ймовірність того, що в\(a\) -shuffle перша карта (тобто карта № 1) переміщається в\(i\) -ю позицію, задається наступним виразом:\[
   ParseError: EOF expected (click for details)

   Callstack:
       at (Статистика/Теорія_ймовірностей/Книга:_Вступна_ймовірність_(Grinstead_і_Snell)/03:_Комбінаторика/3.03:_Перетасування_карт), /content/body/div/div[7]/div[3]/ol/li[1]/span[3]/span, line 1, column 6
   

   .\]

2. Дайте точну оцінку ймовірності того, що в трьох ряфльних перетасуваннях 52-карткової колоди перша карта потрапляє в одну з перших 26 позицій. Використовуючи комп'ютер, точно оцініть ймовірність того ж події після семи перетасовок.

Відповідь

Додайте сюди текст відповіді, і він автоматично буде прихований, якщо на сторінці активний шаблон «AutoNum».

Вправа\(\PageIndex{4}\)

Нехай\(X\) позначають конкретний процес, який виробляє елементи\(S_n\), і нехай\(U\) позначають рівномірний процес. Нехай функції розподілу цих процесів позначаються\(f_X\) і\(u\), відповідно. Показати, що відстань варіації\(\parallel f_X - u\parallel\) дорівнює\[\max_{T \subset S_n} \sum_{\pi \in T} \Bigl(f_X(\pi) - u(\pi)\Bigr).\]

: Запишіть перестановки\(S_n\) в порядку зменшення різниці\(f_X(\pi) - u(\pi)\).

Відповідь

Додайте сюди текст відповіді, і він автоматично буде прихований, якщо на сторінці активний шаблон «AutoNum».

Вправа\(\PageIndex{5}\)

Розглянемо процес, описаний в тексті, в якому колода\(n\) -карт багаторазово маркується і 2-unshuffled, способом, описаним у доведенні теореми [thm 3.3.1]. (Див. Малюнки [рис. 3.12] і [рис. 3.13].) Процес триває до тих пір, поки етикетки не стануть різними. Покажіть, що процес ніколи не припиняється, поки не буде зроблено принаймні\(\lceil \log_2(n) \rceil\) unshuffles.

Відповідь

Додайте сюди текст відповіді, і він автоматично буде прихований, якщо на сторінці активний шаблон «AutoNum».