Решение задачи о вероятности для последовательности 3Blue1Brown (без ИИ)

Давайте попрактикуемся в аналитическом мышлении на примере задачи на теорию вероятностей.

Делиться

Зачем я в свободное время возился с решением глупой задачи по теории вероятности, когда мог бы просто листать ленту новостей? Потому что я стараюсь оставаться в тонусе в этот уникальный период, когда мы можем передать большую часть критического мышления генеративному искусственному интеллекту. Если вы читаете статьи на TDS, то, вероятно, мы с вами разделяем эту цель.

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

Постановка задачи

Приведённый ниже короткий ролик даст вам наилучшее представление о теме, но я кратко расскажу о её структуре здесь в качестве дополнения.

Представьте, что у нас есть коробка с несколькими нитками внутри. Мы случайным образом выбираем конец одной нити, а затем случайным образом выбираем конец другой нити. Затем мы связываем концы вместе. Может произойти одно из двух: (1) концы окажутся от разных нитей, и у нас получится одна, более длинная нить, или (2) второй конец окажется от той же самой нити, которую мы выбрали изначально, и их связывание образует петлю.

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

Проблема заключается в том, сколько циклов, по нашим ожиданиям, создаст этот процесс? Или, говоря менее точно, но более практично: если мы повторим этот процесс много раз, каково будет среднее количество циклов, которые будут созданы?

Основные замечания по проблеме

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

Наблюдение №1

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

Наблюдение №2

В каждом раунде количество строк в окошке уменьшается на одну, независимо от обстоятельств. Если образуется петля, строка, создавшая эту петлю, удаляется. Если образуется более длинная строка, две строки объединяются в одну, уменьшая количество строк в окошке на 1.

Наблюдение №3

Количество вытягиваний не является случайной величиной. В каждом раунде из ящика удаляется строка независимо от результата (наблюдение №2). В каждом раунде происходит два вытягивания, поэтому количество раундов будет равно количеству строк. Например, если у нас 10 строк, то у нас будет 20 случайных вытягиваний в 10 раундах. Обратите внимание, что в последнем «раунде» остается только одна строка, и это всегда приводит к циклу.

Наблюдение №4

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

Следует отметить, что если бы нас интересовали такие метрики, как ожидаемая длина окружности круга, это наблюдение было бы неверным. Длина строк (и, следовательно, длина окружности петель) зависит от предыдущих раундов.

Итак, после этих наблюдений, давайте перейдем к тому, как мы можем решить проблему!

Решение методом «грубой силы»

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

Для решения этой задачи мы можем построить дерево вероятностей и вручную рассчитать ожидаемое количество циклов. Здесь мы это подробно рассмотрим.

Это неуклюжее, но вполне приемлемое решение для небольшого количества строк. В видео Грант специально указывает на число 50 строк, которое нужно найти (для этого потребовалось бы дерево с 250 листьями!). Он сделал это, чтобы подтолкнуть свою аудиторию к отказу от метода перебора и поиску более разумных решений.

Давайте попробуем придумать более разумный подход.

Решение «разделяй и властвуй»

Тщательно проанализировав характеристики случайного процесса, мы поняли, что каждый раунд случайных выборок независим от других (наблюдение № 4). Благодаря этому свойству мы можем рассчитать ожидаемое значение отдельных выборок, а затем посмотреть, сможем ли мы найти способ объединить несколько отдельных выборок для решения задачи.

Ожидаемое количество петель из одного цикла рисования

Мы уже поняли, что первый случайный розыгрыш не очень важен (наблюдение №1) – всё дело во втором розыгрыше.

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

Представьте, что в коробке у нас 4 нити, что дает нам 8 концов. После выбора первого конца мы не можем выбрать его снова, поэтому у нас есть 7 концов, из которых мы можем выбирать. Один из 7 концов образует петлю, остальные концы не образуют петлю. Изображение ниже иллюстрирует схему более наглядно, чем объяснение чисел.

Таким образом, вероятность образования цикла составляет 1/7, а вероятность отсутствия цикла — 6/7, что дает 1/7 ожидаемого количества циклов (1*1/7 + 0*6/7).

Давайте обобщим это на формулу, используя количество строк в качестве входных данных. Если S — количество строк, то количество концов равно 2S (два конца на строку). После первого выбора мы можем выбрать из 2S-1 концов, и только один из этих концов приведет к образованию петли. Таким образом, формула для ожидаемого количества петель — 1/(2S-1).

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

Теперь, когда мы создали формулу для расчета ожидаемого количества циклов за один раунд, давайте разберемся, как объединить несколько раундов. Благодаря наблюдению №4 (независимость раундов для подсчета циклов) и наблюдению №2 (детерминированное количество раундов) мы можем просто сложить ожидаемое количество циклов из каждого раунда. Конечно, нам нужно обновить количество строк для каждого раунда — мы можем сделать это с помощью функции суммирования.

Теперь, когда у нас есть формула, завершить задачу так же просто, как подставить 50 вместо S, что даст нам примерно 2,94 цикла – миссия выполнена!

Решение Монте-Карло

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

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

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

 from monte_carlo_funcs import create_strings, select_ends, tie_ends # Run the Monte Carlo list_of_circles = [] num_strings = 50 num_simulations = 10000 if __name__ == "__main__": for _ in range(0, num_simulations): # create the simulated starting box of strings strings = create_strings(num_strings) # start circle counter for this simulation circle_counter = 0 # draw from the box until there are no more strings left while len(strings) > 0: end_1, end_2, strings = select_ends(strings) strings, circle_bool = tie_ends(strings, end_1, end_2) circle_counter += circle_bool # add the number of circles that counts number of circles for each round list_of_circles.append(circle_counter) print(np.mean(list_of_circles))

Когда я запустил этот процесс (результат будет немного меняться каждый раз), я получил 2,95 – очень близко к правильному значению 2,94. Это подчеркивает важный момент: метод Монте-Карло – хороший способ получить приблизительную оценку, но гибкость достигается за счет точности.

Усложнение проблемы

Давайте уделим немного времени тому, чтобы показать, в чем преимущество метода Монте-Карло, значительно усложнив задачу. Что если мы изменим задачу с вычисления ожидаемого количества витков на вычисление ожидаемой средней длины окружности витков? Эта задача гораздо сложнее, поскольку она зависит от взаимозависимостей между каждым раундом случайных выборок.

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

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

Заключение

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

Хотя вам, как специалисту по работе с данными, не придётся вычислять ожидаемое количество итераций в блоке строк (по крайней мере, это крайне маловероятно), вы часто будете сталкиваться с ситуациями, когда путь к решению не сразу очевиден. Глубокое понимание проблемы, её разбиение на более мелкие компоненты и тщательная разработка индивидуального решения — это навыки, которые напрямую применимы в реальной работе в области анализа данных.

Яром Юлет Посмотреть все от Яром Хулет

Источник: towardsdatascience.com