1626435387-5d0ec7dd22f55dfcc65f3209f497fb0b (844202), страница 7
Текст из файла (страница 7)
Поэтому имеется возможность использования «упрощенных» версий функции fξ (x).В частности, часто разумнымбывает предположить, что компоненты вектора ξ = ξ (1) , . . . , ξ (d) являются независимыми (см., например,[14]). Это означает, что плотность fξ x(1) , . . . , x(d) имеет видfξ x(1) , . . .
, x(d) = fξ(1) x(1) × fξ(2) x(2) × . . . × fξ(d) x(d) ,(2.24)т. е. условные плотности из соотношения (2.10) становятся «независимыми» и вся разница между представлениями(2.10) связана толькос порядком умножения плотностей fξ(i) x(i) .37(i)В этом случае каждое выборочное значение ξ0 случайной компоненты ξ (i) можно моделировать согласно своей разумно выбранной (сточки зрения решения проблемы 2.2) плотности fξ(i) x(i) , причем порядок моделирования – произвольный.Однако необходимо всегда помнить, что «удобство» моделирования случайного вектора ξ не всегда означает эффективность(экономичность) соответствующего метода Монте-Карло(алгоритмов 1.1 или 1.2) с оценивателем (монте-карловской оценкой) ζ = q(ξ).Для оптимизации этого метода необходимо минимизироватьзначение трудоемкости S = t × Dζ (см.
формулу (1.18)). Выборплотности fξ (x) в форме (2.24) отражает попытку уменьшить величинусреднего времени t, в то время как величина дисперсии Dζ при такомвыборе может быть достаточно большой (даже бесконечной).В ряде прикладных задач (в частности, при решении важной задачиоценки линейного функционала от решения интегрального уравненияФредгольма второго рода – см., например, [9, 13], а также разделы 6, 7данного пособия) требуется численно моделировать выборочное значе(m+1)(m+1)случайного вектора ξ̃= ξ˜(0) , ξ˜(1) , . . .
, ξ˜(m) , распредение ξ̃ 0ленного согласно плотности видаf(ξ̃(0) ,ξ̃(1) ,...,ξ̃(m) ) x(0) , x(1) , .., x(m) = π̃ x(0) × r1 x(0) , x(1) ××r2 x(1) , x(2) × . . . × rm x(m−1) , x(m) .(2.25)(m+1)Представление (2.25) означает, что вектор ξ̃обладает так называемым марковским свойством: для одного из представлений вида(2.10), а конкретнее, для тождественной подстановки(i0 , i1 , .
. . , im ) = (0, 1, . . . , m),распределение случайной компоненты ξ˜(j) полностью определяется фиксированным значением x(j−1) предыдущей по номеру компоненты ξ˜(j−1) :fξ̃(j) xx(0) , . . . , x(j−1) ≡ fξ̃(j) xξ˜(j−1) = x(j−1) = rj x(j−1) , x .(m+1)Таким образом, вектор ξ̃= ξ˜(0) , ξ˜(1) , . . . , ξ˜(m) представляетсобой отрезок длины (m + 1) цепи Маркова ξ˜(0) , ξ˜(1) , ξ˜(2) , . . . (см.,38например, [14]) с начальной плотностью π̃(x) = fξ̃(0) (x) и переходными плотностямиhirj (x0 , x) = rj ξ˜(j−1) = x0 → ξ˜(j) = x = rj xξ˜(j−1) = x0 ; (2.26)это условные плотности компонент ξ (j) при условии, что ξ˜(j−1) = x0 .Численное моделирование выборочных значений(0) (1)(m)ξ˜0 , ξ˜0 , .
. . , ξ˜0первых m + 1 состояний цепи Маркова реализуется с помощью следующего алгоритма.АЛГОРИТМ 2.5 (см., например, [9, 13]). Численно моделируем (ре(0)ализуем на компьютере) выборочное значение ξ˜0 начального состоя(0)˜ния ξцепи Маркова согласно плотности π̃(x). Затем для(j)j = 1, 2, . . . , m последовательно моделируем выборочные значения ξ˜0случайных величин (состояний цепи Маркова) ξ˜(j) согласно плотно(j−1)стям rj ξ˜0,x .Важным для приложений является случай, когда переходные плотности (2.26) одинаковы для всех j = 1, 2, . . .:rj (x0 , x) ≡ r(x0 , x),что означает, что марковская цепь ξ˜(0) , ξ˜(1) , ξ˜(2) , . . .
является однородной (см., например, [14]).соотношением (2.25) совместная плотность состояний По аналогии с (0) ˜(1)(m)˜˜ξ ,ξ ,...,ξдля однородной цепи Маркова имеет видf(ξ̃(0) ,ξ̃(1) ,...,ξ̃(m) ) x(0) , x(1) , .., x(m) = π̃ x(0) × r x(0) , x(1) ××r x(1) , x(2) × . . . × r x(m−1) , x(m) .(2.27)Численное моделирование выборочных значений первых m + 1 состояний однородной цепи Маркова реализуется следующим образом.АЛГОРИТМ 2.6 (см., например, [9, 13]). Численно моделируем выбо(0)рочное значение ξ˜0 согласно плотности π̃(x). Затем для j = 1, 2, .
. . , m(j)последовательно моделируем выборочные значения ξ˜0 согласно плот(j−1)ностям r ξ˜0,x .39Наконец, для практически важных расчетов, связанных с решением интегральных уравнений Фредгольма второго рода, нам потребуется введение и численное моделирование прикладной цепи Марковаили однородной цепи Маркова, обрывающейся с вероятностьюединицаξ (0) , ξ (1) , ..., ξ (N )(2.28)(см., например, [9, 13], а также разделы 6, 7 данного пособия).(m+1)Здесь номер m = N последней компоненты вектора ξ̃являетсяслучайным, а вместо переходной плотности рассматривается переходная функцияp(x0 , x) = 1 − p(a) (x0 ) × r(x0 , x),(2.29)где значение 0 ≤ p(a) (x0 ) ≤ 1 трактуется как вероятность обрыватраекторииприкладнойцепиМаркова(соответственноp(s) (x0 ) = 1 − p(a) (x0 ) – вероятность «выживания»), аr(x0 , x) = rξ(j) xξ (j−1) = x0 – условная вероятностная плотность типа (2.26) (одинаковая для всех j = 1, ..., N ).При моделировании траекторий прикладной цепи Маркова (2.28) используется аналог алгоритмов 2.5, 2.6, в котором перед моделированием(j−1)(j)очередного перехода ξ0→ ξ0 проверяется, не является ли состоя(j−1)ние ξ0точкой обрыва траектории.Этот розыгрыш обрыва траектории происходит согласно стандартному алгоритму моделирования выборочных значений дискретной случайной величины, принимающей только два значения (см., например,[9, 13], а также подраздел 10.3 данного пособия – алгоритм 10.3).(j−1) АЛГОРИТМ 2.7.
Если α0 < p(a) ξ0, то происходит обрыв траектории; иначе моделирование траектории продолжается; здесьα0 ∈ U (0, 1) – стандартное случайное число.В итоге алгоритм моделирования траекторий прикладной цепи Маркова (2.28) выглядит следующим образом.АЛГОРИТМ 2.8 (см., например, [9, 13]). 1. Полагаем j := 1.
Чис(j−1)(0)ленно моделируем выборочное значение ξ0= ξ0 согласно начальнойплотности π(x).(j−1) 2. Согласно вероятности p(a) ξ0и алгоритму 2.7 определяемфакт обрыва траектории.3. Если обрыв траектории произошел, то полагаем N = j − 1 ипрекращаем моделирование траектории.404. Если обрыва не произошло, то численно моделируем выбороч(j)(j−1)ное значение ξ0 согласно плотности r ξ0, x , а затем полагаемj := j + 1 и переходим на пункт 2 данного алгоритма.В алгоритме 2.8 и далее знак «:=» означает переприсваивание,т. е. при A := B числа или результаты вычислений в правой части Bпомещаются в ячейку памяти ЭВМ с именем A.3.
Метод интегральной суперпозиции.Рандомизация. Метод условногоматематического ожидания. Методрасщепления3.1. Метод интегральной суперпозиции. В этом разделе мы используем рассуждения подразделов 2.1 и 2.2 в многомерном случае (т. е.с учетом замечания 2.2) для изучения методов рандомизации, означающих специальное введение случайных величин для построения и модификации численных алгоритмов.Сразу отметим, что сама общая схема метода Монте-Карло (алгоритм 1.1) и ее применение для вычисления интеграла (алгоритм 1.2)являются примерами рандомизации задачи приближенного вычислениявеличины I, связанными со специальным введением случайных величин(оценивателей) ζ.Сначала представим следующий пример применения метода рандомизации при численном моделировании случайных векторов.Предположим, что требуется построить алгоритм численного моделирования (реализации на компьютере) выборочного значения ξ̃ 0k-мерного вектора ξ̃, плотность которого представляет собой интеграл,зависящий от параметра u ∈ U ⊆ Rk :Zf ˜ (u) =p(u, v) dv; u ∈ U ; V ⊆ Rm ,(3.1)ξVи, кроме того,1) функция p(u, v) является совместной плотностью распределенияd-мерного случайного вектора ξ = ξ̃, η̃ в X = U × V ⊆ Rk (здесьd = k + m), для которой, в частности, можно выписать многомерныйаналог представления (2.6), (2.7) (с заменой ξ (1) на ξ̃ и ξ (2) на η̃):p(u, v) = fη̃ (v)f ˜ (u|v);ξ41(3.2)Zfη̃ (v) =p(u, v)p(u, v) du; f ˜ (u|v) =;ξfη̃ (v)U(3.3)2) в соответствующем аналоге формулы (2.5) (это комбинация формул (3.1) и (3.2))Zf ˜ (u) =fη̃ (v)f ˜ (u|v) dv,(3.4)ξξVкоторый можно назвать формулой для «безусловной» плотности случайного вектора (случайной величины) ξ̃, плотности (3.3) являются«моделируемыми»: для реализации выборочного значения η̃ 0 случайного вектора (случайной величины) η̃, распределенного согласно плотности fη̃ (v), и выборочного значения ξ̃ 0 случайного вектора ξ̃, распределенного согласно плотности f ˜ (u|v) (для каждого фиксированногоξv), имеютсяэффективные (экономичные)алгоритмы (формулы) видаη̃ 0 = ψη̃ ᾱ1 , ξ̃ 0 = ψ ˜ ᾱ2 ; v , где ᾱi – соответствующие наборы станξдартных случайных чисел.При сделанных предположениях можно рассмотреть следующий многомерный аналог алгоритма 2.2 (с заменой ξ (1) на ξ̃ и ξ (2) на η̃) – методинтегральной суперпозиции (рандомизации).АЛГОРИТМ 3.1 (см., например, [9, 13]).
Численно моделируем выборочное значение ξ̃ 0 случайного вектора (случайной величины) ξ̃, распределенного согласно плотности (3.4), используя алгоритм (формулу) ξ̃ 0 = ψ ˜ ᾱ2 ; η̃ 0 , где выборочное значение η̃ 0 случайного вектораξ(случайной величины) η̃ реализованона компьютере с помощью алгоритма (формулы) η̃ 0 = ψη̃ ᾱ1 .ЗАМЕЧАНИЕ 3.1. Отличие алгоритма 3.1 от многомерного аналогаалгоритма 2.2 (с заменой ξ (1) на ξ̃ и ξ (2) на η̃) состоит в том, что в алгоритме 2.2 компоненты ξ (1) и ξ (2) являются равнозначными (одинакововажными), в то время как в алгоритме 3.1, учитывая постановку задачидля метода интегральной суперпозиции, компонента ξ̃ вектора ξ = ξ̃, η̃является основной (для моделирования), а компонента η̃ – вспомогательной.ЗАМЕЧАНИЕ 3.2. Метод интегральной суперпозиции (алгоритм 3.1)является некоторой альтернативой алгоритму 2.3 (когда последний алгоритм неприменим и одновременно справедливо представление (3.4) с соответствующими предположениями).Следует отметить, что применение алгоритма 3.1 является довольноредким.42При этом весьма частым является применение дискретного аналогаалгоритма 3.1 для случая, когда вспомогательный случайный вектор η̃является одномерной целочисленной случайной величиной η.Здесь интеграл (3.4) превращается в соответствующую взвешеннуюсумму моделируемых плотностей, а при моделировании целочисленногозначения η0 вспомогательной случайной величины η используется тот илииной алгоритм моделирования дискретной случайной величины (см.,например, [9, 13], а также раздел 10 данного пособия).Соответствующий алгоритм называется методом дискретной суперпозиции или просто методом суперпозиции (см., например, [9, 13], атакже подраздел 11.1 данного пособия).ЗАМЕЧАНИЕ 3.3.
Ситуацию, возникающую при постановке задачидля метода интегральной суперпозиции можно трактовать следующим образом.Пусть нам требуется численно смоделировать выборочное значениеk-мерной компоненты ξ̃ d-мерного случайного вектора ξ = ξ̃, η̃ (здесьd = k + m).«Подходящим» для моделирования оказывается многомерный аналогалгоритма 2.2 (с заменой ξ (1) на ξ̃ и ξ (2) на η̃) для разложения (3.2), (3.3)(это аналог формул (2.6), (2.7)), в то время как для разложения типа (2.4),(2.5) многомерный аналог алгоритма 2.1 (все с той же заменой ξ (1) на ξ̃и ξ (2) на η̃) построить не удается по той причине, что интеграл (3.4) (или(3.1)) не берется аналитически.К слову, такую ситуацию, когда одно из разложений (2.4), (2.5) или(2.6), (2.7) является «моделируемым», а второе – нет, дает технологияраспределенного (взвешенного) параметра для конструирования моделируемых распределений двумерных случайных векторов с зависимыми компонентами (технология Б), представленная далее в подразделе 14.3 данного пособия (см.