🌀 Андрей Марков: человек, который приручил случайность

Настроение сегодня философское, поэтому снова порассуждаем о случайностях. А заодно расскажем о математике, который посвятил изучению этих случайностей годы.

➡️ В начале прошлого века считалось, что если знать прошлое, можно безошибочно предсказать будущее — так думал, например, математик Пьер-Симон Лаплас. Но российский математик Андрей Марков показал, что есть процессы, где только текущее состояние определяет будущее, а прошлое не имеет значения.

Представьте человека, который гуляет по городу. На каждом перекрёстке он бросает монетку, чтобы решить, куда идти: орёл — направо, решка — налево. Куда он попадёт в итоге, зависит не от того, откуда он пришёл, а от его поведения на текущем перекрёстке. Решает момент!

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

❓ Где используют марковские цепи

Марков не подозревал, что его работа ляжет в основу сервисов, которыми пользуемся мы с вами. Например, в популярных поисковиках работает PageRank: это марковская цепь, которая определяет, какие сайты должны быть в топе выдачи. Работает это так:

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

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

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

Другой пример — распознавание речи в Siri и других ассистентах: алгоритмы прогнозируют следующее слово с помощью скрытых марковских моделей.

Никакой магии, только математика 🔮

#как_устроено

🧊Задача о муравье и кубе: сколько нужно шагов?

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

➡️Условие
Допустим, у нас есть куб. У куба 8 вершин и 12 ребер. На одну из вершин этого куба мы посадили муравья. Он начинает двигаться случайным образом: на каждом шаге выбирает одно из трёх соседних рёбер с равной вероятностью и переходит по нему в следующую вершину.

➡️Вопрос
Сколько шагов в среднем понадобится муравью, чтобы добраться до противоположной вершины — то есть до той, которая соединена с начальной диагональю через весь куб?

Делитесь рассуждениями и ответами в комментариях, а мы опубликуем решение уже вечером!

#задача