AOP_Tom2 (1021737), страница 56
Текст из файла (страница 56)
19. [НМУ5[ Рассмотрите модификацию определения К4, требуя, чтобы подпоследовательность была только 1-распределенной, а не оо-распределенной. Суп(ествует ли последовательность, удовлетворяющая этому более слабому определению, которая не будет ос-распределенной? (Действительно ли это определение более слабое?) ь 20. [НМЗб[ (Н.
Г. де Брейн ()У(. С с)е Вгп)) и) и П. Эрдеш (Р. Егббв) .) Первые и точек любой [О .. »-последовательности (17 ) с Па = 0 делят интервал [О .. » на и подынтервалов. Пусть эти подынтервалы имеют длины 1„> 1» 1 . Очевидно, что 1 » — „ 1 (с) ш) ( ) (1) с (о) поскольку (о' -ь . +1„" = 1. Одним из способов измерения равномерности распределения О) . () ((?о) является рассмотрение пределов 21. [НМ40] (Л, Г. Рамшоу (Е.
Н. ВюпвЬаи).) а) Продолжаем предыдущее упражнение. Будет лн последовательность ()1'„) равно- распределена? Ь) Покажите, что (И~„) является только [0..1)-последовательностью, для которой выполняетсн ~ . ,1,~ < (б(1 + )()'и) всякий раз, как только 1 < )г < и. с) Пусть (~~((м...,( )) — любая последовательность непрерывных функций на множествах строк размерности и (((м...;1 ) [ 11 » . („и 11 + + 1 = Ц, удовлетворяющая следующим двум свойствам: если ~ ., 1, > ~, 1) для 1 < )г < и, то у„(1),...,1„) > ~„(1„,1„). [Примеры: н((~)) — п(("); 1(~)/1(~)) п((ч(~)~+ +1( ) ).[ Пусть 7 =1(шеар у,(1(,'~,...,1(")) ~ 00 для последовательности (И'„). Покажите, что ~„(1,...,1„" ) < 7 для всех и отно- (1) ( ) сительно (И'„), а также 6ш зпр„у„(1„,, 1„) > 7 относительно каждой другой (1) (а) [0..1)-последовательности, ь 22.
(НМуй) (Герман Вейль (Негшапп %еу!).) Покажите, что [0..1)-последователыюсть (() ) Й-распределена тогда н только тогда, когда 1 )пп — ~ ехр(2я((с1Г'„+ + сей„.)ь г)) = О об <к 1 х йп — ~ ~(ӄ— -')(У)е„— 1) = 0 для всех )с > 1. -~сч н т ей)< 26. [НМЯ4[ (Дж. Франклин (Л.
ггапЫ(п).) Белая последовательность, определенная в предыдущем упражнении, может не быть случайной. Пусть Пе, Ум... — сю-распределенная последовательность. С)пределим последовательность Им Ъм ... следующим образом." % -1 )'з ) = (6з - и с)з«), %~-мРз ) = ((1), Узп-1), если (Пг -м()т ) е 1(, если (У)а-и Узч) ~ С, для каждого множества не всех равных нулю целых чисел см см..., сю 23. (МЗЗ] (а) Покажите, что [О .. 1)-последовательность (6'„) Ь-распределена тогда и только тогда, когда все последовательности ((с1К, + с(У +1+ + с(6'„» ь 1) шоб1) 1-распределены всякий раз, когда см см ..., сь — целые числа, не все равные нулю. (Ь) Покажите, что Ь-ичная последовательность (Л„) )г-распределена тогда и только тогда, когда все последовательности ((с~Х + сзЛ +1+ + сьЛ„+ь 1) шобб) 1-распределены всякий раз, когда см см ..., сь — целые числа с Оса(см, .., сь) = 1.
° 24. [МИ[ (Й. Г. Ван дер Корпут (). С кап бег Согрп().) (а) Докажите, что [О .. 1)-последовательность (Уа) равнораспределена всегда, когда последовательности ((('„+ь У„) шоб1) равнораспределены для всех Й > О, (Ь) Следовательно, ((пап + + а~и+ па) шоб 1) равнораспределена, когда 4 > 0 и ак — иррациональные числа. 25. [НМЯО[ Последовательность называется белой, если все сериальные коэффициенты корреляции равны нулю, т..е. если соотношение в следствии Б выполняется для всех Ь > 1.
(Согласно следствию Б со-распределенная последовательность является белой.) Покажите, что если [О .. 1)-последовательность равнораспределена, то она белая тогда и только тогда, когда где С вЂ” множество ((х, р) [ х — -' < р < х или х+ -' < р). Покажите, что (а) последовательнскть Уэ, К, ... равнораспределениая и белая, (Ь) Рг(Ъ'„> 1'ь~.г) = э.
(Это указывает на слабость критерия сериальной корреляции.) 27. [НМ4э] Чему равно наибольшее возможное значение для Рг(1'к > К,.ьь) в равно- распределенной белой последовательности? (Д. Копперсмит (П. СоррегэшйЬ) построил такую пскледовательность, для которой это значение достигает э.) ь 26.
[НМ21] Воспользуйтесь последовательностью (11), чтобы построить 3-распределенную [О, 1)-последовательность, ддя которой Рг((?э > 1) ы э. 20. [НМ!4] Пусть Ха, Хп .., — (2(г)-распределенная двоичная последовательность. Покажите, что Рг(Хэ„=О) < -+ ( )/2' . ь 30. [Мур] Постройте (26)-распределенную двоичную последовательность, для которой Рг(Хг =О) = — + ( )/2 (Таким образом, неравенство в предыдущем упражнении является наилучшим.) 31. [МЮО] Покажите, что существуют [О .. 1)-последовательности, удовлетворяющие определению К5, однако и„/и > — для всех и > О, где и„— число,у < и, для которых (? < 3.
1 1 (Это можно рассматривать как неслучайное свойство последовательности.) 32. [М24] Задана (Х„) "случайная" 6-ичная последовательность, удовлетворяющая определению К5, и Š— 'исчисляемое правило подпоследовательности, точно задающее бесконечную подпоследовательность (Х„) К.
Покажите, что последняя подпоследовательность не только 1-распределена, но и "случайна" согласно определению К5. 33. [НМЗЗ] Пусть (К „) и (с ы ) — бесконечные непересекающиеся подпоследовательности последовательности (К,) (Иначе говоря, го < гг < гэ < и ва < э~ < ээ < возрастающие последовательности целых чисел и г эь э для любых т, и.) Предположим, что (Ц„) — комбинированная подпоследовательность, такая, что 1а < 1г < $э <, и положим (1 ) = (г„) 11 (э ). Покажите, что если Рг(Ь;„Е А) = Рг(сьы Е А) = Р, то Рг(К„Е А) = р.
ь 34. [М25] Определите правила подпоследовательностей Км гсэ, Кэ, ..., такие, что с этими правилами можно использовать алгоритм ЧГ, чтобы задать эффективный алгоритм построения [О,. 1)-последовательности, удовлетворяющей определению В1. ь 35. [НМ35] (Д. В. Лавленд (П. Ч'. Ьоге(апб).) Покажите, что если двоичная последовательность (Х ) В5-случайна и если (э ) — любая исчисляемая погледовательность соответственно с определением В4, то Рг(Х,„= 1) > -' и Рг(Х,„= 1) < -'. 36. [Нар] Пусть (К,) — двоичная последовательность, "случайная" согласно определению Кб.
Покажите, что [О .. 1)-последовательность ((7 ), определенная в двоичной системе счисления по схеме УО = (О.ХО)2, (7! = (О.Х!хэ)2, (72 = (О.ХЗХ4Хэ)2, Цэ = (О.хэХгХВХ9)2, случайна в смысле определения Кб. 37. [МЯ7] (Д. Копперсмит (П. Соррегэшйй).) Постройте последовательность, удовлетворяющую определению В4, но не определению Н5, [Указание.
Рассмотрите преобразование Пе, Ьы (?ж (?в, истинно случайной последовательности.] 33. [Мгр] (А. Н. Колмогоров.) Пусть заданы?сс, и и г. Чему равно наименьшее число алгоритмов в множестве А, таких, чтобы не существоиали (п,е)-случайные двоичные последовательности длины Ю по отношению к А? (Если нельзя задать точные формулы, можно ли найти асимптотические формулы? Суть этой проблемы — обнаружить, как точная грань (37) становится "наилучшей возможной".) 39.
[ВМ45] (В. М. Шмидт (%. М. Бсйш!Ф).) Пусть ӄ— [0..1)-последовательность и пусть о„(и) — число таких неотрицательных целых чисел,1 < и, что О < У, < и. Докажите, что существует такая положительная настоянная с, что для любого йс и любой [О .. 1)-последовательности (??„) мы получим [оо(и) — ип[ > с1п Ас для некоторых и и и при О < и < )сс', О < и < 1, (другими словами, никакан [О .. 1)-последовательность не может быть слишком равнораспределена.) 40. [М28] Завершите доказательство леммы Р1. 41.
[МИ] В лемме Р2 показано существование критерия прогноза, но при доказательстве предполагается существование подходящего?с без объяснения, как конструктивно находить lс из А. Покажите, что любой алгоритм А можно обратить в алгоритм А' с Т(А') < Т(А) + 0(дс), который предсказывает Вл по Вс... В,с с с вероятностью, по крайней мере равной -' -ь (Р(А, Я) — Р(А, $л))/Ас на любом симметричном сдвиге Ьс-источника Я. ь 42. [М28] (Попарнал независимость.) а) Пусть Хс,, Х вЂ” случайные величины со средним, равным д = ЕХ,, и дисперсией а = ЕХг — (ЕХ„) при 1 < У < п. Докажите неравенство Чебышева Рг((Х + +Х вЂ” и ) >г ) <1/1 прн дополнительных предположениях, что Е(ХсХз) = (Е Х,)(ЕХ„) всякий раз, когда с ф у.
Ь) Пусть В -- случайная двоичная матрица размера?с х сс. Докажите, что если с и с'— фиксированные не равные нулю двоичные векторы размерности Ь, то сВ и с'В— независимые случайные двоичные векторы размерности П (по модулю 2).
с) Примените (а) н (Ь) к анализу алгоритма Ь. 43. [20] Кажется, точно так же тяжело найти множители любого фиксированного целого числа Блюма М, состоящего иэ В двоичных разрядов. Как найти множители случайного целого числа, состоящего из П двоичных рвэрядов7 Почему тогда теорема Р сформулирована для случайного, а не фиксированного М? ь 44. [13] (И. Дж. Гуд (1.
Л. Соос1).) Может ли правильная таблица случайных чисел содержать точно одну ошибку? 3.6. ВЫВОДЫ В этой гллнк было рассмотрено довольно много тем: генерирование случайных чисел, их проверка, их видоизменение при использовании и методы получения теоретических фактов. Возможно, главным для многих читателей баял вопрос "Что получено в результате всей этой теории и что такое простой добротный генератор, который можно использовать в программах в качестве надежного источника случайных чисел?".
Подробные исследования в этой главе наводят на мысль, что следующая процедура позволяет получить простейший генератор случайных чисел для машинного языка большинства компьютеров. В начале программы присвойте целой переменной Х некоторое значение Хе. Эта величина Л используется только для генерирования случайного числа. Как только в программе потребуется новое случайное число, положите Х с — (аХ + с) пюб т (1) и используйте новое значение Х в качестве случайной величины. Необходимо тщательно выбрать Хэ, а, с и то и разумно использовать случайные числа согласно следующим принципам. ~) "Начальное" число Хе может быть выбрано произвольно.
Если программа используется несколько раз и каждый раз требуются различные источники случайных чисел, то нужно присвоить Хэ последнее полученное значение Х на предыдущем прогоне или, если это более удобно, присвоить Хе текущие дату н время. Чтобы снова запустить программу с шахима же случайиымн числами (например, прн отладке црограммы), нужно напечатать Лв, если иначе его невозможно получить. й) Число т должно быть большим, скажем, по крайней мере 2зе. Возможно, удобно взять его равным размеру компьютерного слова, так как это делает вычисление (аХ + с) пюд гп вполне аффективным.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
