\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