Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 16
Текст из файла (страница 16)
Он заметит много кажущихся закономерностей. В соответствии с высказыванием доктора И. Дж. Матрикса (1. 3. МасПх), который цитировал Мартина Гарднера (Магсш Оагбпег) в Яс~епс)бс Ашег1сап, Лапивху, 1965, "Математики рассматривают десятичное разложение числа я как случайную последовательность, но современный специалист по магическим свойствам чисел найдет для себя множество интересных примеров"'. Матрикс указал, например, что первым повторяющимся двузначным числом в разложении числа х является 26, а второй раз оно появляется как раз посередине любопытных повторений пар чисел: 3.14159265358979323846264338327950 Составив список дюжины или более подобных свойств этих чисел, он заметил, что разложение числа х, если его правильно интерпретировать, может рассказать обо всей истории человечества! Все мы замечаем закономерности в наших телефонных номерах, номерах водительских прав и т.
д., чтобы их запомнить. Наша основная мысль состоит в том, что нельзя быть уверенным в том, что данная последовательность является случайной. Для этого нужно применять какой-нибудь беспристрастный критерий. Теоретическая статистика предоставляет некоторые количественные меры случайности. Существует буквально бесконечное число критериев, которые можно использовать для проверки того, будет ли последовательность случайной. Обсудим критерии, с нашей точки зрения, наиболее полезные, наиболее поучительные и наиболее приспособленные к вычислениям на компьютерах.
Если критерии Тм Т~, ..., Т„подтверждают, что последовательность ведет себя случайным образом, это еще не означаеш, вообще говоря, что проверка с помощью Т„.ы-го критерия будет успешной. Однако каждая успешная проверка дает все больше и больше уверенности в случайности цогледовательности. Обычно к последовательности применяется около полудюжины статистических критериев, и если она удовлетворяет этим критериям, то последовательность считается случайной [это презумпция невиновности до доказательства вины).
Каждую последовательность, которая будет широко использоваться, необходимо тщательно проверить. В следующих разделах объясняется, как правильно применять критерии. Различаются два вида критериев: эмпирические критерии, при использовании которых компьютер манипулирует группами чисел последовательности и вычисляет определенные статистики, н и!еврея!ические крин!ерни, для которых характеристики последовательности определяются с помощью теоретикочисловых методов, основанных на рекуррентных правилах, которые используются для образования последовательности.
Если информации, содержащейся в этой книге, будет недостаточно, можете обратиться к книге Даррелла Хаффа за техническими указаниями (Нов го Ые И'!гЛ 81а!!эг!сэ ВеггеП Нпй' (Ног!оп, 1954)). Хафф Д. Б. (НиК, Оагге!1 Впгтоп) 3.3.1. Основные: критерии проверки случайных наблюдений А.
Критерий "хи-квадрат". Критерий "хн-кведрат" (тт-критерий), возможно, самый известный из всех статистических критериев. Он является основным методом, используемым в сочетании с другими критериями. Прежде чем рассматривать идею в пелом, проанализируем частный пример применения э!э-критерия к бросанию игральной кости. Используем две "правильные" игральные кости (каждая иэ которых независимо допускает выпадение значений 1, 2, 3, 4, 5 вли 6 с равной вероятностью).
В следующей таблице дана вероятность получения определенной суммы е при одном бросании игральных костей. Значение е = 2 3 4 5 6 ! 8 9 10 11 12 ! ! ! ! ! ! Ь ! 1 ! ! (1) Вероятность р =— р» эе !э 12 9 эе е эб э !т !е 36 Например, величина 4 может быть получена тремя способами: 1+3, 2+ 2, 3+1; это составляет эе = — = р! из 36 возможных результатов. Если бросать игральную кость и раз, то в среднем мы получим величину а примерно пр, раз. Например, при 144 бросаниях величина 4 выпадает около 12 раз.
В сведующей таблице показано, какие результаты в дайся!вип!ельноспэи получены при 144 бросаниях игральных костей. Величина э= 2 3 4 5 6 7 8 9 10 11 12 Наблюдаемое число, У, = 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' = (1г прг) + (1э пръ) + ' ' '+ (1и пръг) (3) 1т — + + + (1г прг) (1з — прг) (1и при) (4) прг пРз ПР1г Эта статистика называется статистикой "хи-квадрат" наблЬдаемых значений 1'г,..., 1'1г при бросании игральных костей. Для данных из таблицы (2) получим, что (2 — 4)г (4 — 8)г (9 — 8)г (6 — 4)г 7 1:— 4 8 8 4 48 + — + .+ — + — — 7 (3) Теперь возникает важный вопрос: "Будет ли 74~э- невероятно большим значением для Г при наших предположениях?".
Прежде чем ответить на него, рассмотрим, как применяется метод "хи-квадрат"' в общих ситуациях. Предположим, что каждое наблюдение может принадлежать одной из й категорий. Проводим и независимых наблюдении. Это означает, что исход одного наблюдения абсолютно не влияет на исход других наблюдений. Пусть р, — вероятность того, что каждое наблюдение относится к категории э, и пусть У,— число наблюдений, которые действительно оигнослтсл к категории в.
Образуем статистику й (1 ю прв)" (6) прв В примере, приведенном выше, существует одиннадцать возможных исходов каждого бросания игральных костей, т. е. Й = 11. (Формула (6) немного изменила обозначения формулы (4)„так как нумеруются возможности 1-Й вместо 2-12.) Плохой набор игральных костей привел бы к относительно большому значению Ъ; а для данного значения Е можно сказать следующее: "Чему равна вероятность таких больших значений Ъ', если использовать тправильныеэ игральные кости?".
Если эта вероятность очень мала, скажем, +, мы будем знать, что только около одного раза из ста "правильные" игральные кости будут давать результаты, настолько далекие от ожидаемых значений. что возникнут определенные основания для подозрений. (Помним, тем не менее, что те же самые хорошие игральные кости будут давать такое большое значение 1' приблизительно в одном случае из ста, так что предусмотрительным лицам придется повторять эксперимент, когда большие значения Ъ' являются частыми.) В статистике 1" в (3) слагаемым (1т — прт) и (Уг — прг) приписываются равные веса, несмотря на то что (Ут — прт)г, вероятно, будет больше, чем (1г — прг)г, так как 7 появляются приблизительно в шесть раз чаще, чем 2. Оказывается, что "правильная" статистика, по крайней мере статистика, которая, как доказано, наиболее важна, бУдет пРиписывать (тт — прт)г только -' веса, пРиписываемого г е (Уг — црг)', и необходимо изменить (3) следующим образом: Возводя в квадрат (1;, — пр,)т = 1;т — 2пр,); + пзр~ в (б) и учитывая тот факт, что Г1+Ут+ .+Уь =и, (7) р1 + Рз + ''' + Рь = 1 получаем формулу которая часто упрощает вычисление И.
Возвратимся к вопросу "Чему равно приемлемое значение 1'7". Его можно определить с помощью таких таблиц, как табл. 1, которая дает значения "~з-распределения с и степеиямн свободы" для различных значений и. Используем строку таблицы с и = Й-1, так как число "степеней свободы" равно Й-1, что на единш~~ меньше, чем число категорий. (Интуитивно это означает, что 1з, 1'з,..., 1ь не являются полностью независимыми, так как формула (7) показывает, что Уь может быть вычислено, если 1ы ..., Уь 1 известны.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
