Теория вероятностей: задача о совпадениях
Как-то, лет 20 назад, смотрел передачу с одним психологом*. Там к нему на консультацию пришла девушка, которая считала себя ясновидящей (или экстрасенсом). Психолог, чтобы доказать девушке, что никакого дара у нее нет, предложил ей эксперимент.
Он дал 6 фотографий людей и шесть листов, где была написана их биография. И предложил совместить их, чтобы фотографии совпали с биографиями. Девушка правильно совместила 3 фото и 3 био. После чего психолог сказал, что раз она угадала лишь половину, это как с монеткой, вероятность 1/2, никакого дара у нее нет, и она может не беспокоиться по поводу того, о чем она там беспокоилась.
А мы как раз проходили теорвер в институте (в школе такого не было). Я, конечно, заморачиваться с решением не стал тогда, но понял, что так просто, как представляется психологу с телеэкрана, вероятность не вычисляется. И вот настала все-таки пора мне, закрыть гештальт и разобраться, какова же была эта вероятность.
Задачи о совпадениях (встречах)
Как оказалось, эксперимент, предложенный психологом, является классической комбинаторной "задачей о встречах" (Problème des rencontres). Есть похожие "задачи о беспорядках", например, "Задача о шляпах" ("Задача Эйлера"), "Задача о конвертах" и т.п. Там в классической формулировке спрашивается, какова вероятность, что ни один из мужчин, оставивших шляпы в гардеробе, не получит назад свою (здесь решение для случая, когда некоторые все же получат). Или что ни один адресат не получит свое письмо. Но у нас немного другая ситуация: часть фото и био должны совпасть — это "частичный беспорядок".
Essay d'analyse sur les jeux de hazard. Выкладки Бернулли (на латыни). Как знак умножения используется точка " . ", а как знак факториала ничего не используется (не придумали) поэтому 1 . 2 . 3 ... n-1 — это "(n-1)!". Номинал — a, b, c…, номер — 1, 2, 3…
Буквально пару слов об истории вопроса. Подобными проблемами математики озаботились в связи с карточной игрой Тринадцать (фр. Treize). Банкующий доставал по очереди из колоды карты. Если порядковый номер карты совпадал с ее номиналом (например, второй картой оказалась двойка), то банкир выигрывал, если ни один номинал не совпадал с порядковым номером, то побеждал игрок. Вычислением вероятностей обоих вариантов занимался Пьер Монмор. Он написал в 1708 году книгу "Аналитическое исследование азартных игр", во 2-м издании которой опубликовал свою переписку (есть на англ.) с Николаем Бернулли. На стр. 301—303 Бернулли приводит математический анализ "встреч" (совпадений): опираясь на известные биномиальные коэффициенты (число сочетаний), он впервые вывел формулу субфакториалов ("беспорядков")**. Ниже будем использовать современную компактную запись этих же идей.
Итак...
Итак, как известно, чтобы вычислить вероятность P, надо число исходов, которые удовлетворяют нашему критерию — 3 фото соотнесены с биографиями верно — разделить на общее число вариантов:
Общее число вариантов, когда n биографий совмещаются с n фотографиями любым образом это n!
А числитель — это "число встреч", рассчитывается по формуле: C(n, k) ⋅ !(n - k). Подставим все это в исходное отношение и получим:
C(n k) — это число сочетаний из n по k. Субфакториал !(n - k) — это "число беспорядков". Факториал n! — это общее число вариантов
Хотя вроде бы у нас 12 элементов — 6 фото и 6 био — но фотографии это фактически позиции, по которым расладывают биографии, или наоборот, биографии — это позиции. Поэтому n = 6. Значит, n! = 6! = 720 — это наш знаменатель. Теперь найдем числитель.
Найдем число сочетаний
Сначала нам надо получить число вариантов, которые дадут три совпадения фотографии и биографии. То есть какие-то три фотографии могут совпасть в разных сочетаниях, и надо найти число этих сочетаний. Есть формула для сочетаний C из n по k, то есть в нашем случае из 6 по 3 (три совпавшие пары из 6): С(n, k) = n! / k! (n - k)!. Но поскольку тут число вариантов не слишком большое, то для наглядности можно проиллюстрировать — цифры будут обозначать фотографии, а буквы — биографии:
1 2 3 4 5 6 — фотографии
а б в г д е — биографии
При такой записи видно, что это та же задача, которую решали Бернулли с Монмором, где был номинал карт a, b, c… и порядковый номер 1, 2, 3… Это еще похоже на задачу, о том, как рассадить n человек по n стульям (если имена подписаны на стульях), чтобы только часть k села на свои места — просто вместо стульев тут фотографии, на которые "рассаживают" биографии.
Возьмем в качестве первого варианта такой, где первые три пары совпали: 1 - а, 2 - б, 3 - в (остальные нас не интересуют). Теперь зафиксируем первые две позиции (1 - а, 2 - б) и будем менять третью, когда варианты для 1 - а, 2 - б кончатся, оставим 1 - а, а 2 - б изменим на 3 - в, когда кончатся все варианты, начинающиеся с 1 - а, начнем искать начинающиеся с 2 - б и т.д. Всего получится 20 вариантов.
Варианты, начинающиеся с 1:
1. 1 - а, 2 - б, 3 - в
2. 1 - а, 2 - б, 4 - г
3. 1 - а, 2 - б, 5 - д
4. 1 - а, 2 - б, 6 - е
5. 1 - а, 3 - в, 4 - г
6. 1 - а, 3 - в, 5 - д
7. 1 - а, 3 - в, 6 - е
8. 1 - а, 4 - г, 5 - д
9. 1 - а, 4 - г, 6 - е
10. 1 - а, 5 - д, 6 - е
Варианты, начинающиеся с 2:
11. 2 - б, 3 - в, 4 - г
12. 2 - б, 3 - в, 5 - д
13. 2 - б, 3 - в, 6 - е
14. 2 - б, 4 - г, 5 - д
15. 2 - б, 4 - г, 6 - е
16. 2 - б, 5 - д, 6 - е
Варианты, начинающиеся с 3:
17. 3 - в, 4 - г, 5 - д
18. 3 - в, 4 - г, 6 - е
19. 3 - в, 5 - д, 6 - е
Вариант, начинающийся с 4:
20. 4 - г, 5 - д, 6 - е
Или то же самое на картинке:
Цветом отмечены сочетания, когда три биографии "сели" на свои позиции (фотографии). Остальные (серые) элементы при этом могут совпасть, могут не совпасть — но нам надо, чтобы они точно не совпали, поэтому ниже будем искать для них число беспорядков
Ну и такой же результат был бы, если бы мы ничего не выписывали, а просто подставили значения в формулу сочетаний:
Найдем число беспорядков
Но на каждое такое удачное "сочетание" трех совпавших пар приходятся еще разные сочетания оставшихся 3-х фотографий и 3-х биографий.
Возьмем первое сочетание, которое мы нашли 1-а, 2-б, 3-в и посмотрим как могут расположиться оставшиеся элементы:
4 - г, 5 - д, 6 - е — 3 совпадения
4 - г, 5 - е, 6 - д — 1 совпадение
4 - е, 5 - д, 6 - г — 1 совпадение
4 - д, 5 - г, 6 - е — 1 совпадение
4 - д, 5 - е, 6 - г — Нет новых совпадений
4 - е, 5 - г, 6 - д — Нет новых совпадений
Вот первые четыре варианта нам не подходят — потому что нас интересуют только ситуации, где правильно выбраны только три пары, не больше — а эти дадут нам новые совпадения, и получится больше 3-х. Значит, на каждое найденное нами сочетание из 6 по 3, которых мы насчитали 20, придется еще по 2 варианта комбинаций оставшихся элементов, которые при этом не дадут новых совпадений. Поэтому надо умножить 20 на 2. Это же число, то есть 2, можно было получить, вычислив субфакториал !3 (так называемое "число беспорядков", т. е. число вариантов, где нет никаких совпадений) по формуле:
Подставим значения в формулу: 3! * (1 - 1/1! + 1/2! - 1/3!) = 6 * ( 1 - 1/1 + 1/2 - 1/6 ) = 6 * 2 / 6 = 2
Ниже опять историческое отступление — можно его пропустить и перейти в конец раздела.
Мы просто подставили значения в формулу субфакториала. Но интересно, как Бернулли ее получил. Когда он пытался вычислить вероятность, что в игре Тринадцать выиграет банкующий — то есть хоть одна карта окажется на своем месте (ее номинал совпадет с порядковым номером) — то заметил следующую странность. Если взять, к примеру, колоду из трех карт (аналог наших оставшихся трех биографий), и предположить, что 1/3 — это вероятность одной конкретной карте оказаться на своей позиции, а затем попытаться вычислить вероятность того, что хоть одна карта окажется на своем месте, то получится 1/3 + 1/3 + 1/3 = 1. Но такого быть не может, иначе банкующий всегда бы выигрывал. А мы сами видели, когда выписывали комбинации, что буквы находятся не на своих позициях, то есть дают "полный беспорядок" только в двух случаях.
Бернулли понял, что карта может оказаться на своем месте в разных вариантах: в нашем случае каждая буква на месте в "г, д, е" и отдельно в "г, е, д", "е, д, г", "д, г, е" — то есть одному условию "буква (карта) на месте" удовлетворяют два варианта. Поэтому нельзя просто сложить 1/3 три раза, а надо еще из вероятности 1 вычесть вероятность того, что карта попадет в один из этих вариантов — C(3, 2) ⋅ 1/6. Это будет 6/6 - 3/6 = 3/6 = 1/2. Теперь вероятность получилась 0.5, что опять противоречит нашим эмпирическим данным — мы видели что буквы были на своих местах в 4-х случаях из шести (4/6), а не в половине. Это произошло потому что вероятность 3/6 полностью поглотила событие "г, д, е", которое удовлетворяет условиям "буква на месте" сразу для всех трех букв.
Поэтому Бернулли еще раз прибавляет вероятность для этой комбинации: 6/6 - 3/6 + 1/6. Вот теперь получается 4/6, что согласовывается с тем, что мы видели, когда писали комбинации с г, д, е. Это вероятность того, что выиграет банкующий — если вычесть ее из 1, получим вероятность того, что выиграет игрок (вероятность беспорядков). P-беспор = 1 - (6/6 - 3/6 + 1/6). Теперь, если заменить 3/6 обратно на C(3, 2) ⋅ 1/6 = 3! / ( 2! ⋅ (3 - 2)!) ⋅ 1/6 и произвести сокращения, то получим 1/2!, а если представить 6/6 как C(3, 1), а 1/6 как C(3, 3) и произвести аналогичные действия, то вместо них получим 1/1! и 1/3!, то есть P-беспор = 1 - (1/1! - 1/2! + 1/3!), а чтобы получить число всех вариантов беспорядков, надо умножить (из формулы вероятности) P-беспор на n! — вот мы и пришли к формуле, которую записали выше.
И кажется, в ходе решения Бернулли первым применил принцип включений-исключений, хотя его еще несколько раз переоткроют — Леонард Эйлер, Адриен-Мари Лежандр, Эжен Каталан, Даниэль Аугусто да Силва. Надо так же упомянуть, что Монмор искал сочетания рекуррентным перебором, "вручную", поэтому не мог считать беспорядки для колод, где карт больше пяти. А Николай Бернулли использовал ту же формулу сочетаний, что и мы — он обнаружил ее в труде своего дяди Якоба Бернулли. Якоб Бернулли много лет писал "Ars Conjectandi" ("Искусство предположений"), но был перфекционистом, постоянно дописывал текст (прямо как я этот пост) и в итоге умер в 1705 году, так и не успев опубликовать свой главный труд — за него это сделал Николай.
Переписка Монмора с Бернулли важна и для теории игр. Вместе с Чарльзом Уолдгрейвом (он был заговорщиком-якобитом и о нем известно в основном из этих писем) они обсуждали стратегию игры "Бедолага" (Задача Уолдгрейва) — в результате последним впервые была предложена стратегия минимакс.
Историческое отступление закончилось.
Теперь имеем числитель и знаменатель для дроби P = 20 * 2 / 720 = 1/18. Это и есть наша вероятность ровно трех совпадений. Как видно, она намного меньше 1/2.
Математическое ожидание
Можно также посчитать, сколько люди будут угадывать в среднем. Для этого надо вычислить математическое ожидание. Сделаем это с помощью метода индикаторных случайных величин — такая величина, которая показывает, произошло событие или нет. То есть, если пара совпала эта величина будет 1, если не совпала — 0. Для математического ожидания надо значения индикатора умножить на его вероятность. Для случая, когда найдена конкретная пара это будет 1 * 1/6 + 0 * 5/6 = 1 / 6. Теперь сложим матожидания для всех пар 1/6 + 1/6 + 1/6 + 1/6 + 1/6 + 1/6 = 6/6 = 1. То есть в среднем, если взять результаты всех людей (кто-то угадает 0, кто-то больше) и разделить на число людей, то получим 1.
Так что там с экстрасенсорикой?
Тут наша девушка могла бы обрадоваться — казалось бы в 3 раза превысила среднестатистические показатели. Но надо еще проверить ее результат на статистическую значимость. Для этого надо вычислить P-value — это вероятность получить такой же или еще более высокий результат при условии, что нулевая гипотеза (девушка угадывает случайно) верна.
Для этого в формулу, которой мы пользовались для определения P, надо подставить в числитель не 40 (то есть число исходов с 3-мя угаданными парами), а общее число исходов для 3-х или более угаданных пар: ровно 3 пары — 40 исходов, ровно 4 пары — 15 исходов, ровно 5 — 0 исходов***, ровно 6 — 1 исход. Всего 56 исходов. Теперь подставим в формулу P-value = 56 / 720 ≈ 0.0777. И... К несчастью (или к счастью) для девушки, статистически значимым считается значение P-value ниже 0.05 — то есть, если бы она угадала 4 пары, то можно было бы о чем-то говорить. А так, это ей просто ну оооооочень сильно повезло. Хотя одного эксперимента, в любом случае, было бы недостаточно.
P. S. Кстати, интересный момент. В статье про беспорядки в википедии в абзаце про задачу о письмах ("если n писем случайным образом положить в n различных конвертов, то какова вероятность, что какое-нибудь из писем попадёт в свой конверт") написано: "ответ почти не зависит (при n ≥ 5) от количества писем и конвертов и примерно равен константе 1-e^-1 ≈ 0,63212". То есть вероятность угадать хотя бы одну пару фото и био из любого их числа, если оно больше 5 (хоть 6 как у нас, хоть миллион), будет близка к 0,63212.
А теория вероятностей меня похоже не отпускает. Переехал на новую квартиру и вокруг моего дома попадается много автомобилей с номерами либо из трех одинаковых цифр, либо вида "001, 002...". Ну то есть каждый день встречаю рядом с домом по пять таких припаркованных автомобилей (из пары десятков). И по-моему не все из них жильцы. Даже шестерка жигули с номером 555 попалась.
P. P. S. Я далеко не Савватеев, поэтому замечания приветствуются=)
* Психологом, предложившим такую проверку девушке, был Андрей Курпатов
** Наткнулся, когда писал пост, на вопрос на math.stackexchange: "I'm looking for the method by which the partial derangement formula D(n,k) was derived. I can determine the values for small values of N empirically, but how the general case formula arose still alludes me." То есть человек спрашивал, как вывели формулу частичных беспорядков — монография Монмора и переписка с Бернулли ему наверное помогли бы это понять (займусь-ка некропостингом). Интересно, что эту задачу позже независимо решил (и усложнил) тогда еще 23-летний Эжен Каталан, и только уже перед публикацией своей статьи D'un Problème de Probabilité, relatif au Jeu de rencontre (оригинал статьи на фр.) узнал, что он далеко не первый — после Монмора и Бернулли ею занимался Эйлер.
*** Для меня это было контринтуитивно — исходов для 5 (или n-1) элементов — 0, а для 6 (или n) — 1. Но по условию задачи, не просто 5 элементов по своим позициям должны расположиться, а оставшийся 1 элемент должен занять не свою. Если ты пять биографий угадал, шестая угадывается автоматически.



















