Результаты экспериментов
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ФАКУЛЬТЕТ ПРИКЛАДНОЙ МАТЕМАТИКИ И ИНФОРМАТИКИ Кафедра математического моделирования и анализа данных
ЦЕПЬ МАРКОВА С ЧАСТИЧНЫМИ СВЯЗЯМИ И ПЕРЕМЕННЫМ ШАБЛОНОМ Курсовая работа
Батуры Олега Владимировича
студента 3 курса, специальность «Компьютерная безопасность»
Научный руководитель: доктор физ.-мат. наук, заведующий кафедрой ММАД
Ю. С. Харин
Минск, 2015 БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ФАКУЛЬТЕТ ПРИКЛАДНОЙ математики и информатики Кафедра математического моделирования и анализа данных
ЗАДАНИЕ НА КУРСОВУЮ РАБОТУ Студент Батура Олег Владимирович, 3 курс, 9 группа
1. Тема работы Цепь Маркова с частичными связями и переменным шаблоном
2. Срок сдачи студентом законченной работы________ 2015 г. 3. Перечень вопросов, подлежащих разработке · Исследовать вероятностные характеристики модели цепи Маркова с частичными связями и переменным шаблоном. Найти -мерное распределение вероятностей . · Построить компьютерную модель ЦМ с переменным шаблоном. · Построить статистические оценки параметров модели при известной функции шаблона , исследовать свойства оценок. · Построить оценки параметров модели при периодически изменяющемся, но неизвестном шаблоне.
Руководитель курсовой работы______________ / Ю. С. Харин/ ______ 2015 г.
Задание принял к исполнению_______________ 2015 г. ОГЛАВЛЕНИЕ Введение. 4 1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ. 5 1.1. Цепь Маркова порядка . 5 1.2.Цепь Маркова с частичными связями ЦМ . 7 1.3.Цепь Маркова с частичными связями и переменным шаблоном ЦМ 9 1.4.Статистическое оценивание параметров ЦМ , состоятельность оценок 11 1.5.Статистическое оценивание параметров ЦМ . 15 2.ПРАКТИЧЕСКАЯ ЧАСТЬ. 16 2.1.Описание программы.. 16 2.2.Моделирование временного ряда длительности . 17 2.3.Построение оценок максимального правдоподобия и . 18 2.4.Результаты экспериментов. 21 2.5.Вывод. 23 Заключение. 24 Список использованной литературы.. 25 Введение При математическом моделировании сложных систем и процессов в различных научных сферах часто возникает необходимость построения вероятностно-статистических моделей дискретных временных рядов , где пространство состояний — конечное множество мощности с длинной памятью [1]. Известной моделью таких дискретных временных рядов является цепь Маркова достаточно высокого порядка , определяющего длину памяти; если , то цепь Маркова называется простой, если — сложной. Однако для такой модели число параметров растет экспоненциально при увеличении порядка : , и для статистического оценивания параметров требуется иметь реализацию не всегда доступной на практике длительности . В связи с этим актуальна проблема построения малопараметрических моделей цепей Маркова высокого порядка. В данной работе исследуется малопараметрическая модель цепи Маркова порядка с частичными связями ЦМ , рассмотренная в [2], для которой шаблон связей зависит от времени, исследуются ее вероятностные характеристики, строятся статистические оценки параметров при известной функции шаблона, а также при периодически изменяющемся, но неизвестном шаблоне.
ТЕОРЕТИЧЕСКАЯ ЧАСТЬ 1.1. Цепь Маркова порядка В криптологии для моделирования дискретных временных рядов с глубиной памяти используется цепь Маркова порядка (ЦМ ), обобщающая модель простой цепи Маркова [3]. Определение.Цепь Маркова , порядка с пространством состояний , определенная на вероятностном пространстве ( ) и временной области , характеризуется обобщенным марковским свойством:
Это означает, что условное распределение вероятностей будущих состояний при фиксированной предыстории зависит не от всей этой предыстории, а от ближайшей на глубину предыстории Цепь Маркова ЦМ( ) характеризуется -мерным начальным распределением вероятностей
и -мерной матрицей вероятностей одношаговых переходов в момент времени :
=
Матрица при этом удовлетворяет условиям нормировки (если она не зависит от времени, то есть , ЦМ( ) в таком случае называется однородной):
В таком случае -мерное распределение вероятностей имеет вид:
Число независимых параметров, определяющих матрицу вероятностей одношаговых переходов для однородной ЦМ( ), равно . При увеличении глубины памяти число параметров экспоненциально возрастает, и для идентификации такой модели требуется наблюдать реализацию не всегда доступной на практике длительности . Возникает задача поиска малопараметрической модели цепи Маркова высокого порядка, для которой число параметров в матрице задается числом параметров . Одной из таких моделей является цепь Маркова порядка с частичными связями (ЦМ ) [2].
1.2. Цепь Маркова с частичными связями ЦМ Пусть – однородная ЦМ( ), заданная на вероятностном пространстве ( ) с некоторой ( )-мерной матрицей вероятностных переходов Рассмотрим – параметр, который называется числом связей; – произвольный целочисленный -вектор с упорядоченными компонентами:
Этот вектор называется шаблоном связей, – множество всевозможных таких векторов с компонентами, мощность – некоторая -мерная стохастическая матрица. Определение.Цепь Маркова называется цепью Маркова -го порядка с -частичными связями и обозначается ЦМ( ), если ее вероятности одношаговых переходов имеют вид:
Это означает, что вероятность перехода процесса в состояние в момент времени зависит не от всех значений предыдущих состояний процесса, а лишь от некоторых избранных состояний . В данном случае, вместо параметров ЦМ( ) данная модель полностью определяется параметрами , что играет существенную роль на практике. Замечание.Если , , то и ЦМ( ) представляет из себя цепь Маркова порядка , то есть ЦМ( ЦМ . В дальнейшем будем рассматривать однородную цепь Маркова с частичными связями. Следует отметить, что -мерное распределение вероятностей для данной модели имеет следующий вид:
Возникает проблема исследования свойств такой модели цепи Маркова, в которой шаблон зависел бы от какой-либо функции. Данное свойство помогло бы сделать распознавание шаблона для злоумышленника более проблематичным, что сыграло бы важную роль в криптостойкости модели.
1.3. Цепь Маркова с частичными связями и переменным шаблоном ЦМ Пусть – однородная ЦМ( ), заданная на вероятностном пространстве ( ), определенная ранее. Рассмотрим обобщение данной модели, когда шаблон зависит от времени :
причем:
В общем случае шаблон зависит от некоторой функции, определяющей его изменение. Простейшая модель такой зависимости – периодическая функция с некоторым периодом :
.
В частности, при имеются два различных шаблона и которые циклично повторяются:
Для данного частного случая -мерное распределение вероятностей имеет вид:
При произвольной модели зависимости шаблона от времени имеем общую формулу:
Использование такой модели цепи Маркова позволяет сделать выборку для злоумышленника как можно более случайной, что сильно влияет на криптостойкость модели, так как появляются сложности с распознаванием зависимости и поиском используемого шаблона. Полезно исследование такой модели ЦМ , в которой шаблон периодически изменяется, но неизвестен. Далее рассмотрим задачу статистической оценки параметров модели ЦМ при известном шаблоне и поиска свойств оценок.
1.4. Статистическое оценивание параметров ЦМ , состоятельность оценок Для статистического оценивания параметров ЦМ( ) будем пользоваться методом максимального правдоподобия. Рассмотрим задачу построения оценок максимального правдоподобия (ОМП) для параметров шаблона и стохастической матрицы по наблюдаемой реализации длительности . Введем обозначения, пусть – мультииндекс -го порядка; – функция, которую назовем селектором -го порядка с параметрами и – индикатор события ; – начальное -мерное распределение вероятностей ЦМ ;
– частота -граммы для шаблона , удовлетворяющая условию нормировки:
Для модели ЦМ логарифмическая функция правдоподобия имеет вид:
Для того, чтобы найти ОМП для матрицы , необходимо решить задачу на условный экстремум:
В результате получаем условную ОМП для матрицы ( ):
Далее рассматривается задачу поиска ОМП для шаблона . Пусть – стационарное распределение вероятностей ЦМ . Пусть ЦМ – стационарна ( ), тогда распределение вероятностей -граммы для шаблона будет иметь следующий вид:
Соответствующая частотная оценка вероятностей:
.
Энтропия -мерного распределения вероятностей запишется в виде:
Количество информации по Шеннону, содержащейся в -грамме о будущем символе :
Логарифмическая функция правдоподобия для оценки имеет следующий вид:
где – подстановочная оценка энтропии, получающаяся при подстановке вместо истинных значений их оценок { }. Учитывая, что не зависит от , добавляя также не зависящее от слагаемое , а также используя тот факт, что:
приходим к следующей ОМП шаблона :
где – подстановочная оценка количества информации по Шеннону, получающаяся при подстановке вместо истинных значений их оценок { }. Теорема 1.Если ЦМ является стационарной, то при истинном шаблоне и оценка состоятельна:
Теорема 2.Если ЦМ является стационарной и шаблон идентифицируемый, то при оценка состоятельна:
1.5. Статистическое оценивание параметров ЦМ Для ЦМ оценки параметров генератора с переменной обратной связью строятся аналогично модели с постоянной обратной связью с учетом периодически изменяющегося шаблона . Логарифмическая функция правдоподобия имеет следующий вид:
Задача на условный экстремум
решается в общем виде, и это позволяет решить частную задачу оценки параметров генератора с переменной обратной связью. Теорема 3.Если ЦМ является стационарной, то при истинном шаблоне и оценка состоятельна:
Теорема 4.Если ЦМ является стационарной и шаблон идентифицируемый, то при оценка состоятельна:
ПРАКТИЧЕСКАЯ ЧАСТЬ Описание программы Построена компьютерная модель цепи Маркова с частичными связями и переменным шаблоном со следующими входными параметрами: · глубина предыстории однородной цепи Маркова ЦМ . · длина временного ряда с пространством состояний . · Шаблоны и , которые повторяются с периодом
· Стохастическая матрица вероятностей одношаговых переходов для шаблонов:
В частном случае, при данная матрица имеет следующий вид:
Реализовано моделирование цепи Маркова с частичными связями и переменным шаблоном, нахождение оценок максимального правдоподобия матрицы вероятностей одношаговых переходов и переменного шаблона смоделированного временного ряда. Далее более подробно рассматривается алгоритм работы программы.
2.2. Моделирование временного ряда длительности Случайным образом выбираются первые элементов последовательности. Для моделирования элементов с нечетными номерами выбирается шаблон . Рассматривается -предыстория элемента. Распределениями вероятностей исхода для данных элементов являются строки матрицы , соответствующие состояниям предыдущих элементов
В частности, если предыстория элемента имеет вид
, то при
Элементы с четными номерами моделируются аналогичным образом с использованием шаблона На каждом шаге моделирование происходит с помощью генератора псевдослучайных чисел, работающего по следующему алгоритму: 1. Генерируется число в диапазоне . 2. В результате имеется временной ряд , где пространство состояний – конечное множество мощности .
2.3. Построение оценок максимального правдоподобия и Логарифмическая функция правдоподобия имеет вид:
Задача на условный экстремум:
Поиск условной оценки максимального правдоподобия матрицы одношаговых переходов ищется путем приравнивания к нулю компонент градиента логарифмической функции правдоподобия:
Используя тот факт, что матрица стохастическая, , условная оценка полностью определяется шаблоном Для вычисления оценки шаблона при известном истинном значении числа связей можно воспользоваться алгоритмом полного перебора значений логарифмической функции правдоподобия. В частности, при имеется следующая система уравнений:
где частота выпадения при предыстории . Условной оценкой максимального правдоподобия является решение данной системы:
.
Логарифмическая функция правдоподобия перепишется в следующей форме:
Оценка максимального правдоподобия ищется путем перебора вариантов шаблонов. Производится подсчет частот при всевозможных вариантах пар шаблонов и выбирается та пара, которая максимизирует логарифмическую функцию правдоподобия. Таким образом:
Оценка максимального правдоподобия матрицы имеет вид:
Результаты экспериментов Экспериментальные оценки параметров построены при следующих входных данных:
Рис. 1.Зависимость числа ошибок распознавания истинного шаблона при 100 экспериментах от При :
При :
При :
При :
Вывод Результаты показывают состоятельность оценки при истинном шаблоне и . Также очевидна состоятельность оценки шаблона при . Таким образом, для более точного распознавания матрицы одношаговых переходов и шаблона требуется наблюдать реализацию как можно большей длительности .
Заключение В данной работе исследованы вероятностные характеристики модели цепи Маркова с частичными связями и переменным шаблоном, реализована компьютерная модель ЦМ с переменным шаблоном. Построены статистические оценки параметров модели при известной функции шаблона , периодически изменяющемся, но неизвестном шаблоне. Исследована состоятельность данных оценок. Результаты экспериментов показали, что для более точного распознавания матрицы одношаговых переходов и шаблона требуется наблюдать реализацию как можно большей длительности .
Список использованной литературы 1. Алферов А. П. и др. Основы криптографии / Алферов А. П., Зубов А. Ю., Кузьмин А. С., Черемушкин А. В. – 2-е изд., испр. и доп. – М.: Гелиос АРВ, 2002. – 480 с. 2. Харин Ю. С., Петлицкий А. И. Цепь Маркова -го порядка с частичными связями и их статистическое оценивание – Дискретная математика, 2007. – Т. 12, вып. 2. С. 109-130. 3. Харин Ю. С. и др. Криптология / Харин Ю. С., Агиевич С. В., Васильев Д. В., Матвеев Г. В. – Мн.: БГУ, 2013. – 511 с.
Популярное: Организация как механизм и форма жизни коллектива: Организация не сможет достичь поставленных целей без соответствующей внутренней... Личность ребенка как объект и субъект в образовательной технологии: В настоящее время в России идет становление новой системы образования, ориентированного на вхождение... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (330)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |