Линейность математического ожидания или Typewriter Monkey

"Абсолютно случайным образом ударяя по 

клавишам пишущей машинки, гипотетическая 

обезьяна рано или поздно напечатает одну 

из пьес Шекспира."

Теорема о бесконечных обезьянах

Вы знаете что такое математическое ожидание? Тогда сегодня я вам предлагаю поразмыслить над следующей задачкой по программированию Typewriter Monkey.

На прошлых выходных я участвовал в конкурсе Google Code Jam и единственная задача, которая не далась мне полностью оказалась задача про обезьян с печатными машинками.

Итак, для начала, вкратце об условиях конкурса. Условия задачи описаны в тексте по ссылке выше. Решать задачу можно на абсолютно любом языке программирования. На странице с заданием можно скачать два тестовых набора данных: маленький и большой. Данные в обоих случаях структурированы одинаково, отличие в ограничениях на начальные  условия и количество времени, которое можно потратить на генерирование ответа. 

В нашем случае ограничения следующие:

• Маленький набор данных
• 100 однотипных задач
• 1 ≤ K ≤ 7
• 1 ≤ L ≤ S ≤ 7
• 4 минуты на генерирование корректного ответа
• Большой набор данных
• 100 однотипных задач
• 1 ≤ K ≤ 100
• 1 ≤ L ≤ S ≤ 100
• 8 минут на генерирование корректного ответа

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

Маленький набор данных

Здесь всё просто: ограничения на данные достаточно низкие, а 4х минут хватит с лихвой для того чтобы сгенерировать все возможные строки длинной в 7 (или меньше) символов из предложенного алфавита и в каждой из них посчитать количество вхождений искомой строки. Максимум находится во время подсчёта, а мат. ожидание по старинной формуле:

, где х – кол-во вхождений искомой строки, а Р(х) – вероятность появления строк с ровно х вхождениями искомой строки.

Viva Brute force!

Большой набор данных

Здесь всё сложнее и именно этот набор послужил причиной для статьи. Brute Force для строк из 100 символов из большого алфавита займёт слишком много времени и даже близко не уложится в 8 минут. Приходится придумывать более изощрённые аналитические решения.

Подсчитать максимум не представляется сложным, а вот ожидаемое значение (или мат. ожидание) гораздо проблематичнее. Как ни странно всё начинается с той же самой формулы мат. ожидания: E[x] = Σ x*P(x)

Попробуем немного преобразовать равенство:

Σ x*P(x) = Σ x*COUNT(кол-во всевозможных строк, в которых ровно x вхождений искомой строки) / COUNT(все возможные строки, которые могут генерировать обезьяны)
В нашем случае всё логично – вероятность можно выразить подсчётом возможных исходов.

Как можно легко убедится: COUNT(все возможные строки, которые могут генерировать обезьяны) = K^S

Итого: Σ x*P(x) = 1/K^S * [Σ x*COUNT(кол-во всевозможных строк, в которых ровно x вхождений искомой строки)]

К сожалению, посчитать COUNT(кол-во всевозможных строк, в которых ровно x вхождений искомой строки) не очень легко, особенно с учётом того факта, что строки могут пересекаться (смотри условие задачи).

Тем не менее, если пойти дальше и заметить, что Σ x*COUNT(кол-во всевозможных строк, в которых ровно x вхождений искомой строки) есть ни что иное, как кол-во ВСЕХ появлений искомой строки среди всех возможных строк, которые генерируют обезьяны, то жизнь становится веселее.

Получается: Σ x*P(x) = 1/K^S * COUNT(кол-во всевозможных появлений искомой строки)

Уже интересно. Осталось понять как лучше посчитать кол-во всех появлений искомой строки. Легче всего это сделать разбив задачу на кусочки, а именно посчитать сколько раз искомая строка может появится в самом начале строки длины S, сколько раз начиная с позиции 1, сколько раз начиная с позиции 2 и т.д.

Т.е. COUNT(кол-во всевозможных появлений искомой строки) = Σ COUNT(кол-во искомых строк на позиции i)

Вероятность появления искомой строки на разных позициях одинакова, а кол-во позиций с которых может начинаться искомая строка ровно (S-L+1), т.о.
Σ COUNT(кол-во искомых строк на позиции i) = (S-L+1) * COUNT(кол-во искомых строк на позиции 0)

Вернёмся к нашему равенству:
Σ x*P(x) = 1/K^S * COUNT(кол-во всевозможных появлений искомой строки) =
= (S-L+1)/K^S * COUNT(кол-во искомых строк на позиции 0)

Заметим, что
COUNT(кол-во искомых строк на позиции 0) = P(набора искомой строки обезьянами) * K^L * K^S-L

, где первые L символов образуют исходную строку, а оставшиеся S-L символов – любые из заданного алфавита.

Итого:
Σ x*P(x) = (S-L+1)/K^S * COUNT(кол-во искомых строк на позиции 0) =
= (S-L+1) / K^S * P(набора искомой строки обезьянами) * K^L * K^S-L =

= (S-L+1) * P(набора искомой строки обезьянами)

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

Bingo!

P.S. По сути мы с вами сегодня вывели одно из свойств математического ожидания – линейность.

item