Случайное блуждание: исследователи ответили на один из давних вопросов математики

Почему некоторые случайные блуждания обладают «памятью»?

Элементы случайного блуждания можно встретить практически везде: от биологии до видеоигр. Допустим, у нас есть плоскость с размеченной сеткой с началом координат (0,0). Случайное блуждание – это процесс перемещения, при котором мы можем шагнуть в любую из 4 возможных точек из начала координат, причем решение, куда сделать шаг, принимается случайным образом. Если вы хоть раз играли в видеоигры с самостоятельно создаваемым контентом, например в Майнкрафт, Ферму (Stardew Valley), Spelunky и Dwarf Fortress, вы точно сталкивались со случайным блужданием в ​​виде подземелья или территории, созданной программистами в характерной форме.

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

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

^{Пять восьмиступенчатых случайных блужданий из центральной точки.} 

Именно эту разницу Омер Тамуз и его студенты Джошуа Фриш, Яир Хартман и Пуя Вахиди Фердоуси исследовали и, в конце концов, объяснили. Команда математиков из Калифорнийского технологического института совместно с коллегой из израильского университета имени Бен-Гуриона пришли к своему открытию однажды вечером. Один из авторов решения, Омер Тамуз, изучающий экономику и математику, использовал теорию вероятностей и эргодическую теорию в качестве связующего звена – прогрессивный и смешанный подход, который открыли математики, лауреаты Абелевской премии 2020 года.

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

Вот что сказал Омер Тамуз в своем заявлении:

«Допустим, у вас есть два общества. Одно из них совершает технологические открытия, а другое страдает от стихийного бедствия. Сохранятся ли различия между ними навечно, или они в конечном итоге исчезнут, и мы забудем, что у первого когда-то было преимущество? Возвращаясь к случайным блужданиям, давно известно, что есть пути, у которых есть воспоминания, а есть те, у которых они стираются. Но было не совсем ясно, какие группы путей обладают памятью, а какие нет. Главный вопрос, который стоял перед учеными, – что заставляет определенную группу иметь это самое свойство? На него мы и нашли ответ».

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

Секрет, который открыла команда математиков, – в том, чтобы объединить идеи алгебры и геометрии при описании процесса случайных блужданий и использовать эту связь для исследования. Математики обнаружили, что случайные блуждания, которые соответствуют критерию, основанному на векторной геометрии, совпадают со всеми остальными. «Мы были рады наконец найти решение математического вопроса, который оставался открытым многие годы», – подчеркнул Пуя Фирдоуси.