Abstract: Пусть $\{Z_{n}(s)\}_{s\in\mathbb{N}\cup\{0\}}$ последовательность вырождающихся цепей Маркова с $n+1\in\mathbb{N}$ состоянием при фиксированном $n$. Вероятности перехода определяются с помощью циклов случайных процессов, являющихся двухшаговыми экстремальными эволюциями популяции частиц, которым присвоены $n$--мерные бинарные типы $\mathrm{x}$ с нормой Хэмминга $|\mathrm{x}|$. Значение цепи Маркова $Z_{n}(s)=n-|\mathrm{x}|$ задается нормой типа $\mathrm{x}$ некоторой частицы. Пусть на входе в цикл имеется частица типа $\mathrm{x}$, а на выходе получается частица типа $\mathrm{y}$. Вероятность последнего события является вероятностью перехода из состояния $Z_{n}(s)=n-|\mathrm{x}|$ в состояние $Z_{n}(s+1)=n-|\mathrm{y}|$. %Случайный процесс, начинающийся с частицы типа $\mathrm{x}$, которая на первом этапе порождает много мутантов и из них выбирается частица с максимальной нормой типа $\mathrm{x}'$. На втором этапе частицы типов $\mathrm{x}$ и $\mathrm{x}'$ многократно скрещиваются, и из этих потомков выбирается частица типа $\mathrm{y}$ с максимальной нормой. Если $|\mathrm{y}|\geq |\mathrm{x}|$, то $Z_{n}(s+1)=n-|\mathrm{y}|$, а иначе $Z_{n}(s+1)=Z_{n}(s)=n-|\mathrm{x}|$. На основании предельных теорем описаны асимптотические свойства случайных величин $Z_{n}(s)-Z_{n}(s+1)\geq 0$ при $n\to\infty$ и оценено среднее время вырождения цепи. Результаты применимы для исследования эволюционные алгоритмы оптимизации.

Cite: Топчий В.А.
Последовательности вырождающихся цепей Маркова, управляемые дважды максимальными случайными процессами
Математические труды. 2026. Т.29. №2. С.113-151. DOI: 10.25205/1560-750X-2026-29-2-113-151

Dates:

Submitted:	Dec 5, 2025
Accepted:	May 6, 2026
Published print:	Jun 24, 2026
Published online:	Jun 24, 2026

Identifiers: No identifiers

Altmetrics: