Построение оценок энтропии стационарных случайных процессов тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Тимофеева, Нина Евгеньевна

• Тимофеева, Нина Евгеньевна
• кандидат физико-математических наук
• 2010

Введение диссертации (часть автореферата) на тему «Построение оценок энтропии стационарных случайных процессов»

В настоящей работе предлагаются три новые статистические оценки энтропии, основанные на методе "расстояния до ближайших соседей "(см. раздел 1.2.2). Принципиальные преимущества новых оценок гго:

1) степенной порядок точности дисперсии:

2) при оценивании энтропии динамических систем значения оценок не зависят от разбиения пространства;

3) в ряде случаев удается показать степенной порядок убывания смещения (для оценки из главы 2).

При выполнении определенных условий показан прием уменьшения смещения оценки (глава 3). В работе также приведен эффективный алгоритм вычисления оценки но экспериментальным данным.

Напомним определение энтропии (см. напр. [2], [32], [29]).

Пусть дан конечный алфавит А. Пусть есть случайная последовательность символов этого алфавита. Тогда энтропией случайной последовательности £ (энтропией па символ) называется величина

И = 1пп (1) л—*-1ЛО п где

Н = Я- • •, = ~ ]Г = ■ • ■. & = гп) \ogPfa = ¿1, .,£„ = О

11,.,<„6-4

В этой формуле логарифм обычно берегся по основанию 2.

Впервые эго понятие ввел К.Шеннон в 1948 г. (см. [37]). Он использовал его для измерения количества информации и показал, что энтропия определяет границу степени сжатия текста. Это одно из важных практических применений энтропии: почти любой текст £ь . нельзя закодировать менее, чем Нп символами.

В 50-е гг. А.П. Колмогоров перенес понятие энтропии на динамические системы (см. например [2], [29], [32], [26]).

Пусть (М,ц,Т) — динамическая система: Л/ — множество, // — мера па МиГ — измеримое преобразование множества М, сохраняющее меру, т.е. ц(Т — Для любого измеримого А.

Будем рассматривать конечные или счетные измеримые разбиения пространства М, т.е. наборы множеств а = {Аг}, Д- - измеримое, таких, что г((^| /1г) = ц(М) и /1(Лг Р) Л3) = 0 для любых 1 и

Считается, что ц(Аг) > 0 при всех i.

Энтропией разбиения а = {Ai} называется число i

Для разбиений а = {Ai}, ß = {В,} их произведением a\J ß назовем разбиение, элементами которого служат всевозможные множества вида Aif]Bj. Энтропией на символ разбиения а называется величина h(a, Т) = lim -Н(а \/ Та \/ . \/ Тпа). п-'ОО п V V V

Энтропией динамической системы (А/,/¿,Т) называется величина

ЦТ) = вир h(a,T), n где верхняя грань берегся по всем конечным птп счетным измеримым разбиениям а пространства М.

А.Н. Колмогоров показан, чю для многих разбиений энтропия на символ разбиения совпадает с энтропией динамической системы. А.Н. Колмогоров доказал, что энтропия есть инвариант динамической системы, изоморфные динамические системы имеют одинаковую энтропию. В частности, A.Ii. Колмогоров применил понятие энтропии для решения задачи об изоморфности сдвигов Вернул ли.

В 1971 г. Д.Орнстейп доказал утверждение, обратное теореме Колмогорова: если энтропии сдвигов Бериуллн одинаковы, то эти сдвиги изоморфны (см. [30], |29|). Эти исследования показывают важное теоретическое значение энтропии.

Как говорилось выше, энтропия определяет границу сжатия информации. Поэтому в прикладных задачах нужно оценить значение энтропии по экспериментальным данным. В терминах определения (1) задача формулируется следующим образом: дан текст из п символов ¿ц,. построенных над некоторым конечным алфавитом. Нужно найти значение энтропии этого текста. Очевидно, что при такой постановке нахождение точного значения энтропии по определению (1) невозможно, т.к. число символов в тексте конечно п. значит, о существовании предела речь идти не может. Таким образом, по экспериментальным данным можно построить только оценку энтропии.

Задаче построения оценок энтропии посвящено большое число работ. Приведем краткий обзор известных в настоящее время результатов.

Существуют два основных подхода к построению оценок: построение эмпирической функции распределения и непараметрические оценки. Рассмотрим эти два подхода.

0.1 Построение эмпирической функции распределения

Определение (1) можно переписать в виде:

1,. ,гп ел E(-logP(eb.,£„)).

Эта формула показывает, что наибо ice естественный способ построения оценки — это прямое вычисление математического ожидания логарифма эмпирической функции распределения. Этот способ удобен, если число параметров, от которых зависит распределение, конечно.

Рассмотрим, например, бесконет шую случайную последовательность , которая принимает значения 0 и 1 независимо с вероятностями а и ¡3 соотвеетвенно Тогда, как показано в работе Шеннона [37], формула (1) принимает вид: h — —a log а — р log (3.

Если значения а и (3 неизвестны, то оценку энтропии можно посчитать простейшим способом. Рассмотрим достаточно длинную последовательность Пусть /„(0) и /п( 1) счетчики, сколько раз встретился 0 и I в конечной последовательности ., соответственно. Тогда оценка энтропии считается по формуле: h„ = —/„ (0) log /„(0) - /„(l)log/n(l).

Последовательность случайных величии hп сходится по вероятности к энтропии h. Также можно показать схочпмосгь почт ниол\ и справедливость центральной предельной теоремы: нормированные величины /;,, сходшся к нормальному распределению (см. [24]).

Если число параметров бесконечно или неизвестен вид зависимости от параметров, то этот подход применяется следующим образом.

Пусть Л — конечный алфавит и пусть w = и<\ . wm G Л7". Обозначим ц(и>) = Р(£i = wi,.,£m = wm). По теореме Шепнопа-МлкМиллапа-Брепмапа (см. [37]). случайные величины

Нт =--V fi(w) log fj.(w). rn ' we A1" сходятся к энтропии h для почти всех w.

Если процесс эргодический, то частота появления слова ги сходится к величине ¡-i(w). Таким образом, предлагается следующий способ построения оценки энтропии.

1) фиксируем бо 1ЫПОС число т:

2) рассмотрим достаточно длинную последовательность .

3) оценим числа fi{w), w € Лт, т.е. найдем частоты fn(w) всех слов w, w £ Ат в рассматриваемой нос 1едовательности, н, наконец, получим оценку h по формуле:

Кт = - Y1 /«И1оё/пИweAm

При п —> оо и т • оо величины hnm сходятся к /;.

Но в этом методе есть ряд существенных недостатков: неизвестно, что точно означают слова "болыное"т; что точно означает "болыпое"?7; двойной переход к бесконечности (по п и т).

Эти три недостатка делают этот метод неудобным д ш -теоретических исследований. Впервые такой подход к построению оценок энтропии описан Г.И.Башарииым [24]. Если же число возможных слов w G Лт экспоненциально растет, то этот метод становится не применим и в прикладных задачах.

Например, пусть |Д| = 2 и рассмотрим всевозможные слова длины 50. Число таких слов равно 2d0. Будем считать, что все эти слова возможны. Однако, современная техника позволяет получить последовательность длины п = 230 -т- 240 символов. Таким образом, вероятность получения каждого слова оценить невозможно, т.к. какие-то слова просто получены не будут. Значит оценить математическое ожидание эмпирической функции распределения также невозможно и об оценке энтропии речь идти не может.

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

0.2 Непараметрические оценки.

Ненараметрические оценки энтропии могут быть поделены на два больших класса. Первый класс использует алгоритмы сжатия данных Лемпеля-Зива [22]. [23]. Второй класс основан на методе "расстояния до ближайших соседей".

0.2.1 Класс оценок, основанный на алгоритме Лемпеля-Зива.

Обзор этого алгоритма можно найти в работе [21]. Приведем краткое описание алгоритма.

Пусть а = ((in)neiv — последовательность элементов алфавита Л. Определим разложение Зива последовательности а как последовали1 1ьноеть (гип) = (ши(а)) пои, определяемых по индукции:

1. г/'о = а0

2. Пусть wi, u)2, ■ ■ ■ ,ii'k определены и wqU)\ . . w^ = o-oaj . an. Тогда

Пн = ftn-ii"ui2 • • Л|т, где т — наименьшее целое такое, что a„+1a„, 2. ■. ап+т {»'о, и)\,. Wk}- Для всех а 6 и для всех к £ N иотожим к п(к,а) = |^1(a)«;2(a) . . ?n(a)| = ^ |шг(а)|, 1 где через |ш| обозначена длина слова w.

Основной резул1>гат Лемпеля-Зива формулируется следующим образом:

Теорема 1. Если п —> оо, то случайная величина ^ц^а) сх°дится по вероятности к h — энтропии стационарного эргодического процесса.

П.Грасбергер, основываясь на этом алгоритме, предложил оценку величины обратной к энтропии, т.е. величины 1/h. |б[: у-п гп

К = , \ (2)

V logn где L" — наименьший префикс всех слов, начиная с г-го символа текста до п-го. Также он предположил, что у^п j-n ^ lim ———L = — почти всюду. (3)

-►оо /¿logn II

Из формул (2) и (3) видно, что с теоретической точки зрения удобнее работать с величиной обратной к энтропии. В этом случае суммиронаппе идет в числителе п проще применять вероятностные теоремы. Для простоты, здесь и далее, говоря об оценках энтропии будем иметь ввиду оценку величины обратной к энтропии.

Используя результаты Д.С.Орнстеина и Б.Вейса [17], П.Шилдс (см. [18]) доказал, что эта оценка не является сходящейся дчя общих эргодических процессов.

В этой же рабо1 е П.Шилдс доказа ь ч 1 о при наложении определенных условий предложенная П.Грасбергером оценка (2) 6\дет состоятельной.

Теорема 2. Равенство

7 = 1 1 lim

П >эс П lüg П II, верно для независимых одинаково распределенных процессов, для перемещивающих цепей Маркова и для процессов с нулевой энтропией (в этом случае предел полагается равным -J-oo)

Основываясь на этом результате И.Контояннис п 10.М.Сухов [13] распространили оценку па более широкий класс стационарных эргодических процессов.

Теорема 3. Равенство

Em*) lim

7 = 1 1 п log п h верно для стационарных эргодичесиил процессов £ = (£„). построенных •над конечным, алфавитом, которые удовлетворяют условию Деблина: с уществует такое г ^ 1, что для почти вес л■ процессов inf Р{ХпЛ г = п\х „, = а о----,xn = an+m) ^ а > 0. о, ■

В работе [14] предложены три модификации оценки П.Грасбергера (2). Похожие оценки энтропии появляются в [19], |5|, где их работоспособность показана на обработке английских текстов.

0.2.2 Метод "расстояния до ближайших соседей".

Первую оценку такого рода предложил Р.Л.Добрунштт [4]. Он сделал это следующим образом.

Рассмотрим класс последова течьиостей, образованный конечно зависимыми величинами ц1. • • •• т.е. пусть л' — параметр конечной зависимости, тогда если ,., и — наборы случайных величии и ¿1 <.<%).< < . < го при

3\ ~ 1к > величины . не зависят от .

При оценивании энтропии этой последовательности можно применить следующий прием. Для некоторого натурального числа Т из последовательности {&} выбираются отрезки длины Т с пропусками длины я между ними и формируется последовательность векторов длины Т: где = (£(74-0(7-1) I 1----1 непоследовательность образована независимыми одинаково распределенными случайными величинами. Энтропия этой последовательности совпадает с энтропией /г исходной послсдова1 етьностн ([4]).

Таким образом, энтропия оценивается следующим образом.

Рассмотрим последовательность серий независимых одинаково распределенных случайных величин и положим N = \Л\1. v

Р{£ = к} = рь /с = 1. 2.N ]Г> = 1. с=1

Величины рк и /V зависят от Т: р*. = рА (7-1) иАС-»^ при Г —> оо. Требуется оцепить эитропшо к. Положим

71 =шш{?(, ^ 1 Ч'чи =£1'}, г, = тш{п ^ 1 : = Г ^ 2, о = 1, = Г! + . -г гг1 4- 1, г = 2, 3,---

В качестве оценки /г берется выражение;

- 1 г, = — ^ 1 пт7 + С. т

1 — 1 где С - константа, Эйлера. С = 0.5772157., а т вычисляется в процессе работы и зависит от числа символов исходной последовательности.

Таким образом, Р. I Добрушпн предложил следующий прием построения оценок: если ранее рассматривалась одна бесконечная последовательность (как в определение (2)), то при новом подходе рассматривается бесконечное число конечных последовательностей.

В.А.Ватутин и В.Г.Михайлов [20] нашли смещение оценки Р.Л.Добрушина, оценили значение ее дисперсии и доказали соеюятепьность.

Теорема 4. Для некоторого вг 6 (0.13, 0.578)

ЕЙ = Н+\ь\ + вхР2.

Теорема 5. Пусть р ^ 0.377. Тогда

ВЫ = — [В2 - /г + П + -А - (/г + 1Ж - вхНР2 + в2Р2) , т \ 2 ) где вх £ (0.13, 0.578) и в2 е (-3.83, 2.202).

Теорема 6. Пусть при Т —» ос параметры схемы меняются так, чти

1 1 + Я, - 4Д,/1 + 6Б2Л2 - З/г4 т2 3 1 -т- (Zi2 - Д2)2

0. тогда распределение случайной величины (Н — EiH)(Dh) 112 сходится при Т —► оо к: нормальному стандартному распределению.

В формулировках теорем Р2, В2, D, Вз, В.х — это константы, определенные в работе [20].

Позднее исследователи развили идею Р.Л.Добрушина следующим образом.

Пусть Q — пространство последовательностей, р — некоторая метрика на Q. ¡л — мера на Q, . ., — независимые одинаково распределенные по мере д случайные точки из Г2.

Расстояние между точками определяется по формуле:

Гп = -- V*lo s (minpte.i,)) . (4) п ' )

Тогда оценка энтропии считается по формуле:

К = -т^—- (5) log п

В этих формулах логарифм может браться по любому основанию.

В случае произвольной метрики р величина hn оценивает обратную размерность меры ц. В работе [33] приведен следующий пример, который показывает, что в обычном евклидовом пространстве предлагаемая оценка совпадает с размерностью.

Пример. Пусть Q — .ч-мерный куб с обычной метрикой и лебеговой мерой /л. Пусть ■ • • Лп — независимые точки равномерно распределенные в Q, тогда среднее минимальное расстояние ги между точками si, £2, ^-мерном кубе равно 0(n~ll/s). Оценка энтропии совпадает величиной i/s.

Р.Бадии и А.Полити [1] предложили оценивать размерность Хаусдорфа в общем метрическом пространстве, основываясь на величине

П.Биллингслей [2] показал, что при выборе подходящей метрики энтропия совпадает с размерностью Хаусдорфа.

Основываясь на результатах Р.Бадии и А.Полити, П.Грассбергер ввел свою вторую оценку энтропии на пространстве = 4N (см. [6]) hu = -ГТ~Г JZ 1о& С?)) ' (6)

71 log 77 ^ где метрика р(х,у) = 2-m'm{k:Xh^Vk],

И X = {хиХ2, . . .), У = {?Уь 1/2, - - •}•

Он также предположил существование следующего предела: lini hn = — почти всюду. п—> ОО h

Пример, приведенный П.Шилдсом в работе [18], показывает, что оценка П.Грасс-бергера (6) несостоятельна для общего эргодического процесса.

В этой же работе П.Шилдс показал, что предлагаемая П.Грасбергером оценка (5) состоятельна для неприводимых непериодических марковских цепей. В работах [28], |33] было введено обобщение оценки (5): —

-¿logLm(fcV(eb^)V (7) п log п где для любого упорядоченного множества хх ^ х2 ^ . . . ^ xN min^jx'i,. . , xN} полагается равным Хк. Было показано (ем.|33|), что дисперсия оценки (7) имеет порядок 0(п~с), где с — некоторая константа:

Теорема 7. Пусть выполнено условие

Ч-'ОО In и u->ос In и

Тогда для с < min{fi2, d/d, 1}«

Здесь B(x.r) — шар с центром в точке х радиуса г.

Отметим, что оба класса непараметрических оценок связаны между собой. Действительно, оцеика( 2) связана с оцопкой( 6) следующим образом. Если

К =--;п log п где

Ра = i ' "J ' min{A : хк ф <д.}'

Тогда величина (м)(ч,.ч;)) 1 равна длине наименьшего префикса между словами и увеличенного на единицу.

0.3 Результаты диссертации

Перейдем к описанию результатов диссертации.

Рассматривается пространство нос. юдователышетеп О = Пусть ¡1 — эргодпче-ская. инвариантная относительно сдвига мера на пространстве Пусть — независимые, одинаково распределенные по мере /./ случайные точки из П.

Если рассматривается прикладная задача, то задано п слов длины т. В этом случае, считаем, что эти слова совпадают с первыми т символами точек ¿д,.,^ и будем обозначать эти слова через . -. чп"1

Нужно построить оценку величины обратной к энтропии.

В каждой главе предлагается сном оценка энтропии, в зависимости от того какая метрика задана на пространстве П.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Тимофеева, Нина Евгеньевна

3.4 Заключение

Таким образом, предлагается новое семейство оценок энтропии. Вычислительный эксперимент подсказывает, что эти оценки )ффективны на примерах, которые рассмотрены, что позволяет предположить следующее: трудпопроверяемые условия теоремы 21 выполняются для достаточно широкого класса мер.

Глава 4

Для построения оценок энтропии в главах 1-3 и построения оценок размерности в работе [28] нужно находить следующую величину:

Г"Л) = ^ТТ ^ ф (-Й(к)р{^ ' ^ где ф — некоторая монотонная функция. В этой главе предлагается алгоритм нахождения величин для всех значении я ^ п. Результат опубликован в работе |36].

Трудоемкость алгоритма равна 0(гип), где т —длина строк. Таким образом, нахож

О (к) (к^ дение всех величин гк .гк+1.г„ имеет такую же трудоемкость но порядку роста как и нахождение одной величины . Нахождение оценок различных для значений п позволяет определить смещение, которое зависит от п.

4.1 Постановка задачи

Пусть заданы и + 1 последовательностей £0 = (®оь • • •, х0т).= • -.Хлт), г,те х,3 € Л ={1,2,., а}.

Будем обозначать лексикографический порядок на пространстве = Л"1 через х =<: У

Пусть на задана метрика р, п])о которую будем предполагать, что она согласована с порядком, т.е. у) < р(х, г) Ух 4 г. (4.2)

Требуется найти величины г[1\ заданные по формуле (4.1), для всех к < я < п, 1 < I < к, где к - заданное число.

4.2 Описание алгоритма

На вход алгоритма подается последовательность ■ - - функция ф, параметр к. к1

В результате работы алгоритма получаем величины 7^ для всех к < в ^ п. Работа алгоритма состоит из трех шагов.

1. Выполним сортировку строк £„, в возрастающем порядке. Пусть

7]0 =4 ■ ■ • Г]п

- отсортированные строки, а а - перестановка такая, что

Пег, = г = 0,1,., п. Организуем строки г]0, . г}п в двусвязаииый список. 2. Для j = 0, 1,. . , п и / = 1, 2,. . . , к находим величины

9j= min Mpirn.Tij). (4.3)

Затем считаем величины где / = 1,2.к.

3 Для 5 = п. п — 1. . . , к делаем следующее: a) удаляем строку г)СГв — из двусвязанного списка, потому что для нахождения г{к^ величина £а не нужна, ее уже нет в формуле (4.1). b) для / = 1.2, . . ., к и j = I. . . , а3 + 1 находим величины д1- по формуле (4.3); c) для I = 1.2.к пересчитываем величины заменяя в формуле (4.4) величины д13 д. ш ] = ст., — /. , стЛ + I.

Отметим, что нумерация по 7 на шаге ЗЬ идет по двусвязанному списку. Отметим также, что поскольку величины д' находятся последовательно для I = 1,2.,/с, то для нахождения каждой величины д^ по формуле (4.3) достаточно находить минимум только из двух расстояний.

Пример работы алгоритма будет приведен в п.4.6.

4.3 Обоснование алгоритма

Покажем, что в результате работы алгоритма были найдены значения величин i-k, определенные в формуле (4.1), где s ^ vi. Действительно, по свойству согласованности (2.9) min ik)p(rjh rfc) = . min . {k)р{тц, rjj). r.lyij iT3'J^kS^S3+k

Т.к. на этапе (Зс) в (формуле (4.4) поменялись значения величии дк только для j = as — /,., CTj,. + /, то для подсчета нужно заменить в формуле (4.4) только значения этих

1 1 'л (к) величин и поменять множитель —цт па Это озпачаел-, что величины Гп , панде

S+1 иные по формулам (4.4) и (4.1), совпадают'.

4.4 Трудоемкость алгоритма

Трудоемкость шага 1 равна 0(пт). Приведем алгоритм, с помощью которого можно получить названную трудоемкость.

Вспомним, что координаты точки принадлежат Л. Воспользуемся этим. Пусть А = [а.\., o.q}, £oi - ■ - ■ , — первые координаты точек . . . , Сделаем следующее: 1. Посчитаем величины кг — сколько раз а, встречается в последовательности оъ • • • j 12. Посчитаем "границы": (7г = О, G2 = к\. G¿ = к\ + к2, ■ ■., Gm^ i = ki + . kq = n + 1. 3. Для каждого О г ^ q делаем следующее: если == аь то ставим на место G¿, G¿ заменяем на + 1, остальные границы пе меняем.

В результате получаем последовательность точек . ., отсортированных по первой координате. Всего т координат, значит трудоемкость первого niara равна 0(пт). На остальных шагах наиболее трудоемкой операцией является нахождение расстояния между двумя строками. Будем считать, что ее трудоемкость равна 0(т), т.к. метрика произвольна:.

Трудоемкость шага 2 равна 0(k2vm). Действительно, для нахождения (]13 нужно выполнить 21 + 1 нахождение расстояний, которое по предположению делаются с трудоемкостью 0(т). Это повторяется пк раз Значит, трудоемкость равна

2к + 1)пкО(т), как и утверждалось.

Трудоемкость шага 3 равна 0(кгпт), г к. для каждого s пересчптывается 2к + 1 значение в формуле (4.4).

Итак, трудоемкость алгоритма равна 0(к2пт).

Подчеркнем, что при небольших к (не зависящих от п) трудоемкость алгоритма равна 0(пт).

4.5 Свойство согласованности

Нетрудно видеть, что свойство согласованности (2.9) выполняется для метрики

Ро(я,у)= , 1-г-(4.5) mm {к : :гк ф ук} где х — (х\,х-2, ■ ■ ■), и у = 0/1,г/2> • • • )• Действительно, пусть х, у, z — три точки, связанные соотношением:

Распишем это: х 3 У <=> X! = /Уь .То - У2,---, -П < Ук

У -< z г/i = zuy2 = г2,. ,ут < =т.

Рассмотрим два случая. Случай 1: т < к. Тогда

Х\ = Z1, . . . . Хп!— 1 — Zrn \, хт — ут ^ . следовательно. 1

Л)(х, z) = —. m

Значит свойство сог тсовапности имеет вид 11 , Ро(х,у) = - < — = А)(х, z), с 1 п что верно, т.к. по предположению m < к. Сличай 2: m ^ к. Тогда

Xi = zu . . . ,.ТА! = zk-i,xk < ук <= zk,---

Следовательно.

Po(x. z) = и свойство согласованности иереписывае геи следующим образом

N 1 / N 1

Ро(х,у) = j ^ Po(x.z) = -, чю. очевидно, верно. Для метрики m px{x,ij) = J2e~k\xk-Vk\, (4.6) fc=i где в > 1, свойство согласованности не выполнено.

4.6 Пример работы алгоритма

Положим к = 2, ф = х"1. Рассмотрим десять точек. = (0,0,0,0,0); = (0,0,1,1,0); 6 = (0,0.0,1,0); ^ = (0,0,1,0,0); ^ = (0.1,1,1,0); (0,1,1,1,1); & = (0,0, 0,0,1); & = (1,1,1,1,1). & = (0,0,0,1.1); = (0,0,1,1,1);

На первом шаге работы алюритма нужно эти точки упорядочить. Сделаем это: = (0,0,0,0,0); (0.0,0.0,1) т - (0.0,0. 1,0) ш = (0,0,0.1,1)

Ц\ = (0.0,1,0,0) т> = (0.0.1.1,0)

Vg = (0,0,1,1,1)

V- = (0,1,1,1,0)

Пя = (0,1,1,1,1)

Щ = (1,L, 1,1,1)

Выпишем перестановку: ст0 = 0, сг\ = 5, а2 = 2, сг3 = 4. <74 = 7, сг5 = 8, сте = П "г = <т8 = 3,а9 = 6.

Перейдем ко второму шагу: j = 0,., 9, I = 1,2. Посчитаем д^р. Пусть 1 = 1.

Тогда д[р = min 7/i) = pfao, 7?i) = о = min(1){p(//o,/?i),/y(77b?72)) = р{-П2,т) = р g¡1} = тт(1){р(?]1,г/2),р(772,г?з)} = О r/.^ = min(1){p(77o. '/з),р(т,щ)} = l] О g[1] = mm(1){/4'M-//i). p(??4, %)} = min ll1{/4'/i-= 7; O g£l) = min (n{/'(//;,.//„)■ /Ч'А- ^7)} = 7: O min(1){/)(//í;, ?/7),/;(//7л/8)} = 7; O

1} = min(1){p(í/7. '/s),p('/s,7]9)} = 7: min(1V(//8 , 779) = 1.

Следовательно, x) 1 1 5 + 5 + 5 + 5 + 4 + 5 + 5 + 5 + 5+1

7-9 10 ~ '5j=o

Выполним второй шаг алгоритма для I = 2. дР = min (2){р(?]о, /7г), р(г?0, %)} = 5G gW =inin [2) {р(т]о,т)- ('Uli - П2)* pOh- Пз)} = p(vi,V 2) = I', 0 gf] = тт{2){р(гю,г]2), p(rii,V2), p(V2iih)- p(V2^]i)} == minj/^b щ), 774)} = = min {2){p(t]i, 77.0, = rain(2){p(7?4,?y6);p(7?5,7/6),p(7/7^6),p(7/8,776)} = с/72) = mill (2){р(??5, Г)7), p(r/G, Г]7),р{щ, 777), /3(779,777)} =

722) = min (2) {^('/'/0, '/2). /0(771. П2),р(г}2, m),P(V2, V4)} =

Огмогим, нто при вычислении второго минимума из четырех чисел достаточно вычис-1ягь минимум только из двух чисел. Действительно, число, на котором достигается первый минимум, в сравнении не участвует, т.к. второй минимум больше либо равен первом>'. Из оставшихся трех чисел достаточно сравнить два близ лежащих, т.к. точки упорядочены п чем дальше точки лежат- друг от друга, тем больше расстояние между ними

Теперь легко вычислить 4 + 4 + 44-4 + 4 — 4 + 5 + 2 + 2 + 1 n „ г\' =---= 3,4.

9 10

Прежде чем переходить к третьему шаг\ а п оритма посчитаем вспомогательные суммы: 41) = г^ • 10 - ((£>) ' - (г/,п) 1 - "l = 4, 5 • 10 - 5 - 5 - 5 = 30.

42) = = Ю-3,4-4-4-4-2-4 = 16.

Третий шаг. s = {

Пусть I = 1, тогда

Третий шаг. s = 9. Удаляем = щ. Пересчитываем д^ для / = 1, 2 и j — 6 — 1,. , 6+/. ш (1).1 gl = min{р(/71. //;,), р(//5. i/o)} дР = min{/5(?77,i/-,), /7(777, %)} = го

1).1 5

Теперь можно найти г^.

-г ) -г [д7 ) 30 + 5 + 5 40

Гя1) " 9 " 9 " У'

2)

Теперь сделаем тоже самое для I = 2. Пересчитываем дк для j = 4,., 8. gf] = min {2){p(r] 4,772), р(щ. Пъ),р{щ- ф), р(щ, щ)} =

Тогда

7^2) = т1П(2){р(г)7,1]Г1),р(1];-щ),р(г17,щ),р(г]71г]9)} = = тт (2){Мг/8, 77, т),р(ш, Ла)} =

Х2) + 1 + 16 + 3 + 3 + 2 + 2.

7 о — „ — , 1),

8 9 9

Далее слюна находится г)г, которую нужно удалить из списка и действия повторяются, рассмотрение примера закончено.

Список литературы диссертационного исследования кандидат физико-математических наук Тимофеева, Нина Евгеньевна, 2010 год

1. Badii, R. Hauhdorif dimension and uniiormity factor of strange attractors // Badii R., Politi A. / Pins Rev. Lett. - 198 1. - ,Y" 52. - pp. 1661-1664.

2. Billingsley, P. Ergodio Theory and Information / Billingsley P. Wiley, New York, 1965.

3. Devroye, L Exponential meqnalties in nonparametric estimation // Devroye L., G. Roussas, editor Xonpaiamei i i ic Functional Estimation and Related Topics, NATO ASI Series. Kluwer Academic PubLshei>. Dordrecht. -1991. pp. 31-44.

4. Dobrushin. R.L. The simplified method of experimental estimatation of the entropy of stationary sequence Dobrushin R L ' Theor. Prob. Appl. 1958. - JVs 3. - pp. 462-464.

5. Grassberger, P. Estimating the information content of sybol sequences abd efficient codes

6. Giassberger P. / 1EE Trans. Inform. Theory. 1989. - 35 - pp. 669-675.

7. Kaltchenko, A., Timofeeva. N. Entropy Estimators with Almost Sure Convergence and an O(n-l) Variance // Kaltchenko A., Timofeeva N. / Advances in Mathematics of Communications. Feb. 2008. - Vol. 2, No. 1. - pp. 1-13.

8. Kaltchenko, A., Timofeeva, N., Timofeev, E. Bias Reduction of the Nearest Neighbor Entropy Estimator // Kaltchenko A., Timofeeva N., Timofeev E. / International Journal of Bifurcation and Chaos. 2008. - pp. 3781 -8787.

9. Kaltchcnko, A., Timofceva, N. Rate of convergence of the nearest neighbor entropy estimator // Kaltchenko A., Timofeeva N. ' Int. Л. Electron. Conmnm. (AEU). 2008.- V. 62, No 12.

10. Kontoyiannis, I., Suhov, Yu.M. Prefixes and the entropy rate for long-range sources // Kontoyiannis I., Suhov Yu.M. / Probability Statistics and Optimization (cd. F.P. Kelly).- Wiley, New York. 1994. - pp. 89-98.

11. Marsaglia, G. Zainan. A. A New Class of Random Number Generators // Marsaglia G., Zaman A. ' Annals of Applied Piobabilitv. 1991. - V.3, Л'а.З. - pp. 462-480.

12. McDiarmid. С On the method of bounded differences. / McDiarmid C. Surveys in Combinatorics. Cambridge Univeinity Press, Cambridge, 1989. pp. 148-188.

13. Ornstein, 13.S. Weiss. B. Entrop\ and data compression schemes // Ornstein D.S., Weiss B. / IEEE Trans. Inform. Theory. 1993. - № 39. - pp. 78-83.

14. Shields, P.O. Entropy and prefxes Shields P.C. / Annals of Probability. 1992. -20. - pp. 403-409.

15. Schurmann, Т., Grassbergcr, P. Entropy estimation of symbol sequences // Schurmann Т., Grassberger P. / Chaos. 1996. - .V* 6. - pp. 414-427.

16. Yatutin. V.A. Mikhailov, V.G. Statistical estimation of the entropy of discrete random variables with a large number of outcomes // Vatutin V.A., Mikhailov V.G. / Uspekhi Mat. Nauk. 1995. - ,\s 50. - pp. 121-134.

17. Wvner. A., Ziv, ,J. Some asymptotic properties of the entropy of a stationary ergodic data source with applications to data compression // Wyner A. Ziv J. / IEEE Trans. Inform. Theory. 1989. 35. - pp. 1250-1258.

18. Ziv. J. Lempel, A. A universal algorithm for sequential data compression // Ziv J., Lempel A. / IEEE Trans. Inform. Theory. 1977. - № 23. - pp. 337-343.

19. Ziv. J. Lempel, A. Compression of individual sequences via variable-rate coding // Ziv J. Lempel A. / IEEE Trans. Inform. Theory. 1978. - № 24. - pp. 530-536.

20. Башарин, Г.П. О статистическом оценивании энтропии последовательности независимых случайных величин. // Башарин Г.П. / Теория вероятности и ее применение.- 1959. Т. IV, Лг-°3. - с. 361-364.

21. Грапдштейп, И.С., Рыжик, И.М. Таблица интегралов, рядов и производных // Грандштейн И.С., Рыжик И.М. Академическое издеине, пятая редация, 1994.

22. Колмогоров, А.Н. Теория информации и теория алгоритмов. / Колмогоров А.Н. -М.: Наука, 1987.

23. Крамер, Г. .Математические методы статистики. / Крамер Г. М.: Мир, 1975.

24. Майоров. В.В., Тимофеев, Е.А. Статистическая оценка обобщенных размерностей // Майоров В.В., Тимофеев Е.Л 1 Мат. заметки 2002. - Т. 71. Лг» 5. - с. 679 - 712.

25. Мартин, Н. Инг. юнд, Дж. Математическая теория энтропии. / Мартин Ii., Ингленд Дж. М.:Мнр. 1988.

26. Ористейн, Д. Эргодическая теория, случайность и динамические системы. Орн-стейн Д. М.: Мир.

27. Синай, Я.Г. Современные проблемы эргодичеекой теории. / Сипай Я.Г. М.:Физ,-мат чпт., 1995.

28. Синап. Я.Г. Введение в эргодическую теорию. / Синай Я.Г. М.:ФАЗИС, 1996.

29. Тимофеев. Е.А. Состоятельная оценка энтропии мер и динамических систем. // Тимофеев Е.А. ,/ Мат. заметки 2005. - .X'- 77. - с. 903-916.

30. Тимофеев, Е.А. Статистически оцениваемые инварианты мер // Тимофеев Е.А. / Алгебра и анализ. 2005. - Т. 17. .\'о 3. - с. 204-236.

31. Тимофеева, Н.Е. Линейная метрика для оценивания энтропии. // Тимофеева Н.Е.

32. Модсл. и анализ пнформ. систем. 2009. - Т.16, №1. - с.39-48.36. 'Тимофеева, Н.Е. Эффективный алгоритм нахождения средних минимальных расстояний // Тимофеева Н.Е. / Модсл. и анализ информ. систем. 2007. - Т.14, No 3. - с.50-52.

33. Шеннон, К. Работы по теории информации и кибернетике./ Шеннон К. М.: Изд-во иностр. литерачуры, 1963.1. Глава 5