\input style
С ИЗБЫТКОМ КОМПЕНСИРУЕТ ЭТОТ НЕДОСТАТОК. пРОГРАММУ ДЛЯ МЕТОДА мАРСАЛЬИ
НАПИСАТЬ ГОРАЗДО ТРУДНЕЕ, НО ЕСЛИ ПОДПРОГРАММУ, ОСНОВАННУЮ НА АЛГОРИТМЕ~M,
СОСТАВИТЬ В ОБЩЕМ ВИДЕ, ОНА ЯВИТСЯ ЦЕННЫМ ВКЛАДОМ В ЛЮБУЮ БИБЛИОТЕКУ
ПОДПРОГРАММ. мНОГОЧИСЛЕННЫЕ ПРИМЕНЕНИЯ НОРМАЛЬНО РАСПРЕДЕЛЕННЫХ
СЛУЧАЙНЫХ ВЕЛИЧИН ТРЕБУЮТ БОЛЬШОГО КОЛИЧЕСТВА СЛУЧАЙНЫХ ЧИСЕЛ, ТАК
ЧТО ВАЖНА СКОРОСТЬ ИХ ВЫРАБОТКИ.

дОПОЛНИТЕЛЬНУЮ ИНФОРМАЦИЮ О МЕТОДЕ тЕЙЧРОЕВА, А ТАКЖЕ ОБЗОР НЕКОТОРЫХ
ДРУГИХ МЕТОДОВ, ХУДШИХ, КАК ТЕПЕРЬ ВЫЯСНИЛОСЬ, ЧЕМ ОБСУЖДАЕМЫЕ ЗДЕСЬ,
МОЖНО ПОЛУЧИТЬ ИЗ СТАТЬИ м.~мАЛЛЕРА ({\sl JACM,\/} {\bf 6} (1959), 376--383).

{\sl (5)~рАЗНОВИДНОСТИ НОРМАЛЬНОГО РАСПРЕДЕЛЕНИЯ.\/} мЫ
РАССМОТРЕЛИ НОРМАЛЬНОЕ РАСПРЕДЕЛЕНИЕ С НУЛЕВЫМ СРЕДНИМ ЗНАЧЕНИЕМ И
СТАНДАРТНЫМ ОТКЛОНЕНИЕМ, РАВНЫМ ЕДИНИЦЕ. еСЛИ $X$~ИМЕЕТ ТАКОЕ
РАСПРЕДЕЛЕНИЕ, ТО У ФУНКЦИИ РАСПРЕДЕЛЕНИЯ СЛУЧАЙНОЙ ВЕЛИЧИНЫ
$$
Y=\mu+\sigma X
\eqno(24)
$$
СРЕДНЕЕ ЗНАЧЕНИЕ РАВНО~$\mu$, А СТАНДАРТНОЕ ОТКЛОНЕНИЕ~$\sigma$.
бОЛЕЕ ТОГО, ЕСЛИ~$X_1$ И~$X_2$---НЕЗАВИСИМЫЕ НОРМАЛЬНЫЕ СЛУЧАЙНЫЕ ВЕЛИЧИНЫ
СО СРЕДНИМ ЗНАЧЕНИЕМ НУЛЬ И ЕДИНИЧНЫМ СТАНДАРТНЫМ ОТКЛОНЕНИЕМ И ЕСЛИ
$$
Y_1=\mu_1+\sigma_1 X_1, \qquad
Y_2=\mu_2+\sigma_2(\rho X_1+\sqrt{1-\rho^2}X_2),
\eqno(25)
$$
ТО~$Y_1$ И~$Y_2$---\emph{ЗАВИСИМЫЕ} СЛУЧАЙНЫЕ ВЕЛИЧИНЫ, РАСПРЕДЕЛЕННЫЕ  СО
СРЕДНИМИ ЗНАЧЕНИЯМИ~$\mu_1$, $\mu_2$, СТАНДАРТНЫМИ ОТКЛОНЕНИЯМИ~$\sigma_1$,
$\sigma_2$ И КОЭФФИЦИЕНТОМ КОРРЕЛЯЦИИ~$\rho$. (оБОБЩЕНИЕ НА СЛУЧАЙ~$n$
ПЕРЕМЕННЫХ СМ.~В~УПР.~13.)

\section{D.~эКСПОНЕНЦИАЛЬНОЕ РАСПРЕДЕЛЕНИЕ}. дРУГОЙ ВАЖНЫЙ ВИД СЛУЧАЙНЫХ
ВЕЛИЧИН---ВЕЛИЧИНЫ С \emph{ЭКСПОНЕНЦИАЛЬНЫМ РАСПРЕДЕЛЕНИЕМ.} тАКИЕ СЛУЧАЙНЫЕ
ВЕЛИЧИНЫ БЫВАЮТ НУЖНЫ В ЗАДАЧАХ, ГДЕ РАССМАТРИВАЕТСЯ "ВРЕМЯ ПОЯВЛЕНИЯ".
нАПРИМЕР, ЕСЛИ РАДИОАКТИВНОЕ ВЕЩЕСТВО ИЗЛУЧАЕТ В СРЕДНЕМ КАЖДЫЕ
$\mu$~СЕКУНД ОДНУ АЛЬФА-ЧАСТИЦУ, ТО ПРОМЕЖУТКИ ВРЕМЕНИ МЕЖДУ ДВУМЯ
ПОСЛЕДОВАТЕЛЬНЫМИ ВЫЛЕТАМИ ЧАСТИЦ ИМЕЮТ ЭКСПОНЕНЦИАЛЬНОЕ РАСПРЕДЕЛЕНИЕ СО
СРЕДНИМ ЗНАЧЕНИЕМ~$\mu$. эТО РАСПРЕДЕЛЕНИЕ ОПРЕДЕЛЯЕТСЯ ФОРМУЛОЙ
$$
F(x)=1-e^{-x/\mu}, \rem{$x\ge0$.}
\eqno(26)
$$
оТСЮДА СЛЕДУЕТ, ЧТО ЕСЛИ $X$~ИМЕЕТ ЭКСПОНЕНЦИАЛЬНОЕ РАСПРЕДЕЛЕНИЕ СО
СРЕДНИМ ЗНАЧЕНИЕМ~$1$, ТО $\mu X$~ПОДЧИНЯЕТСЯ ЭКСПОНЕНЦИАЛЬНОМУ
РАСПРЕДЕЛЕНИЮ СО СРЕДНИМ~$\mu$. пОЭТОМУ ДОСТАТОЧНО РАССМОТРЕТЬ
СЛУЧАЙ~$\mu=1$. оБЫЧНО ИСПОЛЬЗУЮТСЯ ТРИ МЕТОДА.

{\sl (1)~лОГАРИФМИЧЕСКИЙ МЕТОД.\/} яСНО, ЧТО~$y=F(x)=1-e^{-x}$
МОЖНО ПРЕДСТАВИТЬ В ВИДЕ~$x=F^{-1}(y)=-\ln(1-y)$. пОЭТОМУ, ВСЛЕДСТВИЕ
%% 142
СООТНОШЕНИЯ~(6), ВЕЛИЧИНА~$-\ln(1-U)$ ИМЕЕТ ЭКСПОНЕНЦИАЛЬНОЕ РАСПРЕДЕЛЕНИЕ.
тАК КАК $1-U$~РАСПРЕДЕЛЕНА РАВНОМЕРНО, ЕСЛИ~$U$---РАВНОМЕРНО РАСПРЕДЕЛЕННОЕ
СЛУЧАЙНОЕ ЧИСЛО, ТО СЛУЧАЙНАЯ ВЕЛИЧИНА
$$
X=-\ln U
\eqno(27)
$$
РАСПРЕДЕЛЕНА ЭКСПОНЕНЦИАЛЬНО СО СРЕДНИМ ЗНАЧЕНИЕМ, РАВНЫМ ЕДИНИЦЕ. (в
ПРОГРАММАХ СЛЕДУЕТ ИЗБЕГАТЬ СЛУЧАЯ~$U=0$.)

{\sl (2)~мЕТОД СЛУЧАЙНОЙ МИНИМИЗАЦИИ.\/} сЛЕДУЮЩИЙ АЛГОРИТМ (дЖ.~мАРСАЛЬЯ)
ВЫЧИСЛЯЕТ ЗНАЧЕНИЯ ЭКСПОНЕНЦИАЛЬНО РАСПРЕДЕЛЕННОЙ СЛУЧАЙНОЙ ВЕЛИЧИНЫ БЕЗ
ИСПОЛЬЗОВАНИЯ ПОДПРОГРАММЫ ЛОГАРИФМА.

\alg E.(эКСПОНЕНЦИАЛЬНОЕ РАСПРЕДЕЛЕНИЕ СО СРЕДНИМ~$1$.) иСПОЛЬЗУЮТСЯ
ТАБЛИЦЫ КОНСТАНТ~$P[j]$, $Q[j]$ ДЛЯ~$j\ge 1$, ОПРЕДЕЛЕННЫЕ ФОРМУЛАМИ
$$
P[j]=1-{1\over e^j}, \quad
Q[j]={1\over e-1}\left({1\over1!}+{1\over2!}+\cdots+{1\over j!}\right).
\eqno(28)
$$

дЛИНА ТАБЛИЦ ОГРАНИЧИВАЕТСЯ ЗНАЧЕНИЕМ МАКСИМАЛЬНОЙ ДРОБИ, КОТОРУЮ МОЖНО
РАЗМЕСТИТЬ В МАШИННОМ СЛОВЕ.

\st[нАЧАЛО ДРОБНОЙ ЧАСТИ.] уСТАНОВИТЬ~$j\asg1$. вЫРАБОТАТЬ СЛУЧАЙНЫЕ
ЧИСЛА~$U_0$ И~$U_1$ И УСТАНОВИТЬ~$X\asg -U_1$.

\st[мИНИМИЗАЦИЯ ЗАКОНЧЕНА?] еСЛИ~$U_0<Q[j]$, ПЕРЕЙТИ К~\stp{4}.

\st[мИНИМИЗИРОВАТЬ.] уСТАНОВИТЬ~$j\asg j+1$. вЫРАБОТАТЬ СЛУЧАЙНОЕ
ЧИСЛО~$U_j$; ЕСЛИ~$X>U_j$, УСТАНОВИТЬ~$X\asg U_j$. вЕРНУТЬСЯ ОБРАТНО К ШАГУ~\stp{2}.

\st[нАЧАЛО ЦЕЛОЙ ЧАСТИ.] (мЫ УЖЕ ВЫЧИСЛИЛИ ДРОБНУЮ ЧАСТЬ ОКОНЧАТЕЛЬНОГО
РЕЗУЛЬТАТА, $X$, И ДОЛЖНЫ ДОБАВИТЬ К НЕМУ СООТВЕТСТВУЮЩЕЕ ЦЕЛОЕ ЧИСЛО,
ЧТОБЫ ЗАКОНЧИТЬ ВЫЧИСЛЕНИЯ.) вЫРАБОТАТЬ НОВОЕ СЛУЧАЙНОЕ ЧИСЛО~$U$ И
УСТАНОВИТЬ~$j\asg 1$.

\st[сДЕЛАНА ЛИ ПОПРАВКА?] еСЛИ~$U<P[j]$, АЛГОРИТМ ЗАКАНЧИВАЕТСЯ.

\st[пОПРАВКА НА~1.] уСТАНОВИТЬ~$j\asg j+1$, $X\asg X+1$ И ВЕРНУТЬСЯ К ШАГУ~\stp{5}.
\algend

чТОБЫ ПОКАЗАТЬ СПРАВЕДЛИВОСТЬ МЕТОДА, ПРОАНАЛИЗИРУЕМ РАСПРЕДЕЛЕНИЕ~$X$ В
НАЧАЛЕ ШАГА~E4. еСЛИ~$n$---ОКОНЧАТЕЛЬНОЕ ЗНАЧЕНИЕ~$j$, МЫ
ИМЕЕМ~$X=\min(U_1, U_2,~\ldots, U_n)$, ГДЕ~$U_1$, $U_2$,~\dots,
$U_n$---НЕЗАВИСИМЫЕ СЛУЧАЙНЫЕ ЧИСЛА; ПОЭТОМУ ВЕРОЯТНОСТЬ ТОГО, ЧТО~$X\le x$,
ЕСТЬ~$p_n(x)=1-(1-x)^n$. вЕРОЯТНОСТЬ ТОГО, ЧТО~$n$---ОКОНЧАТЕЛЬНОЕ
ЗНАЧЕНИЕ, РАВНА~$Q[n]-Q[n-1]=1/(e-1)n!$. пОЭТОМУ ПОЛНАЯ ВЕРОЯТНОСТЬ
СОБЫТИЯ~$X\le x$ РАВНА
$$
\sum_{n\ge 1} {p(x)\over (e-1)n!}={e\over e-1}(1-e^{-x}), \rem{$0\le x\le 1$.}
$$
%% 143
аНАЛОГИЧНО, ПРИ РАССМОТРЕНИИ ШАГОВ~E4--E6 МЫ НАХОДИМ, ЧТО~$\floor{X}\le m$
С ВЕРОЯТНОСТЬЮ~$P[m+1]$. оКОНЧАТЕЛЬНО, ВЕРОЯТНОСТЬ ТОГО, ЧТО~$m\le X \le m+x$, ЕСТЬ
$$
(P[m+1]-P[m])\left({e\over e-1}(1-e^{-x}\right)=e^{-m}-e^{-(m+x)},
\rem{$0\le x \le 1$.}
$$
эТО ДОКАЗЫВАЕТ, ЧТО $X$~ИМЕЕТ РАСПРЕДЕЛЕНИЕ~$F(x)=1-e^{-x}$ ДЛЯ~$0\le x<\infty$.

эТОТ АЛГОРИТМ ДОВОЛЬНО БЫСТРЫЙ. в СРЕДНЕМ ШАГИ~E2 И~E5 ВЫПОЛНЯЮТСЯ ТОЛЬКО
$1.582$~РАЗ И ТОЛЬКО $2.582$~СЛУЧАЙНЫХ ЧИСЛА ВЫЧИСЛЯЕТСЯ ДЛЯ ПОЛУЧЕНИЯ
ОДНОЙ ЭКСПОНЕНЦИАЛЬНОЙ СЛУЧАЙНОЙ ВЕЛИЧИНЫ. эТО МОЖЕТ ОКАЗАТЬСЯ ЗНАЧИТЕЛЬНО
БЫСТРЕЕ, ЧЕМ ВЫЧИСЛЕНИЕ ЛОГАРИФМА ОДНОГО СЛУЧАЙНОГО ЧИСЛА. иНТЕРЕСНАЯ
МОДИФИКАЦИЯ МЕТОДА СОДЕРЖИТСЯ В РАБОТЕ
[м.~Sibuya, {\sl Ann.\ Inst.\ Stat.\ Math.,\/} {\bf 13} (1962), 231--237].

{\sl (3)~мЕТОД ПРЯМОУГОЛЬНИКА---КЛИНА---ХВОСТА.\/} дЛЯ
НОРМАЛЬНОГО РАСПРЕДЕЛЕНИЯ (КАК И ДЛЯ МНОГИХ ДРУГИХ) СУЩЕСТВУЕТ ОЧЕНЬ
БЫСТРЫЙ МЕТОД, ОСНОВАННЫЙ НА РАЗЛОЖЕНИИ ФУНКЦИИ ПЛОТНОСТИ ВЕРОЯТНОСТИ.
дЕТАЛИ ОБСУЖДАЮТСЯ В {\sl CACM,\/} {\bf 7} (1964), 298--300.

\section{E.~дРУГИЕ НЕПРЕРЫВНЫЕ РАСПРЕДЕЛЕНИЯ}. мЫ ПЕРЕЧИСЛИМ ЗДЕСЬ КОРОТКО
НЕКОТОРЫЕ ДРУГИЕ РАСПРЕДЕЛЕНИЯ, КОТОРЫЕ БЫВАЮТ ДОВОЛЬНО ЧАСТО НУЖНЫ НА
ПРАКТИКЕ, И МЕТОДЫ МОДЕЛИРОВАНИЯ СООТВЕТСТВУЮЩИХ СЛУЧАЙНЫХ ВЕЛИЧИН С
ПОМОЩЬЮ УЖЕ ИЗВЕСТНЫХ НАМ ПРИЕМОВ.

{\sl $\chi^2$-РАСПРЕДЕЛЕНИЕ\/} С $\nu$~СТЕПЕНЯМИ СВОБОДЫ, КОТОРОЕ ТАКЖЕ
НАЗЫВАЮТ ГАММА-РАСПРЕДЕЛЕНИЕМ ПОРЯДКА~$\nu/2$. мЫ ИМЕЕМ
$$
F(x)={1\over 2^{\nu/2} \Gamma(\nu/2)} \int_0^x t^{\nu/2-1}e^{-t/2}\,dt, \rem{$x\ge0$}.
\eqno(29)
$$
еСЛИ~$\nu=2k$, ГДЕ~$k$---ЦЕЛОЕ ЧИСЛО, ПОЛОЖИМ~$X=2(Y_1+Y_2+\cdots+Y_k)$,
ГДЕ~$Y_i$---НЕЗАВИСИМЫЕ ЭКСПОНЕНЦИАЛЬНО РАСПРЕДЕЛЕННЫЕ СЛУЧАЙНЫЕ ВЕЛИЧИНЫ,
СО СРЕДНИМ ЗНАЧЕНИЕМ~$1$ КАЖДАЯ. еСЛИ~$\nu=2k+1$,
ПОЛОЖИМ~$X=2(Y_1+\cdots+Y_k)+Z^2$, ГДЕ~$Y_i$---ТЕ ЖЕ ВЕЛИЧИНЫ,
a~$Z$---НЕЗАВИСИМАЯ НОРМАЛЬНО РАСПРЕДЕЛЕННАЯ СЛУЧАЙНАЯ ВЕЛИЧИНА
(СРЕДНЕЕ~$0$, ДИСПЕРСИЯ~$1$). дЛЯ ДОКАЗАТЕЛЬСТВА СМ.~УПР.~16. зАМЕТИМ, ЧТО,
ЕСЛИ~$Y_1$,~\dots, $Y_k$ НАХОДЯТСЯ ЛОГАРИФМИЧЕСКИМ МЕТОДОМ, ДЛЯ
ОПРЕДЕЛЕНИЯ~$Y_1+\cdots+Y_k=-\ln(U_1\ldots{}U_k)$ ТРЕБУЕТСЯ ВЫЧИСЛИТЬ
ТОЛЬКО ОДИН ЛОГАРИФМ.

{\sl (2)~бЕТА-РАСПРЕДЕЛЕНИЕ\/} С~$\nu_1$ И~$\nu_2$ СТЕПЕНЯМИ СВОБОДЫ,
ОПРЕДЕЛЯЕТСЯ ФОРМУЛОЙ:
$$
F(x)={\Gamma((\nu_1+\nu_2)/2)\over \Gamma(\nu_1/2)\Gamma(\nu_2/2)}
\int_0^x t^{\nu_1/2-1}(1-t)^{\nu_2/2-1}\,dt, \rem{$0\le x \le 1$.}
\eqno(30)
$$
%% 144
пУСТЬ~$Y_1$ И~$Y_2$ НЕЗАВИСИМЫ И ИМЕЮТ $\chi^2$-РАСПРЕДЕЛЕНИЕ С~$\nu_1$,
$\nu_2$~СТЕПЕНЯМИ СВОБОДЫ СООТВЕТСТВЕННО. пОЛАГАЕМ~$X\asg Y_1/(Y_1+Y_2)$.

дРУГОЙ МЕТОД, КОТОРЫЙ ОСТАЕТСЯ СПРАВЕДЛИВЫМ И ДЛЯ НЕЦЕЛЫХ~$\nu_1$
И~$\nu_2$, СВОДИТСЯ К ВЫЧИСЛЕНИЮ~$Y_1\asg U_1^{2/\nu_1}$,
$Y_2\asg U_2^{2/\nu_2}$ С ПОВТОРЕНИЕМ В СЛУЧАЕ НЕОБХОДИМОСТИ ЭТОГО ПРОЦЕССА ДО
ТЕХ ПОР, ПОКА НЕ БУДЕТ ВЫПОЛНЕНО НЕРАВЕНСТВО~$Y_1+Y_2\le 1$. нАКОНЕЦ,
$X\asg Y_1/(Y_1+Y_2)$. [сМ.~M.~D.~J\"ohnk, {\sl Metrika,\/} {\bf 8} (1964), 5--15.]
пО-ДРУГОМУ, ЕСЛИ~$\nu_1=2k_1$, a~$\nu_2=2k_2$---ОБА ЧЕТНЫЕ ЦЕЛЫЕ
ЧИСЛА, МЫ МОЖЕМ ОПРЕДЕЛИТЬ~$X$ КАК $k_1\hbox{-Е}$ ПО ПОРЯДКУ НАИМЕНЬШЕЕ ИЗ
$k_1+k_2-1$~НЕЗАВИСИМЫХ СЛУЧАЙНЫХ ЧИСЕЛ.

{\sl (3)~$F$-РАСПРЕДЕЛЕНИЕ\/} (РАСПРЕДЕЛЕНИЕ ОТНОШЕНИЙ ДИСПЕРСИЙ)
С~$\nu_1$ И~$\nu_2$~СТЕПЕНЯМИ СВОБОДЫ ОПРЕДЕЛЯЕТСЯ КАК
$$
F(x)={\nu_1^{\nu_1/2}\nu_2^{\nu_2/2}\Gamma((\nu_1+\nu_2)/2) \over \Gamma(\nu_1/2)\Gamma(\nu_2/2)}
\int_0^x t^{\nu_1/2-1}(\nu_2+\nu_1t)^{-\nu_1/2-\nu_2/2}\,dt, \rem{$x\ge0$.}
\eqno(31)
$$

пУСТЬ~$Y_1$ И~$Y_2$---НЕЗАВИСИМЫЕ СЛУЧАЙНЫЕ ВЕЛИЧИНЫ,
ИМЕЮЩИЕ $\chi^2$-РАСПРЕДЕЛЕНИЕ С~$\nu_1$, $\nu_2$~СТЕПЕНЯМИ СВОБОДЫ
СООТВЕТСТВЕННО. пОЛОЖИМ~$X\asg Y_1\nu_2/Y_2\nu_1$,
ИЛИ~$X\asg\nu_2 Y/\nu_1(1-Y)$, ГДЕ $Y$~ИМЕЕТ БЕТА-РАСПРЕДЕЛЕНИЕ~(30).

{\sl(4) $t$-РАСПРЕДЕЛЕНИЕ\/} С~$\nu$~СТЕПЕНЯМИ СВОБОДЫ ОПРЕДЕЛЯЕТСЯ КАК
$$
F(x)={\Gamma((\nu+1)/2)\over \sqrt{\pi\nu}\Gamma(\nu/2)} \int_{-\infty}^x (1+t^2/\nu)^{-(\nu+1)/2}\,dt.
\eqno(32)
$$
пУСТЬ~$Y_1$---НОРМАЛЬНО РАСПРЕДЕЛЕННАЯ СЛУЧАЙНАЯ ВЕЛИЧИНА (СРЕДНЕЕ~$0$,
ДИСПЕРСИЯ~$1$), ПУСТЬ~$Y_2$---НЕЗАВИСИМАЯ ОТ~$Y_1$ СЛУЧАЙНАЯ ВЕЛИЧИНА,
ИМЕЮЩАЯ $\chi^2$-РАСПРЕДЕЛЕНИЕ С $\nu$~СТЕПЕНЯМИ СВОБОДЫ. пОЛОЖИМ~$X\asg Y_1/\sqrt{Y_2/\nu}$.

{\sl (5)~сЛУЧАЙНАЯ ТОЧКА НА $n$-МЕРНОЙ СФЕРЕ С ЕДИНИЧНЫМ
РАДИУСОМ.\/} пУСТЬ~$X_1$, $X_2$,~\dots, $X_n$---НЕЗАВИСИМЫЕ НОРМАЛЬНЫЕ
СЛУЧАЙНЫЕ ВЕЛИЧИНЫ (СРЕДНЕЕ~$0$, ДИСПЕРСИЯ~$1$). сЛУЧАЙНАЯ ТОЧКА НА
ЕДИНИЧНОЙ СФЕРЕ ИМЕЕТ КООРДИНАТЫ
$$
(X_1/r, X_2/r, \ldots, X_n/r), \rem{ГДЕ $r=\sqrt{X_1^2+X_2^2+\cdots+X_n^2}$.}
\eqno (33)
$$
зАМЕТИМ, ЧТО ЕСЛИ $X_i$~ВЫЧИСЛЯЮТСЯ С ПОМОЩЬЮ МЕТОДА ПОЛЯРНЫХ КООРДИНАТ
(АЛГОРИТМ~P), ТО КАЖДЫЙ РАЗ В РЕЗУЛЬТАТЕ МЫ ИМЕЕМ ДВЕ НЕЗАВИСИМЫЕ
ВЕЛИЧИНЫ~$X_1$ И~$X_2$ И~$X_1^2+X_2^2=-2\ln S$ (В ОБОЗНАЧЕНИЯХ
АЛГОРИТМА~P). эТО ЭКОНОМИТ НЕМНОГО ВРЕМЕНИ, НЕОБХОДИМОГО ДЛЯ
ВЫЧИСЛЕНИЯ~$r$. сПРАВЕДЛИВОСТЬ МЕТОДА ПРОИСТЕКАЕТ ИЗ ТОГО ФАКТА, ЧТО
ФУНКЦИЯ РАСПРЕДЕЛЕНИЯ ТОЧКИ~$(X_1,~\dots, X_n)$ ИМЕЕТ ПЛОТНОСТЬ, ЗАВИСЯЩУЮ
ТОЛЬКО ОТ РАССТОЯНИЯ ДО ЦЕНТРА.
%% 145
пОЭТОМУ ПРОЕКЦИЯ ТАКОЙ ТОЧКИ НА ЕДИНИЧНУЮ СФЕРУ ИМЕЕТ РАВНОМЕРНОЕ
РАСПРЕДЕЛЕНИЕ. мЕТОД ВПЕРВЫЕ БЫЛ ПРЕДЛОЖЕН дЖ.~бРАУНОМ.

\section{F.~вАЖНЫЕ ДИСКРЕТНЫЕ РАСПРЕДЕЛЕНИЯ}. вООБЩЕ ГОВОРЯ, К
ВЕРОЯТНОСТНЫМ РАСПРЕДЕЛЕНИЯМ СЛУЧАЙНЫХ ВЕЛИЧИН, ПРИНИМАЮЩИХ
ТОЛЬКО ЦЕЛОЧИСЛЕННЫЕ ЗНАЧЕНИЯ, ПРИМЕНИМЫ ПРИЕМЫ, ОПИСАННЫЕ В НАЧАЛЕ ЭТОГО
РАЗДЕЛА. нО НЕКОТОРЫЕ ИЗ ЭТИХ РАСПРЕДЕЛЕНИЙ СТОЛЬ ВАЖНЫ ДЛЯ ПРАКТИЧЕСКИХ
ПРИМЕНЕНИЙ, ЧТО ЗАСЛУЖИВАЮТ СПЕЦИАЛЬНОГО РАССМОТРЕНИЯ.

{\sl (1)~гЕОМЕТРИЧЕСКОЕ РАСПРЕДЕЛЕНИЕ.\/} еСЛИ НЕКОТОРОЕ СОБЫТИЕ
ПРОИСХОДИТ С ВЕРОЯТНОСТЬЮ~$p$, ЧИСЛО~$N$ НЕЗАВИСИМЫХ ИСПЫТАНИЙ,
НЕОБХОДИМЫХ, ЧТОБЫ ЭТО СОБЫТИЕ ПРОИЗОШЛО (ИЛИ ЧИСЛО ИСПЫТАНИЙ МЕЖДУ
СОБЫТИЯМИ), ПОДЧИНЯЕТСЯ ГЕОМЕТРИЧЕСКОМУ РАСПРЕДЕЛЕНИЮ. мЫ ИМЕЕМ~$N=1$ С
ВЕРОЯТНОСТЬЮ~$p$, $N=2$ С ВЕРОЯТНОСТЬЮ~$(1-p)p$,~\dots, $N=n$ С
ВЕРОЯТНОСТЬЮ~$(1-p)^{n-1}p$. (в СУЩНОСТИ ЭТО ТА ЖЕ СИТУАЦИЯ, С КОТОРОЙ МЫ
ВСТРЕЧАЛИСЬ ПРИ "ПРОВЕРКЕ ИНТЕРВАЛОВ" В~П.~3.3.2; ОНА ВОЗНИКАЕТ, КОГДА МЫ
ИНТЕРЕСУЕМСЯ, СКОЛЬКО РАЗ ВЫПОЛНЯЮТСЯ ОПРЕДЕЛЕННЫЕ ЦИКЛЫ В АЛГОРИТМАХ
ЭТОГО РАЗДЕЛА, НАПРИМЕР ШАГИ~P1--P3 В МЕТОДЕ ПОЛЯРНЫХ КООРДИНАТ.)

дЛЯ ВЫРАБОТКИ ЗНАЧЕНИЯ СЛУЧАЙНОЙ ВЕЛИЧИНЫ С ТАКИМ РАСПРЕДЕЛЕНИЕМ, КОГДА
$p$~МАЛО, ЕСТЬ УДОБНАЯ ФОРМУЛА:
$$
N=\ceil{\ln U/\ln (1-p)}.
\eqno (34)
$$
чТОБЫ ПРОВЕРИТЬ ЕЕ, УБЕДИМСЯ, ЧТО~$\ceil{\ln U/\ln(1-p)}=n$ ТОГДА И ТОЛЬКО
ТОГДА, КОГДА~$n-1<\ln U/\ln (1-p)\le n$, Т.~Е.~$(1-p)^{n-1}>U\ge (1-p)^n$,
А ЭТО ПРОИСХОДИТ С ВЕРОЯТНОСТЬЮ~$p(1-p)^{n-1}$, ЧТО И ТРЕБОВАЛОСЬ ПОКАЗАТЬ.

чАСТНЫЙ СЛУЧАЙ~$p=1/2$ ЕЩЕ ЛЕГЧЕ МОДЕЛИРОВАТЬ НА ДВОИЧНОЙ МАШИНЕ, ТАК КАК
ФОРМУЛА~(34) ПРЕВРАЩАЕТСЯ В~$N=\ceil{-\log_2 U}$, Т.~Е.~$N$ НА ЕДИНИЦУ
БОЛЬШЕ, ЧЕМ ЧИСЛО ПЕРВЫХ НУЛЕВЫХ РАЗРЯДОВ В ДВОИЧНОМ ПРЕДСТАВЛЕНИИ~$U$.

{\sl (2)~бИНОМИАЛЬНОЕ РАСПРЕДЕЛЕНИЕ~$(t, p)$.\/} еСЛИ НЕКОТОРОЕ
СОБЫТИЕ ПРОИСХОДИТ С ВЕРОЯТНОСТЬЮ~$p$, И МЫ ПРОВОДИМ
$t$~НЕЗАВИСИМЫХ ИСПЫТАНИЙ, ПОЛНОЕ ЧИСЛО~$N$ ПРОИСХОДЯЩИХ ПРИ ЭТОМ СОБЫТИЙ
РАВНО~$n$ С ВЕРОЯТНОСТЬЮ~$\perm{t}{n}p^n(1-p)^{t-n}$ (СМ.~П.~1.2.10). дЛЯ
ЭТОГО РАСПРЕДЕЛЕНИЯ НЕТ КАКОГО-ЛИБО ПРЯМОГО МЕТОДА, АНАЛОГИЧНОГО~(34).
оДНАКО МЫ МОГЛИ БЫ ИСПОЛЬЗОВАТЬ ТО ОБСТОЯТЕЛЬСТВО, ЧТО ЕСЛИ $N_1$~ИМЕЕТ
БИНОМИАЛЬНОЕ РАСПРЕДЕЛЕНИЕ~$(t_1, p)$ И ЕСЛИ, НЕЗАВИСИМО, $N_2$~ИМЕЕТ
БИНОМИАЛЬНОЕ РАСПРЕДЕЛЕНИЕ~$(t_2, p)$, ТО $N_1+N_2$~ИМЕЕТ БИНОМИАЛЬНОЕ
РАСПРЕДЕЛЕНИЕ~$(t_1+t_2, p)$. кОГДА $t$~ВЕЛИКО,
%%146
БИНОМИАЛЬНОЕ РАСПРЕДЕЛЕНИЕ ПРИБЛИЖЕННО ОПИСЫВАЕТСЯ НОРМАЛЬНЫМ
РАСПРЕДЕЛЕНИЕМ СО СРЕДНИМ~$tp$ И СРЕДНЕКВАДРАТИЧНЫМ
ОТКЛОНЕНИЕМ~$\sqrt{tp(1-p)}$. сМ. ТАКЖЕ ПРИЕМ, РАССМОТРЕННЫЙ В УПР.~25.

{\sl (3)~рАСПРЕДЕЛЕНИЕ пУАССОНА\/} СО СРЕДНИМ ЗНАЧЕНИЕМ~$\mu$. эТО
РАСПРЕДЕЛЕНИЕ ТАК ЖЕ СВЯЗАНО С ЭКСПОНЕНЦИАЛЬНЫМ РАСПРЕДЕЛЕНИЕМ,
КАК БИНОМИАЛЬНОЕ С ГЕОМЕТРИЧЕСКИМ. оНО ХАРАКТЕРИЗУЕТ ЧИСЛО РЕАЛИЗАЦИИ В
ЕДИНИЦУ ВРЕМЕНИ СОБЫТИЙ, КАЖДОЕ ИЗ КОТОРЫХ МОЖЕТ ПРОИЗОЙТИ В ЛЮБОЙ МОМЕНТ.
нАПРИМЕР, ЧИСЛО ИЗЛУЧАЕМЫХ В СЕКУНДУ АЛЬФА-ЧАСТИЦ ИМЕЕТ РАСПРЕДЕЛЕНИЕ
пУАССОНА. вЕРОЯТНОСТЬ ТОГО, ЧТО~$N=n$, РАВНА
$$
e^{-\mu}\mu^n/n!, \rem{$n\ge0$.}
\eqno(35)
$$

еСЛИ~$N_1$, $N_2$---НЕЗАВИСИМЫЕ ПУАССОНОВСКИЕ СЛУЧАЙНЫЕ ВЕЛИЧИНЫ СО
СРЕДНИМИ~$\mu_1$, $\mu_2$, ТО ВЕРОЯТНОСТЬ ТОГО, ЧТО~$N_1+N_2=n$, РАВНА
$$
\sum_{0\le k \le n}{e^{-\mu_1}\mu_1^k\over k!} {e^{-\mu_2}\mu_2^{n-k}\over (n-k)!}
={e^{-(\mu_1+\mu_2)}(\mu_1+\mu_2)^n\over n!}.
$$
тАКИМ ОБРАЗОМ, $N_1+N_2$~ИМЕЕТ РАСПРЕДЕЛЕНИЕ пУАССОНА СО СРЕДНИМ ЗНАЧЕНИЕМ~$(\mu_1+\mu_2)$.

пРЕДПОЛОЖИМ, ЧТО МЫ ХОТИМ НАПИСАТЬ ОБЩУЮ ПОДПРОГРАММУ, ВЫРАБАТЫВАЮЩУЮ
ЗНАЧЕНИЯ ПУАССОНОВСКИХ СЛУЧАЙНЫХ ВЕЛИЧИН СО СРЕДНИМ~$\mu$, ГДЕ
$\mu$~ЗАДАЕТСЯ ПРИ ВХОДЕ В ПОДПРОГРАММУ.

\alg Q.(рАСПРЕДЕЛЕНИЕ пУАССОНА С ПРОИЗВОЛЬНЫМ~$\mu$.)

\st[вЫЧИСЛИТЬ ЭКСПОНЕНТУ.] пРИСВОИТЬ~$p\asg e^{-\mu}$ И~$N\asg0$, $q\asg1$.
(хОТЯ $e^{-\mu}$~ОБЫЧНО ВЫЧИСЛЯЕТСЯ С ПОМОЩЬЮ АРИФМЕТИКИ С ПЛАВАЮЩЕЙ
ТОЧКОЙ С ПРИВЛЕЧЕНИЕМ СТАНДАРТНОЙ ПОДПРОГРАММЫ, ВОЗМОЖНО, РАЗУМНЕЙ
ПОЛЬЗОВАТЬСЯ АРИФМЕТИКОЙ С ФИКСИРОВАННОЙ ТОЧКОЙ, ПРАВИЛЬНО ВЫБРАВ
МАСШТАБ И ОКРУГЛЕНИЕ ДЛЯ ПОСЛЕДУЮЩИХ ОПЕРАЦИЙ С~$p$ И~$q$.)

\st[пОЛУЧИТЬ СЛУЧАЙНОЕ ЧИСЛО.] вЫРАБОТАТЬ СЛУЧАЙНОЕ ЧИСЛО~$U$, РАВНОМЕРНО
РАСПРЕДЕЛЕННОЕ МЕЖДУ~$0$ И~$1$.

\st[уМНОЖИТЬ.] уСТАНОВИТЬ~$q\asg qU$.

\st[пРОВЕРИТЬ, МЕНЬШЕ ЛИ~$e^{-\mu}$.] еСЛИ~$q\ge p$, УСТАНОВИТЬ~$N\asg N+1$
И ВЕРНУТЬСЯ К ШАГУ~\stp{2}. в ПРОТИВНОМ СЛУЧАЕ АЛГОРИТМ
ЗАКАНЧИВАЕТСЯ ВЫВОДОМ~$N$.
\algend

чТОБЫ ДОКАЗАТЬ СПРАВЕДЛИВОСТЬ МЕТОДА, ЗАМЕТИМ, ЧТО НЕЗАВИСИМЫЕ
РАВНОМЕРНО РАСПРЕДЕЛЕННЫЕ СЛУЧАЙНЫЕ ВЕЛИЧИНЫ УДОВЛЕТВОРЯЮТ УСЛОВИЯМ
$$
U_1\ge p, \quad U_1U_2\ge p, \quad, \ldots, \quad U_1U_2\ldots U_n\ge p,
\quad U_1U_2\ldots U_{n+1}<p
$$
%% 147
С ВЕРОЯТНОСТЬЮ
$$
p\left(\ln{1\over p}\right)^n\bigg/n! \rem{ДЛЯ $0<p\le 1$.}
$$
пРИМЕНЯЯ ИНДУКЦИЮ ПО~$n$, ПОСРЕДСТВОМ ИНТЕГРИРОВАНИЯ
$$
\int_p^1(p/u_1)(\ln (u_1/p))^{n-1}\,du_1/(n-1)!
$$
ПОЛУЧИМ НУЖНЫЙ РЕЗУЛЬТАТ.

дРУГОЙ МЕТОД ВЫРАБОТКИ СЛУЧАЙНЫХ ВЕЛИЧИН С РАСПРЕДЕЛЕНИЕМ пУАССОНА,
ПРИНАДЛЕЖАЩИЙ п.~кРИБС, ОСНОВАН НА УПОМИНАВШЕМСЯ РАНЕЕ СВОЙСТВЕ
СУММИРОВАНИЯ. пРИ ЭТОМ ТРЕБУЕТСЯ БОЛЕЕ ТЩАТЕЛЬНОЕ ПРОГРАММИРОВАНИЕ, ЧЕМ
ПРИ РЕАЛИЗАЦИИ АЛГОРИТМА~Q, НО ПРИ ВЫСОКОМ УРОВНЕ ПРОГРАММИРОВАНИЯ ЕГО
МОЖНО СДЕЛАТЬ БОЛЕЕ БЫСТРЫМ.

\alg K.(рАСПРЕДЕЛЕНИЕ пУАССОНА С ПРОИЗВОЛЬНЫМ~$\mu$.) иСПОЛЬЗУЕТСЯ
ВСПОМОГАТЕЛЬНАЯ ТАБЛИЦА~$M[1]<M[2]<\cdots<M[n]$, ОПИСАННАЯ НИЖЕ%
\note{1}{
в ЭТОМ АЛГОРИТМЕ $n$~ОЗНАЧАЕТ СОВСЕМ НЕ ТО, ЧТО В ПРЕДЫДУЩИХ АБЗАЦАХ И
ЗАДАЕТСЯ ДОСТАТОЧНО ПРОИЗВОЛЬНО; СМ. НИЖЕ.---{\sl пРИМ. ПЕРЕВ.\/}}.

\st[нАЧАЛЬНАЯ УСТАНОВКА.] уСТАНОВИТЬ~$m\asg \mu$, $j\asg n$, $N\asg 0$.

\st[$m\ge M[j]$?] еСЛИ~$m<M[j]$, ПЕРЕЙТИ К ШАГУ~\stp{5}.

\st[вЫРАБОТАТЬ ДЛЯ СРЕДНЕГО~$M[j]$.] вЫРАБОТАТЬ ЗНАЧЕНИЕ~$X$ СЛУЧАЙНОЙ
ЦЕЛОЧИСЛЕННОЙ ВЕЛИЧИНЫ, ИМЕЮЩЕЙ РАСПРЕДЕЛЕНИЕ пУАССОНА СО СРЕДНИМ~$M[j]$.
(эТО МОЖНО ЭФФЕКТИВНО СДЕЛАТЬ, ИСПОЛЬЗУЯ ЗАРАНЕЕ СОСТАВЛЕННЫЕ ТАБЛИЦЫ В
СООТВЕТСТВИИ С ОБЩИМ МЕТОДОМ ДЛЯ ЦЕЛОЧИСЛЕННЫХ РАСПРЕДЕЛЕНИЙ,
РАССМОТРЕННЫМ В УПР.~21.)

\st[иЗМЕНИТЬ~$N$, $m$.] уСТАНОВИТЬ~$m\asg m-M[j]$, $N\asg N+X$
И ВЕРНУТЬСЯ К ШАГУ~\stp{2}.

\st[уМЕНЬШИТЬ~$j$.] уМЕНЬШИТЬ~$j$ НА~$1$. еСЛИ~$j>0$, ВЕРНУТЬСЯ К
ШАГУ~\stp{2}, В ПРОТИВНОМ СЛУЧАЕ АЛГОРИТМ ЗАКАНЧИВАЕТСЯ.
\algend

чТОБЫ ИСПОЛЬЗОВАТЬ ЭТОТ АЛГОРИТМ, МЫ ДОЛЖНЫ СОСТАВИТЬ СПЕЦИАЛЬНЫЕ
ПРОГРАММЫ ДЛЯ ЧАСТНЫХ ЗНАЧЕНИЙ~$\mu$, ЗАДАННЫХ В ТАБЛИЦЕ~$M[1]$, $M[2]$,~\dots,
$M[n]$.

нАПРИМЕР, МЫ МОГЛИ БЫ ПРИНЯТЬ~$n=10$, ТОГДА
$$
\vcenter{\halign{
\hfil$#$&${}#$\hfil\bskip&&\bskip$#$\hfil\bskip\cr
   j&=1       & 2       & 3      & 4      & 5      & 6      & 7 & 8 & 9 & 10\cr
M[j]&=2^{-15} & 2^{-12} & 2^{-9} & 2^{-6} & 2^{-3} & 2^{-1} & 1 & 2 & 4 & \hfill 8 \cr
}}
\eqno(36)
$$
%% 148

эТОТ МЕТОД НЕЭФФЕКТИВЕН ДЛЯ БОЛЬШИХ ЗНАЧЕНИЙ~$\mu$, СКАЖЕМ~$\mu\ge50$.
пРИ~$\mu<M[1]=2^{-15}$ ОПИСАННЫЙ АЛГОРИТМ ПРИСВАИВАЕТ~$N=0$, ТАК КАК
ВЕРОЯТНОСТЬ ТОГО, ЧТО~$N>0$, РАВНА~$1-e^{-\mu}$, Т.~Е.\ МЕНЬШЕ~$1\over 32\,000$.
рАСПРЕДЕЛЕНИЕ пУАССОНА ДЛЯ МАЛЫХ ЗНАЧЕНИЙ~$\mu$ МОДЕЛИРОВАТЬ
ЧРЕЗВЫЧАЙНО ЛЕГКО, ТАК КАК ДЛЯ ВСЕХ ПРАКТИЧЕСКИХ ЦЕЛЕЙ $N$~БУДЕТ ДОВОЛЬНО
МАЛО. тОЛЬКО ДЛЯ РАСПРЕДЕЛЕНИЙ С~$M[j]=4$ И~$8$ ИЗ ПРИВЕДЕННОГО ВЫШЕ
СПИСКА ЗНАЧЕНИЙ ПОТРЕБУЮТСЯ БОЛЬШИЕ ТАБЛИЦЫ ПРИ ВЫПОЛНЕНИИ ШАГА~K3.

дЛЯ БОЛЬШИХ ЗНАЧЕНИЙ~$\mu$ аРЕНС ПРЕДЛОЖИЛ ЭФФЕКТИВНЫЙ, НО ДОВОЛЬНО
СЛОЖНЫЙ МЕТОД ПОРЯДКА~$\sqrt{\mu}$. еГО ПРОЦЕДУРА ДЕЛИТ ПУАССОНОВСКОЕ
РАСПРЕДЕЛЕНИЕ НА ДВЕ ЧАСТИ, ОДНА ИЗ КОТОРЫХ НАПОМИНАЕТ РАВНОБЕДРЕННЫЙ ТРЕУГОЛЬНИК.

\excercises
\ex[10] кАК ВЫ ПРЕДЛОЖИТЕ ВЫРАБАТЫВАТЬ СЛУЧАЙНЫЕ ЧИСЛА,
РАВНОМЕРНО РАСПРЕДЕЛЕННЫЕ МЕЖДУ СЛУЧАЙНЫМИ ЧИСЛАМИ~$\alpha$ И~$\beta$ ($\alpha<\beta$)?

\ex[M16] пРЕДПОЛАГАЯ, ЧТО~$mU$---СЛУЧАЙНОЕ ЦЕЛОЕ ЧИСЛО МЕЖДУ~$0$ И~$m-1$,
НАЙДИТЕ \emph{ТОЧНУЮ} ВЕРОЯТНОСТЬ ТОГО, ЧТО~$\floor{kU}=r$, ЕСЛИ~$0\le r < k$.
сРАВНИТЕ РЕЗУЛЬТАТ С ТРЕБУЮЩЕЙСЯ ВЕРОЯТНОСТЬЮ~$1/k$.

\rex[14] оБСУДИТЕ, ЧТО ПОЛУЧИТСЯ, ЕСЛИ ТРАКТОВАТЬ~$U$ КАК ЦЕЛОЕ ЧИСЛО И
ВЫРАБАТЫВАТЬ ИЗ НЕГО СЛУЧАЙНОЕ ЦЕЛОЕ МЕЖДУ~$0$ И~$k-1$, \emph{ДЕЛЯ}~$U$
НА~$k$ ВМЕСТО ПРЕДЛОЖЕННОГО В ТЕКСТЕ УМНОЖЕНИЯ. тАКИМ ОБРАЗОМ, (1)
СЛЕДУЕТ ИЗМЕНИТЬ ТАК:
% ПРИДЕТСЯ СТАВИТЬ CR, ТАК КАК ТОКЕНЫ КОНЦА СТРОК УЖЕ ЗАСОСАНЫ В АРГУМЕНТЕ
% С КАТЕГОРИЕЙ НЕАКТИВНЫЙ СИМВОЛ
$$
\vbox{
\mixcode
ENTA & 0 \cr
LDX  & U \cr
DIV  & K \cr
\endmixcode
}
$$
рЕЗУЛЬТАТ ОКАЖЕТСЯ В РЕГИСТРЕ~$X$. хОРОШИЙ ЛИ ЭТО МЕТОД?

\ex[м20] дОКАЖИТЕ ОБА СООТНОШЕНИЯ В~(7).

\rex[21] пРЕДЛОЖИТЕ ЭФФЕКТИВНЫЙ МЕТОД ВЫЧИСЛЕНИЯ СЛУЧАЙНОЙ ВЕЛИЧИНЫ С
РАСПРЕДЕЛЕНИЕМ~$px+qx^2+rx^3$, ГДЕ~$p\ge0$, $q\ge0$, $r\ge0$ И~$p+q+r=1$.

\rex[вм21] вЕЛИЧИНА~$X$ ВЫЧИСЛЯЕТСЯ СЛЕДУЮЩИМ МЕТОДОМ.
{\medskip\narrower
{\sl "шАГ~1.\/}~вЫРАБОТАТЬ ДВА СЛУЧАЙНЫХ ЧИСЛА~$U$, $V$.
   %
{\sl шАГ~2.\/}~еСЛИ~$U^2+V^2\ge1$, ВЕРНУТЬСЯ К ШАГУ~1, ИНАЧЕ
УСТАНОВИТЬ~$X\asg U$."
\medskip}
\noindent кАКОВА ФУНКЦИЯ РАСПРЕДЕЛЕНИЯ~$X$? кАК ЧАСТО БУДЕТ ВЫПОЛНЯТЬСЯ
ШАГ~1? (оПРЕДЕЛИТЕ СРЕДНЕЕ И СРЕДНЕКВАДРАТИЧНОЕ ОТКЛОНЕНИЕ.)

\ex[M18] оБЎЯСНИТЕ, ПОЧЕМУ В МЕТОДЕ мАРСАЛЬИ ДЛЯ НОРМАЛЬНЫХ СЛУЧАЙНЫХ
ВЕЛИЧИН ЖЕЛАНИЕ ВЫБРАТЬ~$p_j$ КРАТНЫМИ~$1/256$ ПРИВОДИТ К
ФОРМУЛЕ~$p_j=\floor{64 f(j/4)}/256$,  $1\le j \le 12$.

\ex[10] зАЧЕМ ОСОБО ВЫДЕЛЯТЬ УЗКИЕ ПРЯМОУГОЛЬНИКИ~$f_{13}$,~\dots,
$f_{24}$ В МЕТОДЕ мАРСАЛЬИ НАРАВНЕ С БОЛЬШИМИ~$f_1$,~\dots, $f_{12}$?
(пОЧЕМУ ЭТО ЛУЧШЕ, ЧЕМ ОБЎЕДИНЕНИЕ КАЖДОЙ ПАРЫ~$(f_1, f_{13})$,
$(f_2, f_{14})$,~\dots{} В ОДИН БОЛЬШОЙ ПРЯМОУГОЛЬНИК?)

\ex[вм10] пОЧЕМУ КРИВАЯ~$f(x)$ НА РИС.~9 ВЫПУКЛА ВВЕРХ ПРИ~$x<1$ И ВНИЗ
ДЛЯ~$x>1$?

\ex[вм21] вЫВЕДИТЕ ФОРМУЛЫ ДЛЯ~$a_j$, $b_j$ В СООТНОШЕНИИ~(20). пОКАЖИТЕ
ТАКЖЕ, ЧТО~$E[j]=16/j$, ЕСЛИ~$1\le j \le 4$; $E[j]=1/(e^{j/16-1/32}-1)$,
ЕСЛИ~$5\le j \le 12$.
%% 149

\rex[вм27] дОКАЖИТЕ, ЧТО ШАГИ~M8--M9 В АЛГОРИТМЕ~M ВЫРАБАТЫВАЮТ ЗНАЧЕНИЕ
СЛУЧАЙНОЙ ВЕЛИЧИНЫ, СООТВЕТСТВУЮЩЕЙ ХВОСТУ НОРМАЛЬНОГО РАСПРЕДЕЛЕНИЯ,
Т.~Е.\ ПРИ~$x\ge3$ ВЕРОЯТНОСТЬ ТОГО, ЧТО~$X<x$, РАВНА
$$
\int_3^x e^{-t^2/2}\,dt\bigg/\int_3^{\infty} e^{-t^2/2}\,dt.
$$

\ex[вм46] пОЛИНОМ тЕЙЧРОЕВА~(22)---ЭТО УСЕЧЕННАЯ СУММА
ЧЕБЫШЕВСКИХ ПОЛИНОМОВ, ТАК ЧТО НЕ МОЖЕТ БЫТЬ ЛУЧШЕГО ПРИБЛИЖЕНИЯ ПОЛИНОМОМ
СТЕПЕНИ~$9$ К ФУНКЦИИ~$F^{-1}(F_1(R))$. мОЖНО ЛИ ИСПОЛЬЗОВАТЬ ЛУЧШИЙ ПОЛИНОМ?

\ex[вм25] зАДАНО МНОЖЕСТВО $n$ НЕЗАВИСИМЫХ НОРМАЛЬНЫХ СЛУЧАЙНЫХ ВЕЛИЧИН
$X_1$, $X_2$,~\dots, $X_n$ СО СРЕДНИМ~$0$ И ДИСПЕРСИЕЙ~$1$. пОКАЖИТЕ, КАК
НАЙТИ КОНСТАНТЫ~$b_j$ И~$a_{ij}$, $1\le j \le i \le n$, ТАКИЕ, ЧТО ЕСЛИ
$$
Y_1=b_1+a_{11}X_1, \quad Y_2=b_2+a_{21}X_1+a_{22}X_2, \quad\ldots, \quad
Y_n=b_n+a_{n1}X_1+a_{n2}X_2+\cdots+a_{nn}X_n,
$$
ТО~$Y_1$, $Y_2$,~\dots, $Y_n$---ЗАВИСИМЫЕ, НОРМАЛЬНО РАСПРЕДЕЛЕННЫЕ
СЛУЧАЙНЫЕ ВЕЛИЧИНЫ С ЗАДАННОЙ МАТРИЦЕЙ КОВАРИАЦИЙ~$(c_{ij})$, И КАЖДАЯ
СЛУЧАЙНАЯ ВЕЛИЧИНА~$Y_j$ ИМЕЕТ СРЕДНЕЕ~$\mu_j$. (кОВАРИАЦИЯ~$c_{ij}$
ВЕЛИЧИН~$Y_i$ И~$Y_j$  ОПРЕДЕЛЯЕТСЯ КАК СРЕДНЕЕ
ЗНАЧЕНИЕ~$(Y_i-\mu_i)(Y_j-\mu_j)$. в ЧАСТНОСТИ, $c_{jj}$~ЯВЛЯЕТСЯ
ДИСПЕРСИЕЙ~$Y_j$, КВАДРАТОМ СРЕДНЕКВАДРАТИЧНОГО ОТКЛОНЕНИЯ. нЕ ВСЯКАЯ
МАТРИЦА~$(c_{ij})$ МОЖЕТ БЫТЬ МАТРИЦЕЙ КОВАРИАЦИЙ, И ПРЕДПОЛАГАЕТСЯ,
КОНЕЧНО, ЧТО ВАШ МЕТОД ДОЛЖЕН РАБОТАТЬ ЛИШЬ В ТОМ СЛУЧАЕ, ЕСЛИ РЕШЕНИЕ
ЗАДАЧИ СУЩЕСТВУЕТ.)

\ex[M20] еСЛИ~$X$---СЛУЧАЙНАЯ ВЕЛИЧИНА С НЕПРЕРЫВНОЙ ФУНКЦИЕЙ
РАСПРЕДЕЛЕНИЯ~$F(x)$, А~$c$---КОНСТАНТА, КАКОВО РАСПРЕДЕЛЕНИЕ~$cX$?

\ex[вм21] еСЛИ~$X_1$ И~$X_2$---НЕЗАВИСИМЫЕ СЛУЧАЙНЫЕ ВЕЛИЧИНЫ С ФУНКЦИЯМИ
РАСПРЕДЕЛЕНИЯ~$F_1(x)$ И~$F_2(x)$ И ПЛОТНОСТЯМИ~$f_1(x)=F_1'(x)$,
$f_2(x)=F_2'(x)$, ТО КАКОВЫ ФУНКЦИИ РАСПРЕДЕЛЕНИЯ И ПЛОТНОСТИ ВЕРОЯТНОСТИ
СЛУЧАЙНОЙ ВЕЛИЧИНЫ~$X_1+X_2$?

\ex[вм25] (a)~пОКАЖИТЕ, ЧТО $\chi^2$-РАСПРЕДЕЛЕНИЕ С ОДНОЙ СТЕПЕНЬЮ
СВОБОДЫ---ЭТО РАСПРЕДЕЛЕНИЕ ДЛЯ~$X^2$, ГДЕ~$X$---НОРМАЛЬНАЯ СЛУЧАЙНАЯ
ВЕЛИЧИНА СО СРЕДНИМ, РАВНЫМ НУЛЮ, И ДИСПЕРСИЕЙ, РАВНОЙ ЕДИНИЦЕ.
(b)~пОКАЖИТЕ, ЧТО $\chi^2$-РАСПРЕДЕЛЕНИЕ С ДВУМЯ СТЕПЕНЯМИ СВОБОДЫ---ЭТО
ЭКСПОНЕНЦИАЛЬНОЕ РАСПРЕДЕЛЕНИЕ СО СРЕДНИМ~$2$. (c)~пОКАЖИТЕ, ЧТО
ЕСЛИ~$X_1$ И~$X_2$---НЕЗАВИСИМЫЕ СЛУЧАЙНЫЕ ВЕЛИЧИНЫ, ИМЕЮЩИЕ
$\chi^2$-РАСПРЕДЕЛЕНИЕ С~$\nu_1$ И $\nu_2$~СТЕПЕНЯМИ СВОБОДЫ, ТО
$X_1+X_2$~ИМЕЕТ $\chi^2$-РАСПРЕДЕЛЕНИЕ С $\nu_1+\nu_2$~СТЕПЕНЯМИ СВОБОДЫ.

\rex[м24] кАКОВА \emph{ФУНКЦИЯ РАСПРЕДЕЛЕНИЯ}~$F(x)$ ДЛЯ ГЕОМЕТРИЧЕСКОГО
РАСПРЕДЕЛЕНИЯ С ВЕРОЯТНОСТЬЮ~$p$? кАКОВА \emph{ПРОИЗВОДЯЩАЯ
ФУНКЦИЯ}~$G(z)$? чЕМУ РАВНЫ СРЕДНЕЕ И СРЕДНЕКВАДРАТИЧНОЕ ОТКЛОНЕНИЕ ЭТОГО
РАСПРЕДЕЛЕНИЯ?

\ex[м24] пРЕДЛОЖИТЕ МЕТОД ВЫЧИСЛЕНИЯ СЛУЧАЙНОГО ЦЕЛОГО ЧИСЛА~$N$, ТАКОГО,
ЧТО ОНО ПРИНИМАЕТ ЗНАЧЕНИЕ~$n$ С ВЕРОЯТНОСТЬЮ~$np^2(1-p)^{n-1}$, $n\ge0$.
(оСОБЫЙ ИНТЕРЕС ПРЕДСТАВЛЯЕТ СЛУЧАЙ, КОГДА $p$~ОЧЕНЬ МАЛО.)

\ex[м22] (a)~нАЙДИТЕ, СКОЛЬКО РАЗ В СРЕДНЕМ ВЫПОЛНЯЕТСЯ ШАГ~E2 В
АЛГОРИТМЕ~E; ЧЕМУ РАВНО СРЕДНЕКВАДРАТИЧНОЕ ОТКЛОНЕНИЕ? (b)~тОТ ЖЕ ВОПРОС ДЛЯ ШАГА~E6.

\edef\exref{\the\excerno}
\rex[23] пРЕДПОЛОЖИМ, ЧТО МЫ ХОТИМ ВЫЧИСЛИТЬ СЛУЧАЙНОЕ ЗНАЧЕНИЕ
ВЕЛИЧИНЫ~$X$ С ТАКИМ ДИСКРЕТНЫМ РАСПРЕДЕЛЕНИЕМ:
$$
\vcenter{\halign{
\hfil$#$&\hfil${}#$\hfil\quad&&\hfil$#$\hfil\quad\cr
  \hbox{зНАЧЕНИЕ }X=&x_1           & x_2          & x_3           & x_4          & x_5          & x_6 \cr
\hbox{вЕРОЯТНОСТЬ} =& 90 \over 512 & 81 \over 512 & 131 \over 512 & 10 \over 512 & 32 \over 512 & 168 \over 512 \cr
}}
$$

пОКАЖИТЕ, КАК МОЖНО ЭФФЕКТИВНО ВЫЧИСЛЯТЬ~$X$, ИСПОЛЬЗУЯ ДЕВЯТИРАЗРЯДНОЕ
ДВОИЧНОЕ СЛУЧАЙНОЕ ЧИСЛО~$b_1b_2b_3b_4b_5b_6b_7b_8b_9$, ОПРЕДЕЛЕННОЕ
АНАЛОГИЧНО ФОРМУЛЕ~(16)
%% 150
С ПОМОЩЬЮ ВСПОМОГАТЕЛЬНЫХ ТАБЛИЦ, СОДЕРЖАЩИХ НЕ БОЛЕЕ 35~ЭЛЕМЕНТОВ.

\rex[24] сИТУАЦИЯ В ПРЕДЫДУЩЕМ УПРАЖНЕНИИ НЕСКОЛЬКО ИДЕАЛИЗИРОВАНА, ПОТОМУ
ЧТО ОБЫЧНО ТАК НЕ БЫВАЕТ, ЧТОБЫ ВСЕ ВЕРОЯТНОСТИ ИМЕЛИ ОДИН И ТОТ ЖЕ СТОЛЬ
УДОБНЫЙ МНОЖИТЕЛЬ, КАК~$1/512$. пРЕДПОЛОЖИМ, ЧТО ВЕРОЯТНОСТИ В
ПРЕДЫДУЩЕМ УПРАЖНЕНИИ БЫЛИ ИЗМЕНЕНЫ, А В ДЕЙСТВИТЕЛЬНОСТИ ОНИ ДОЛЖНЫ БЫТЬ ТАКИМИ:
$$
\vcenter{\halign{
\hfil$#$&\hfil${}#$\hfil\quad&&\hfil$#$\hfil\quad\cr
  \hbox{зНАЧЕНИЕ }X=& x_1                          & x_2                          & x_3                           & x_4                          & x_5                          & x_6 \cr
\hbox{вЕРОЯТНОСТЬ} =& {89 \over 512}+\varepsilon_1 & {80 \over 512}+\varepsilon_2 & {131 \over 512}+\varepsilon_3 & {10 \over 512}+\varepsilon_4 & {32 \over 512}+\varepsilon_5 & {168 \over 512}+\varepsilon_6 \cr
}}
$$
зДЕСЬ~$0\le +\varepsilon_j <{1\over 512}$
И~$+\varepsilon_1++\varepsilon_2+\varepsilon_3+\varepsilon_4+\varepsilon_5+\varepsilon_6={2\over 512}$.
пОКАЖИТЕ, КАК ЭФФЕКТИВНО ВЫБРАТЬ ЭТИ ЧИСЛА ДЛЯ ДАННОГО РАВНОМЕРНО
РАСПРЕДЕЛЕННОГО СЛУЧАЙНОГО
%% ?? U=\cdot b_1 b_2
ЧИСЛА~$U=b_1b_2\ldots b_t$, ГДЕ $t$~СРАВНИТЕЛЬНО ВЕЛИКО. кАК И В
УПР.~\exref, ПОПЫТАЙТЕСЬ ИСПОЛЬЗОВАТЬ ВСПОМОГАТЕЛЬНЫЕ ТАБЛИЦЫ,
СОДЕРЖАЩИЕ НЕ БОЛЕЕ 35~ЭЛЕМЕНТОВ.

\ex[вм46] мОЖНО ЛИ ПОЛУЧИТЬ ТОЧНОЕ ПУАССОНОВСКОЕ РАСПРЕДЕЛЕНИЕ
ДЛЯ БОЛЬШИХ~$\mu$, ВЫРАБОТАВ СООТВЕТСТВУЮЩУЮ НОРМАЛЬНУЮ СЛУЧАЙНУЮ
ВЕЛИЧИНУ И ПРЕОБРАЗОВАВ ЕЕ КАКИМ-НИБУДЬ УДОБНЫМ СПОСОБОМ В ЦЕЛОЕ ЧИСЛО,
ПОЛЬЗУЯСЬ ПРИ ЭТОМ (ВОЗМОЖНО УСЛОЖНЕННОЙ) ПОПРАВКОЙ НА НЕБОЛЬШОЙ ПРОЦЕНТ
ВРЕМЕНИ. мОЖНО ЛИ ПОДОБНЫМ ОБРАЗОМ РЕАЛИЗОВАТЬ БИНОМИАЛЬНОЕ РАСПРЕДЕЛЕНИЕ ДЛЯ
БОЛЬШИХ~$t$?

\let\npar=\par
\ex[вм23] (дЖ.~ФОН~нЕЙМАН.) эКВИВАЛЕНТНЫ ЛИ СЛЕДУЮЩИЕ ДВА
СПОСОБА ВЫРАБОТКИ СЛУЧАЙНОЙ ВЕЛИЧИНЫ~$X$ (Т.~Е.\ БУДЕТ ЛИ ВЕЛИЧИНА~$X$
ИМЕТЬ ОДНО И ТО ЖЕ РАСПРЕДЕЛЕНИЕ)?
{\medskip\narrower
{\sl мЕТОД~1.\/}~уСТАНОВИТЬ~$X\asg \sin((\pi/2)U)$, ГДЕ~$U$---СЛУЧАЙНОЕ ЧИСЛО.
 \npar
{\sl мЕТОД~2.\/}~вЫРАБОТАТЬ ДВА НЕЗАВИСИМЫХ СЛУЧАЙНЫХ ЧИСЛА~$U$, $V$
И, ЕСЛИ~$U^2+V^2\ge1$, ПОВТОРИТЬ ТО ЖЕ САМОЕ, ПОКА НЕ БУДЕТ
ВЫПОЛНЯТЬСЯ~$U^2+V^2<1$. тОГДА ПОЛОЖИТЬ~$X\asg \abs{U^2-V^2}/(U^2+V^2)$.
\medskip}

\ex[вм40] (с.~уЛАМ, дЖ.~ФОН~нЕЙМАН.) пУСТЬ~$V_0$---СЛУЧАЙНОЕ ЧИСЛО
МЕЖДУ~$0$ И~$1$. оПРЕДЕЛИМ ПОСЛЕДОВАТЕЛЬНОСТЬ~$\<V_n>$
СООТНОШЕНИЕМ~$V_{n+1}=4V_n\times(1-V_n)$. тЕПЕРЬ, ЕСЛИ ВЫЧИСЛЕНИЯ ДЕЛАЮТСЯ
АБСОЛЮТНО ТОЧНО, РЕЗУЛЬТАТ ИМЕЕТ РАСПРЕДЕЛЕНИЕ~$\sin^2\pi U$,
ГДЕ~$U$---РАВНОМЕРНО РАСПРЕДЕЛЕННОЕ СЛУЧАЙНОЕ ЧИСЛО. дРУГИМИ СЛОВАМИ,
ФУНКЦИЯ РАСПРЕДЕЛЕНИЯ ТАКОВА:
$$
F(x)={1\over \sqrt{2\pi}}\int_0^x {dx \over \sqrt{x(1-x)}}.
$$
в САМОМ ДЕЛЕ, ЕСЛИ МЫ НАПИШЕМ~$V_n=\sin^2 \pi U_n$, ТО ЯСНО,
ЧТО~$U_{n+1}=(2U_n)\bmod 1$. и ИЗ ТОГО, ЧТО ПОЧТИ ВСЕ ДЕЙСТВИТЕЛЬНЫЕ ЧИСЛА
ИМЕЮТ СЛУЧАЙНОЕ ДВОИЧНОЕ ПРЕДСТАВЛЕНИЕ (СМ.~\S~3.5), СЛЕДУЕТ, ЧТО
ПОСЛЕДОВАТЕЛЬНОСТЬ~$U_n$ РАВНОМЕРНО РАСПРЕДЕЛЕННАЯ. нО ЕСЛИ
ВЫЧИСЛЕНИЕ~$V_n$ ПРОИЗВОДИТСЯ С КОНЕЧНОЙ ТОЧНОСТЬЮ, ЭТИ АРГУМЕНТЫ,
ОКАЗЫВАЮТСЯ НЕВЕРНЫМИ, ТАК КАК СКОРО МЫ НАЧИНАЕМ ИМЕТЬ ДЕЛО С ШУМОМ ОТ
ОШИБОК ОКРУГЛЕНИЯ (von Neumann, {\sl Collected Works,\/} Vol.~V, pp.~768--770).
пРОВЕДИТЕ ТЕОРЕТИЧЕСКОЕ И ЭКСПЕРИМЕНТАЛЬНОЕ (ПРИ РАЗНЫХ
ЗНАЧЕНИЯХ~$V_0$) ИССЛЕДОВАНИЕ ПОСЛЕДОВАТЕЛЬНОСТИ~$\<V_n>$, ОПРЕДЕЛЕННОЙ
ВЫШЕ, КОГДА ВЫЧИСЛЕНИЯ ПРОВОДЯТСЯ С КОНЕЧНОЙ ТОЧНОСТЬЮ. пОХОЖЕ ЛИ
РАСПРЕДЕЛЕНИЕ НА ОЖИДАЕМОЕ? мОЖНО ЛИ КАК-НИБУДЬ ИСПОЛЬЗОВАТЬ ЭТИ ЧИСЛА?

\ex[м25] пУСТЬ $X_1$, $X_2$~\dots, $X_5$---ДВОИЧНЫЕ СЛОВА, А КАЖДЫЙ ИЗ
ДВОИЧНЫХ РАЗРЯДОВ НЕЗАВИСИМО ПРИНИМАЕТ ЗНАЧЕНИЕ~$0$ ИЛИ~$1$ С
ВЕРОЯТНОСТЬЮ~$1/2$. кАКОВА ВЕРОЯТНОСТЬ ТОГО, ЧТО В ДАННОЙ ПОЗИЦИИ
РЕЗУЛЬТАТ~$X_1\lor (X_2\land (X_3\lor (X_4 \land X_5)))$ СОДЕРЖИТ~$1$.
сДЕЛАЙТЕ ОБОБЩЕНИЕ.

%% 151
\bye