Two-Sided Evolution of a Random Chain
A.S. Gajrat, V.A. Malyshev, A.A. Zamyatin
1995, v.1, Issue 2, 281-316
ABSTRACT
A finite chain (string) is just a sequence of symbols from some finite alphabet. We consider Markov chains with the state space equal to the set of all finite strings. In the simplest situation left-sided evolution of the string is defined by the following one-step transition probabilities: $q_l(x,\emptyset )$ is the probability that the leftmost symbol of the string is erased, if this equals $x$; $q_l(x,y)$ is the probability that the leftmost symbol $x$ is substituted by $y$; $q_l(x,yz)$ is the probability that the leftmost symbol $x$ is substituted by $yz$. Right-sided evolution is defined similarly. We consider the case when left and right evolution occur simultaneously and independently. In the generic situation we obtain a complete classification of such Markov chains.
Keywords: Markov chain,string,invariant measure,stabilisation law
COMMENTS
Please log in or register to leave a comment