Evolution of a Random String: Stabilization Laws

A discrete-time homogeneous Markov chain is considered the states of which are sequences (strings) $\alpha=x_n\dots x_1$ of $n$ symbols; the transition probabilities depend only on the $d$ leftmost symbols, and $\alpha$ can jump only to $\beta=y_m\dots y_1$ such that $|n-m|\leq d$ and $x_i=y_i$ for all $i=1,\dots, n-d$.
We prove various stabilization laws for the left end of the string. For a queueing theory, this means that a LIFO queue with $r$ types of customers and with batch arrivals and batch services is considered. This constitutes the first step of the new probabilistic approach to communication networks with several customer types.