30. [М37] (P. П. Брент (R. P. Brent).) Пусть /(ж) = -aix*"-----ak - первообразный

полином по модулю 2, и предположим, что ЛГо, . , Xk-i - целые числа, не все четные.

a) Докажите, что длина периода последовательности, заданной рекуррентным соотношением Хп - {aiXn-\ Л-----1- йкХп-к) mod 2% равна 2~(2* - 1) для всех е > 1 тогда

и только тогда, когда /(х) +/(-х) 2f{x) и f{xf + f{-xf 2{-1)f{-x) (по модулю 8). [Указание. Равенство ж* = -х (по модулям 4 и /(ж)) справедливо тогда и только тогда, когда f(x) + /(-ж) = 2/(ж) (по модулю 8).]

b) Докажите, что это условие всегда выполняется, когда полином /(ж) = ж* ± ж ± 1 является первообразным полиномом по модулю 2 и /с > 2.

31. (Дж. Марсалья (G. Marsaglia).) Какова длина периода последовательности (7), когда m = 2 > 8? Предположите, что не все ЛГо,..., Х54 = ±1 (по модулю 8).

32. [М21] Каким рекуррентным соотношениям удовлетворяют элементы подпоследовательностей (Xin) и {Хзп), когда Хп = {Хп-24 + Хп-55) mod тп?

► 33. [М23] (а) Пусть gn{z)=Xn+30 + Xn+29Z + ---+XnZ°+Xn+b4Z + --- + Xn+ziz\ где Хп удовлетворяют рекуррентному соотношению Фибоначчи с запаздыванием (7). Найдите простое соотношение между gn{z) и gn+t{z). (b) Выразите А500 в терминах Ао, . ., Х54.

34. [М25] Докажите, что обратная рекуррентная последовательность (12) имеет период р + 1 тогда и только тогда, когда полином /(ж) = х - сх - а обладает следующими двумя свойствами: (i) х" mod /(ж) равняется отличной от нуля константе, если вычислять, используя полиномиальную арифметику по модулю р; (ii) х*"" mod /(ж) имеет степень 1 для каждого простого q, делящего р -Ь 1. [Указание. Рассмотрите степени матрицы (° ).]

35. [НМ35] Как много пар (а, с) удовлетворяют условиям упр. 34?

36. [М25} Докажите, что обратная конгруэнтная последовательность Xn+i = (аАГ~--с) mod 2, ЛГо = 1, е > 3, имеет период длиной 2~ всякий раз, когда а mod 4 = 1 и с mod 4= 2.

► 37. [НМ32] Пусть р - простое число, и предположим, что Xn+i = (аХп -Ь с) modp определяет обратную конгруэнтную последовательность с периодом р -Ь 1. К тому же пусть О < 61 < • • < 6d < р. Рассмотрим множество

V = {{Хп+ь,, Хп+ь,Хп+ь,) I о < п < р и Хп+ь, / сю для 1 £ J £ с/}

В нем содержится р + 1 - d векторов; любые d из них лежат в некоторой (d - 1)-мерной

гиперплоскости Н = {{vi,... ,Vd) ritJi -----+rdVd = го (по модулю р)}, где (ri,...,rd)

(О,..., 0). Докажите, что никакие d -Ь 1 векторов из V не лежат в одной и той же гиперплоскости.

3.3. СТАТИСТИЧЕСКИЕ КРИТЕРИИ

Наша основная цель - получить последовательность, которая ведет себя так, как будто она является случайной. Выше рассказывалось, как сделать период последовательности настолько длинным, что при практических применениях он никогда не будет повторяться. Это важный критерий, но он не дает гарантии, что последовательность будет использоваться в приложениях. Как решить, достаточно ли случайной будет последовательность?

Если дать наудачу выбранному человеку карандаш и бумагу и попросить его написать 100 десятичных цифр, то очень мало шансов, что будет получен удовлетворительный результат. Люди стремятся избегать действий, приводящих к результатам, которые кажутся неслучайными, таким, например, как появление пары равных смеж;ных цифр (хотя приблизительно одна из 10 цифр должна равняться предыдущей). И, если показать тому же человеку таблицу настоящих случайных чисел, он, вероятно, скажет, что эти числа не случайны. Он заметит много кажущихся закономерностей.

В соответствии с высказыванием доктора И. Дж. Матрикса (I. J. Matrix), который цитировал Мартина Гарднера (Martin Gardner) в Scientific American, January, 1965, "Математики рассматривают десятичное разложение числа тг как случайную последовательность, но современный специалист по магическим свойствам чисел найдет для себя множество интересных примеров". Матрикс указал, например, что первым повторяющимся двузначным числом в разложении числа тг является 26, а второй раз оно появляется как раз посередине любопытных повторений пар чисел:

3.14159265358979323846264338327950. (1)

ууу-ууу

Составив список дюжины или более подобных свойств этих чисел, он заметил, что разложение числа тг, если его правильно интерпретировать, может рассказать обо всей истории человечества!

Все мы замечаем закономерности в наших телефонных номерах, номерах водительских прав и т. д., чтобы их запомнить. Наша основная мысль состоит в том, что нельзя быть уверенным в том, что данная последовательность является случайной. Для этого нужно применять какой-нибудь беспристрастный критерий.

Теоретическая статистика предоставляет некоторые количественные меры случайности. Существует буквально бесконечное число критериев, которые можно использовать для проверки того, будет ли последовательность случайной. Обсудим критерии, с нашей точки зрения, наиболее полезные, наиболее поучительные и наиболее приспособленные к вычислениям на компьютерах.

Если критерии Ti, Тг, .. .,Тп подтверждают, что последовательность ведет себя случайным образом, это еще не означает, вообще говоря, что проверка с помощью Г„+1-го критерия будет успешной. Однако каждая успешная проверка дает все больше и больше уверенности в случайности последовательности. Обычно к последовательности применяется около полудюжины статистических критериев, и если она удовлетворяет этим критериям, то последовательность считается случайной (это презумпция невиновности до доказательства вины).

Каждую последовательность, которая будет широко использоваться, необходимо тщательно проверить. В следующих разделах объясняется, как правильно применять критерии. Различаются два вида критериев: эмпирические критерии, при использовании которых компьютер манипулирует группами чисел последовательности и вычисляет определенные статистики, и теоретические критерии, для которых характеристики последовательности определяются с помощью теоретико-числовых методов, основанных на рекуррентных правилах, которые используются для образования последовательности.

Если информации, содержащейся в этой книге, будет недостаточно, можете обратиться к книге Даррелла Хаффа за техническими указаниями (How to Lie With Statistics Darrell Huff (Norton, 1954)). Хафф Д. Б. (Huff, Darrell Burton)

3.3.1. Основные: критерии проверки случайных наблюдений

А. Критерий "хи-квадрат". Критерий "хи-квадрат" (х-критерий), возможно, самый известный из всех статистических критериев. Он является основным методом, используемым в сочетании с другими критериями. Прежде чем рассматривать идею в целом, проанализируем частный пример применения х-критерия к бросанию игральной кости. Используем две "правильные" игральные кости (каждая из которых независимо допускает выпадение значений 1, 2, 3, 4, 5 или б с равной вероятностью). В следующей таблице дана вероятность получения определенной суммы S при одном бросании игральных костей.

Значение s=2 3 4 5 б 7 8 9 10 11 12

Веппятнпгтт, n--L-L-Li-LiiiJ-i вероятность Ps - 36 jg 12 9 36 б 36 9 12 18 36

Например, величина4 может быть получена тремя способами: Ц-З, 2-1-2, 3-1-1; это составляет = = Р4 из 36 возможных результатов.

Если бросать игральную кость п раз, то в среднем мы получим величину s примерно пре раз. Например, при 144 бросаниях величина 4 выпадает около 12 раз. В следующей таблице показано, какие результаты в действительности получены при 144 бросаниях игральных костей.

Величина s=23 4 5 б 7 8 9 10 И 12 Наблюдаемое число, Ys = 2 4 10 12 22 29 21 15 14 9 б (2)

Ожидаемое число, пр« = 4 8 12 16 20 24 20 16 12 8 4

< Заметим, что во всех случаях наблюдаемое число отличалось от ожидаемого числа. Действительно, результаты случайного бросания игральной кости вряд ли всегда будут появляться именно с правильной частотой. Существует 36 возможных последовательностей 144 бросаний и все они равновероятны. Одна из таких последовательностей состоит из всех двоек ("змеиные глаза"), и всякий, кто выбросил 144 змеиных глаза подряд, будет убежден, что кости утяжелены. Несмотря на это последовательность всех двоек является такой же вероятной, как и любая другая последовательность, если точно определить результат каждого бросания каждой игральной кости.

Принимая во внимание все сказанное, как проверить, утяжелена ли данная пара игральных костей? На этот вопрос нельзя дать ответ "да" или "нет", но