Несколько дней назад я узнал от своих друзей, что такое «Теорема о бесконечности обезьяны».

Что об этом говорят в Интернете:

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

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

Математика

Хорошо, давайте перейдем к основам. Сказанная обезьяна печатает на английской клавиатуре. Игнорируйте пока знаки препинания или цифровые клавиши (но не пробел).

В современном английском алфавите 26 букв. Эти буквы разной длины составляют английские слова. Основываясь на списке слов, которые я использовал для этого теста, насчитывается 7 186 четырехбуквенных слов. Если пишущая обезьяна случайным образом нажимает четыре клавиши на клавиатуре, то какова вероятность того, что это подходящее четырехбуквенное слово из этого списка?

Это общее количество четырехбуквенных слов в списке слов, разделенное на общее количество четырехбуквенных перестановок, которые можно получить из 26 букв.

Эта вероятность оказывается 7186 / (26! / 22!) = 0,02. Обезьяна имеет 2% шанс составить значащее четырехбуквенное слово, если случайно нажимает четыре клавиши.

Исследовать и создавать сценарии

Я нашел список английских слов в текстовом файле здесь. Я не уверен, что это так же хорошо, как список слов из английского словаря, но служит цели для этого теста. Используемый файл - words_alpha.txt. После загрузки всех слов в список я разделил их по количеству букв в каждом слове.

word_counts = {}
for i in range(1,max_len+1):
    word_counts[i] = []
for i in range(len(words)):
    for key in word_counts.keys():
    if len(words[i]) == key:
        word_counts[key].append(words[i])

Вы когда-нибудь задумывались о распределении слов из разного количества букв? Вот как это выглядит:

Следующим шагом является случайное генерирование последовательностей букв для заданной длины символа. Вы говорите, что генерируете последовательность из 4 символов, вы получаете на выходе 4 символа. Функция будет продолжать случайным образом выбирать буквы из алфавита до тех пор, пока не будет достигнут предел количества символов (ввод).

def generate_string(n, max_len=max_len):
    word = []
    if n <= max_len:
        for i in range(n):
            word.append(word_counts[1][np.random.randint(0, len(word_counts[1]))])
            #word_counts[1] holds the alphabet
    else:
        print("Letter count exceeds")
    return ''.join(word)
  • max_len выше - это наибольшее количество символов в слове в списке слов, полученном из Интернета. Был 31 год!
  • Слово из 31 буквы было: дихлордифенилтрихлорэтан.

Как видите, сгенерированная случайная последовательность не будет словом. Чтобы найти подходящее слово, потребуются некоторые испытания. Чтобы включить это, я продолжаю генерировать строки, пока не найду совпадение.

def generate_word(word_list, n):
    gen_word = ''
    count = 0
    while gen_word not in word_list:
        gen_word = generate_string(n)
        count += 1
    return gen_word, count

Это оказалось забавным упражнением. Слова из двух, трех или четырех букв казались легко предсказуемыми. Гистограмма выше показывает, что количество слов увеличивается с длиной символа до 9 символов, а затем уменьшается. Это падение на самом деле не увеличивает вероятность совпадения случайной строки; чем больше символов в слове, тем меньше вероятность.

Вот пример:

In [11]:
s = generate_word(four_letter_words, 4)
print(s[0])
print("Number of attempts: {}".format(s[1]))
Out [11]:
girl
Number of attempts: 23

Здесь я пытаюсь записать количество попыток найти первое совпадение. Полагаю, это что-то вроде онлайн-знакомств. Я сделал это для слов из 2, 3, 4, 5 и 6 букв, по тысяче раз каждое, и записал количество попыток для первого успешного совпадения.

%%time
attempts = {}
for i in range(2,7):
    start = timeit.default_timer()
    attempts[i] = []
    for j in range(1000):
        s = generate_word(word_counts[i], i)
        attempts[i].append(s[1])
    stop = timeit.default_timer()
    print("Iterations for letter count of {} complete and loop time elapsed is {}s".format(i, round((stop-start),3)))

Обратите внимание на время вычислений (для вычислительной мощности, которую я могу себе позволить). Как видите, время для первого совпадения экспоненциально увеличивается с увеличением длины символа.

Сколько в среднем требуется попыток, чтобы найти подходящее слово для символов разной длины? Ось «количество попыток» - логарифмическая.

По мере увеличения длины символа увеличивается и количество попыток создать подходящее слово.

Обезьяна могла бы использовать RNN, верно? На дворе 2019 год, но он все еще обезьяна, поэтому продолжает грубую силу случайного нажатия клавиш с целью создания произведения Шекспира.

Теперь, когда мы увидели, как играют части итерации, пришло время добавить в картину немного математики. Мы знаем вероятность успеха, но чтобы быть точными, мы должны учитывать количество итераций, необходимых для достижения успешного совпадения.

Для этого воспользуемся геометрическим распределением вероятностей. Скажем, на этой неделе вероятность дождя составляет 20% каждый день. Вероятность того, что ровно через три дня пойдет дождь, составляет 0,8 * 0,8 * 0,2. Это принцип.

Реализуем это с помощью scipy.stats.geom. Здесь успех действительно означает найти подходящее слово, поэтому окончательная вероятность - это просто сумма, а не вычитаемая из 1.

def calc_permutations(l, n=26):
    return factorial(n)/factorial(n-l)
def calc_probability(nl, npl):
    return nl/npl
def prob_success(k, l):
    p = calc_probability(len(word_counts[l]), calc_permutations(l))
    total = 0
    for i in range(k):
        total += geom.pmf(k, p)
    return total

Быть или не быть

Теперь, чтобы собрать все воедино, я попытаюсь оценить вероятность создания той же последовательности, что и заголовок этого подраздела: «быть или не быть» и функция ниже сделал бы это.

def generate_sentence_by_word(string):
    sentence = string.split()
    print("Sentence array: {}".format(sentence))
    letter_count = [len(w) for w in sentence]
    print("Letter count array: {}".format(letter_count))
    generated_sentence = []
    sentence_attempts = []
    success_probs = []
    for i in range(len(letter_count)):
        s = generate_word([sentence[i]], letter_count[i])
        if s[0] == sentence[i]:
            generated_sentence.append(s[0])
            sentence_attempts.append(s[1])
            success_probs.append(prob_success(s[1], letter_count[i]))
            print("Generated word {} in {} attempts".format(s[0], s[1]))
    print("Generation complete: {}".format(" ".join(generated_sentence)))
    return generated_sentence, sentence_attempts, success_probs

Учитывая, что это заняло всего 5 секунд, представьте обезьяну-киборга, которая может печатать около 8000 слов в секунду. Возможно, вы уже заметили это - небольшая проблема с функцией, описанной выше. Он находит совпадение по слову и затем переходит к следующему. Теорема этого не утверждает. Чтобы подчиняться теореме, сгенерированная последовательность букв (с пробелами) должна точно соответствовать произведению Шекспира в этом порядке.

Предположим, вы даете обезьяне шанс найти совпадение слово за словом даже для сгенерированной выше последовательности. Даже в этом случае вероятность получения правильной последовательности составляет порядка 10 ^ -12 (пико). Это действительно мало. Настолько мал.

Generated word "to" in 314 attempts.
Generated word "be" in 170 attempts.
Generated word "or" in 2215 attempts.
Generated word "not" in 9605 attempts.
Generated word "to" in 125 attempts.
Generated word "be" in 494 attempts.

Ладно.

def generate_full_sentence(string):
    letter_count = [len(w) for w in string.split()]
    print("Letter count array: {}".format(letter_count))
    generated_sentence = []
    count = 0
    while " ".join(generated_sentence) != string:
        for i in range(len(letter_count)):
            generated_sentence.append(generate_string(letter_count[i]))
        count += 1
        if count%10000 == 0:
            print("Trial no {}".format(count))
    return generated_sentence, count

Это несколько раз разбивало мой компьютер! Итак, я создал усиленную виртуальную машину из Google Cloud с 8 процессорами и 52 ГБ оперативной памяти.

Sentence array: ['to', 'be', 'or', 'not', 'to', 'be']
Letter count array: [2, 2, 2, 3, 2, 2]
Trial no 10000
Trial no 20000
Trial no 30000
.
.
.
Trial no 710000
Trial no 720000
.
.
Trial no 1000000

К этому моменту он работал около двух дней, и я его убил. Не повезло после миллиона попыток сгенерировать ту же самую последовательность: «быть или не быть».

Так что я полагаю, что обезьяне действительно потребуется бесконечно много времени, чтобы создать произведение Шекспира. Кажется, оспаривается идея воспроизвести одну и ту же работу - это непостижимо, но математика верна!