Sequences of degenerate Markov chains controlled by twice maximal random processes
0000-0003-4310-5665 Let $\{Z_{n}(s)\}_{s\in\mathbb{N}\cup\{0\}}$ be a sequence of degenerate Markov chains with $n+1\in\mathbb{N}$ states for a fixed $n$. The transition probabilities are defined using cycles of random processes that are two-step extreme evolutions of a population of particles assigned $n$--dimensional binary types $\mathrm{x}$ with the Hamming norm $|\mathrm{x}|$. The value of the Markov chain $Z_{n}(s)=n-|\mathrm{x}|$ is given by the norm of the type $\mathrm{x}$ of a certain particle. Let there be a particle of type $\mathrm{x}$ at the input to the cycle, and at the output a particle of type $\mathrm{y}$. The probability of the latter event is the probability of transition fr om the state $Z_{n}(s)=n-|\mathrm{x}|$ to the state $Z_{n}(s+1)=n-|\mathrm{y}|$. Based on lim it theorems, the asymptotic properties of random variables $Z_{n}(s)-Z_{n}(s+1)\geq 0$ are described as $n\to\infty$ and the average time of chain degeneration is estimated. The results are applicable for the study of evolutionary algorithms of optimization.
УДК 519.217.2
Keywords: Markov chains, series scheme, extremal problems, non-uniform estimates in the central limit theorem, Poisson distribution, evolutionary algorithms.