1626435387-5d0ec7dd22f55dfcc65f3209f497fb0b (844202), страница 22
Текст из файла (страница 22)
также формулы (9.10),(9.11) и (9.13)).Особо отметим, что последовательности вида (9.4) являются характерными примерами циклических групп вида (9.3) (см., например, [30]).Конкретные значения для параметров K и Q обусловлены широким применением алгоритма (9.4) с достаточно большими значениямистепеней m и 2p + 1 для реализации датчиков псевдослучайных чисел,используемых в алгоритмах метода Монте-Карло (см., например, [9, 13],а также подразделы 2.4, 9.3, 9.5 данного пособия).Мультипликативный метод вычетов (9.4) по модулю K = 2m длявыбранного множителя Q = 52p+1 обладает минимальной (для различных Q) мерой управляемости, равной µ = 1/2m−2 (см. далее подраз136дел 9.5), что обуславливает целесообразность использования этого алгоритма в качестве численной модели случайной величины α, равномернораспределенной в интервале (0, 1).9.2. Двоичное представление случайной величины α ∈ U (0, 1).Использование стандартных случайных чисел {αi }, представляющихсобой выборочные значения случайной величины α, равномерно распределенной в интервале (0, 1), является по сути единственным инструментом «воспроизведения случайности» на ЭВМ с целью применениячисленных алгоритмов метода Монте-Карло для решения методическихи прикладных задач.Случайная величина α ∈ U (0, 1) имеет функцию распределения 0 для x ∈ (−∞, 0];x для x ∈ (0, 1);Fα (x) = P{α < x} =(9.5)1 для x ∈ [1, +∞)(см.
также формулу (2.12) и рис. 2.2) и характеристики Eα = 1/2,Dα = 1/12 (см. формулы (2.13)). Важным свойством этой случайнойвеличины, которое активно используется при обосновании алгоритмовметода Монте-Карло, является то, чтоP{α ∈ (c, d) ⊆ (0, 1)} = d − c,(9.6)см. также формулу (2.14) и рис. 2.3.Значения {αi } получаются на ЭВМ с помощью специальной программы или устройства, которое называется генератором стандартныхслучайных (псевдослучайных) чисел.Важным для практического построения генераторов стандартныхслучайных чисел является следующее рассуждение (см., например,[9, 13]). Учтем первым делом то обстоятельство, что числа в компьютереимеют двоичное представление.Поскольку α ∈ (0, 1), то двоичное представление каждого выборочного значения этой случайной величины имеет видα = 0, α(1) .
. . α(k) . . . =∞Xα(k) 2−k ,(9.7)k=1причем каждый разряд α(k) мантиссы числа (9.7) равен нулю или единице.УТВЕРЖДЕНИЕ 9.2 (см., например, [9]). Для того чтобы случайная величина α была равномерно распределенной в интервале (0, 1),137необходимо и достаточно, чтобы двоичные цифры α(1) , . . . , α(k) , . . . изсоотношения (9.7) представляли собой последовательность независимых бернуллиевских случайных величин с вероятностью успеха 1/2: 1P α(k) = 1 = P α(k) = 0 = .2ДОКАЗАТЕЛЬСТВО.
Необходимость. Поскольку случайная величина (9.7) равномерно распределена в (0, 1), то α(k) = 0 при0, α(1) . . . α(k−1) 0 ≤ α < 0, α(1) . . . α(k−1) 1,(9.8)причем α(1) , . . . , α(k−1) в (9.8) могут принимать значения 0 и 1. Длина интервала (9.8) равна 2−k , и интервалы (9.8) для разных наборовα(1) , . . . , α(k−1) не пересекаются, поэтому, используя соотношение (9.6),получаем1XP α(k) = 0 =2−k = 2k−1 × 2−k =α(1) ,...,α(k−1) =01.2(9.9)Тогда P α(k) = 1 = 1 − P α(k) = 0 = 1/2.(s)(k)Докажем теперь независимость (k) α и α(s) , где1 ≤ s < k. Для этогорассмотрим вероятность P α = i ∩ α = j .
Это число, очевидно, можно рассматривать как условную вероятность того, что выполнено соотношение типа (9.8) при условии, что α(s) фиксировано. Тогдапо аналогии c равенством (9.9) имеем1XP α(k) = i ∩ α(s) = j =2−k =α(1) ,...,α(s−1) ,α(s+1) ,...,α(k−1) =0= 2k−2 × 2−k =1= P α(k) = i × P α(s) = j .4АналогичноP α(k1 ) = i1 ∩..∩ α(kq ) = iq } = 2−q = P α(k1 ) = i1 ×..×P α(kq ) = iq ,а это и означает независимость случайных цифр числа (9.7).Достаточность. Очевидно, что дробь из правой части соотношения(9.7) принадлежит интервалу (0, 1), поэтому(∞)(∞)XXPα(k) 2−k < x = 0 при x ≤ 0 и Pα(k) 2−k < x = 1k=1k=1138при x ≥ 1.Возьмем произвольноеx = 0, a1 a2 . .
. ak . . . из интервала (0, 1) и поP∞(k) −kα2< x = x.кажем, что Pk=1P∞(k) −kЕсли k=1 α 2 < x , то либо α(1) < a1 , либо α(1) = a1 и α(2) < a2 ,либо α(1) = a1 , α(2) = a2 и α(3) < a3 и т. д. Таким образом,(∞)∞XX(k) −kPα 2 <x =P α(1) = a1 ∩ .. ∩ α(k−1) = ak−1 ∩k=1∩ α(k) < akk=1=∞XP α(1) = a1 ×..×P α(k−1) = ak−1 ×P α(k) < ak ;k=1здесь использована независимостьцифр α(1) , . . . , α(k) .
(k) случайныхЛегко проверить, что P α < ak = ak /2. Поэтому(∞)∞∞XX X(k) −kPα 2 <x =2−(k−1) × ak 2−1 =ak 2−k = x.k=1k=1k=1Таким образом, функция распределения случайной дроби из правойчасти соотношения (9.7) совпадает с функцией (9.5). Утверждение 9.2доказано.9.3. Два типа генераторов стандартных случайных чисел.С одной стороны, доказанное утверждение 9.2 может повергнуть исследователя в некоторое уныние, так как оно говорит о том, что «настоящее» стандартное случайное число (9.7) имеет бесконечную мантиссу,воспроизвести которую на ЭВМ невозможно.С другой стороны, можно отметить, что в вычислительной математике машинные ошибки, связанные с конечностью мантиссы, часто неучитываются (в качестве примера можно указать использование форматов вещественных чисел на ЭВМ).
Для используемых на практикегенераторов случайных чисел эффекты, связанные с конечностью мантиссы, как правило, незначительны.Утверждение 9.2 обосновывает принцип работы так называемых физических датчиков случайных чисел. Это технические устройства(чаще всего «шумящие» электронные приборы), которые вырабатывают случайную последовательность двоичных цифр (условно: лампочкагорит или не горит с вероятностью 1/2; если вероятность не равна 1/2,то целесообразно брать пары событий «да – нет» и «нет – да», а события«да – да», «нет – нет» отбрасывать).139К преимуществам такого способа получения случайных чисел относят быстроту реализации и неограниченность запаса случайных чисел.Недостатком физических датчиков случайных чисел является то,что периодически требуется статистическая проверка вырабатываемыхслучайных чисел (поскольку даже сверхнадежное техническое устройство дает сбои).
Кроме того, нет возможности воспроизвести расчеты.Следует тем не менее заметить, что существует немало вычислителей,которые предпочитают именно физические датчики случайных чисел,и работы по конструированию таких устройств продолжаются.Большинство расчетов по методу Монте-Карло произведено и производится с помощью генераторов псевдослучайных чисел, представляющих собой некоторые вычислительные подпрограммы (чаще всеготакие подпрограммы называются RAN D или RAN DOM ).Аргументами в пользу применения псевдослучайных чисел являются возможность воспроизводить расчеты, быстрота получения чисел,отсутствие внешних устройств и необходимости многократной проверки качества получаемых чисел, малая загруженность памяти ЭВМ.Большинство известных алгоритмов реализации псевдослучайныхчисел представляет собой детерминированную дискретную последовательность и имеет видαn+1 = ψ(αn )(9.10)(это аналог формулы (9.1)), где начальное число α0 задано. Областьюзначений функции ψ(x) должен являться интервал (0, 1).Одно из соображений о том, каким образом следует выбирать функцию ψ(x) из соотношения (9.10), состоит в следующем.
Пары точекα1 , α2 = ψ(α1 ) , α3 , α4 = ψ(α3 ) , α5 , α6 = ψ(α5 ) , . . . ,с одной стороны, должны располагаться на кривой y = ψ(x), а с другой– эти же точки должны (по свойствам «настоящих» стандартных случайных чисел) быть равномерно распределены в квадрате∆(2) = {(x, y) : 0 < x < 1, 0 < y < 1}. Поэтому график функцииψ(x) должен достаточно плотно заполнять этот квадрат.Примером такой функции ψ(x) может служитьψ(x) = {Q x}(9.11)для большого целого положительного множителя Q; здесь {A} обозначает дробную часть числа A (рис. 9.1).140Рис. 9.1.
График функции ψ(x) = {Q x}Алгоритм (9.10) с функцией (9.11) (и с конечными мантиссами чисел{αn } из последовательности (9.10)) называется мультипликативным методом вычетов и является одним из наиболее часто употребляемых алгоритмов при моделировании псевдослучайных чисел.9.4. Два полезных свойства преобразования методавычетов. Отметим следующее свойство преобразования (9.11).УТВЕРЖДЕНИЕ 9.3 (см., например, [9, 13]).
Случайная величинаβ = {Qα} равномерно распределена в интервале (0, 1) для любого целогоположительного числа Q.ДОКАЗАТЕЛЬСТВО.ИсследуемфункциюраспределенияFβ (x) = P(β < x). Согласно определению дробной части числа, имеем β ∈ [0, 1), и поэтому Fβ (x) = 0 при x < 0 и Fβ (x) = 1 при x ≥ 1.Если x ∈ [0, 1) (см. рис. 9.2), то, используя соотношение (9.6), получаем() Q−1Q−1Q−1XXX xk+xkFβ (x) =P{k ≤ Q α < k+x} =P≤α<= x.=QQQk=0k=0k=0Сравнивая функции Fβ (x) и (9.5), делаем вывод о том, что случайная величина β равномерно распределена в интервале (0, 1). Утвержде141Рис. 9.2. Иллюстрация к доказательству утверждения 9.3ние 9.3 доказано.Таким образом, преобразование метода вычетов (9.11) сохраняет равномерное распределение в интервале (0, 1).Одним из существенных сомнений, связанных с использованием мультипликативного метода вычетов (9.10), (9.11) является то обстоятельство, что даже для «настоящих» («теоретических») стандартных случайных величин вида (9.7) члены последовательностиβ(s + 1) = {Qβ(s)} = Qs+1 β(0) ; β(0) = α(9.12)являются зависимыми случайными величинами.
Поэтому весьма важным является следующее свойство преобразования (9.11).УТВЕРЖДЕНИЕ 9.4 (см., например, [9]). Коэффициент корреляции defα − Eα β̃ − Eβ̃ qr α, β̃ = r α, β(s) = E √DαDβ̃равен11r α, β̃ = s = ,QQ̃где β̃ = β(s), Q̃ = Qs , для любых целых положительных чисел Q и s.ДОКАЗАТЕЛЬСТВО. Индукцией по s, используяутверждение 9.3, несложно показать, что случайная величина β̃ = Q̃α = Qs α является также стандартной. При этом Eα = Eβ̃ = 1/2, Dα = Dβ̃ = 1/12(см. соотношения (2.13)), и коэффициент корреляции равен"!!#"!!#α − 1/2β̃ − 1/2Q̃α − Q̃/2β̃ − 1/2ppppr α, β̃ = E=E=1/121/12Q̃ 1/121/12142" !!#Q̃α + Q̃α − Q̃/2 − 1/2 − 1/2β̃ − 1/2pp=E=1/12Q̃ 1/12!#"!!#"!γ − Q̃/2 − 1/2β̃ − 1/2β̃ − 1/2β̃ − 1/2pppp+E,=E1/121/12Q̃ 1/12Q̃ 1/12 где γ = Q̃α (это целая часть числа Q̃α). Случайная величина γ, принимающая значения 0, 1, .