ЗАДАЧА 11.15. Одномерное «истинное» блуждание без самопересечений

Одномерное ИББС соответствует пешеходу, который может «перескакивать» в один нз двух соседних узлов с вероятностью, зависящей от числа уже происшедших посещений этих узлов. Предположим, что в момент времени t пешеход находится в i-м узле. Он уже посетил (i + l)-fi узел rt(.+] раз н (i-l)-fl узел и ^ раз. Тогда вероятность того, что на шаге г + 1 пешеход перепрыгнет в (i + l)-fi узел, равна

Вероятность    скачка    в    (i-l)-fi    узел    составляет    Р.. = \-Р ..

J           1-1 1+1

Параметр   g   представляет   меру   «желательности»   избежать данного

пути. На рис. 11.11 показаны несколько первых шагов типичного ИББС. Основной рассматриваемой величиной является показатель степени V. Нам известно, что g = 0 соответствует обычному случайному блужданию с V = 1/2, а предельное значение g —* со соответствует блужданию без  самопересечения.   Каково  значение  V для

одномерного блуждания без самопересечения? Отличается ли это значение V для любого конечного g от указанных двух предельных случаев? Ниже мы исследуем эти вопросы.

а.         Напишите программу моделирования методом Монте-Карло одномер-ного ИББС. Предусмотрите запоминание числа посещений каждого уз-ла. На каждом шаге вычислите вероятность Р скачка вправо. Сгене-рируйте случайное число г и сравните его с Р. Если г £ Р, тосдвиньте пешехода вправо, в противном случае —влево. Используйтеодну н ту же последовательность случайных чисел для сравненияпутей ИББС при g = 0.1 и обычного случайного блуждания (g = 0).

б.         Вычислите <АХд^, где ж—расстояние пешехода от начальной точ-ки, как функцию от числа шагов N. Постройте в дваждылогарифми-ческом масштабе график зависимости <А*д,> от N н оцените показа-тель степени V. Отличается ли показатель степени V от соответст-вующих значений V для случайного блуждания н блуждания без само-пересечений? Приемлемыми значениями параметров являются g = 0.1и N - 1000 шагов. Для получения качественных результатов вычис-ляются средние по 100 испытаниям. Для сравнения можно обратитьсяк работе Бернаскони н Пьетронеро, где приведены результатывычислений для N = 10 000 шагов н 1000 испытаний; уточненные ре-зультаты для g = 2 получены для 200 000 шагов и 10 000 испытаний.

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