Теперь давайте обсудим, что такое случайные блуждания. Пусть у нас есть какой-то граф, например, неориентированный. Давайте рассмотрим какую-то фиксированную вершину, например, вершину A. Давайте делать дальше следующее — перейдем случайно и равновероятно в одного из ее соседей, в данном случае у нас получилось, что мы перешли в вершину F. Дальше мы повторим такой же переход несколько раз, из F мы перешли в C, тоже случайно выбрали соседа и перешли, дальше из C мы перешли в A, опять же случайно выбрав соседа, из A перешли в B случайным выбором соседа, из B тоже у нас есть три варианта, случайно перешли — получилось D. Такой процесс называется случайным блужданием. Давайте посмотрим, какова вероятность получить такой путь. По сути, у нас случайное блуждание дает путь в графе, но он получается случайным образом. Какая вероятность у нас получить ровно такой путь? На первом шаге мы начинали с вершины A, и вероятность перейти в вершину F была равна одной трети, у нас три варианта, поэтому вероятность перейти в точности в вершину F — одна треть. Дальше, на втором шаге, вероятность перейти в вершину C — это одна четверть, у нас теперь четыре соседа, мы берем случайного, вероятность будет одна четверть. На самом деле, видно, что на каждом следующем шаге вероятность перейти в следующую вершину, в конкретную следующую вершину — одна треть. У C три соседа, у A тоже три соседа и у B тоже три соседа, так что дальше будет одна треть. Это некоторое вероятностное распределение, заданное с помощью процесса. И, как мы обсуждали, в такой ситуации нужно вероятности перемножить, перемножаем все это, и получается, что вероятность получить вот ровно такой путь — это один делить на 324. Случайные блуждания можно рассматривать и в ориентированных графах тоже, ничего принципиально не меняется, но есть такая особенность: оказывается, что в ориентированном графе вершины могут быть труднодостижимы для случайных блужданий. То есть если мы хотим дойти из одной вершины в другую, то, в принципе, это может быть возможно (в этом примере, например, граф сильно-связен), но это может занимать довольно продолжительное время. Например, давайте посмотрим, сколько нужно ходить, чтобы из вершины A попасть в вершину F. Давайте посмотрим, что происходит. Из вершины A мы просто сдвигаемся направо с вероятностью один, а из вершины F мы возвращаемся в вершину A с вероятностью один. Но вот на всех остальных шагах мы с вероятностью одна вторая сдвигаемся направо и приближаемся к нашей цели, и с вероятностью одна вторая начинаем все сначала. Тогда, за первые пять шагов, вероятность того, что мы доберемся до вершины F, если мы сделали всего пять шагов, будет единица на два в четвертой. Первый шаг мы с вероятностью один сделаем направо, а во всех остальных нам должно повезти, нам нужно, чтобы мы сдвинулись именно направо. И вероятность каждого такого сдвига — одна вторая, надо их перемножить, получится единица на два в четвертой, то есть одна шестнадцатая. Если у нас такая цепочка длины n (то есть если у нас там n вершин), то вероятность дойти за n шагов будет единица на два в степени n минус один. Первый шаг мы делаем с вероятностью один, а дальше должно каждый раз повезти, и вероятность получается очень маленькая, это действительно очень мало. На самом деле, можно доказать, это не очень сложно, что в среднем нам нужно порядка два в степени n шагов, то есть мы с не очень большой вероятностью доходим прямо за n шагов, а если не получилось, то мы начинаем сначала. Тут не очень сложно доказать, что нам в среднем нужно будет порядка два в степени n шагов, чтобы дойти до вершины F из вершины A. Это на самом деле очень много, то есть если, например, у нас n равно 100, что по меркам графов из приложений совсем немного, то два в степени n уже будет числом, в котором порядка 30 цифр, это очень большое число, это очень много. Конечно, на практике прямо вот такой плохой случай вряд ли встретится, но, тем не менее, полезно помнить, что это в принципе возможно, что такое бывает. Но в неориентированных графах все гораздо лучше. Давайте рассмотрим такой же пример, тут просто сотрем ориентацию со всех ребер. Если у нас длина n, то из A мы попадаем сразу в F за один ход с вероятностью одна n-тая, то есть у нас длина цепочки это n, то есть у нас n плюс одна вершина, то есть из A есть ребра во все остальные вершины, с вероятностью одна n-тая мы сразу попадем в вершину F. Дальше из любой другой вершины мы довольно часто возвращаемся в вершину A, из каждой другой вершины с вероятностью одна треть мы возвращаемся в вершину A и можем повторить попытку. На самом деле, можно показать, что в среднем тут потребуется не очень много шагов, порядка константа на n, чтобы достигнуть F, и здесь C — это некоторая фиксированная константа. Что, на самом деле, здесь важно сразу оговорить? Мы здесь говорим только о средней длине случайного блуждания, мы считаем ее в среднем. Теоретически блуждание может ходить очень долго, и, в принципе, даже бесконечно долго, и так и не достигнуть F, например, просто блуждание может ходить между вершинами A и B, туда-обратно, бесконечно долго. Но вероятность этого очень мала, так что в среднем, тем не менее, получается, что нам хватит порядка n шагов умножено на какую-то константу. Вот такой пример, чуть сложнее, давайте его тоже рассмотрим. У нас здесь вершины просто расположены в цепочку и больше никаких ребер нет. И в нем нам потребуется порядка n квадрат шагов. На самом деле, оказывается, что всегда для неориентированных графов, если они связные, и граф на вершинах, в среднем окажется достаточно числа шагов, полиномиального от размера графа, то есть полином от n. Это, конечно, гораздо меньше, чем два в степени n, который мы видели для случая ориентированных графов. Давайте еще также скажем, что, на самом деле, мы также можем рассматривать неравновероятные случайные блуждания, и тогда у нас вероятности переходов из текущей вершины в ее соседей могут быть разными для разных соседей, то есть мы можем задать разные вероятности и переходить в разных соседей с разной вероятностью. Это позволяет, например, учитывать какие-то количественные характеристики связей между вершинами.
