Markovian embeddings of general random strings

DOI10.1137/1.9781611972986.2MaRDI QIDQ5194643zbMATH OpenOpenAlexFDO

Authors Manuel E. Lladser

Publication date 16 September 2019

Published in 2008 Proceedings of the Fifth Workshop on Analytic Algorithmics and Combinatorics (ANALCO) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0802.1896

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Formal languages and automata (68Q45) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Algorithms on strings (68W32)

Abstract: Let A be a finite set and X a sequence of A-valued random variables. We do not assume any particular correlation structure between these random variables; in particular, X may be a non-Markovian sequence. An adapted embedding of X is a sequence of the form R(X_1), R(X_1,X_2), R(X_1,X_2,X_3), etc where R is a transformation defined over finite length sequences. In this extended abstract we characterize a wide class of adapted embeddings of X that result in a first-order homogeneous Markov chain. We show that any transformation R has a unique coarsest refinement R' in this class such that R'(X_1), R'(X_1,X_2), R'(X_1,X_2,X_3), etc is Markovian. (By refinement we mean that R'(u)=R'(v) implies R(u)=R(v), and by coarsest refinement we mean that R' is a deterministic function of any other refinement of R in our class of transformations.) We propose a specific embedding that we denote as R^X which is particularly amenable for analyzing the occurrence of patterns described by regular expressions in X. A toy example of a non-Markovian sequence of 0's and 1's is analyzed thoroughly: discrete asymptotic distributions are established for the number of occurrences of a certain regular pattern in X_1,...,X_n, as n tends to infinity, whereas a Gaussian asymptotic distribution is shown to apply for another regular pattern.

Recommendations

• Pattern Markov Chains: Optimal Markov Chain Embedding Through Deterministic Finite Automata
• Waiting time distribution for pattern occurrence in a constrained sequence: an embedding Markov chain approach
• Pattern Correlation Matrices for Markov Sequences and Tests of Randomness
• scientific article; zbMATH DE number 1959509
• On the probability of existence of substrings with the same structure in a random sequence

Cited in

(8)

• scientific article; zbMATH DE number 5023089 (Why is no real title available?)
• scientific article; zbMATH DE number 7229740 (Why is no real title available?)
• Approximation of sojourn-times via maximal couplings: motif frequency distributions
• Constrained Embedding Probability for Two Binary Strings
• Grammatical Inference: Algorithms and Applications
• Moments of the count of a regular expression in a heterogeneous random sequence
• Stochastic analysis of minimal automata growth for generalized strings
• Clairvoyant embedding in one dimension

This page was built for publication: Markovian embeddings of general random strings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5194643)