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

SYMBOLIC MARKOV CHAINS WITH MULTILINEAR MEMORY FUNCTION

Melnyk, SS, Usatenko, OV
Organization: 

O. Ya. Usikov Institute for Radiophysics and Electronics of the National Academy of Sciences of Ukraine
12, Proskura st., Kharkov, 61085, Ukraine
E-mail: olegusatenko@mail.ru

https://doi.org/10.15407/rej2015.03.079
Language: russian
Abstract: 

The problem of designing various radio devices, such as filters, delay lines, random antennas with a given radiation pattern and so on, requires the development of methods for constructing random sequences of the parameters of these systems having specified correlation properties. An adequate mathematical approach for solving such problems is the Markov chains of higher orders. Statistical characteristics of these objects are completely determined by their conditional probability function that, in general, can be very complicated. The purpose of this paper is to present the decomposition procedure for the conditional probability function of random sequences with long-range correlationtions in a form convenient for their numerical generation. Here we restrict ourselves to the case of the state space of the system of such kind, when random values of its elements belong to the finite abstract set. The developed theory opens the way to build a more consistent and nuanced approach for the description of systems with long-range correlations. In the limiting case of weak (by value, but not the distance) correlations memory function is uniquely expressed in terms of higher-order correlation functions, allowing us to generate a random sequence with a given long-range correlations. As an example of the analytical results obtained, which can be used in practical applications, we present an example of the numerical realization of the method of construction of random sequence with specified correlators of the second and third orders.

Keywords: correlation functions, random sequences, the function of conditional probability, the high order Markov chains

Manuscript submitted  09.07.2015 г.
PACS     05.40.-a; 07.05.Mh; 87.10.-e
Radiofiz. elektron. 2015, 20(3): 79-89
Full text  (PDF)

References: 
  1. Amitay, N., Galindo, V. and Wu, Ch., 1974. Theory and Analysis of Phased Array Antennas. Translated from English and ed. by A. F. Chaplin. Moscow: Mir Publ.
  2. Izrailev F. M., Krokhin, A. A. and Makarov, N. M., 2012. Anomalous localization in low-dimensional systems with correlated disorder. Phys. Rep. 512(3), pp. 125–254..DOI: https://doi.org/10.1016/j.physrep.2011.11.002
  3. Lukin, K. A., Mogila, A. A. and Vyplavin, P. L., 2007. Imaging by means of an immobile antenna array, noise signals and SAR method. In: V. M. Yakovenko, ed. 2007. Radiofizika i elektronika. Kharkov: IRE NAS of Ukraine Publ. 12(3), pp. 526–531.
  4. Mandelbrot, B. B. and Wallis, J. R., 1971. A Fast Fractional Gaussian Noise Generator. Water Resour. Res. 7(3), pp. 543–553..DOI: https://doi.org/10.1029/WR007i003p00543
  5. Voss, R. F., 1985. Fundamental Algorithms in Computer Graphics. Berlin: Springer.
  6. Shlesinger, M. F., Zaslavsky, G. M. and Klafter, J., 1993. Strange kinetics. Nature, 363(6424), pp. 31–37..DOI: https://doi.org/10.1038/363031a0
  7. Li, W., 1989. Spatial 1/f Spectra in Open Dynamical Systems. Europhys. Lett., 10, pp. 395–400..DOI: https://doi.org/10.1209/0295-5075/10/5/001
  8. Rice, S. O., 1944. Mathematical analysis of random noise. Bell Syst. Tech. J., 23(3), pp. 282–332..DOI: https://doi.org/10.1002/j.1538-7305.1944.tb00874.x
  9. Wax, N., 1953. Selected Papers on Noise and Stochastic Processes. N. Y.: Dover Phoenix Ed.
  10. Saupe, D., 1988. The Science of Fractal Images. N. Y.: Springer-Verlag New York, Inc.
  11. West, C. S. and O'Donnell, K. A., 1995. Observations of backscattering enhancement from polaritons on a rough metal surface. J. Opt. Soc. Am. A, 12(2), pp. 390–397..DOI: https://doi.org/10.1364/JOSAA.12.000390
  12. Izrailev, F. M. and Krokhin, A. A., 1999. Localization and the Mobility Edge in One-Dimensional Potentials with Correlated Disorder. Phys. Rev. Lett., 82(20), pp. 4062–4065..DOI: https://doi.org/10.1103/PhysRevLett.82.4062
  13. Izrailev, F. M. and Makarov, N. M., 2005. Anomalous transport in low-dimensional systems with correlated disorder. J. Phys. A: Math. Gen., 38(49), pp. 10613–10637..DOI: https://doi.org/10.1088/0305-4470/38/49/010
  14. Cakir, R., Grigolini, P. and Krokhin, A. A., 2006. Dynamical origin of memory and renewal. Phys. Rev. E., 74(2), pp. 021108(6 p.).
  15. Romero, A. and Sancho, J., 1999. Generation of short and long range temporal correlated noises. J. Comput. Phys., 156(1), pp. 1–11..DOI: https://doi.org/10.1006/jcph.1999.6347
  16. Czirok, A., Mantegna, R. N., Havlin, S. and Stanley, H. E., 1995. Correlations in binary sequences and a generalized Zipf analysis. Phys. Rev. E, 52(1), pp. 446–452..DOI: https://doi.org/10.1103/PhysRevE.52.446
  17. Makse, H. A., Havlin, S., Schwartz, M. and Stanley, H. E., 1996. Method for generating long range correlations for large systems. Phys. Rev. E, 53(5), pp. 5445–5449..DOI: https://doi.org/10.1103/PhysRevE.53.5445
  18. Izrailev, F. M., Krokhin, A. A., Makarov, N. M. and Usatenko, O. V., 2007. Generation of correlated binary sequences from white noise. Phys. Rev. E, 76(2), pp. 027701(4 p.).
  19. Izrailev, F. M., Krokhin, A. A. and Makarov, N. M., 2012. Anomalous localization in low-dimensional systems with correlated disorder. Phys. Rep., 512(3), pp. 125–254..DOI: https://doi.org/10.1016/j.physrep.2011.11.002
  20. Usatenko, O. V., Apostolov, S. S., Mayzelis, Z. A. and Melnik, S. S., 2010. Random Finite-Valued Dynamical Systems: Additive Markov Chain Approach. Cambridge: Cambridge Scientific Publ.
  21. Raftery, A., 1985. A model for high-order Markov chains. J. R. Stat. Soc. B, 47(3), pp. 528–539.
  22. Ching, W. K., Fung, E. S. and Ng, M. K., 2004. Higher order Markov chain models for categorical data sequences. Nav. Res. Logist., 51(4), pp. 557–574..DOI: https://doi.org/10.1002/nav.20017
  23. Li, W. K. and Kwok, M. C. O., 1990. Some Results on the Estimation of a Higher Order Markov Chain. Comun. Stat. Simul. Comput., 19(1), pp. 363–380..DOI: https://doi.org/10.1080/03610919008812862
  24. Cocho, J., Miramontes, P., Mansilla, R. and Li, W., 2014. 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. Comput. Biol. Chem., 53(A), pp. 15–25.
  25. Seifert, M., Gohr, A., Strickert, M. and Grosse, I., 2012. Parsimonious Higher-Order Hidden Markov Models for Improved Array-CGH Analysis with Applications to Arabidopsis thaliana. PLoS Comput. Biol., 8(1), pp. e1002286 (15 p.).
  26. Melnyk, S. S., Usatenko, O. V., Yampol'skii, V. A. and Golick, V. A., 2005. Competition of Two Types of Correlations. Phys. Rev. E, 72(2), pp. 026140(7 p.).
  27. Usatenko, O. V. and Yampol'skii, V. A., 2003. Binary N-Step Markov Chains and Long-Range Correlated Systems. Phys. Rev. Lett., 90(11), pp. 110601(4 p.).
  28. Shiryaev, A. N., 1996. Probability. N. Y.: Springer-Verlag New York, Inc..DOI: https://doi.org/10.1007/978-1-4757-2539-1
  29. Melnik, S. S. and Usatenko, O. V., 2014. Entropy and long-range correlations in DNA sequences. Comput. Biol. Chem., 53(A), pp. 26–31.
  30. Melnik, S. S. and Usatenko, O. V., 2014. Entropy of finite random binary sequences with weak long-range correlations. Phys. Rev. E, 90(5), pp. 052106(8 p.).
  31. Melnyk, S. S., Usatenko, O. V. and Yampol'skii, V. A., 2006. Memory functions of the additive Markov chains: applications to complex dynamic systems. Physica A, 361(2), pp. 405–415..DOI: https://doi.org/10.1016/j.physa.2005.06.083
  32. Apostolov, S. S., Mayzelis, Z. A., Usatenko, O. V. and Yampol'skii, V. A., 2008. High Order Correlation Functions of Binary Multi-Step Markov Chains. Int. J. Mod. Phys. B, 22(22), pp. 3841–3853..DOI: https://doi.org/10.1142/S0217979208048589
  33. Hosseinia, R., Leb, N. and Zideka, J., 2011. A Characterization of Categorical Markov Chains. J. Stat. Theory Pract., 5(2), pp. 261–284..DOI: https://doi.org/10.1080/15598608.2011.10412028
  34. Besag, J., 1974. Spatial interactions and the statistical analysis of lattice systems. J. R. Stat. Soc. Series B: Stat. Methodol., 36(2), pp. 192–225.