Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 51
Текст из файла (страница 51)
Чтобы понять идею построения, выполните алгоритм вручную, заменяя число 3 . 4' ' шага %4 значением 2". Алгоритм % не предназначен для получения случайных чисел на практике. Имеется в виду, что он имеет только теоретическое значение. Теорема Ъэ'. Пусть (П„) — последовательность рациональных шсел, определенная алгоритмом И„н пусть й — положительное целое число. Если подпоследовательность ((7„)»ь» бесконечна, то она 1-раслределена. Доказательспшо. Пусть А [ам...
„а,) означает подпоследовательность (С'„) (возможно'пустую), включающую те элементы (!„, которые для всех ! < г принадлежат падпогледовательности (У„) Еу, если а = 1, и не принадлежат подпоследовательности Яп)'й, если п = О. Достаточно доказать для всех г > 1 и всех пар двоичных чисел а~... а, и 6|... Ь„ что Рг(0'„е Уь, ь,) = 2 ' по отношению к подпоследоватечьности А[ам...,а„,' всякий раз, когда последняя бесконечна (см. равенство (30)). Если г > 6, для бесконечной последовательности (Г„)Я» суцюствует конечное объединение непересекающихся подпоследовательностей А[ам ...,а„) для аь = 1 и а„ = 0 или 1 для 1 < у < г, у ~ 6.
Из этого следует, что Рг(1,"„е' !м ь„) = 2 " по отношению к (!У„)1сь (см. упр. 33). Этого достаточно, чтобы показать, что согласно теореме й последовательность 1-распределена. Пусть В(а„..., а„,' означает подпоследовательность ((/„) для тех и, в которых С[ам..., а„[ увеличивается на единицу на шаге Ъ'б алгоритма.
Согласно алгоритму В[вы...,а„] — конечная последовательность с самое большее 3 ° 4' ' элементами. За исключением конечного числа, все члены А[ам ..,, а,[ являются членами подпоследовательностей В[о~ „..., аг...,, аД, где а = 0 или 1 для г < / < й Предположим, что А[ам...,а„) бесконечна, и пусть А[ам...,а,) = ((/,„), где зо < в~ < зт < . Если Ж вЂ” большое целоечислос 4' < 4" < Х < 4~+', логически вытекает, что число значений Й < Ф, для которых У,„принадлежит !М, М, равно (за исключением конечного множества элементов начальных подпоследовательностей) Здесь т — число перечисленных выше подпоследовательностей В[ам ..,, а,), в которых С',„появляется для некоторых й < Х, Х вЂ” число значений й с ь',„в соответствующей подпоследовательности и и(Х ) — число таких значений, которые также принадлежат !м з„. Значит, согласно лемме «Х [и (Х) — 2 "Х[ = [м(й!,) — 2 "Х~ + ° + и(Х ) — 2 "й!„,[ < [и(Х~) — 2 "Х|[+.
+ [и(М ) — 2 "Х„,[ <гп< 1+2+4+ +2 "~~ <2г+~. Неравенство для т следует здесь пз того, что согласно сделанному выбору %элемент (6э принадлежит В[ам..., а~) для некоторых ! < д+ 1. Х!ы доказали, что [я(!з)/й! — 2 "[ < 2~~'/Х < 2/~/У. $ ЧтОбы показать окоцчате!Ьно, что существуют последовательности, удовле" творяющне определению !15, сначала заметим, что, сели (Г„) — !0..1)-последовательность рациональных чисел и если К вЂ” исчисляемое правило подпогледовательностей для 6-ичной последовательности, Я.
можно преобразовать в исчисляемое правило подпоследовательности Я.' для (!!„), полагая /,',(хы ...,х„) в 1С' равным /„([Ьх~),...,[Ьх„)) в К. Если [0..1)-последовательность (Ьл)7Г равнораспределеиа, значнт, существует 6-ичная последовательность ([6(!„))Я. Сейчас множество всех исчисляемых правил подпоследовательностей для Ь.ичных последовательностей для всех значений Ь является счетным (так как возможно только счетное множество эффективных алгоритмов). Значит, они могут образовать некоторую последовательность Км Кт, ..., таким образом, алгоритм % задает [О ..
1)-последовательность, случайную в смысле определения К5. Это приводит к возникновению в некоторой степени парадоксальной ситуации. Как уже упоминалось, ие существует эффективного алгоритма для задания последовательности, удовлетворяющей определению К4. По тем же соображениям неэффективен алгоритм, который задает последовательность, удовлетворяющую опреденению К5. Доказательства существования такой случайной последовательности неизбежно яекоиструктивна. Как тогда алгоритм % может построить такую последовательность? Здесь нет противоречия, есть толька заминка, связанная с тем фактом, что множество всех эффективных алгоритмов не может быть пронумеровано эффективным алгоритмом.
Другими словами, не существует эффективного алгоритма выбора у-го исчислиьюго правила подпоследовательности Е ,поскольку нет эффективного алгоритма определения того, заканчивается ли данный вычислительный метод. Но важные большие классы алгоритмов можно систематически перенумеровывать. Так, например, в алгоритме % показано, что с помощью эффективного алгоритма можно построить последовательность, удовлетворяющую определению К5, если ограничиться рассмотрением "примитивных рекуррентных" правил подпоследовательностей. Преобразовав шаг %6 алгоритма % (присвоив Уч +- Рь~~ вместо 14, где Г— любое неотрицательное целое число, зависящее от ам ..., а,), можно показать, что существует несчешмое множество [0..1)-последовательностей, удовлетворяющих определению К5.
В приведенной ниже теореме дан другой метод доказательства существования несчетного множества случайных последовательностей, который использует менее прямые доводы, основанные на теории меры, даже если применять строгое определение случайной последовательности Кб. Теорема М. Пусть действительное число х, О < х < 1, соответствует двоичной последовательност» (Л ), есле (О.ХеЛ1... )т является двоичным представлением х. Прн этом почти все х соответствуют случайным в смысле определения Кб последовательностям. (Другим словами, множество всех действительных чисел х, соответствующих неслучайным по определению Кб дэюичным последовательностям, имеет меру нуль.) Докаэательсгпео.
Пусть Ю вЂ” эффективный алгоритм, определяющий бескокечную последовательность различных неотрицательных чисел (э„), где выбор э„зависит только от п и Л,„для О < й < и, и пусть Я вЂ” исчислимое правило подпоследовательнасти. Тогда любая двоичная последовательность (Л„) приводит к падпоследовательности (Х,„)И и по определению Кб эта падпоследовательность должна быть либо конечной, либо 1-распределенной. Достаточно доказать, что для фиксированных Я н о лшожество Ю(Тс, Ю) всех действительных х, соответствующих (Х„), такое, что (Х,„)К бесконечна н не 1-распределена, имеет меру нуль. Для х существует неслучайное двоичное представление тогда и только тогда, когда х принадлежит ОХ(К, о), взятому по счетному множеству выборов К и 8. Следовательно, пусть К, Ю фиксированы.
Рассмотрим множество Т(а1оэ... о„), определенное для всех двоичных чисел а1ат... о„как множество всех х, соответству- юших (Л „), такое, что (Л,„) Я имеет > г элемеитов, из которых первые г элементов равны ам аю .. а„соответственно. Первым результатом будет неравенство (32) Т(а~аз...
а,) имеет меру < 2 ". Доказательство качаем с замечаиия, что Т(а~аз... а„) является измеримым множеством: каждый элемент Т(а~ам .. а,) — действительное число х = (О.ХеХ~ . ° ° )г, для которого существует такое целое число т, что алгоритм Я определяет.различные значения эе, эы ..., э~., и правило Тс определяет подпоследовательность Х„„ Х„,, ..., Х,, такую, что Х, является г-и элементом этой подпоследовательности. Множество всех действительных у = (0.1еК ... )ю таких, что 1;„= Л„для 0 < Й < ш, также принадлежит Т(а~аз...
а,) и является измеримым множеством. состоящим из конечного объединения двоичных подыитервалов 1м, и. Поскольку существует только счетное множество таких двоичных интервалов, то Т(щоз... о„) — счетное абъединеиие двоичвых интервалов, и оно, следовательно, измеримо. Более того, даниый довод может быть распространен, чтобы показать, что мера Т(а,...а, ~ О) равна мере Т(а~...
а„~1), так как последнее множество является объединением двоичных интервалов, полученных из предшествующей рекуррентиой формулы 1',„= Х,„для 0 < й < т и 1"„ф Х, . Поскольку Т(аэ... а„~О) 0Т(а~...а, ~1) С Т(а~...а, ~), мера Т(а~аз...а,) равна самое большее половине меры Т(а~...а, ~). Неравенство (32) теперь легко получить иидукцией по г, Сейчас, когда (32) устаяовлено, осталось, по существу., показать, что двоичное представлеиие почти всех действительных чисел равнораспределеио, Пусть для О < е < 1 В(г, с) — это Ц Т(аэ... а„), где объединеиие берется по всем двоичным строкам а~...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
