Представление множеств стохастических матриц с заданными свойствами на основе автономных автоматных моделей

В.М. Захаров, С.В. Шалагин, Б.Ф. Эминов
Казанский национальный исследовательский технический университет им. А.Н. Туполева – КАИ, г. Казань, 420111, Россия
Полный текст PDF
DOI: 10.26907/2541-7746.2019.3.456-467

Для цитирования: Захаров В.М., Шалагин С.В., Эминов Б.Ф. Представление множеств стохастических матриц с заданными свойствами на основе автономных автоматных моделей // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. – 2019. – Т. 161, кн. 3. – С. 456–467. – doi: 10.26907/2541-7746.2019.3.456-467.

For citation: Zakharov V.M., Shalagin S.V., Eminov B.F. Representation of the stochastic matrix sets with given properties based on autonomous automatic models. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2019, vol. 161, no. 3, pp. 456–467. doi: 10.26907/2541-7746.2019.3.456-467. (In Russian)

Аннотация

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

Ключевые слова: множество стохастических матриц, структура, предельный вектор, автономные автоматные модели, оценки мощности множеств

Благодарности. Работа выполнена при финансовой поддержке РФФИ (проект № 18-01-00120).

Литература

1. Katehakis M., Smit L. A successive lumping procedure for a class of Markov chains // Probab. Eng. Inf. Sci. – 2012. – V. 26, No 4. – P. 483–508. – doi: 10.1017/S0269964812000150.

2. Деундяк В.М., Жданова М.А. Полиномиальное представление скрытой полумарковской модели фергюсоновского типа // Вестн. ВГУ: Системный анализ и информационные технологии. – 2013. – № 2. – С. 71–78.

3. Погорелов Б.А., Пудовкина М.А. Об обобщениях марковского подхода при изучении алгоритмов блочного шифрования // Прикл. дискр. матем. Приложение. – 2014. – № 7. – С. 51–52.

4. Geiger B., Temmel C. Lumpings of Markov chains, entropy rate preservation, and higher-order lumpability // Adv. Appl. Probab. – 2014. – V. 51, No 4. – P. 1114–1132. – doi: 10.1239/jap/1421763331.

5. Raikhlin V.A., Vershinin I.S., Gibadullin R.F., Pystogov S.V. Reliable recognition of masked cartographic scenes during transmission over the network // 2016 Int. Sib. Conf. on Control and Communications (SIBCON). – IEEE, 2016. – P. 1–5. – doi: 10.1109/SIBCON.2016.7491657.

6. Бухараев Р.Г. Основы теории вероятностных автоматов. – М.: Наука, 1985. – 287 с.

7. Левин Б.Р., Шварц В. Вероятностные модели и методы в системах связи и управления. – М.: Радио и связь, 1985. – 312 с.

8. Глова В.И., Захаров В.М., Песошин В.А., Шалагин С.В. Моделирование. Вероятностные дискретные модели / Под ред. В.М. Захарова. – Казань: АБАК, 1998. – 52 с.

9. Захаров В.М., Нурмеев Н.Н., Салимов Ф.И., Шалагин С.В. Классификация стохастических эргодических матриц методами кластерного и дискриминантного анализа // Исследования по информатике. – Казань: Отечество, 2000. – С. 91–106.

10. Нурутдинова А.Р., Шалагин С.В. Многопараметрическая классификация автоматных марковских маделей на основе генерируемых ими последовательностей состояний // Прикл. дискр. матем.. – 2010. – № 4. – С. 41–54.

11. Боровиков В.П. Statistica: искусство анализа данных на компьютере. – СПб.: Питер, 2003. – 700 с.

12. Кемени Дж., Снелл Дж. Конечные цепи Маркова. – М.: Наука, 1970. – 272 с.

13. Zakharov V.M., Eminov B.F., Shalagin S.V. Representing lumped Markov chains by minimal polynomials over field GF(q) // J. Phys.: Conf. Ser. – 2018. – V. 1015. – Art. 032033, P. 1–6. – doi: 10.1088/1742-6596/1015/3/032033.

14. Бухараев Р.Г., Захаров В.М. Управляемые генераторы случайных кодов. – Казань: Казан. гос. ун-т, 1978. – 160 с.

15. Ченцов В.М. Об одном методе синтеза автономного стохастического автомата // Кибернетика. – 1968. – № 3. – С. 32–35.

16. Эминов Б.Ф., Захаров В.М. Анализ алгоритмов разложения двоично-рациональных стохастических матриц на комбинацию булевых матриц // Информационные технологии. – 2008. – № 3. – С. 54–59.

17. Бронштейн И.Н, Семендяев К.А. Справочник по математике для инженеров и учащихся втузов. – М.: Наука, 1986. – 544 с.

18. Столов Е.Л. Об одном классе генераторов псевдомарковских цепей // Исследования по прикл. матем. – Казань: Изд-во Казан. ун-та, 1980. – Вып. 8. – С. 66–71.

19. Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии. – М.: Гелиос АРВ, 2002. – 480 с.

20. Сарвате Д.В., Персли М.Б.  Взаимно-корреляционные свойства псевдослучайных и родственных последовательностей // Труды Ин-та инженеров по электротехнике и радиоэлектронике. – 1980. – Т. 68, № 5. – С. 59–90.

21. Нечаев В.И. Элементы криптографии. Основы теории защиты информации. – М.: Высш. шк., 1999. – 109 с.

22. Латыпов Р.Х. Математические основы кодирования информации и криптографии. – Казань: Казан. гос. ун-т, 2005. – 60 с.

Поступила в редакцию

28.05.19

Захаров Вячеслав Михайлович, доктор технических наук, профессор кафедры компьютерных систем

Казанский национальный исследовательский технический университет им. А.Н. Туполева – КАИ

ул. К. Маркса, д. 10, г. Казань, 420111, Россия

E-mail:  gilvv@mail.ru

Шалагин Сергей Викторович, доктор технических наук, профессор кафедры компьютерных систем

Казанский национальный исследовательский технический университет им. А.Н. Туполева – КАИ

ул. К. Маркса, д. 10, г. Казань, 420111, Россия

E-mail:  sshalagin@mail.ru

Эминов Булат Фаридович, кандидат физико-математических наук, доцент кафедры компьютерных систем

Казанский национальный исследовательский технический университет им. А.Н. Туполева – КАИ

ул. К. Маркса, д. 10, г. Казань, 420111, Россия

E-mail:  bulfami@mail.ru

Контент доступен под лицензией Creative Commons Attribution 4.0 License.