В научном мире существует множество исследований, разработок и теорий, важность которых невозможно недооценить. Однако это не значит, что ученые не любят задаваться вопросом «а что если?». Особенно это касается математиков и расчета вероятности того или иного события. Ярким примером является теорема о бесконечных обезьянах, утверждающая, что обезьяна клацающая по клавишам печатной машинки (естественно, в случайном порядке) рано или поздно сможет напечатать полное собрание сочинений Уильяма Шекспира, если имеется бесконечное число обезьян или же одна, но очень настойчивая, трудолюбивая и вполне бессмертная обезьяна. Ученые из Технологического университета Сиднея (Австралия) решили провести расчеты, дабы установить, сколько времени все таки потребуется на реализацию данного труда. Как именно проводились расчеты, и что они показали? Ответы на эти вопросы мы найдем в докладе ученых.

Основа исследования

Теорема о бесконечных обезьянах впервые появилась в 1914 году в труде Эмиля Бореля «Статистическая механика и необратимость» и в его книге «Случай». Обезьяны были выбраны не из большой любви математика к этим животным, а в качестве абстрактного генератора случайных чисел. В труде Бореля указывается, что даже если миллион обезьян будут печатать по 10 часов в день, то вероятность написания ими текстов, полностью совпадающих со всеми книгами всех библиотек мира, крайне мала. Однако вероятность все же есть и она больше, чем вероятность того, что законы статистической механики нарушатся даже незначительно.

В книге «Природа физического мира» (1928 год) за авторством Артура Эддингтона написано следующее описание данной теоремы:

Если я позволю своим пальцам праздно блуждать по клавишам пишущей машинки, может случиться, что у меня получится напечатать какое-нибудь осмысленное предложение. Если армия обезьян будет бить по клавишам пишущих машинок, они могут напечатать все книги Британского музея. Шанс, что они сделают это, определённо больше, чем вероятность того, что все молекулы соберутся в одной половине сосуда.

По сути, данная теорема существует для демонстрации того, что некоторые физические процессы крайне маловероятны. У некоторых вероятность даже меньше, чем вероятность того, что обезьяна напечатает собрание сочинений Шекспира. Следовательно, такие физические процессы можно считать невозможными.

Математически доказательство теоремы является простым следствием леммы Бореля–Кантелли. Проще говоря, когда событие (например, обезьяна, печатающая заданную строку символов) происходит в заданном испытании с конечной ненулевой вероятностью, то вероятность того, что событие никогда не произойдет, стремится к нулю, поскольку число независимых испытаний стремится к бесконечности, каким бы невероятным ни было событие в отдельном испытании.

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

Математическая база исследования

Как отмечают ученые, первым делом необходимо было сформулировать предположение модели. Ученые предположили, что клавиатура содержит K различных клавиш. Каждая печатающая обезьяна нажимает N клавиш (по одной за раз) так, что каждая клавиша выбирается с равной вероятностью при каждом нажатии, независимо от выбора всех других клавиш. Есть целевая последовательность текста длиной L символов. Сначала была рассмотрена комбинаторика моно-обезьяны, т. е. только одна обезьяна печатает за раз.

С N нажатиями клавиш, каждое из которых является одним из K различных символов, существует K^N различных упорядоченных последовательностей, которые можно набрать. Теперь необходимо установить, сколько из этих (равновеликих) последовательностей содержат L последовательных символов из целевой последовательности хотя бы один раз.

Рассматривая последовательность длины L как один «символ», необходимо поместить этот один «символ» в одно место в строке из N − L + 1 символов. Оставшиеся N — L символы могут быть любыми из K возможных символов. Таким образом, есть (N — L+1)K^N-L способов, чтобы это произошло.

Однако это приводит к пересчету, поскольку возможно, что целевая последовательность длины L появляется более одного раза в N нажатиях клавиш. Например, если искать последовательность HH в череде из пяти подбрасываний монеты (т. е. H или T), вышеприведенный метод будет учитывать результат HHTHH дважды, поэтому нужно исправить этот двойной подсчет. Чтобы рассмотреть степень пересчета, сначала необходимо рассмотреть последовательность длины L как один «символ». Нужно поместить этот один «символ» дважды в строку из N − 2L + 2 символов. Оставшиеся N − 2L символы могут быть любыми из K возможных символов.

Следовательно, имеется следующее число способов, чтобы это произошло:

где

обозначает биномиальный коэффициент.

Однако вычитание этих значений не позволяет подсчитать последовательность, в которой целевая строка появляется три или более раз. Применяя принцип включения-исключения, была получена вероятность того, что последовательность из N нажатий клавиш содержит целевую последовательность длины L хотя бы один раз:


где ⌊ N/L ⌋ обозначает пол N/L, т. е. наибольшее целое число, меньшее или равное N/L, поскольку это максимальное количество раз, когда может появиться строка длины L. Это также предполагает, что множественные вхождения не перекрываются, т. е. последнее слово(а) первого появления целевой строки не являются также первым(и) словом(ами) второго появления целевой строки. В действительности, с обычным текстом и правильной пунктуацией, это почти наверняка будет так.

Результат в уравнении выше дает точную вероятность набора целевой последовательности длины L за N нажатий клавиш. Однако это не поддается вычислительной обработке для многих практических целей, например, когда L очень велико. В таких случаях можно вывести приближение для случая 1 ≪ N ≪ K^L.

Пусть P(N, L) — вероятность того, что последовательность из N нажатий клавиш не содержит целевую последовательность длины L. Следовательно, для больших значений L и K получаем:



Это фактически эквивалентно усечению ряда в уравнении №1 на его ведущем члене. Из этого можно получить разложение в ряд Тейлора P(N + ΔN, L) ≈ P(N, L) − ΔN(1/K^L).

Таким образом, видно, что, приближая N к непрерывной переменной, получается, что количество нажатий клавиш до первого появления целевой строки длины L масштабируется как экспоненциально распределенная случайная величина с параметром скорости 1/K^L.

Из этого можно легко распространить результат на многообезьянью комбинаторную задачу. При M > 1 обезьянах, работающих независимо друг от друга, одновременно печатающих тем же способом, что и одна обезьяна в предыдущей задаче, получаем, что минимум набора независимых экспоненциальных случайных величин сам по себе является экспоненциальной случайной величиной с параметром скорости, равным сумме всех параметров скорости.

Это также можно увидеть, заметив, что для экспоненциальной переменной с параметром скорости 1/K^L вероятность того, что одна обезьяна не сможет произвести целевую строку до момента времени N, приблизительно равна e^−(N/KL), следовательно, вероятность того, что M независимо работающих обезьян не произвели строку, является произведением M таких вероятностей, поэтому:



Отсюда становится известно, что время, необходимое для того, чтобы M (1 < M ≪ K^L) обезьян впервые набрали целевую строку, масштабируется как экспоненциальная случайная величина с параметром скорости M/K^L, поэтому ожидаемое количество нажатий клавиш до того, как будет сгенерирована строка, составляет приблизительно K^L/M.

Результаты расчетов

Как отмечают ученые, чтобы количественно оценить вероятности или ожидаемые временные шкалы, необходимо сделать несколько дополнительных предположений. Допустим, что клавиатура содержит K = 30 различных клавиш, охватывающих все буквы английского языка, а также некоторые общие знаки препинания. Для расчетов временной шкалы предполагается, что обезьяна-машинистка нажимает одну клавишу в секунду каждую секунду дня. Поскольку шимпанзе являются ближайшими родственниками человека среди обезьян, ученые сосредоточились на них как на изучаемом виде. Также предполагается продолжительность рабочей жизни шимпанзе равной 10⁹ секунд (чуть более 30 лет), а тепловая смерть вселенной — через 10¹⁰⁰ лет после начала эксперимента. Предполагая, что текущая популяция около 200000 шимпанзе останется постоянной до конца вселенной, следовательно, имеем максимум около 10¹⁰⁰ × 3.2 × 10⁷ × 2 × 10⁵/ (10⁹) = 6.4 × 10¹⁰³ рабочих жизней шимпанзе, поскольку в году примерно 3.2 × 10⁷ секунд. Не учитывается размножение или количество пищи, необходимое для того, чтобы популяция сохранялась без снижения.


Таблица №1

Таблица выше количественно определяет ожидаемое количество нажатий клавиш, пока случайно печатающая обезьяна впервые не произведет заданную целевую строку, для нескольких различных строк в диапазонах сложности от одного слова «Бананы» до полного собрания сочинений Уильяма Шекспира. Они визуализированы ниже в логарифмической шкале, как это требуется для значений, охватывающих такие сильно различающиеся порядки величин. Вероятности численно оцениваются для трех временных шкал: в пределах продолжительности жизни одного шимпанзе, в пределах продолжительности жизни всех шимпанзе, где не происходит размножения для продления популяции, и в пределах тепловой смерти вселенной, предполагая, что популяция обезьян сохраняется до этого времени.


Изображение №1

Из этого видно, что все, кроме самых тривиальных фраз, на самом деле, почти наверняка никогда не будут созданы в течение жизни нашей вселенной. Существует много порядков разницы между ожидаемым количеством клавиш, которые будут случайно нажаты, прежде чем будут воспроизведены произведения Шекспира, и количеством нажатий клавиш, пока вселенная не схлопнется в термодинамическое равновесие (график ниже). Невероятно, что даже с возможным улучшением скорости печати или увеличением популяции шимпанзе эти порядки величины могут быть охвачены до такой степени, что труд обезьяны когда-либо станет жизнеспособным инструментом для разработки письменных произведений чего-либо, выходящего за рамки тривиального. Таким образом, ученые отвергают выводы из теоремы о бесконечных обезьянах как потенциально вводящие в заблуждение в нашей конечной вселенной. Эта оценка фактически противоречит одному из самых известных фрагментов народной математики, но также твердо помещает теорему о бесконечных обезьянах в один ряд с другими кажущимися парадоксами с противоречивыми результатами в конечных и бесконечных случаях.


Изображение №2

Для более детального ознакомления с нюансами исследования рекомендую заглянуть в доклад ученых.

Эпилог

Вывод авторов исследования таков — учитывая правдоподобные оценки продолжительности жизни вселенной и количества возможных обезьян-машинисток, это все еще оставляет огромные порядки разницы между доступными ресурсами и теми, которые требуются для нетривиальной генерации текста. Проще говоря, нет, обезьяна не сможет напечатать полное собрание произведений Шекспира, даже если она будет трудиться неустанно до скончания времен. Однако, данная теория все же имеет свой поучительный смысл, так как наглядно показывает насколько бывает мала вероятность того или иного процесса или события.

Немного рекламы

Спасибо, что остаётесь с нами. Вам нравятся наши статьи? Хотите видеть больше интересных материалов? Поддержите нас, оформив заказ или порекомендовав знакомым, облачные VPS для разработчиков от $4.99, уникальный аналог entry-level серверов, который был придуман нами для Вас: Вся правда о VPS (KVM) E5-2697 v3 (6 Cores) 10GB DDR4 480GB SSD 1Gbps от $19 или как правильно делить сервер? (доступны варианты с RAID1 и RAID10, до 24 ядер и до 40GB DDR4).

Dell R730xd в 2 раза дешевле в дата-центре Maincubes Tier IV в Амстердаме? Только у нас 2 х Intel TetraDeca-Core Xeon 2x E5-2697v3 2.6GHz 14C 64GB DDR4 4x960GB SSD 1Gbps 100 ТВ от $199 в Нидерландах! Dell R420 — 2x E5-2430 2.2Ghz 6C 128GB DDR3 2x960GB SSD 1Gbps 100TB — от $99! Читайте о том Как построить инфраструктуру корп. класса c применением серверов Dell R730xd Е5-2650 v4 стоимостью 9000 евро за копейки?