Законы стабилизации при эволюции случайной струны

Рассматривается однородная марковская цепь с дискретным временем, состояниями которой являются последовательности (струны) $\alpha=x_n\dots x_1$ из $n$ символов, а переходные вероятности зависят только от $d$ символов (считая слева) и переход из $\alpha$ в $\beta=y_m\dots y_1$ возможен лишь, если $|n-m|\leq d$ и $x_i=y_i$ для всех $i=1,\dots, n-d$.
Мы доказываем различные законы стабилизации для левого конца струны. В терминах теории очередей это означает, что рассматривается очередь с дисциплиной LIFO с $r$ типами требований и с групповым приходом и обслуживанием. Это первый шаг в новом вероятностном подходе к изучению сетей связи с несколькими типами заявок.