WWW.KONFERENCIYA.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА - Конференции, лекции

 

364 Труды XXXIX Молодежной школы-конференции

ОБ ЭФФЕКТИВНОСТИ ВЫЯВЛЕНИЯ МАРКОВСКОЙ

ЗАВИСИМОСТИ С ИСПОЛЬЗОВАНИЕМ

УНИВЕРСАЛЬНЫХ ПРЕДИКТОРОВ

Костевич А.Л., Шилкин А.В.

e-mail: kostevich@bsu.by

Рассмотрим задачу проверки гипотезы H0 о том, что бинарная

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

Задача проверки гипотезы о чистой случайности возникает в различных областях: криптографии [1], имитационном моделировании и др. В настоящее время известно большое число статистических критериев проверки гипотезы H0 (см., например, [1]), позволяющих выявлять некоторые альтернативы. Построение критерия проверки H0, позволяющего выявлять большое число альтернатив, в рамках традиционных подходов к тестированию бинарных последовательностей является затруднительным. Поэтому активно развивается альтернативный непараметрический подход к проверке гипотезы H на базе различных мер сложности [2]: последовательность считается чисто случайной, если она не может быть “сжата” с помощью выбранного алгоритма. В [3] предлагается строить критерий проверки гипотезы H0 на основе “предсказуемости” последовательности универсальными предикторами. Выбор данного подхода мотивирован тесной связью между универсальными предикторами, универсальными алгоритмами сжатия и теоремой A. Яо об универсальности теста предсказания следующего бита.

Для развития подхода на базе универсальных предикторов в данной статье исследуется эффективность предложенной в [3] непараметрической схемы тестирования последовательностей в случае параметрического задания альтернативы в виде цепи Маркова и использования оптимального марковского предиктора.

Пусть случайные величины X1, X2,..., (Xt A = {0, 1}) описываются стационарной цепью Маркова c матрицей вероятностей одношаговых переходов (в.о.п.) P = (pij ): pij = P {Xt+1 = j | Xt = i} и стационарным распределением q = (qi ): qi = P {Xt = i}, i, j A.

Компьютерные науки и безопасность.

Обозначим f (P, i) = arg maxjA pij максимальный элемент в i-ой строке матрицы P.

Пусть по первым t наблюдениям X1,..., Xt требуется спрогнозировать значение Xt+1. В случае известной матрицы в.о.п. P оптимальный прогноз Xt+1 определяется максимумом соответствующей условной вероятности, при этом достигается минимальная вероятность ошибочного прогноза t (Xt ) = P Xt+1 = Xt+1 | Xt,..., X1 :

Xt+1 = f (P, Xt ), t (Xt ) = 1 pXt,f (P,Xt ) 0.5. (1) Если истинная матрица в.о.п. неизвестна, то должна быть построена ее оценка P = (ij ) и прогноз строится аналогично (1) с большей p вероятностью ошибки прогноза t (Xt ):

Xt+1 = f (P, Xt ), t (Xt ) = 1 pXt,f (P,Xt ) t (Xt ). (2) Определение ([4]). Предиктор (2) называется универсальным, если t (Xt ) t (Xt ) сходится по вероятности к 0 при t.

Универсальность марковского предиктора означает, что у матриц в.о.п. P и P максимумы по всем строкам совпадают: f (P, i) = f (P, i), i A (т.е. несмещенность оценки не требуется). Тогда они делают одинаковые прогнозы и в этом смысле являются эквивалентными.

Рассмотрим следующую схему проверки гипотезы о чистой случайности H0 с использованием предиктора. Пусть наблюдается выборка X = (xm+1,..., x0, x1,..., xn ) объема n + m. Пусть по первой части выборки объема m построен предиктор (2). По второй части выборки объема n с использованием построенного предиктора в каждый момент времени t = 0,..., n 1 строится прогноз для Xt+1 и вычисляется индикатор успеха прогноза: Yt+1 = I{Xt+1 = xt+1 }.

Лемма. Индикаторы {Yt }, построенные по реализации цепи Маркова с использованием предиктора (2), являются значениями функционала от состояний цепи Маркова и 1 P {Yt = 1} = + iA qi (pi,f (P,i) 2 ), 1 ), E{Yt2 } = 2 + iA qi (pi,f (P,i) µ1 = E{Yt } = (t1) Cov{Y1, Yt } = i,jA qi pi,f (P,i) [pf (P,i),j qj ]pj,f (P,j), (t) где pij вероятность перехода из состояния i в j за t шагов.

366 Труды XXXIX Молодежной школы-конференции Таким образом, если для исходной выборки {Xt } верна гипотеза H0, то последовательность индикаторов успехов прогнозов {Yt } также будет описываться гипотезой H0. Если же выборка {Xt } описывается цепью Маркова (альтернатива H1 ) и предиктор является универсальным, то последовательность {Yt } является скрытой цепью Маркова и P {Yt = 1} > 0.5. Тогда для построения критерия проверки H0 можно использовать статистику частоты успешных прогнозов:

n H0, если 2 n S 2 <, принимается S= Yt, (3) n t= H1, иначе, где (·) функция распределения стандартного нормального распределения, = 1 (1 ), уровень значимости.

Пусть 1 = E{Y12 } E 2 {Y1 } + 2 t=2 Cov{Y1, Yt }, для цепей Марt) кова выполняется |pf (P,i),j qj | t1 с < 1, тогда при n ряд сходится, может быть легко вычислен численно и 1 < +.

Теорема 1. В случае применения универсального предиктора (2) к цепи Маркова статистика S при n имеет предельное нормальное распределение с параметрами µ1, 1 /n; критерий (3) имеет заданный уровень значимости, является состоятельным и его мощность может быть аппроксимирована:

Исследуем теперь оптимальность критерия (3). В качестве альтернативы рассмотрим важный в приложениях класс цепей Маркова с дважды стохастической матрицей в.о.п.: P = 1p 1p, p = 0.5. В этом случае цепь Маркова имеет равномерное стационарное распределение: q0 = q1 = 0.5. (Другие классы бинарных цепей Маркова имеют неравномерное стационарное распределение, и выявление таких альтернатив может быть сведено к выявлению несимметричности в испытаниях Бернулли).

Нетрудно видеть, что выбранный класс цепей Маркова с дважды стохастической матрицей в.о.п. принадлежит однопараметрическому экспоненциальному семейству, имеет монотонное отношение правдоподобия, достаточной статистикой для параметра p являn ется число “знакоперемен”: Sзп (x1,..., xn ) = t=1 I{xt = xt+1 } = n01 + n10, где nij = t=1 I{xt = i, xt+1 = j}, i, j A.

Компьютерные науки и безопасность.

В этом случае равномерно наиболее мощным критерием для проверки гипотезы H0 : p = 0.5 против односторонней альтернативы H1 : p > 0.5 (или p < 0.5) будет критерий “знакоперемен” вида Sзп [5].

Теорема 2. В случае использования (универсального для H1 ) предиктора (2) статистика S критерия (3) основана на статистике “знакоперемен”: nS = Sзп.

Из теоремы 2 можно видеть, что критерий (3) эквивалентен оптимальному критерию “знакоперемен”, статистики S = n Sзп при n имеют стандартное нормальное распределение с параметрами µ1 = 0.5 +, 1 = 1 2, = p 2 и выражения для мощности критериев совпадают.

Таким образом, критерий (3), построенный в рамках (непараметрического) подхода на базе универсальных предикторов, оказывается оптимальным для описанной выше модели.

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

Проиллюстрируем полученные теоретические результаты на численном эксперименте по оценке мощности критериев по методу Монте-Карло по разным выборкам растущего объема и m = n. На рис. приведена теоретическая мощность критериев (сплошная линия) при p = 0.4, а также оценки мощности критерия “знакоперемен” (обозначение ) и критерия (3) на базе марковского предиктора (обозначение 2). На рис. 1 также приведена оценки мощности критерия на базе предиктора Лемпеля-Зива (обозначение ), который является универсальным для цепей Маркова конечного порядка.

Из рис. 1 можно видеть, что теоретические результаты согласуются с результатами численного эксперимента. Критерий на базе предиктора Лемпеля-Зива хотя и имеет меньшую мощность (из-за его алгоритма вычисления оценок условных вероятностей), но является состоятельным, позволяет выявлять большое число альтернатив (марковскую зависимость конечного порядка), а также, в отличие от [1], обоснован и может применяться к выборкам любого объема.

368 Труды XXXIX Молодежной школы-конференции Рис. 1: Сравнение оценок мощности критериев Предлагаемый подход легко может быть обобщен на случай дискретных L-связных цепей Маркова.

Список литературы [1]. NIST Special Publication 800-22. A statistical test suite for random and pseudorandom number generators for cryptographic applications. 2001.

[2]. Ryabko B.Ya., Monarev V.A. Using information theory approach to randomness testing // J. of Statistical Planning and Inference.

2005. V. 133, № 1. P. 95-110.

[3]. Kostevich A.L., Shilkin A.V. Approach to Randomness Testing on the base of the Universal Predictors // Proc. of the 8 Int. Conf.

“Computer Data Analysis and Modeling”. 2007. V. 1, P. 256-259.

[4]. Suzuki J. Universal prediction and universal coding // Systems and Computers. 2003. V. 34, № 6, P. 1-11.

[5]. Боровков А.А. Математическая статистика. М.: Наука, Главная редакция физико-математической литературы, 1984. 472 c.



Похожие работы:

«12-ая международная конференция Балтийского форума ЕС И РОССИЯ В 2007 ГОДУ: ДОГОВАРИВАЯСЬ О НОВЫХ ОТНОШЕНИЯХ 25 – 26 мая 2007 года Maritim Park Hotel, Рига, Латвия Доклады участников Владимир Звонарев, президент Латвийского транспортного объединения (Латвия) Унификация таможенных процедур Европейского Союза и Российской Федерации, как способ ускорения оформления таможенных процедур на границе ЕС и РФ, обеспечения их прозрачности и создания основы для применения технологии передачи информации в...»

«КОНВЕНЦИЯ ООН Конвенция по дорожному движению Вена, 7 октября – 8 ноября 1968 г. Заключительный акт Конвенция по дорожному движению Конференция по дорожным знакам и указателям Заключительный акт и связанные документы Женева, 1969 Содержание Заключительный акт и связанные документы I стр. Заключительный Акт Конференции ООН по дорожному движению II Конвенция по дорожному движению Глава I. Общие положения Статья 1. - Определения Статья 2. - Дополнения к Конвенции Статья 3. - Обязательства...»

«Открытый Master-тренинг Транспортное обеспечение цепи поставок Бизнес-тренер: ВИКТОР БАРАНОВСКИЙ ведущий практик логистики в Украине Дата проведения: 18-19 мая 2012г., Киев Место проведения: Тренинговый центр TradeMaster® В. Барановский: автор 22 статей в специализированных периодических изданиях, член авторского коллектива издания Логистика от А до Я. Автор методик расчета потребности в складских мощностях и проектирования складских систем; расчета нормативов на выполнение складских операций и...»

«ОРГАНИЗАЦИЯ ОБЪЕДИНЕННЫХ НАЦИЙ Distr. РАМОЧНАЯ КОНВЕНЦИЯ GENERAL ОБ ИЗМЕНЕНИИ КЛИМАТА FCCC/SBI/2004/15 24 September 2004 RUSSIAN Original: ENGLISH ВСПОМОГАТЕЛЬНЫЙ ОРГАН ПО ОСУЩЕСТВЛЕНИЮ Двадцать первая сессия Буэнос-Айрес, 6-14 декабря 2004 года Пункт 6 предварительной повестки дня Статья 6 Конвенции Доклад о прогрессе, достигнутом в осуществлении статьи 6 Конвенции Записка секретариата Резюме Настоящий промежуточный обзор прогресса в деле осуществления Нью-Делийской программы работы по статье...»

«Уважаемые коллеги! Приглашаем принять участие в конференции с публикацией в сборнике научных трудов, Тел.: 8-800-250-20-60 ISBN, индекс научного цитирования РИНЦ conf@ucom.ru ucom.ru/conf Международная заочная научно-практическая конференция Современное общество, образование и наук а (Россия, Тамбов, 30 июня 2014 г.) Желающие принять заочное участие в конференции (с публикацией в сборнике научных трудов) должны направить до 30 июня 2014 г. в электронном виде заполненную регистрационную карту...»

«Изучение и понимание гендерных вопросов в образовании: руководство по проведению качественного исследования Изучение и понимание Гендер в образовании Руководство по проведению качественного исследования практиками образовательной сферы и специалистами по гендерным вопросам Азиатское и Тихоокеанское Региональное Образовательное Бюро ЮНЕСКО, Бангкок, Таиланд 2004 Изучение и понимание гендерных вопросов в образовании: руководство по проведению качественного исследования Предисловие Мы не можем...»

«Министерство образования и наук и Российской Федерации  Федеральное государственное бюджетное   образовательное учреждение   высшего профессионального образования  ПЕТРОЗАВОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ                  Университеты в образовательном   пространстве региона:  опыт, традиции и инновации          Материалы  VI региональной научнометодической конференции    (22–23 ноября 2012 г.)    Часть II  (Л–Я)            Петрозаводск  2012        ББК 74.584(2) УДК У Редакционная коллегия...»

«РОССИЙСКАЯ ФЕДЕРАЦИЯ (19) (11) (13) RU 2 521 209 C1 (51) МПК A61K 31/732 (2006.01) A61K 31/79 (2006.01) A61K 31/14 (2006.01) A61K 36/02 (2006.01) A61K 9/08 (2006.01) A61P 17/02 (2006.01) ФЕДЕРАЛЬНАЯ СЛУЖБА A61P 31/04 (2006.01) ПО ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ (12) ОПИСАНИЕ ИЗОБРЕТЕНИЯ К ПАТЕНТУ 2013111207/15, 14.03. (21)(22) Заявка: (72) Автор(ы): Панарин Евгений Федорович (RU), (24) Дата начала отсчета срока действия патента: Деев Игорь Анатольевич (RU), 14.03. Сантурян Юлия Галустовна (RU),...»

«Генеральная конференция GC(51)/1/Add.1 Date: 18 July 2007 General Distribution Russian Original: Arabic Пятьдесят первая очередная сессия Предварительная повестка дня Дополнительный вопрос для включения в предварительную повестку дня 1. 10 июля 2007 года Генеральный директор получил просьбу, представленную послом Султаната Оман от имени арабских государств - членов Агентства, о включении в повестку дня 51-й очередной сессии Генеральной конференции вопроса “Ядерный потенциал и ядерная угроза...»

«Леонид Юзефович ЖУРАВЛИ И КАРЛИКИ Роман ivagant.ru ОГЛАВЛЕНИЕ ГЛАВА 1. Двойник ГЛАВА 2. Побег ГЛАВА 3. На чужбине ГЛАВА 4. Снегопад ГЛАВА 5. Одноглазый и однорукий ГЛАВА 6. Другая жизнь ГЛАВА 7. Двое в саду ГЛАВА 8. Новые лица ГЛАВА 9. Дворец ГЛАВА 10. Сокровище ГЛАВА 11. Последний шанс ГЛАВА 12. Западня ГЛАВА 13. Конец пути ГЛАВА 14. Исчезновение ГЛАВА 15. Эрдене-Дзу ГЛАВА 16. Город мертвых 2 ivagant.ru ГЛАВА 1 Двойник 1 Последний отрог Хэнтейской гряды, Богдо-ул, несколькими могучими кряжами...»

«ИНФОРМАЦИЯ В. О. Г л а д ы ш е в ФИНСЛЕРОВЫ ОБОБЩЕНИЯ ТЕОРИИ ОТНОСИТЕЛЬНОСТИ: ГЛОБАЛЬНАЯ АНИЗОТРОПИЯ ВСЕЛЕННОЙ Поиски новой аксиоматики теории пространства-времени восходят к работам Евклида, Н.И. Лобачевского, К.Ф. Гаусса и могут представлять существенный академический интерес. В настоящее время эти поиски приобретают особую актуальность, что связано с появлением в конце XX и начале XXI столетий первых экспериментальных указаний на возможное отличие реального пространства–времени от метрики...»

«TD/RS/CONF/23 КОНФЕРЕНЦИЯ ОРГАНИЗАЦИИ ОБЪЕДИНЕННЫХ НАЦИЙ ПО ТОРГОВЛЕ И РАЗВИТИЮ Конвенция Организации Объединенных Наций об условиях регистрации судов. Принята КОНференцией Организации Объединенных Наций по условиям регистрации судов фев раля года 7 1 986 ОРГАНИЗАЦИЯ ОБЪЕДИНЕННЬ~ НАЦИЙ ГОД 1986 Distr. GENEru'\.L ТD/RS/СШТF/ 13 1V1arch HUSSIAN Original: нного в его регистр, считая далее, что меры, имеющие целью облегчить идеНТИфикацию и подотчетность лиц, ответственных за суда, могут...»

«1 Леса Карелии. Осень (сентябрь-ноябрь) 2005 г. Осень 2005 года в лесах Карелии, как и погода, была мягкой по факту и очень новой по сути. Висящий дамокловым мечом над лесным комплексом и лесным хозяйством России новый Лесной кодекс так и не был принят. Второе чтение перенесено на 2006 год. На это повлияла как его абсолютная нежизнеспособность, так и активные действия лесных специалистов из наук и, лесного хозяйства, бизнеса и неправительственных организаций. Только СПОК в Карелии осенью 2005...»

«Федеральное агентство морского и речного транспорта Федеральное бюджетное образовательное учреждение высшего профессионального образования Морской государственный университет им. адм. Г.И. Невельского ТРАДИЦИИ И ИННОВАЦИИ В УЧЕБНО-ВОСПИТАТЕЛЬНОМ ПРОЦЕССЕ СОВРЕМЕННОГО УНИВЕРСИТЕТА Сборник материалов двенадцатой региональной научно-практической конференции 20 мая 2011 г. Владивосток 2013 Традиции и инновации в учебно-воспитательном процессе современного университета : Сб. мат-лов 12-ой регион....»

«Предварительная Временная карта конференции 11.10 12 октября, 13 октября, 14 октября, 15 октября, 16 октября, воскр понедельник вторник среда четверг пятница 9.00 ПЛ-9 Князев 9.00 ПЛ-12 Цыбуля 9.00 ПЛ-15 Мазалов 9.00 ПЛ-18 Кочубей 9.40 ПЛ-10 Кирик 9.40 ПЛ-13 Ревенко 9.40 ПЛ-16 Мартьянов 9.40 ПЛ-19 Зайковский 10.20 ПЛ-11 Васильева 10.20 ПЛ-14 Болдырева Е. 10.20 ПЛ-17 Лапина 10.20 ПЛ-20 Титков 11.00 11.00 11.00 11. Кофе Кофе Кофе Кофе КД-1-1 Стре- КД-2-1 КД-1-2 КД-2-2 КД-3-1 КД-4-1 КД-5- 11.20...»

«Конференции и выставки СЕМИНАРСКАЯ ДЕЯТЕЛЬНОСТЬ В 2012 в Институте проводили семинары: общеинститутский, по геологии нефти и газа, палеонтологии и стратиграфии, геофизический, по геоэлектрике и аспирантский. Общеинститутский семинар 27 сентября 2012 г. Закономерности образования нефти из морской воды в недрах земной коры и ее количество. Докладчик: Черных Н.Г. Председатель совета директоров ОАО Консорциум КУЗБАССПОДЗЕММАШСТРОЙ, г. Новокузнецк. 21 декабря 2012 г. Картирование свойств...»

«R CDIP/4/14 ОРИГИНАЛ: АНГЛИЙСКИЙ ДАТА: 22 ИЮНЯ 2010 Г. Комитет по развитию и интеллектуальной собственности (КРИС) Четвертая сессия Женева, 16 – 20 ноября 2009 г. ОТЧЕТ принят Комитетом 1. Четвертая сессия была проведена с 16 по 20 ноября 2009 г. 2. На сессии были представлены следующие государства: Алжир, Аргентина, Австралия, Австрия, Бангладеш, Барбадос, Беларусь, Бельгия, Боливия (Многонациональное государство), Бразилия, Болгария, Буркина Фасо, Бурунди, Канада, Чили, Китай, Колумбия,...»

«DAILY MONITOR 9 июля 2014 г. НОВОСТИ ИНДИКАТОРЫ Значение Изменение -0,41% 34,4258 Азиатские импортеры зерна воздерживаются Курс $, ЦБ РФ -0,28% от закупок, ожидая дальнейшего снижения 46, Курс €, ЦБ РФ мировых цен -0,12% 2, Курс UAH, ЦБ РФ Reuters -0,61% 11, Курс $/UAH, межбанк -0,58% 15, Курс €/UAH, НБУ Экспорт российской пшеницы нового урожая +0,18% 1, Курс $/€ при действующей мировой цене пока +0,37% 70, рентабелен при условии возврата НДС DJ-UBS Agro -0,17% Интерфакс 52, DJ-UBS Grains...»

«ПОЛЕВЫЕ ПРАКТИКИ В СИСТЕМЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ IV МЕЖДУНАРОДНАЯ КОНФЕРЕНЦИЯ Симферополь 2012 С А Н К Т -П Е Т Е РБУ РГ С К И Й Г О С У Д А РС Т В ЕН Н Ы Й У Н И В ЕРС И ТЕТ 80 лет геологическому факультету СЛбГУ 60 лет Крымской учебной практике Памяти В. А. Прозоровского ПОЛЕВЫЕ ПРАКТИКИ В СИСТЕМЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ IV МЕЖДУНАРОДНАЯ КОНФЕРЕНЦИЯ Тезисы докладов Крым, с. Трудолюбовка, 29 июля - 6 августа 2012 г. С им ф ерополь Д И А Й П И У ДК 551. П...»

«131 Электронное научное издание Устойчивое инновационное развитие: проектирование и управление том 7 № 3 (12), 2011, ст. 6 www.rypravlenie.ru Выпуск подготовлен по итогам Международной конференции по фундаментальным проблемам устойчивого развития в системе природа – общество – человек (24 и 25 октября 2011 г., проект РФФИ №11-06-06128-г). УДК 331.21 УПРАВЛЕНИЕ ПРОИЗВОДСТВЕННЫМ ПРОЦЕССОМ НА ОСНОВЕ ТЕОРИИ УСТОЙЧИВОГО РАЗВИТИЯ И ПРИНЦИПА ДЕЛОКРАТИИ Александр Иванович Протопопов, старший...»









 
2014 www.konferenciya.seluk.ru - «Бесплатная электронная библиотека - Конференции, лекции»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.