• Українська
  • English
  • Русский
ISSN 1028-821X (Online)
ISSN 2415-3400 (Print)

СИМВОЛЬНЫЕ ЦЕПИ МАРКОВА С МУЛЬТИЛИНЕЙНОЙ ФУНКЦИЕЙ ПАМЯТИ

Мельник, СС, Усатенко, ОВ
Organization: 

Институт радиофизики и электроники им. А. Я. Усикова НАН Украины
12, ул. Ак. Проскуры, Харьков, 61085, Украина
E-mail: olegusatenko@mail.ru

https://doi.org/10.15407/rej2015.03.079
Язык: русский
Аннотация: 

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

Ключевые слова: корреляционные функции, случайные последовательности, функция условной вероятности, цепи Маркова высших порядков

Статья поступила  09.07.2015 г.
PACS     05.40.-a; 07.05.Mh; 87.10.-e
УДК 535.421+519.2
Radiofiz. elektron. 2015, 20(3): 79-89
Полный текст (PDF)
 

References: 
  1. Амитей Н. Теория и анализ фазированных антенных решеток / Н. Амитей, В. Галиндо, Ч. Ву; пер. с англ. под ред. А. Ф. Чаплина. – М.: Мир, 1974. – 455 с.
  2. Izrailev F. M. Anomalous localization in low-dimensional systems with correlated disorder / F. M. Izrailev, A. A. Krokhin, N. M. Makarov // Phys. Rep. – 2012. – 512, Iss. 3. – P. 125–254.
  3. Лукин К. А. Получение изображений с помощью неподвижной антенной решетки, шумовых сигналов и метода синтезирования апертуры / К. А. Лукин, А. А. Могила, П. Л. Выплавин // Радиофизика и электрон.: сб. науч. тр. / 12, № 3. – С. 526–531.
  4. Mandelbrot B. B. A Fast Fractional Gaussian Noise Generator / B. B. Mandelbrot, J. R. Wallis // Water Resour. Res. – 1971. –7, Iss. 3. – P. 543–553.
  5. Voss R. F. Fundamental Algorithms in Computer Graphics / R. F. Voss – Berlin: Springer, 1985. –805 p.
  6. Shlesinger M. F. Strange kinetics / M. F. Shlesinger, G. M. Zaslavsky, J. Klafter // Nature. – 1993. – 363, N 6424. – P. 31–37.
  7. Li W. Spatial 1/f Spectra in Open Dynamical Systems / W. Li // Europhys. Lett. – 1989. – 10. – P. 395–400.
  8. Rice S. O. Mathematical analysis of random noise / S. O. Rice // Bell Syst. Tech. J. – 1944. – 23. – P. 282–332.
  9. Wax N. Selected Papers on Noise and Stochastic Processes / N. Wax – N. Y.: Dover, 1953. – 343 p.
  10. Saupe D. The Science of Fractal Images / D. Saupe. – N. Y.: Springer, 1988. – 312 p.
  11. West C. S. Observations of backscattering enhancement from polaritons on a rough metal surface / C. S. West, K. A. O'Donnell // J. Opt. Soc. Am. A. – 1995. – 12, N 2. – P. 390–397.
  12. Izrailev F. M. Localization and the Mobility Edge in One-Dimensional Potentials with Correlated Disorder / F. M. Izrailev, A. A. Krokhin // Phys. Rev. Lett. – 1999. – 82, N 20. – P. 4062–4065.
  13. Izrailev F. M. Anomalous transport in low-dimensional systems with correlated disorder / F. M. Izrailev, N. M. Makarov // J. Phys. A: Math. Gen. – 2005. – 38, N 49. – P. 10613–10637.
  14. Cakir R. Dynamical origin of memory and renewal / R. Cakir, P. Grigolini, A. A. Krokhin // Phys. Rev. E. – 2006. – 74, Iss. 2. – P. 021108(6 p.).
  15. Romero A. Generation of short and long range temporal correlated noises / A. Romero, J. Sancho // J. Computational Phys. – 1999. – 156, Iss. 1. – P. 1–11.
  16. Correlations in binary sequences and a generalized Zipf analy sis / A. Czirok, R. N. Mantegna, S. Havlin, H. E. Stanley // Phys. Rev. E. – 1995. – 52, Iss. 1. – P. 446–452.
  17. Method for generating long range correlations for large systems / H. A. Makse, S. Havlin, M. Schwartz, H. E. Stanley // Phys. Rev. E. – 1996. – 53, Iss. 5. – P. 5445–5449.
  18. Izrailev F. M. Generation of correlated binary sequences from white noise / F. M. Izrailev, A. A. Krokhin, N. M. Makarov, O. V. Usatenko // Phys. Rev. E. – 2007. – 76, Iss. 2. – P. 027701(4 p.).
  19. Izrailev F. M. Anomalous localization in low-dimensional systems with correlated disorder / F. M. Izrailev, A. A. Krokhin, N. M. Makarov // Phys. Rep. – 2012. – 512, Iss. 3. – P. 125–254.
  20. Random Finite-Valued Dynamical Systems: Additive Markov Chain Approach / O. V. Usatenko, S. S. Apostolov, Z. A. Mayzelis, S. S. Melnik. – Cambridge: Cambridge Scientific Publ., 2010. – 176 p.
  21. Raftery A. A model for high-order Markov chains / A. Raftery // J. R. Stat. Soc. B. – 1985. – 47, N 3. – P. 528–539.
  22. Ching W. K. Higher‐order Markov chain models for categorical data sequences / W. K. Ching, E. S. Fung, M. K. Ng //  Naval Res. Logist. – 2004. – 51, N 4. – P. 557–574.
  23. Li W. K. Some results on high order Markov chain models / W. K. Li, M. C. O. Kwok // Comun. Stat. Simul. Comput. – 1990. – 19. – P. 363–380.
  24. Bacterial genomes lacking long-range correlations may not be modeled by low-order Markov chains: the role of mixing statistics and frame shift of neighboring genes / J. Cocho, P. Miramontes, R. Mansilla, W. Li // Comput. Biol. Chem. – 2014. – 53, pt. A. – P. 15–25.
  25. Parsimonious Higher-Order Hidden Markov Models for Improved Array-CGH Analysis with Applications to Arabidopsis thaliana / M. Seifert, A. Gohr, M. Strickert, I. Grosse // PLoS Computat. Biol. – 2012. – 8, Iss. 1. – P. e1002286.
  26. Competition of Two Types of Correlations / S. S. Melnyk, O. V. Usatenko, V. A. Yampol'skii, V. A. Golick // Phys. Rev. E. – 2005. – 72, Iss. 2. – P. 026140(7 p.).
  27. Usatenko O. V. Binary N-Step Markov Chains and Long-Range Correlated Systems / O. V. Usatenko, V. A. Yampol'skii // Phys. Rev. Lett. – 2003. – 90, Iss. 11. – P. 110601(4 p.).
  28. Shiryaev A. N. Probability / A. N. Shiryaev. – N. Y.: Springer, 1996. – 624 p.
  29. Melnik S. S. Entropy and long-range correlations in DNA sequences / S. S. Melnik, O. V. Usatenko // Computational Biology and Chemistry – 2014. – 53, pt. A. – P. 26–31.
  30. Melnik S. S. Entropy of finite random binary sequences with weak long-range correlations / S. S. Melnik, O. V. Usatenko // Pys. Rev. E – 2014. – 90, Iss. 5. – P. 052106(8 p.).
  31. Melnyk S. S. Memory functions of the additive Markov chains: applications to complex dynamic systems / S. S. Melnyk, O. V. Usatenko, V. A. Yampol'skii // Physica A. – 2006. – 361, Iss. 2. – P. 405–415.
  32. High Order Correlation Functions of Binary Multi-Step Markov Chains / S. S. Apostolov, Z. A. Mayzelis, O. V. Usatenko, V. A. Yampol'skii // Int. J. Mod. Phys. B. – 2008. – 22, N 22. – P. 3841–3853.
  33. Hosseinia R. A Characterization of Categorical Markov Chains / R. Hosseinia, N. Leb, J. Zideka // Journal of Statistical Theory and Practice – 2011. Vol. 5, I. 2, – P. 261–284.
  34. Besag J. Spatial interactions and the statistical analysis of lattice systems / J. Besag // J. Royal Statistical Soc. B. – 1974. – 36, N 2. – P. 192–225.