\input style of a Random Sequence" ({\sl BIT,\/} {\bf 5} (1965), 246--250). пОСЛЕДОВАТЕЛЬНОСТЬ, ПОСТРОЕННАЯ В ЭТОЙ СТАТЬЕ, ЦЕЛИКОМ СОСТОИТ ИЗ РАЦИОНАЛЬНЫХ ЧИСЕЛ. кАЖДОЕ ЧИСЛО~$U_n$ ИМЕЕТ КОНЕЧНОЕ ПРЕДСТАВЛЕНИЕ В ДВОИЧНОЙ СИСТЕМЕ СЧИСЛЕНИЯ. нЕСКОЛЬКО БОЛЕЕ СЛОЖНЫЙ ЯВНЫЙ СПОСОБ ПОСТРОЕНИЯ $\infty\hbox{-РАСПРЕДЕЛЕННОЙ}$ ПОСЛЕДОВАТЕЛЬНОСТИ МОЖНО ПОЛУЧИТЬ ИЗ ПРИВЕДЕННОЙ НИЖЕ ТЕОРЕМЫ~W. \qsection{C. эКВИВАЛЕНТНЫ ЛИ ПОНЯТИЯ $\infty\hbox{-РАСПРЕДЕЛЕННОСТИ}$ И СЛУЧАЙНОСТИ}? иЗ ВСЕГО СКАЗАННОГО ВЫШЕ ПРО $\infty\hbox{-РАСПРЕДЕЛЕННЫЕ}$ ПОСЛЕДОВАТЕЛЬНОСТИ СЛЕДУЕТ, ЧТО ПОНЯТИЕ $\infty\hbox{-РАСПРЕДЕЛЕННОСТИ}$ ВАЖНО САМО ПО СЕБЕ. мОЖНО ТАКЖЕ С ДОСТАТОЧНЫМ ОСНОВАНИЕМ СЧИТАТЬ, ЧТО СЛЕДУЮЩЕЕ ОПРЕДЕЛЕНИЕ ХОРОШО ОПИСЫВАЕТ ИНТУИТИВНОЕ ПОНЯТИЕ СЛУЧАЙНОСТИ. \proclaim оПРЕДЕЛЕНИЕ R1. пОСЛЕДОВАТЕЛЬНОСТЬ НА~$[0, 1)$ НАЗЫВАЕТСЯ "СЛУЧАЙНОЙ", ЕСЛИ ОНА $\infty\hbox{-РАСПРЕДЕЛЕНА}$. мЫ ВИДЕЛИ, ЧТО ТАКИЕ ПОСЛЕДОВАТЕЛЬНОСТИ УДОВЛЕТВОРЯЮТ ВСЕМ ТЕСТАМ П.~3.3.2 И ЕЩЕ МНОГИМ ДРУГИМ. пОПРОБУЕМ КРИТИЧЕСКИ ПОДОЙТИ К ЭТОМУ ОПРЕДЕЛЕНИЮ. пРЕЖДЕ ВСЕГО, ЯВЛЯЕТСЯ ЛИ ЛЮБАЯ "ИСТИННО СЛУЧАЙНАЯ" ПОСЛЕДОВАТЕЛЬНОСТЬ $\infty\hbox{-РАСПРЕДЕЛЕННОЙ}$? сУЩЕСТВУЕТ НЕСЧЕТНОЕ КОЛИЧЕСТВО ПОСЛЕДОВАТЕЛЬНОСТЕЙ~$U_0$, $U_1$,~\dots{} ДЕЙСТВИТЕЛЬНЫХ ЧИСЕЛ, ЗАКЛЮЧЕННЫХ МЕЖДУ НУЛЕМ И ЕДИНИЦЕЙ. еСЛИ ЗНАЧЕНИЯ~$U_0$, $U_1$,~\dots{} ПОЛУЧАЮТСЯ С ПОМОЩЬЮ ДАТЧИКА ИСТИННО СЛУЧАЙНЫХ ЧИСЕЛ, ЛЮБУЮ ИЗ ПОСЛЕДОВАТЕЛЬНОСТЕЙ МОЖНО СЧИТАТЬ РАВНОЦЕННОЙ. пРИ ЭТОМ НЕКОТОРЫЕ ИЗ ЭТИХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ (В ДЕЙСТВИТЕЛЬНОСТИ БЕСКОНЕЧНО БОЛЬШОЕ ИХ ЧИСЛО) НЕ БУДУТ ДАЖЕ РАВНОМЕРНО РАСПРЕДЕЛЕНЫ. с ДРУГОЙ СТОРОНЫ, ПРИ ЛЮБОМ РАЗУМНОМ ОПРЕДЕЛЕНИИ ВЕРОЯТНОСТИ НА ЭТОМ ПРОСТРАНСТВЕ ВСЕХ ВОЗМОЖНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ МЫ ДОЛЖНЫ ЗАКЛЮЧИТЬ, ЧТО СЛУЧАЙНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ $\infty\hbox{-РАСПРЕДЕЛЕНА}$ С \emph{ВЕРОЯТНОСТЬЮ}~$1$. тАКИМ ОБРАЗОМ, МЫ ПРИХОДИМ К ФОРМАЛИЗАЦИИ ОПРЕДЕЛЕНИЯ СЛУЧАЙНОСТИ, ДАННОГО фРЭНКЛИНОМ (СМ.\ НАЧАЛО ПАРАГРАФА). \proclaim оПРЕДЕЛЕНИЕ R2. пОСЛЕДОВАТЕЛЬНОСТЬ~$\$ НА~$[0, 1)$ НАЗЫВАЕТСЯ "СЛУЧАЙНОЙ", ЕСЛИ ДЛЯ ЛЮБОГО СВОЙСТВА~$P$, ТАКОГО, ЧТО~$P(\)$ СПРАВЕДЛИВО С ВЕРОЯТНОСТЬЮ~1 ДЛЯ ПОСЛЕДОВАТЕЛЬНОСТИ~$\$ НЕЗАВИСИМЫХ ВЫБОРОК СЛУЧАЙНЫХ ВЕЛИЧИН ИЗ РАВНОМЕРНОГО РАСПРЕДЕЛЕНИЯ, СПРАВЕДЛИВО~$P(\)$. вОЗМОЖНО ЛИ, ЧТО ОПРЕДЕЛЕНИЕ~R1 ЭКВИВАЛЕНТНО ОПРЕДЕЛЕНИЮ~R2? пОПРОБУЕМ ВЫДВИНУТЬ ПРОТИВ ОПРЕДЕЛЕНИЯ~R1 НЕКОТОРЫЕ ВОЗРАЖЕНИЯ. пРЕЖДЕ ВСЕГО ОПРЕДЕЛЕНИЕ~R1 ИМЕЕТ ДЕЛО ТОЛЬКО С ПРЕДЕЛЬНЫМИ СВОЙСТВАМИ ПОСЛЕДОВАТЕЛЬНОСТИ ПРИ~$n\to\infty$. сУЩЕСТВУЮТ $\infty\hbox{-РАСПРЕДЕЛЕННЫЕ}$ ПОСЛЕДОВАТЕЛЬНОСТИ, НАЧИНАЮЩИЕСЯ ОТРЕЗКОМ %% 172 ИЗ МИЛЛИОНА НУЛЕЙ. сЛЕДУЕТ ЛИ СЧИТАТЬ ТАКУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ СЛУЧАЙНОЙ? эТО ВОЗРАЖЕНИЕ НЕ ОЧЕНЬ СЕРЬЕЗНО. пУСТЬ~$\varepsilon$---ЛЮБОЕ ПОЛОЖИТЕЛЬНОЕ ЧИСЛО, ТОГДА ВПОЛНЕ ВОЗМОЖНО, ЧТО КАЖДЫЙ ИЗ ПЕРВОГО МИЛЛИОНА ЧЛЕНОВ ПОСЛЕДОВАТЕЛЬНОСТИ МЕНЬШЕ~$\varepsilon$. кАК МЫ УЖЕ ОТМЕЧАЛИ РАНЕЕ, НЕТ СПОСОБА, ПОЗВОЛЯЮЩЕГО СУДИТЬ О ТОМ, СЛУЧАЙНА ИЛИ НЕТ КОНЕЧНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ. иСТИННО СЛУЧАЙНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ С ВЕРОЯТНОСТЬЮ ЕДИНИЦА СОДЕРЖИТ БЕСКОНЕЧНО МНОГО ОТРЕЗКОВ ПО МИЛЛИОНУ ПОСЛЕДОВАТЕЛЬНЫХ ЧЛЕНОВ, КАЖДЫЙ ИЗ КОТОРЫХ МЕНЬШЕ~$\varepsilon$. пОЧЕМУ ЖЕ ТАКОЙ ОТРЕЗОК НЕ МОЖЕТ ОКАЗАТЬСЯ В НАЧАЛЕ ПОСЛЕДОВАТЕЛЬНОСТИ? с ДРУГОЙ СТОРОНЫ, РАССМОТРИМ ОПРЕДЕЛЕНИЕ~R2, И ПУСТЬ $P$---СВОЙСТВО ПОСЛЕДОВАТЕЛЬНОСТИ, СОСТОЯЩЕЕ В ТОМ, ЧТО ВСЕ ЕЕ ЭЛЕМЕНТЫ РАЗЛИЧНЫ. сВОЙСТВО~$P$ СПРАВЕДЛИВО С ВЕРОЯТНОСТЬЮ ЕДИНИЦА, ПОЭТОМУ ЛЮБАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ С МИЛЛИОНОМ НУЛЕЙ ПО \emph{ЭТОМУ} КРИТЕРИЮ НЕ ЯВЛЯЕТСЯ СЛУЧАЙНОЙ. пУСТЬ ТЕПЕРЬ СВОЙСТВО~$P$ ЗАКЛЮЧАЕТСЯ В ТОМ, ЧТО \emph{НИ ОДИН} ЭЛЕМЕНТ ПОСЛЕДОВАТЕЛЬНОСТИ НЕ РАВЕН НУЛЮ. оНО СПРАВЕДЛИВО С ВЕРОЯТНОСТЬЮ ЕДИНИЦА, ПОЭТОМУ ПО ОПРЕДЕЛЕНИЮ~R2 ЛЮБАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ, У КОТОРОЙ ЕСТЬ НУЛЕВОЙ ЭЛЕМЕНТ, НЕ ЯВЛЯЕТСЯ СЛУЧАЙНОЙ. рАССМОТРИМ БОЛЕЕ ОБЩИЙ СЛУЧАЙ: ПУСТЬ~$x_0$---ЛЮБОЕ ЗАДАННОЕ ЧИСЛО, ЗАКЛЮЧЕННОЕ МЕЖДУ НУЛЕМ И ЕДИНИЦЕЙ, И~$P$---СВОЙСТВО, СОСТОЯЩЕЕ В ТОМ, ЧТО НИ ОДИН ЭЛЕМЕНТ ПОСЛЕДОВАТЕЛЬНОСТИ НЕ РАВЕН~$x_0$. иЗ ОПРЕДЕЛЕНИЯ~R2 СЛЕДУЕТ, ЧТО НИКАКАЯ СЛУЧАЙНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ НЕ МОЖЕТ СОДЕРЖАТЬ ЭЛЕМЕНТ, РАВНЫЙ~$x_0$! тЕПЕРЬ МОЖНО ДОКАЗАТЬ, ЧТО \emph{НИ ОДНА ПОСЛЕДОВАТЕЛЬНОСТЬ НЕ МОЖЕТ УДОВЛЕТВОРЯТЬ УСЛОВИЯМ, СФОРМУЛИРОВАННЫМ В ОПРЕДЕЛЕНИИ}~R2. (в САМОМ ДЕЛЕ, ЕСЛИ~$U_0$, $U_1$,~\dots{} ЕСТЬ ПОСЛЕДОВАТЕЛЬНОСТЬ, УДОВЛЕТВОРЯЮЩАЯ ЭТИМ УСЛОВИЯМ, ТО ПОЛОЖИМ~$x_0=U_0$.) тАКИМ ОБРАЗОМ, ЕСЛИ~R1---СЛИШКОМ СЛАБОЕ ОПРЕДЕЛЕНИЕ, ТО R2---СЛИШКОМ СИЛЬНОЕ. "пРАВИЛЬНОЕ" ОПРЕДЕЛЕНИЕ ДОЛЖНО БЫТЬ МЕНЕЕ ОГРАНИЧИТЕЛЬНЫМ, ЧЕМ~R2. оДНАКО МЫ, ВООБЩЕ ГОВОРЯ, ЕЩЕ НЕ ДОКАЗАЛИ, ЧТО R1 СЛИШКОМ СЛАБО, ПОЭТОМУ ПРОДОЛЖИМ ЕГО ИЗУЧЕНИЕ. вЫШЕ ГОВОРИЛОСЬ О ТОМ, ЧТО МОЖНО ПОСТРОИТЬ $\infty\hbox{-РАСПРЕДЕЛЕННУЮ}$ ПОСЛЕДОВАТЕЛЬНОСТЬ \emph{РАЦИОНАЛЬНЫХ} ЧИСЕЛ. (рАЗУМЕЕТСЯ, В ЭТОМ НЕТ НИЧЕГО ОСОБЕННО УДИВИТЕЛЬНОГО: СМ.\ УПР.~1.8.) пОЧТИ ВСЕ ДЕЙСТВИТЕЛЬНЫЕ ЧИСЛА ИРРАЦИОНАЛЬНЫ, ПОЭТОМУ МОЖНО ПОТРЕБОВАТЬ, ЧТОБЫ ДЛЯ СЛУЧАЙНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ИМЕЛО МЕСТО РАВЕНСТВО \EQ{ \Pr(U_n \hbox{ РАЦИОНАЛЬНО})=0. } зАМЕТИМ, ЧТО РАВНОМЕРНАЯ РАСПРЕДЕЛЕННОСТЬ, ПО ОПРЕДЕЛЕНИЮ ОЗНАЧАЕТ, ЧТО~$\Pr(u\le U_n$". в ЧАСТНОСТИ, ЕСЛИ МНОЖЕСТВО~$S$ СОСТАВЛЕНО ИЗ РАЦИОНАЛЬНЫХ ЧИСЕЛ, ОНО ИМЕЕТ МЕРУ НУЛЬ, И, ТАКИМ ОБРАЗОМ, НИКАКАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ РАЦИОНАЛЬНЫХ ЧИСЕЛ НЕ ЯВЛЯЕТСЯ РАВНОМЕРНО РАСПРЕДЕЛЕННОЙ В ЭТОМ ОБОБЩЕННОМ СМЫСЛЕ. мОЖНО ОЖИДАТЬ, ЧТО ТЕОРЕМА~B ОБОБЩАЕТСЯ НА СЛУЧАЙ ИНТЕГРИРОВАНИЯ В СМЫСЛЕ лЕБЕГА, ЕСЛИ ПОТРЕБОВАТЬ ВЫПОЛНЕНИЯ СВОЙСТВА~\eqref[27]. оДНАКО МЫ ОПЯТЬ ПРИХОДИМ К ВЫВОДУ, ЧТО ОПРЕДЕЛЕНИЕ~\eqref[27] ЯВЛЯЕТСЯ СЛИШКОМ ЖЕСТКИМ, ПОСКОЛЬКУ НИ ОДНА ПОСЛЕДОВАТЕЛЬНОСТЬ \emph{НЕ} ОБЛАДАЕТ ЭТИМ СВОЙСТВОМ! еСЛИ $U_0$, $U_1$,~\dots---НЕКОТОРАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ, ТО МЕРА МНОЖЕСТВА~$S=\set{U_0, U_1,~\ldots}$ РАВНА НУЛЮ, ОДНАКО~$\Pr(U_n\in S)=1$. тАКИМ ОБРАЗОМ, ПУТЕМ ТЕХ ЖЕ РАССУЖДЕНИЙ, С ПОМОЩЬЮ КОТОРЫХ МЫ ИСКЛЮЧИЛИ ИЗ СЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ РАЦИОНАЛЬНЫЕ ЧИСЛА, МОЖНО ИСКЛЮЧИТЬ ВСЕ СЛУЧАЙНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ. пОКА ВСЕ ЕЩЕ НЕ ПОКАЗАНО, ЧТО ОПРЕДЕЛЕНИЕ~R1 НЕПРИГОДНО. пРОТИВ НЕГО, ОДНАКО, СУЩЕСТВУЮТ ВЕСКИЕ ВОЗРАЖЕНИЯ. еСЛИ, НАПРИМЕР, ИМЕЕТСЯ СЛУЧАЙНАЯ В ИНТУИТИВНОМ СМЫСЛЕ ПОСЛЕДОВАТЕЛЬНОСТЬ, БЕСКОНЕЧНАЯ ЕЕ ПОДПОСЛЕДОВАТЕЛЬНОСТЬ \EQ[28]{ U_0, U_1, U_4, U_9,~\ldots, U_{n^2},~\ldots } ДОЛЖНА ТАКЖЕ БЫТЬ СЛУЧАЙНОЙ. дЛЯ $\infty\hbox{-РАСПРЕДЕЛЕННОЙ}$ ПОСЛЕДОВАТЕЛЬНОСТИ ЭТО НЕ ВСЕГДА СПРАВЕДЛИВО. (дЕЙСТВИТЕЛЬНО, ЕСЛИ ВЗЯТЬ ЛЮБУЮ $\infty\hbox{-РАСПРЕДЕЛЕННУЮ}$ ПОСЛЕДОВАТЕЛЬНОСТЬ И ПОЛОЖИТЬ~$U_{n^2}\leftarrow 0$ ДЛЯ ВСЕХ~$n$, ВЕЛИЧИНЫ~$\nu_k(n)$, КОТОРЫЕ ПОЯВЛЯЮТСЯ ПРИ ПРОВЕРКЕ $k\hbox{-РАСПРЕДЕЛЕННОСТИ}$, ИЗМЕНЯТСЯ НЕ БОЛЬШЕ, ЧЕМ НА ВЕЛИЧИНУ ПОРЯДКА~$\sqrt{n}$, ТАК ЧТО ПРЕДЕЛЫ ОТНОШЕНИЙ~$\nu_k(n)/n$ НЕ ИЗМЕНЯТСЯ.) оТСЮДА СЛЕДУЕТ, ЧТО~R1 НЕ ОБЛАДАЕТ ЭТИМ СВОЙСТВОМ СЛУЧАЙНОСТИ. пОПРОБУЕМ УСИЛИТЬ~R1 СЛЕДУЮЩИМ ОБРАЗОМ. \proclaim оПРЕДЕЛЕНИЕ~R3. пОСЛЕДОВАТЕЛЬНОСТЬ НА~$[0, 1)$ НАЗЫВАЕТСЯ "СЛУЧАЙНОЙ", ЕСЛИ КАЖДАЯ ЕЕ БЕСКОНЕЧНАЯ ПОДПОСЛЕДОВАТЕЛЬНОСТЬ $\infty\hbox{-РАСПРЕДЕЛЕНА}$. оДНАКО И ЭТО ОПРЕДЕЛЕНИЕ ОКАЗЫВАЕТСЯ СЛИШКОМ ОГРАНИЧИТЕЛЬНЫМ, ПОСКОЛЬКУ ИЗ ЛЮБОЙ РАВНОМЕРНО РАСПРЕДЕЛЕННОЙ ПОСЛЕДОВАТЕЛЬНОСТИ~$\$ МОЖНО ВЫДЕЛИТЬ МОНОТОННУЮ ПОДПОСЛЕДОВАТЕЛЬНОСТЬ~$U_{s_0}$ НА~$[0, 1)$ НАЗЫВАЕТСЯ "СЛУЧАЙНОЙ", ЕСЛИ КАКОВ БЫ НИ БЫЛ ЭФФЕКТИВНЫЙ АЛГОРИТМ, С ПОМОЩЬЮ КОТОРОГО ПОЛУЧАЕТСЯ БЕСКОНЕЧНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ РАЗЛИЧНЫХ НЕОТРИЦАТЕЛЬНЫХ ЦЕЛЫХ ЧИСЕЛ~$s_n$, ГДЕ~$n\ge0$, ПОДПОСЛЕДОВАТЕЛЬНОСТЬ~$U_{s_0}$, $U_{s_1}$,~\dots, СООТВЕТСТВУЮЩАЯ ЭТОМУ АЛГОРИТМУ, ЯВЛЯЕТСЯ $\infty\hbox{-РАСПРЕДЕЛЕННОЙ}$. аЛГОРИТМЫ, О КОТОРЫХ ИДЕТ РЕЧЬ,---ЭТО ПРОЦЕДУРЫ, ВЫЧИСЛЯЮЩИЕ~$s_n$ ПО ЗАДАННОМУ~$n$. в ЭТОМ ОПРЕДЕЛЕНИИ ГОВОРИТСЯ ОБО ВСЕХ БЕСКОНЕЧНЫХ "РЕКУРСИВНО ПЕРЕЧИСЛИМЫХ" ПОДПОСЛЕДОВАТЕЛЬНОСТЯХ В СООТВЕТСТВИИ С ОБЫЧНЫМ ОПРЕДЕЛЕНИЕМ РЕКУРСИВНОЙ ПЕРЕЧИСЛИМОСТИ (СМ.~ГЛ.~11). оТНОСИТЕЛЬНО ДАННОГО ОПРЕДЕЛЕНИЯ СЛЕДУЕТ СДЕЛАТЬ НЕСКОЛЬКО ЗАМЕЧАНИЙ. пОСЛЕДОВАТЕЛЬНОСТЬ~$\<\pi^n\bmod 1>$ НАВЕРНЯКА \emph{НЕ} БУДЕТ УДОВЛЕТВОРЯТЬ ОПРЕДЕЛЕНИЮ~R4, ПОСКОЛЬКУ ИЛИ ОНА НЕ ЯВЛЯЕТСЯ РАВНОМЕРНО РАСПРЕДЕЛЕННОЙ, ИЛИ СУЩЕСТВУЕТ ЭФФЕКТИВНЫЙ АЛГОРИТМ, ОПРЕДЕЛЯЮЩИЙ БЕСКОНЕЧНУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ~$s_n$, ТАКУЮ, ЧТО~$(\pi^{s_0}\bmod 1) < (\pi^{s_1}\bmod 1) < \ldots\,$. мОЖНО ПОЭТОМУ УТВЕРЖДАТЬ, ЧТО \emph{НИ ОДНА ЯВНЫМ ОБРАЗОМ ОПРЕДЕЛЕННАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ НЕ МОЖЕТ УДОВЛЕТВОРЯТЬ ОПРЕДЕЛЕНИЮ}~R4. с ЭТИМ СЛЕДУЕТ СОГЛАСИТЬСЯ, ЕСЛИ СЧИТАТЬ, ЧТО ЯВНЫМ ОБРАЗОМ ОПРЕДЕЛЕННАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ НЕ МОЖЕТ БЫТЬ ДЕЙСТВИТЕЛЬНО СЛУЧАЙНОЙ. вПОЛНЕ ВОЗМОЖНО, ОДНАКО, ЧТО ПОСЛЕДОВАТЕЛЬНОСТЬ~$\<\theta^n\bmod 1>$ БУДЕТ УДОВЛЕТВОРЯТЬ ОПРЕДЕЛЕНИЮ~R4 ДЛЯ ПОЧТИ ВСЕХ ДЕЙСТВИТЕЛЬНЫХ ЧИСЕЛ~$\theta>1$. зДЕСЬ НЕТ ПРОТИВОРЕЧИЯ, ПОСКОЛЬКУ ПОЧТИ ВСЕ~$\theta$ НЕВОЗМОЖНО ВЫЧИСЛИТЬ С ПОМОЩЬЮ АЛГОРИТМА. иЗВЕСТНЫ, НАПРИМЕР, СЛЕДУЮЩИЕ ФАКТЫ. (i)~пОСЛЕДОВАТЕЛЬНОСТЬ~$\<\theta^m\bmod 1>$ УДОВЛЕТВОРЯЕТ ОПРЕДЕЛЕНИЮ~R4 ДЛЯ ПОЧТИ ВСЕХ ДЕЙСТВИТЕЛЬНЫХ~$\theta>1$, ЕСЛИ УСЛОВИЕ $\infty\hbox{-РАСПРЕДЕЛЕННОСТИ}$ ЗАМЕНИТЬ НА УСЛОВИЕ $1\hbox{-РАСПРЕДЕЛЕННОСТИ}$. эТА ТЕОРЕМА БЫЛА ДОКАЗАНА ю.~кОКСМОЙ ({\sl Compositio Mathematica,\/} {\bf 2} (1935), 250--258). (ii)~пОСЛЕДОВАТЕЛЬНОСТЬ~$\<\theta^{s(n)}\bmod 1>$ $\infty\hbox{-РАСПРЕДЕЛЕНА}$ ДЛЯ ПОЧТИ ВСЕХ ДЕЙСТВИТЕЛЬНЫХ~$\theta>1$, ЕСЛИ~$\$ ЕСТЬ ПОСЛЕДОВАТЕЛЬНОСТЬ ЦЕЛЫХ ЧИСЕЛ, ТАКИХ, ЧТО~$s(n+1)-s(n)\to\infty$ ПРИ~$n\to\infty$. мОЖНО, НАПРИМЕР, ПОЛОЖИТЬ~$s(n)=n^2$, ИЛИ~$s(n)=\floor{n\log n}$. оПРЕДЕЛЕНИЕ~R4 НАМНОГО СИЛЬНЕЕ ОПРЕДЕЛЕНИЯ~R1, ОДНАКО И ОНО ВСЕ ЕЩЕ СЛИШКОМ СЛАБО. пУСТЬ, НАПРИМЕР, ИМЕЕТСЯ ИСТИННО СЛУЧАЙНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ~$\$. оПРЕДЕЛИМ ПОДПОСЛЕДОВАТЕЛЬНОСТЬ~$\$ СЛЕДУЮЩИМ ОБРАЗОМ: $s_0=0$, И ДЛЯ~$n>0$ ЧИСЛО~$s_n$---НАИМЕНЬШЕЕ ПОЛОЖИТЕЛЬНОЕ ЦЕЛОЕ, ТАКОЕ, ЧТО ВСЕ ЧИСЛА~$U_{s_n-1}$, $U_{s_n-2}$,~\dots, $U_{s_n-n}$ МЕНЬШЕ ПОЛОВИНЫ. тЕМ САМЫМ МЫ РАССМАТРИВАЕМ ПОДПОСЛЕДОВАТЕЛЬНОСТЬ ВЕЛИЧИН, СЛЕДУЮЩИХ СРАЗУ ЖЕ ЗА СЕРИЕЙ ИЗ $n$~ЧЛЕНОВ, КАЖДЫЙ ИЗ КОТОРЫХ МЕНЬШЕ~$1/2$. пРЕДПОЛОЖИМ, ЧТО "$U_n<1/2$" СООТВЕТСТВУЕТ ВЫПАДЕНИЮ "РЕШЕТКИ" ПРИ БРОСАНИИ МОНЕТЫ. иГРОКИ ОБЫЧНО СЧИТАЮТ, ЧТО ЕСЛИ МОНЕТА БРОСАЕТСЯ ЧЕСТНО, ТО ДЛИННАЯ СЕРИЯ ВЫПАДЕНИЯ "РЕШЕТОК" УВЕЛИЧИВАЕТ %% 175 ВЕРОЯТНОСТЬ ПОСЛЕДУЮЩЕГО ВЫПАДЕНИЯ "ОРЛА", И ОПРЕДЕЛЕННАЯ НАМИ ПОДПОСЛЕДОВАТЕЛЬНОСТЬ~$\$ СООТВЕТСТВУЕТ СТРАТЕГИИ ИГРОКА, ПРИ КОТОРОЙ ОН ДЕЛАЕТ $n\hbox{-Ю}$~СТАВКУ ПРИ БРОСАНИИ МОНЕТЫ, СЛЕДУЮЩЕМ ВСЛЕД ЗА ПЕРВЫМ ПОСЛЕДОВАТЕЛЬНЫМ ВЫПАДЕНИЕМ $n$~"РЕШЕТОК". иГРОК МОЖЕТ СЧИТАТЬ, ЧТО~$\Pr(U_{s_n}\ge 1/2)$ ПРЕВОСХОДИТ ПОЛОВИНУ, НО, РАЗУМЕЕТСЯ, В ИСТИННО СЛУЧАЙНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ЗНАЧЕНИЯ~$\$ БУДУТ СОВЕРШЕННО СЛУЧАЙНЫМИ. нЕТ ТАКОЙ СТРАТЕГИИ, КОТОРАЯ ОБЕСПЕЧИВАЛА БЫ ПРЕИМУЩЕСТВО В ИГРЕ. в ОПРЕДЕЛЕНИИ~R4 НИЧЕГО НЕ ГОВОРИТСЯ О ПОДПОСЛЕДОВАТЕЛЬНОСТЯХ, СОСТАВЛЕННЫХ СОГЛАСНО ТАКОЙ СТРАТЕГИИ, ПОЭТОМУ НУЖНО ПРЕДЛОЖИТЬ НЕЧТО БОЛЬШЕЕ. оПРЕДЕЛИМ "ПРАВИЛО ПОСТРОЕНИЯ ПОДПОСЛЕДОВАТЕЛЬНОСТИ"~$\cR$ КАК БЕСКОНЕЧНУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ ФУНКЦИЙ~$\$, ГДЕ~$n\ge0$, $f_n$---ФУНКЦИЯ $n$~ПЕРЕМЕННЫХ, И~$f_n(x_1,~\ldots, x_n)$ МОЖЕТ ПРИНИМАТЬ ЗНАЧЕНИЕ~$0$ ИЛИ~$1$. зДЕСЬ $x_1$,~\dots, $x_n$ ЯВЛЯЮТСЯ ЭЛЕМЕНТАМИ НЕКОТОРОГО МНОЖЕСТВА~$S$. (тАКИМ ОБРАЗОМ, $f_0$~ЕСТЬ ПОСТОЯННАЯ ФУНКЦИЯ, РАВНАЯ~$0$ ИЛИ~$1$.) пРАВИЛО~$\cR$ ПОСТРОЕНИЯ ПОДПОСЛЕДОВАТЕЛЬНОСТИ ОПРЕДЕЛЯЕТ ПОДПОСЛЕДОВАТЕЛЬНОСТЬ ЛЮБОЙ БЕСКОНЕЧНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ~$\$ ЭЛЕМЕНТОВ~$S$ СЛЕДУЮЩИМ ОБРАЗОМ: \dfn{$n\hbox{-Й}$ ЧЛЕН~$X_n$ СОДЕРЖИТСЯ В ПОДПОСЛЕДОВАТЕЛЬНОСТИ~$\\cR$ В ТОМ И ТОЛЬКО ТОМ СЛУЧАЕ, КОГДА~$f_n(X_0, X_1,~\dots, X_{n-1})=1$.} зАМЕТИМ, ЧТО ОПРЕДЕЛЕННАЯ ТАКИМ ОБРАЗОМ ПОДПОСЛЕДОВАТЕЛЬНОСТЬ~$\\cR$ НЕ ОБЯЗАТЕЛЬНО ЯВЛЯЕТСЯ БЕСКОНЕЧНОЙ И МОЖЕТ ДАЖЕ БЫТЬ ПУСТОЙ. "пОДПОСЛЕДОВАТЕЛЬНОСТЬ ИГРОКА", ОПИСАННАЯ ВЫШЕ, СООТВЕТСТВУЕТ СЛЕДУЮЩЕМУ ПРАВИЛУ ПОСТРОЕНИЯ ПОДПОСЛЕДОВАТЕЛЬНОСТИ: "$f_0=1$; $f_n(x_1,~\ldots, x_n)=1$ ПРИ~$n>0$ В ТОМ И ТОЛЬКО ТОМ СЛУЧАЕ, КОГДА СУЩЕСТВУЕТ НЕКОТОРОЕ~$k$, $0$ НА~$[0, 1)$ НАЗЫВАЕТСЯ "СЛУЧАЙНОЙ", ЕСЛИ $b\hbox{-ИЧНАЯ}$ ПОСЛЕДОВАТЕЛЬНОСТЬ~$\<\floor{bU_n}>$ "СЛУЧАЙНА" ДЛЯ ВСЕХ ЦЕЛЫХ ЧИСЕЛ~$b\ge2$. } зАМЕТИМ, ЧТО В ОПРЕДЕЛЕНИИ~R5 ПОДПОСЛЕДОВАТЕЛЬНОСТЬ "$1\hbox{-РАСПРЕДЕЛЕНА}$", А НЕ "$\infty\hbox{-РАСПРЕДЕЛЕНА}$". иНТЕРЕСНО ЗАМЕТИТЬ, ЧТО ОБЩНОСТЬ ПРИ ЭТОМ НЕ ТЕРЯЕТСЯ. в САМОМ ДЕЛЕ, ДЛЯ ЛЮБОГО $b\hbox{-ИЧНОГО}$ ЧИСЛА~$a_1\ldots a_k$ МОЖНО ТАК ОПРЕДЕЛИТЬ ОЧЕВИДНЫМ ОБРАЗОМ ВЫЧИСЛИМОЕ ПРАВИЛО~$\cR(a_1{}\ldots{}a_k)$ ПОСТРОЕНИЯ ПОДПОСЛЕДОВАТЕЛЬНОСТИ. пОЛОЖИМ~$f_n(x_1,~\dots, x_n)=1$ В ТОМ И ТОЛЬКО ТОМ СЛУЧАЕ КОГДА~$n\ge k-1$ И~$x_{n-k+1}=a_1$,~\dots, $x_{n-1}=a_{k-1}$, $x_n=a_k$. еСЛИ $\$ ЯВЛЯЕТСЯ $k\hbox{-РАСПРЕДЕЛЕННОЙ}$ $b\hbox{-ИЧНОЙ}$ ПОСЛЕДОВАТЕЛЬНОСТЬЮ, ТО УПОМЯНУТОЕ ПРАВИЛО~$\cR(a_1\ldots{}a_k)$, КОТОРОЕ ОТБИРАЕТ ПОДПОСЛЕДОВАТЕЛЬНОСТЬ, СОСТОЯЩУЮ ИЗ ЧЛЕНОВ, СЛЕДУЮЩИХ СРАЗУ ЗА ПОЯВЛЕНИЕМ~$a_1{}\ldots{}a_k$, ОПРЕДЕЛЯЕТ БЕСКОНЕЧНУЮ ПОДПОСЛЕДОВАТЕЛЬНОСТЬ, И ЕСЛИ ЭТА ПОДПОСЛЕДОВАТЕЛЬНОСТЬ $1\hbox{-РАСПРЕДЕЛЕНА}$, ТО КАЖДЫЙ ИЗ НАБОРОВ, СОСТОЯЩИХ ИЗ $k+1$~ЭЛЕМЕНТОВ $a_1\ldots{}a_k{}a_{k+1}$, ПРИ УСЛОВИИ, ЧТО~$0\le a_{k+1}$ С ВЕРОЯТНОСТЬЮ~$1/b^{k+1}$. тАКИМ ОБРАЗОМ, ИНДУКЦИЕЙ ПО~$k$ МОЖНО ДОКАЗАТЬ, ЧТО ПОСЛЕДОВАТЕЛЬНОСТЬ, УДОВЛЕТВОРЯЮЩАЯ ОПРЕДЕЛЕНИЮ~R5, $k\hbox{-pacПРЕДЕЛЕНА}$ ДЛЯ ВСЕХ~$k$. аНАЛОГИЧНЫМ ОБРАЗОМ, РАССМАТРИВАЯ "КОМПОЗИЦИЮ" ПРАВИЛ ПОСТРОЕНИЯ ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ (ЕСЛИ $\cR_1$~ОПРЕДЕЛЯЕТ БЕСКОНЕЧНУЮ ПОДПОСЛЕДОВАТЕЛЬНОСТЬ~$\\cR_1$, МОЖНО ОПРЕДЕЛИТЬ~$\cR_1\cR_2$ КАК ПРАВИЛО ПОСТРОЕНИЯ ПОДПОСЛЕДОВАТЕЛЬНОСТИ, ТАКОЕ, ЧТО~$\\cR_1\cR_2=((\\cR_1) \cR_2)$, МЫ ПРИХОДИМ К ВЫВОДУ, ЧТО ВСЕ ПОДПОСЛЕДОВАТЕЛЬНОСТИ, ОПИСАННЫЕ В ОПРЕДЕЛЕНИИ~R5, $\infty\hbox{-РАСПРЕДЕЛЕНЫ}$ (СМ.\ УПР.~32). пОСКОЛЬКУ $\infty\hbox{-РАСПРЕДЕЛЕННОСТЬ}$ СЛЕДУЕТ ИЗ ОПРЕДЕЛЕНИЯ~R5 КАК ОЧЕНЬ ЧАСТНЫЙ СЛУЧАЙ, МОЖНО НАДЕЯТЬСЯ НА ТО, ЧТО МЫ, НАКОНЕЦ, СФОРМУЛИРОВАЛИ ИСКОМОЕ ОПРЕДЕЛЕНИЕ СЛУЧАЙНОСТИ. нО, УВЫ, ОСТАЕТСЯ ЕЩЕ ОДНА ПРОБЛЕМА! вОВСЕ НЕ ОЧЕВИДНО, ЧТО ПОСЛЕДОВАТЕЛЬНОСТИ, УДОВЛЕТВОРЯЮЩИЕ ОПРЕДЕЛЕНИЮ~R4, ДОЛЖНЫ ТАКЖЕ УДОВЛЕТВОРЯТЬ ОПРЕДЕЛЕНИЮ~R5. "вЫЧИСЛИМЫЕ ПРАВИЛА ПОСТРОЕНИЯ ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ", КОТОРЫЕ МЫ ВВЕЛИ, ВСЕГДА ПЕРЕЧИСЛЯЮТ ПОДПОСЛЕДОВАТЕЛЬНОСТИ~$\$, ДЛЯ КОТОРЫХ~$s_0$ НЕ ОБЯЗАНА БЫТЬ МОНОТОННОЙ; ДОЛЖНО ЛИШЬ СОБЛЮДАТЬСЯ УСЛОВИЕ~$s_n\ne s_m$, ПРИ~$n=m$. сТОЛКНУВШИСЬ С ТАКИМ ПРЕПЯТСТВИЕМ, МЫ ПРИХОДИМ К КОМБИНАЦИИ ОПРЕДЕЛЕНИЙ~R4 И~R5. \proclaim оПРЕДЕЛЕНИЕ~R6. {$b\hbox{-ИЧНАЯ}$ ПОСЛЕДОВАТЕЛЬНОСТЬ~$\$ НАЗЫВАЕТСЯ "СЛУЧАЙНОЙ", ЕСЛИ ДЛЯ ЛЮБОГО ЭФФЕКТИВНОГО АЛГОРИТМА, ОПРЕДЕЛЯЮЩЕГО БЕСКОНЕЧНУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ РАЗЛИЧНЫХ НЕОТРИЦАТЕЛЬНЫХ ЦЕЛЫХ ЧИСЕЛ~$\$ КАК ФУНКЦИЮ ОТ~$n$ И ЗНАЧЕНИЙ~$X_{s_0}$,~\dots, $X_{s_{n-1}}$, СООТВЕТСТВУЮЩАЯ ПОДПОСЛЕДОВАТЕЛЬНОСТЬ~$\$ "СЛУЧАЙНА" В СМЫСЛЕ ОПРЕДЕЛЕНИЯ~R5. \hiddenpar пОСЛЕДОВАТЕЛЬНОСТЬ~$\$ НА~$[0, 1)$ НАЗЫВАЕТСЯ "СЛУЧАЙНОЙ", ЕСЛИ $b\hbox{-ИЧНАЯ}$ ПОСЛЕДОВАТЕЛЬНОСТЬ~$\<\floor{bU_n}>$ "СЛУЧАЙНА" ПРИ ВСЕХ ЦЕЛЫХ ЧИСЛАХ~$b\ge 2$. } аВТОР УТВЕРЖДАЕТ, ЧТО ЭТО ОПРЕДЕЛЕНИЕ, НЕСОМНЕННО, ОТВЕЧАЕТ ВСЕМ РАЗУМНЫМ ФИЛОСОФСКИМ ТРЕБОВАНИЯМ, ПРЕДўЯВЛЯЕМЫМ К ПОНЯТИЮ СЛУЧАЙНОСТИ, И, ТАКИМ ОБРАЗОМ, ДАЕТ ОТВЕТ НА ГЛАВНЫЙ ВОПРОС, ПОСТАВЛЕННЫЙ ЗДЕСЬ. \section{D.~сУЩЕСТВОВАНИЕ СЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ}. мЫ ВИДЕЛИ, ЧТО ОПРЕДЕЛЕНИЕ~R3 ПОТОМУ ОКАЗАЛОСЬ СЛИШКОМ СИЛЬНЫМ, ЧТО НИ ОДНА ПОСЛЕДОВАТЕЛЬНОСТЬ ЕМУ НЕ УДОВЛЕТВОРЯЛА, И ВВОДЯ ОПРЕДЕЛЕНИЯ~R4, R5 И~R6, МЫ СТАРАЛИСЬ СОХРАНИТЬ ОСНОВНЫЕ СВОЙСТВА ОПРЕДЕЛЕНИЯ~R3. дЛЯ ТОГО ЧТОБЫ ПОКАЗАТЬ, ЧТО ОПРЕДЕЛЕНИЕ~R6 НЕ ЯВЛЯЕТСЯ СЛИШКОМ ОГРАНИЧИТЕЛЬНЫМ, СЛЕДУЕТ ДОКАЗАТЬ ФАКТ СУЩЕСТВОВАНИЯ ПОСЛЕДОВАТЕЛЬНОСТЕЙ, УДОВЛЕТВОРЯЮЩИХ СООТВЕТСТВУЮЩИМ ТРЕБОВАНИЯМ. иСХОДЯ ИЗ ИНТУИТИВНЫХ СООБРАЖЕНИЙ, НИКТО НЕ СОМНЕВАЕТСЯ В ИХ СУЩЕСТВОВАНИИ, ПОСКОЛЬКУ КАЖДЫЙ ВЕРИТ В ТО, ЧТО ИСТИННО СЛУЧАЙНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ СУЩЕСТВУЮТ И УДОВЛЕТВОРЯЮТ ОПРЕДЕЛЕНИЮ~R6. оДНАКО ЧТОБЫ УБЕДИТЬСЯ В СОСТОЯТЕЛЬНОСТИ ОПРЕДЕЛЕНИЯ, НЕОБХОДИМО ДОКАЗАТЕЛЬСТВО. иНТЕРЕСНЫЙ МЕТОД ПОСТРОЕНИЯ ПОСЛЕДОВАТЕЛЬНОСТЕЙ, УДОВЛЕТВОРЯЮЩИХ ОПРЕДЕЛЕНИЮ~R5, ПРЕДЛОЖИЛ а.~вАЛЬД. сНАЧАЛА СТРОИТСЯ ОЧЕНЬ ПРОСТАЯ $1\hbox{-РАСПРЕДЕЛЕННАЯ}$ ПОСЛЕДОВАТЕЛЬНОСТЬ. \proclaim лЕММА~T. пУСТЬ В ДВОИЧНОЙ СИСТЕМЕ СЧИСЛЕНИЯ ОПРЕДЕЛЕНА ПОСЛЕДОВАТЕЛЬНОСТЬ ДЕЙСТВИТЕЛЬНЫХ ЧИСЕЛ~$\$: \EQ[29]{ V_0=0, V_1=.1, V_2=.01, V_3=.11, V_4=.001,~\ldots, V_n=.c_r\ldots{}c_1 1, \rem{ЕСЛИ~$n=2^r+c_12^{r-1}+\cdots+c_r$.} } пУСТЬ $I_{b_1\ldots{}b_r}$~ОБОЗНАЧАЕТ МНОЖЕСТВО ТАКИХ ДЕЙСТВИТЕЛЬНЫХ ЧИСЕЛ НА ОТРЕЗКЕ~$[0, 1)$, ДВОИЧНОЕ ПРЕДСТАВЛЕНИЕ КОТОРЫХ НАЧИНАЕТСЯ С~$0.b_1\ldots{}b_r$. тАКИМ ОБРАЗОМ, \EQ[30]{ I_{b_1\ldots{}b_r}=[0.b_1\ldots{} b_r, 0.b_1\ldots{}b_r+2^{-r}). } %%178 тОГДА, ЕСЛИ $\nu(n)$~ОБОЗНАЧАЕТ КОЛИЧЕСТВО ЧИСЕЛ~$V_k$, СОДЕРЖАЩИХСЯ В~$I_{b_1\ldots{}b_r}$ ПРИ~$0\le k < n$, ИМЕЕТ МЕСТО НЕРАВЕНСТВО \EQ[31]{ \abs{\nu(n)/n-2^{-r}}\le 1/n. } \proof пОСКОЛЬКУ $\nu(n)$~ЕСТЬ ЧИСЛО ТЕХ~$k$, ДЛЯ КОТОРЫХ~$k\bmod 2^r=b_r\ldots{}b_1$, МЫ ИМЕЕМ~$\nu(n)=t$ ИЛИ~$t+1$, КОГДА~$\floor{n/2^r}=t$. тАКИМ ОБРАЗОМ, $\abs{\nu(n)-n/2^r}\le 1$. \proofend иЗ ФОРМУЛЫ~\eqref[31] СЛЕДУЕТ, ЧТО ПОСЛЕДОВАТЕЛЬНОСТЬ~$\<\floor{2^rV_n}>$ ЯВЛЯЕТСЯ РАВНОМЕРНО РАСПРЕДЕЛЕННОЙ $2^r\hbox{-ИЧНОЙ}$ ПОСЛЕДОВАТЕЛЬНОСТЬЮ; ОТСЮДА И ИЗ ТЕОРЕМЫ~A ЗАКЛЮЧАЕМ, ЧТО~$\$---РАВНОМЕРНО РАСПРЕДЕЛЕННАЯ НА~$[0, 1)$ ПОСЛЕДОВАТЕЛЬНОСТЬ. в САМОМ ДЕЛЕ, ЯСНО, ЧТО~$\$ НАСТОЛЬКО РАВНОМЕРНО РАСПРЕДЕЛЕНА, НАСКОЛЬКО МОЖЕТ БЫТЬ РАВНОМЕРНО РАСПРЕДЕЛЕННОЙ ПОСЛЕДОВАТЕЛЬНОСТЬ НА~$[0, 1)$! (дАЛЬНЕЙШЕЕ ОБСУЖДЕНИЕ СВОЙСТВ ЭТОЙ И СВЯЗАННЫХ С НЕЙ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ИМЕЕТСЯ В СТАТЬЯХ и.~ВАН~ДЕР~кОРПУТА ({\sl Proc. Koninklijke Nederlandse Akademie van Wetenschappen,\/} {\bf 38} (1935), 813--821, 1058--1066) И дЖ.~хОЛТОНА ({\sl Numerische Mathematik,\/} {\bf 2} (1960), 84--90, 196). пУСТЬ ТЕПЕРЬ~$\cR_1$, $\cR_2$,~\dots---БЕСКОНЕЧНОЕ МНОЖЕСТВО ПРАВИЛ ПОСТРОЕНИЯ ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ. мЫ ХОТИМ НАЙТИ ПОСЛЕДОВАТЕЛЬНОСТЬ~$\$, ВСЕ БЕСКОНЕЧНЫЕ ПОДПОСЛЕДОВАТЕЛЬНОСТИ~$\\cR_j$ КОТОРОЙ РАВНОМЕРНО РАСПРЕДЕЛЕНЫ. \alg W.(пОСЛЕДОВАТЕЛЬНОСТЬ вАЛЬДА.) эТА ПРОЦЕДУРА ОПРЕДЕЛЯЕТ ПОСЛЕДОВАТЕЛЬНОСТЬ~$\$ НА~$[0, 1)$, ЕСЛИ ЗАДАНО БЕСКОНЕЧНОЕ МНОЖЕСТВО ПРАВИЛ ПОСТРОЕНИЯ ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ~$\cR_1$, $\cR_2$,~\dots, ОПРЕДЕЛЯЮЩИХ ПОДПОСЛЕДОВАТЕЛЬНОСТИ ПОСЛЕДОВАТЕЛЬНОСТЕЙ \emph{РАЦИОНАЛЬНЫХ} ЧИСЕЛ НА~$[0, 1)$. пРИ ВЫЧИСЛЕНИИ ТРЕБУЕТСЯ БЕСКОНЕЧНО БОЛЬШОЕ КОЛИЧЕСТВО ВСПОМОГАТЕЛЬНЫХ ПЕРЕМЕННЫХ~$C[a_1,~\ldots,a_r]$, ГДЕ~$r\ge 1$ И~$a_j=0$ ИЛИ~$1$, $1\le j \le r$. в НАЧАЛЬНЫЙ МОМЕНТ ВРЕМЕНИ ВСЕ ЭТИ ПЕРЕМЕННЫЕ РАВНЫ НУЛЮ. \st[нАЧАЛЬНАЯ УСТАНОВКА~$n$.] уСТАНОВИТЬ~$n\asg 0$. \st[нАЧАЛЬНАЯ УСТАНОВКА~$r$.] уСТАНОВИТЬ~$r\asg 1$. \st[пРОВЕРИТЬ~$\cR_r$.] еСЛИ ЭЛЕМЕНТ~$U_n$, ДОЛЖЕН ПОПАСТЬ В ПОДПОСЛЕДОВАТЕЛЬНОСТЬ, ОПРЕДЕЛЯЕМУЮ~$\cR_r$, НА ОСНОВАНИИ ЗНАЧЕНИЙ~$U_k$, ГДЕ~$0\le k < n$, ТО НУЖНО ПРИСВОИТЬ~$a_r\asg 1$, В ПРОТИВНОМ СЛУЧАЕ---ПРИСВОИТЬ~$a_r\asg 0$. \st[$B[a_1,~\ldots, a_r]$ ПОЛНО?] еСЛИ~$C[a_1,~\ldots, a_r]<3\cdot 4^{r-1}$, ПЕРЕЙТИ К~\stp{6}. \st[уВЕЛИЧИТЬ~$r$.] уСТАНОВИТЬ~$r\asg r+1$ И ВОЗВРАТИТЬСЯ К~\stp{3}. \st[уСТАНОВИТЬ~$U_n$.] уВЕЛИЧИТЬ~$C[a_1,~\ldots, a_r]$ НА~$1$. пУСТЬ $k$~ЕСТЬ НОВОЕ ЗНАЧЕНИЕ~$C[a_1,~\ldots, a_r]$. уСТАНОВИТЬ~$U_n\asg V_k$, ГДЕ ВЕЛИЧИНА~$V_k$ ОПРЕДЕЛЕНА ВЫШЕ В ЛЕММЕ~T. \st[уВЕЛИЧИТЬ~$n$.] уВЕЛИЧИТЬ~$n$ НА~$1$ И ВОЗВРАТИТЬСЯ К~\stp{2}. \algend %% 179 сТРОГО ГОВОРЯ, ЭТО НЕ ЕСТЬ АЛГОРИТМ, ПОСКОЛЬКУ ОН НЕ КОНЕЧЕН. лЕГКО, ОДНАКО, ИЗМЕНИТЬ ЕГО ТАК, ЧТОБЫ ОН ЗАКАНЧИВАЛСЯ, КОГДА $n$~ДОСТИГАЕТ ЗАДАННОЙ ВЕЛИЧИНЫ. чИТАТЕЛЮ ЛЕГЧЕ БУДЕТ ПОЧУВСТВОВАТЬ ИДЕЮ ПРИВЕДЕННОГО ПОСТРОЕНИЯ, ЕСЛИ ОН ПОПРОБУЕТ "ПРОКРУТИТЬ" ЕГО ВРУЧНУЮ, ЗАМЕНИВ ПРИ ЭТОМ ЧИСЛО~$3\cdot 4^{r-1}$ НА ШАГЕ~W4 НА~$2^r$. аЛГОРИТМ~W НЕ ПРЕДНАЗНАЧЕН ДЛЯ ПРИМЕНЕНИЯ В КАЧЕСТВЕ ДАТЧИКА СЛУЧАЙНЫХ ЧИСЕЛ, ОН СЛУЖИТ ЛИШЬ ТЕОРЕТИЧЕСКИМ ЦЕЛЯМ. \proclaim тЕОРЕМА~W. пУСТЬ~$U_n$---ПОСЛЕДОВАТЕЛЬНОСТЬ РАЦИОНАЛЬНЫХ ЧИСЕЛ, ОПРЕДЕЛЕННАЯ С ПОМОЩЬЮ АЛГОРИТМА~W, И~$k$---ПОЛОЖИТЕЛЬНОЕ ЦЕЛОЕ ЧИСЛО. еСЛИ ПОДПОСЛЕДОВАТЕЛЬНОСТЬ~$\\cR_k$ БЕСКОНЕЧНА, ТО ОНА $1\hbox{-РАСПРЕДЕЛЕНА}$. \proof пУСТЬ $A[a_1,~\ldots, a_r]$ ОБОЗНАЧАЕТ ПОДПОСЛЕДОВАТЕЛЬНОСТЬ (МОЖЕТ БЫТЬ, ПУСТУЮ) ПОСЛЕДОВАТЕЛЬНОСТИ~$\$, СОДЕРЖАЩУЮ ТЕ И ТОЛЬКО ТЕ ЭЛЕМЕНТЫ~$U_n$, КОТОРЫЕ ДЛЯ ВСЕХ~$j$, ТАКИХ, ЧТО~$1\le j \le r$, ПРИНАДЛЕЖАТ ПОДПОСЛЕДОВАТЕЛЬНОСТИ~$\\cR_j$, ЕСЛИ~$a_j=1$, И НЕ ПРИНАДЛЕЖАТ ПОДПОСЛЕДОВАТЕЛЬНОСТИ~$\\cR_j$, ЕСЛИ~$a_j=0$. дОСТАТОЧНО ДОКАЗАТЬ, ЧТО ДЛЯ ВСЕХ~$r\ge 1$ И ВСЕХ ПАР ДВОИЧНЫХ ЧИСЕЛ~$a_1\ldots{}a_r$ И~$b_1\ldots{}b_r$ ИМЕЕТ МЕСТО РАВЕНСТВО~$\Pr(U_n \in I_{b_1\ldots{}b_r})=2^{-r}$ ПО ОТНОШЕНИЮ К ПОДПОСЛЕДОВАТЕЛЬНОСТИ~$A[a_1\ldots{}a_r]$ В ТОМ СЛУЧАЕ, КОГДА ПОСЛЕДНЯЯ БЕСКОНЕЧНА [СМ.~\eqref[30]]. в САМОМ ДЕЛЕ, ЕСЛИ~$r\ge k$, ТО БЕСКОНЕЧНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ~$\\cR_k$ ПРЕДСТАВЛЯЕТ СОБОЙ КОНЕЧНОЕ ОБўЕДИНЕНИЕ НЕПЕРЕСЕКАЮЩИХСЯ ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ~$A[a_1,~\ldots, a_r]$ ДЛЯ~$a_k=1$ И~$a_j=0$ ИЛИ~$1$ ПРИ~$1\le j \le r$, $j\ne k$; СЛЕДОВАТЕЛЬНО, $\Pr(U_n\in I_{b_1\ldots{}b_r})=2^{-r}$ ПО ОТНОШЕНИЮ К~$\\cR_k$ (СМ.~УПР.~33). дОСТАТОЧНО ВОСПОЛЬЗОВАТЬСЯ ЕЩЕ ТЕОРЕМОЙ~A, ЧТОБЫ ПОКАЗАТЬ, ЧТО ПОСЛЕДОВАТЕЛЬНОСТЬ $1\hbox{-РАСПРЕДЕЛЕНА}$. пУСТЬ $B[a_1,~\ldots, a_r]$ ОБОЗНАЧАЕТ ПОДПОСЛЕДОВАТЕЛЬНОСТЬ ЭЛЕМЕНТОВ~$\$, ДЛЯ КОТОРЫХ~$C[a_1,~\ldots, a_r]$ УВЕЛИЧИВАЕТСЯ НА ЕДИНИЦУ НА ШАГЕ~W6 АЛГОРИТМА. кАК ВИДНО ИЗ АЛГОРИТМА, $B[a_1,~\ldots, a_r]$---КОНЕЧНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ, МАКСИМАЛЬНОЕ ЧИСЛО ЭЛЕМЕНТОВ КОТОРОЙ РАВНО~$3\cdot4^{r-1}$. вСЕ ЧЛЕНЫ~$A[a_1,~\ldots, a_r]$, КРОМЕ КОНЕЧНОГО ИХ ЧИСЛА, БЕРУТСЯ ИЗ ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ~$B[a_1,~\ldots, a_r,~\ldots, a_t]$, ГДЕ~$a_j=0$ ИЛИ~$1$ ПРИ~$r$, ГДЕ~$s_0$---ПОСЛЕДОВАТЕЛЬНОСТЬ РАЦИОНАЛЬНЫХ ЧИСЕЛ НА~$[0, 1)$ И ЕСЛИ~$\cR$---ВЫЧИСЛИМОЕ ПРАВИЛО ПОСТРОЕНИЯ ПОДПОСЛЕДОВАТЕЛЬНОСТИ ЧЛЕНОВ $b\hbox{-ИЧНОЙ}$ ПОСЛЕДОВАТЕЛЬНОСТИ, МЫ МОЖЕМ ПРЕВРАТИТЬ~$\cR$ В ВЫЧИСЛИМОЕ ПРАВИЛО~$\cR'$ ПОСТРОЕНИЯ ПОДПОСЛЕДОВАТЕЛЬНОСТИ ЧЛЕНОВ~$\$, ПОЛОЖИВ~$f'_n(x_1,~\ldots, x_n)$ В~$\cR'$ РАВНЫМ~$f_n(\floor{bx_1},~\ldots, \floor{bx_n})$ В~$\cR$. еСЛИ ПОСЛЕДОВАТЕЛЬНОСТЬ~$\\cR'$ РАВНОМЕРНО РАСПРЕДЕЛЕНА, ТО ЭТИМ ЖЕ СВОЙСТВОМ ОБЛАДАЕТ И~$\<\floor{bU_n}>\cR$. мНОЖЕСТВО ВСЕХ ВЫЧИСЛИМЫХ ПРАВИЛ ПОСТРОЕНИЯ ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ $b\hbox{-ИЧНЫХ}$ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ПРИ ВСЕХ ЗНАЧЕНИЯХ~$b$ СЧЕТНО (ПОСКОЛЬКУ СУЩЕСТВУЕТ ЛИШЬ СЧЕТНОЕ КОЛИЧЕСТВО ЭФФЕКТИВНЫХ АЛГОРИТМОВ), ПОЭТОМУ ЕГО ЭЛЕМЕНТЫ МОЖНО ПЕРЕЧИСЛИТЬ В ВИДЕ НЕКОТОРОЙ ПОСЛЕДОВАТЕЛЬНОСТИ~$\cR_1$, $\cR_2$,~$\ldots\,$. оТСЮДА СЛЕДУЕТ, ЧТО АЛГОРИТМ~W ОПРЕДЕЛЯЕТ ПОСЛЕДОВАТЕЛЬНОСТЬ НА~$[0, 1)$, КОТОРАЯ ЯВЛЯЕТСЯ СЛУЧАЙНОЙ В СМЫСЛЕ ОПРЕДЕЛЕНИЯ~R5. тЕПЕРЬ МЫ ОКАЗАЛИСЬ В НЕСКОЛЬКО ПАРАДОКСАЛЬНОМ ПОЛОЖЕНИИ. кАК ОТМЕЧАЛОСЬ РАНЬШЕ, ЭФФЕКТИВНЫЙ АЛГОРИТМ, КОТОРЫЙ ОПРЕДЕЛЯЛ БЫ ПОСЛЕДОВАТЕЛЬНОСТЬ, УДОВЛЕТВОРЯЮЩУЮ ОПРЕДЕЛЕНИЮ~R4, СУЩЕСТВОВАТЬ НЕ МОЖЕТ, И ПО ТОЙ ЖЕ ПРИЧИНЕ НЕ МОЖЕТ СУЩЕСТВОВАТЬ ЭФФЕКТИВНЫЙ АЛГОРИТМ, ОПРЕДЕЛЯЮЩИЙ ПОСЛЕДОВАТЕЛЬНОСТЬ, УДОВЛЕТВОРЯЮЩУЮ ОПРЕДЕЛЕНИЮ~R5. дОКАЗАТЕЛЬСТВО СУЩЕСТВОВАНИЯ ТАКОЙ СЛУЧАЙНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ПО НЕОБХОДИМОСТИ ДОЛЖНО БЫТЬ НЕКОНСТРУКТИВНЫМ. кАКИМ ЖЕ ОБРАЗОМ ЭТА ПОСЛЕДОВАТЕЛЬНОСТЬ ПОЛУЧАЕТСЯ ПО АЛГОРИТМУ~W? пРОТИВОРЕЧИЯ ЗДЕСЬ НЕТ. дЕЛО В ТОМ, ЧТО НЕВОЗМОЖНО С ПОМОЩЬЮ ЭФФЕКТИВНОГО АЛГОРИТМА ПРОНУМЕРОВАТЬ МНОЖЕСТВО ВСЕХ АЛГОРИТМОВ. дРУГИМИ СЛОВАМИ, ЭФФЕКТИВНЫЙ АЛГОРИТМ, КОТОРЫЙ %% 181 \bye

Home | Contact | Directory | Register Your Domain | Become Domain and Hosting Reseller


Copyleft 2008 ruslib.com