ЗАДАЧА 11.1. Точный расчет одномерных случайных блужданий

а.         Для N = 3 имеются три блуждания с х = 1 и три блуждания с х == -1 (рис. 11.2). Сколько имеется блужданий для N = 4 с х = О?Как это число связано с числом блужданий для случая х = ±1 v N == 3? Как связано число четырехшаговых блужданий с х = 2 с числомтрехшаговых блужданий с х = 1 и х = 3? Получите точное соотноше-ние между числом /V-шаговых блужданий со смещением х и числом(N - 1)-шаговых блужданий со смещением х ± 1. Используя получен-ное соотношение, определите число возможных блужданий для задан-ного х и значений N = 4 к N = Ъ, а также точные результаты дляPN(x), <Хд,> и <Ах^> при N = 4 н N = 5.

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

о

значений JV и Jt.  Вычислите точные значения Р^ (х),  <х^> и <Ах^>

для W от 1 до 8. Используя полученные результаты точного расчета, покажите, что Р ^ (х) можно записать в виде

где (N + ^x) и (Af-^x) — число шагов вправо и влево соответственно.

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

Ниже приведен пример программы моделирования методом Монте-Карло одномерного случайного блуждания; в подпрограмме walk реализован алгоритм случайного блуждания.

Для вычисления распределения вероятности Р^(х) необходимо рассмотреть большое число испытаний и зафиксировать относительное число появлений пешехода в точке с координатой х после N шагов. От-дельно вычислять в программе <х^> и <АХд,> не нужно, поскольку эти величины можно получить из Р^(х). Однако во многих приложениях величины <Хд,> и <Лх^> уже достаточно информативны и нет необходимости вычислять распределение PN(x), требующее большого объема памяти.