Markovian embeddings of general random strings

DOI10.1137/1.9781611972986.2zbMATH Open1429.68151arXiv0802.1896OpenAlexW1629107725MaRDI QIDQ5194643FDOQ5194643

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)

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.

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

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

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)

Cited In (8)

• Title not available (Why is that?)
• 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
• Title not available (Why is that?)

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)