Waiting time distributions of runs in higher order Markov chains (Q1768130)

This is an extensive and rich paper with a few exact and several asymptotic results on waiting times for, and numbers of occurrences of, runs and scans. More precisely, the authors consider a \(\{0,1\}\)-valued \(m\)th order Markov chain \(X_1, X_2,\dots,X_n,\dots\) and study the behavior of the random variables (rv's) \(T_r^{(\text{M})}\), \(T_r^{(\text{E})}\), \(T_r^{(\text{L})}\), \(M^{(\text{M})}_n\), \(M^{(\text{E})}_n\), \(M^{(\text{L})}_n\), \(T^{(k_1,j)}_r\) and \(S_{k_1,k}^{(j)}(n)\) \((j= \text{I,II,III})\), for any nonnegative integer \(k\) and positive integers \(r\) and \(k_1\), \(1< k_1< k\). The rv \(T_r^{(\text{M})}\) (resp. \(T_r^{(\text{E})}\), \(T_r^{(\text{L})}\)) denotes the waiting time for the \(r\)th occurrence of at most (resp. exactly, at least) \(k\) consecutive 1's, \(M^{(\text{M})}_n\) (resp. \(M_n^{(\text{E})}\), \(M^{(\text{L})}_n\)) denotes the number of runs of at most (resp. exactly, at least) \(k\) consecutive 1's up to time \(n\), \(T^{(k_1,j)}_r\) denotes the waiting time for the \(r\)th occurrence of scan, and \(S_{k_1,k}^{(j)}(n)\) denotes the number of scans up to time \(n\). The superscript \((j)\) denotes the rule of counting: ``I'' means that each 1 is counted by only one window, ``II'' means that the windows are disjoint, and ``III'' means that overlap is allowed. The authors first examine the exact distribution of \(T_r^{(\text{M})}\) and \(T_r^{(\text{E})}\) by means of the method of conditional probability generating functions. For both variables they derive a system of linear equations. Next, they establish Poisson type convergence results for the waiting time rv's \(T_r^{(\text{M})}\), \(T_r^{(\text{E})}\), \(T_r^{(\text{L})}\) and \(T_r^{(k_1,j)}\) \((j= \text{I,II,III})\), providing there is a strong tendency towards success (occurrence of 1) or reversing its states. Finally, the authors obtain a central limit theorem and a law of the iterated logarithm for each of the four rv's \(M_n^{(\text{M})}\), \(M_n^{(\text{E})}\), \(M_n^{(\text{L})}\) and \(S_{k_1,k}^{(\text{III})}(n)\).