AOP_Tom2 (1021737), страница 6
Текст из файла (страница 6)
Последовательность строится так: сначала произвольно выбирают Хо и Хз, а затем полагают, что Х„+з = 1(Хо, Х„з), где и > О. Чему предположительяо равен максимальный период в этом случает 17. (!6] Обобщите ситуацию из предыдущего упражнения так, чтобы Х„+з зависело от предыдущих 1г значений последовательности.
18. (МЯО] Придумайте метод, аналогичный методу из упр. 7, для определения цикла генератора случайных чисел, описанного в упр. 17, в общем виде. 19. (М4В] Выполните упр. 11, нспазьзуя упр. 15, в более общем случае, когда Х„эз зависят ат х предыдущих значений последовательности; каждая иэ зн"' функций 1(хз,...,хг) считается равновероятной, [Замечание. Числа функций, которые дают максимолоний период, аззализнруется в упр, 2.3.4.2 — 23.] 20. [ВО] Найдите все неотрицательные числа Х < 10'о, которые при использовании алгоритма К в конечном счете приводят к самовоспроизводящимся числам из табл. 1.
21. [69] Докажите или опровергните следующее утверждение; отображение Х з-з 1'(Х), определенное алгоритмом К, имеет ровно пять циклов длиной 3178, 1606, 1024, 943 и 1. 22. [91] (Г. Роллетшек (Н. НойезвсЬей).) Хороша ли идея генерирования случайных чисел с помощью последовательности 1(0), 1(1), /(2), ..., где 1 — случайная функция, вместо того, чтобы использовать хо, 1(хо), з(з(хо)) и т. д.? ° 23. [М96] (Д. Фаата (О. Роаеа) и А.
Фучс (А. Гисьо), 1970.) Покажите, что каждая из т функций Дх), рассмотренных в упр. б, может быть представлена как последовательность (хо, хз,..., х„-з), имеющая такие свойства. 1) (хо,хз,...,х з) — это перестановки последовательности (1(0),1(1),...,1(т — 1)). й) (1(0),...,1(т — 1)) может быть единственным образом восстановлена из последовательности (хо, х з,..., х — з) й!) Элементы, которые появляются в циклах иэ 1, имеют вцд (хо,хз,..., хь-з), где 1г— самый большой индекс, такай, что зти 1г элементов различны.
го) х1 Ф (хш хз,, х,-з) влечет хз з = 1(хз), если хз не ЯвлЯетси наименьшим элементам о цикле из 1. т) (У(8)~ У(1): -, Дгп — 1)) — это перестановка последовательности (О, 1,...,гп — 1) тогда и только тогда, когда (хе, хы.,., х,„~) представляет собой обратную перестановку к той перестановке, которая в разделе 1.3.3 названа необычным соответствием. т1) хе = х~ тогда и только тогда, когда (хм..., хж ~) представляет собой ориентированное дерево, построенное в упр. 2.3.4.4-18, с 1(х) порождающим х. 3.3.
СТАТИСТИЧЕСКИЕ КРИТЕРИИ Наша основная циль — получить последовательность, которая ведет себя так, как будто она является случайной. Выше рассказывалось, как сделать период последовательности настолько длинным, что при практических применениях он никогда не будет повторяться. Это важный критерий,но он не дает гарантии, что последовательность будет использоваться в приложениях. Как решить, достаточно ли случайной будет последовательность? Если дать наудачу выбранному человеку карандаш и бумагу и попросить его написать 100 десятичных цифр, то очень мало шансов, что будет получен удовлетворительный результат. Люди стремятся избегать действий, приводящих к результатам, которые кажутся неслучайными, таким, например, как появление пары равных смежных цифр (хотя приблизительно одна из 10 цифр должна равняться предыдущей). И, если показать тому же человеку таблицу настоящих случайных чисел, он, вероятно, скажет, что эти числа не случайны.
Он заметит много кажущихся закономерностей. В соответствии с высказыванием доктора И. Дж. Матрикса (1. д. МагПх), который цитировал Мартина Гарднера (Магбп Сагдпег) в Яс1еш?йс Ашег1сан, 3аппагу, 1965, "Математики рассматривают десятичное разложение числа х как случайную последовательность, но современный специалист по магическим свойствам чисел найдет для себя множество интересных примеров". Матрикс указал, например, что первым повторяющимся двузначным числом в разложении числа х является 26, а второй раз оно появляется как раз посередине любопытных повторений пар чисел: 3.14159265358979323846264338327950 Составив список дюжины или более подобных свойств этих чисел, он заметил, что разложение числа х, если его правильно интерпретировать, может рассказать обо всей истории человечества! Все мы замечаем закономерности в наших телефонных номерах, номерах водительских прав и т.
д... чтобы их запомнить. Наша основная мыгль состоит в том, что нельзя быль уверенным в том, что данная последовательность является случайной. Для этого нужно применять какой-нибудь беспристрастный критерий. Теоретическая статистика предоставляет некоторые количественные меры случайности. Существует буквально бесконечное число критериев, которые можно использовать для проверки того, будет ли последовательность случайной. Обсудим критерии, с нашей точки зрения, наиболее полезные, наиболее поучительные и наиболее приспособленные к вычислениям на компьютерах. Если критерии Ты ?з,..., Т„подтверждают, что последовательность ведет себя случайным образом, это еще не означает, вообще говоря, что проверка с помощью Т„.~,-го критерия будет успешной.
Однако каждая успешная проверка дает все больше и больше уверенности в случайности последовательности. Обычно к последовательности применяется около полудюжины статистических критериев, и если ояа удовлетворяет этим критериям, то последовательность считается случайной (это презумпция невиновности до доказательства вины). Каждую последовательность, которая будет широка использоваться, необходимо тщательно проверить.
В следующих разделах объясняется, как правильна применять критерии. Различаются два вида критериев; эмпирические критерии, при использовании которых компьютер манипулирует группами чисел последовательности и вычисляет определенные статистики, и тлеоретическне критерии, для которых характеристики последовательности определяются с помощью теоретикочисловых методов, основанных на рекуррентных правилах, которые используются для образования последовательности.
Если информации, содержащейся в этой книге, будет недостаточно, можете обратиться к книге Даррелла Хаффа за техническими указаниями (Нозг бо Ые ЫсИ Я!а!!э!!сэ Вагге1! Нц)з (.'1огтоп, 1954)). Хафф Д. Б. (Нцй, Папе!1 Виг!оп) 3.3.1. Основные'критерии проверки случайных наблюдений А. Критерий "хи-книдрат". Критерий "хи-квадрат" (у!2-критерий), возможно, самый известный из всех статистических критериев.
Он является основным методом, используемым в сочетании с другими критериями. Прежде чем рассматривать идею в целом, проанализируем частный пример применения ~2-критерия к бросанию игральной кости. Используем две "правильные" игральные кости (каждая из которых независимо допускает выпадение значений 1, 2, 3, 4, 5 или 6 с равной вероятностью). В следующей таблице дана вероятность получения определенной суммы 8 при одном бросании игральных костей.
Значение в = 2 Вероятность рв = 28 3 4 5 6 7 8 9 10 11 12 1 1 ! б 1 б 1 1 1 1 (1) 18 12 9 Зб б Зб 9 12 18 88 Например, величина 4 может быть получена тремя способами: 1+ 3, 2+ 2, 3+ 1; это составляет 88 — — — = рб из 36 возможных результатов. Если бросать игральную кость и раз, то в среднем мы получим величину 8 примерно пр, раз. Например, при 144 бросаниях величина 4 выпадает около 12 раз. В следующей таблице показано, какие результаты е дейстеип1ЕЛьности ПОЛуЧЕИЫ при 144 бросаниях игральных костей. Величинаб= 2 3 4 5 6 7 8 9 10 11 12 Наблюдаемое число, 1; = 2 4 10 12 22 29 21 15 14 9 6 (2) Ожидаемое число, пр, = 4 8 12 16 20 24 20 16 12 8 4 ! Заметим, что во всех случаях наблюдаемое число отличалось от ожидаемого числа. Действительно, результаты случайного бросания игральной кости вряд ли всегда будут появляться именно с правильной частотой. Существует 36ы~ возможных последовательностей 144 бросаний и все они равновероятны.
Одна нз таких последовательностей состоит из всех двоек (" змеиные глаза"), и всякий, кто выбросил 144 змеиных глаза подряд, будет убежден, что кости утяжелены. Несмотря на это последовательность всех двоек является такой же вероятной, как н любая другая последовательность, если точно определить результат каждого бросания каждой игральной кости.
Принимая во внимание все сказанное, как проверить, утяжелена ли данная пара игральных костей? На этот вопрос нельзя дать ответ "да" или "нет", но можно дать ееролзнносглнмй ответ, т. е. сказать, насколько вероятно или не вероятно происшедшее событие. В приведенном выше примере совершенно естественно рассмотреть квадраты разностей между наблюдаемыми числами У, и ожидаемыми числами пр,. Можно сложить их, получив 1'= (1'з — прз) +(уз — прз) + +(Узз — прзз) .
(3) У вЂ” + + + (Уз прз) (уз — прз) (1 зз пр12) прз прз прзз Эта статистика называется статистикой "хи-квадрат" набл)одаемзях значений 1'з,..., Узз при бросании игральных костей. Для данных нз таблицы (2) получим, что (2 — 4)' (4 — 3)з (й — 3)з (6 — 4)' 4 (3) Теперь возникает важный вопрос: "Будет ли 71з невероятно большим значением для У при наших предположениях?". Прежде чем ответить на него, рассмотрим, как применяется метод "хи-кввдрат" в общих ситуациях. Предположим, что каждое'наблюдение может принадлежать одной из?з категорий. Проводим п незаеиснмъзх наблюдений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
