On effective algorithms solving regularity of Markov chains

• Autorzy: Dańko A. , Sawicka A. , Dańko W.

Warianty tytułu

PL

Efektywne algorytmy rozstrzygania regularności łańcuchów Markowa

• Języki publikacji: EN

Abstrakty

EN

We propose algorithms deciding whether a Markov chain with an n_n transition matrix M is regular. The lowest complexity of such an algorithm can be not greater than O(n ³ ) and we argue that it cannot be essentially diminished.

PL

W pracy proponujemy algorytmy rozstrzygające regularność łańcuchów Markowa o macierzy przejść rozmiaru n x n. Najniższa złożoność takiego algorytmu może być nie większa niż O(n ³ i podana jest argumentacja, że nie można jej istotnie obniżyć.

Słowa kluczowe

EN

Markov chain; ergodic Markov chain; regular Markov chain

PL

łańcuch Markowa; ergodyczny łańcuch Markowa; regularny łańcuch Markowa

• Wydawca: Oficyna Wydawnicza Politechniki Białostockiej
• Czasopismo: Advances in Computer Science Research
• Rocznik: 2016
• Tom: Nr 13
• Strony: 5--25
• Opis fizyczny: Bibliogr. 13 poz.

Twórcy

autor

Dańko A.

autor

Sawicka A.

• Polish-Japanese Academy of Information Technology, Warsaw, Poland

autor

Dańko W.

• Faculty of Computer Science, Bialystok University of Technology, Bialystok, Poland

Bibliografia

• [1] Aho A.V., Hopcroft J.E., Ullman J.D.: Design and Analysis of Computer Algorithms, Addison-Vesley, 1981.
• [2] Cormen T., Leiserson C., Riverst R., Stein C.: Introduction to Algorithms, Massachusetts Institute of Technology, 2001.
• [3] Dańko A., Da´nko W.: Improving Pseudo-Random Generators, International Conference on Biometrics and Kansei Engineering 24-28 June, Cieszyn, Poland, pp. 163-166, 2009.
• [4] Dańko W.: The Set of Probabilistic Algorithmic Formulas Valid in a Finite Structure is Decidable with Respect to Its Diagram, Fundamenta Informaticae, vol. 19 (3-4), pp. 417-431, 1993.
• [5] Feller W.: An Introduction to Probability Theory and Its Applications, John Wiley and Sons, Inc., New York, London, 1961.
• [6] Josifescu M.: Finite Markov Processes and Their Applications, JohnWiley and Sons, New York, London 1988.
• [7] Kubik L., Krupowicz A.: Introduction to Probability Theory and Its Applications, PWN, Warszawa, 1982, (in Polish).
• [8] Mirkowska G., Salwicki A.: Algorithmic Logic, D.Reidel Publ. Co. & PWN, Warsaw, 1987.
• [9] Modica G., Poggiolini L.: A First Course in Probability and Markov Chains, John Wiley and Sons, 2013.
• [10] Mora´s K.: Markov Chains. Analysis of Regular Chains, bachelor thesis, Bialystok University of Technology, 2015, (in Polish).
• [11] Ross S. M.: Introduction to Probability Models Academic Press, 2003.
• [12] Rubino G., Sericola B.: Markov Chains and Dependability Theory, Cambridge University Press, 2014.
• [13] Snell Laurie J.: Introduction to Probability, Random House Inc., New York, 1988.

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).