Hostname: page-component-586b7cd67f-l7hp2 Total loading time: 0 Render date: 2024-11-21T23:35:41.788Z Has data issue: false hasContentIssue false
  • English
  • Français

ON DISCRETE STOCHASTIC PROCESSES WITH DISJUNCTIVE OUTCOMES

Part of: Control systems Markov processes Discrete mathematics in relation to computer science

Published online by Cambridge University Press:  12 May 2014

KRZYSZTOF LEŚNIAK
KRZYSZTOF LEŚNIAK*
Affiliation:
Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, ul. Chopina 12/18, 87-100 Toruń, Poland email [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We introduce a class of discrete-time stochastic processes, called disjunctive processes, which are important for reliable simulations in random iteration algorithms. Their definition requires that all possible patterns of states appear with probability 1. Sufficient conditions for nonhomogeneous chains to be disjunctive are provided. Suitable examples show that strongly mixing Markov chains and pairwise independent sequences, often employed in applications, may not be disjunctive. As a particular step towards a general theory we shall examine the problem arising when disjunctiveness is inherited under passing to a subsequence. An application to the verification problem for switched control systems is also included.

Keywords

disjunctive sequenceBernoulli schemeMarkov chainchain with complete connectionsswitched control systemverification problem

MSC classification

Secondary: 60J10: Markov chains (discrete-time Markov processes on discrete state spaces) 68R15: Combinatorics on words 93C30: Systems governed by functional relations other than differential equations (such as hybrid and switching systems)
Type
Research Article
Information
Bulletin of the Australian Mathematical Society , Volume 90 , Issue 1 , August 2014 , pp. 149 - 159
Copyright
Copyright © 2014 Australian Mathematical Publishing Association Inc. 

References

Barnsley, M. F., Fractals Everywhere. New edition (Dover, New York, 2012).Google Scholar
Barnsley, M. F. and Le’sniak, K.,‘The chaos game on a general iterated function system from a topological point of view’. arXiv:1203.0481v2 (2013).Google Scholar
Barnsley, M. F. and Vince, A., ‘The chaos game on a general iterated function system’, Erg. Theory Dynam. Syst. 31 (2011), 1073–1079.CrossRefGoogle Scholar
Calude, C. S. and Staiger, L., ‘Generalisations of disjunctive sequences’, Math. Log. Q. 51 (2005), 120–128.CrossRefGoogle Scholar
Daafouz, J., Riedinger, P. and Iung, C., ‘Stability analysis and control synthesis for switched systems: a switched Lyapunov function approach’, IEEE Trans. Automat. Control 47 (2002), 1883–1887.CrossRefGoogle Scholar
Dang, T., Donz’e, A. and Maler, O., ‘Verification of analog and mixed-signal circuits using hybrid system techniques’, in: FMCAD’04, Lecture Notes in Computer Science 3312 (Springer, Berlin, 2004), 21–36.Google Scholar
Dugundji, J. and Granas, A., Fixed Point Theory (Polish Scientific Publishers, Warsaw, 1982).Google Scholar
Goodman, G. S., ‘A Probabilist looks at the chaos game’, in: Fractals in the Fundamental and Applied Sciences (eds. Peitgen, H.-O., Henriques, J. M. and Penedo, L. F.) (North-Holland, Amsterdam, 1991), 159–168.Google Scholar
Gray, R. M., Probability, Random Processes, and Ergodic Properties (Springer, Dordrecht, Heidelberg, London, New York, 2009).CrossRefGoogle Scholar
Hayes, B., ‘Quasirandom ramblings’, Amer. Sci. 99 (2011), 282–287.Google Scholar
Istrate, G. and Puaun, G., ‘Some combinatorial properties of self-reading sequences’, Discrete Appl. Math. 55 (1994), 83–86.CrossRefGoogle Scholar
Jones, N. C. and Pevzner, P. A., An Introduction to Bioinformatics Algorithms (MIT Press, Cambridge, 2004).Google Scholar
Knill, O., Probability Theory and Stochastic Processes with Applications (Overseas Press, New Delhi, 2009).Google Scholar
Landers, D. and Rogge, L., ‘Weak ergodicity of stationary pairwise independent processes’, Proc. Amer. Math. Soc. 128 (2000), 1203–1206.CrossRefGoogle Scholar
Liberzon, D., Switching in Systems and Control (Birkhäuser, Boston, 2003).CrossRefGoogle Scholar
Lothaire, M., Applied Combinatorics on Words (Cambridge University Press, Cambridge, 2005).Google Scholar
Luby, M. and Wigderson, A., Pairwise Independence and Derandomization (Now Publishers, Hanover–Delft, 2006).Google Scholar
Merkle, W., ‘The Kolmogorov–Loveland stochastic sequences are not closed under selecting subsequences’, J. Symbolic Logic 68 (2003), 1362–1376.Google Scholar
Mitzenmacher, M. and Upfal, E., Probability and Computing: Randomized Algorithms and Probabilistic Analysis (Cambridge University Press, Cambridge, 2005).CrossRefGoogle Scholar
Şen, Z., Spatial Modeling Principles in Earth Sciences (Springer, Dordrecht, Heidelberg, London, New York, 2009).Google Scholar
Shields, P. C., The Ergodic Theory of Discrete Sample Paths (American Mathematical Society, Providence, RI, 1996).Google Scholar
Stenflo, Ö., ‘Ergodic theorems for iterated function systems with time dependent probabilities’, Theory Stoch. Process. 19 (1997), 436–446.Google Scholar
Stenflo, Ö., ‘Iterated function systems with a given continuous stationary distribution’, Fractals 20 (2012), 197–202.Google Scholar
Strohmer, T. and Vershynin, R., ‘A randomized Kaczmarz algorithm with exponential convergence’, J. Fourier Anal. Appl. 15 (2009), 262–278.CrossRefGoogle Scholar
Thorisson, H., Coupling, Stationarity, and Regeneration (Springer, New York, 2000).Google Scholar