Repetitions of the values of a function of segments of a sequence of independent trials

A. M. Shoitov

Diskretnaya Matematika, Tome 12 (2000) no. 3, pp. 49-59

Résumé

We consider the problem on the number $\xi(N)$ of $k$-fold matchings of symbols that occur in a sequence of random variables resulting from aggregating the states of a Markov–Bruns chain generated by $n$-tuples $(X_i,\dots,X_{i+n-1})$ consisting of elements of the sequence $(X_1,\dots,X_{N+n-1})$ of independent realisations of a random variable $X$. The aggregation of states consists of applying a given function $f$, which takes a finite number of values, to the $n$-tuples $(X_i,\dots,X_{i+n-1})$. We prove a theorem on convergence to a multivariate normal law for the joint distribution of $\xi(N)$ under various aggregation functions, and give sufficient conditions on convergence of the distribution of $\xi(N)$ to the chi-square law as $N\to\infty$. These results are applied to the problem on $k$-fold imperfect matchings of $n$-tuples in a sequence of polynomial trials. In particular, we prove a theorem on convergence to a multivariate normal law for the vector of numbers of $k$-fold imperfect matchings of various lengths and ranks.