RUS  ENG
Полная версия
ЖУРНАЛЫ // Проблемы передачи информации // Архив

Пробл. передачи информ., 2021, том 57, выпуск 2, страницы 71–89 (Mi ppi2342)

Эта публикация цитируется в 1 статье

Большие системы

Предельные теоремы для максимального веса пути в направленном графе на целочисленной прямой со случайными весами ребер

Т. Константопулосa, А. В. Логачёвbcd, А. А. Могульскийdb, С. Г. Фоссedb

a Отделение математических наук, Ливерпульский университет, Ливерпуль, Великобритания
b Институт математики им. С.Л. Соболева СО РАН, Новосибирск
c Сибирский государственный университет геосистем и технологий, Новосибирск
d Новосибирский государственный университет, Новосибирск
e Школа математических наук, Университет Хериот-Ватта, Эдинбург, Великобритания

Аннотация: Рассматривается бесконечный направленный граф, вершины которого занумерованы целыми числами $\ldots, -2,-1,0,1,2, \ldots\strut$, а любая пара вершин $j<k$ соединена ребром $(j,k)$ между ними, направленным из $j$ в $k$ и имеющим случайный вес $v_{j,k}\in [-\infty,\infty)$, где $\{v_{j,k}, j<k\}$ – семейство независимых и одинаково распределенных случайных величин, которые принимают либо конечные значения (любого знака), либо значение $-\infty$. Путь в таком графе – это последовательность связанных между собой ребер $(j_0,j_1), (j_1,j_2),\ldots,(j_{m-1},j_m)$ (где $j_0<j_1<\ldots <j_m$), а его вес – сумма весов этих ребер $\sum\limits_{s=1}^m v_{j_{s-1},j_s}\ge -\infty$. Пусть $w_{0,n}$ – максимальный вес среди всех путей из $0$ в $n$. В предположениях, что $\mathbf{P}(v_{0,1}>0)>0$, условное распределение $\mathbf{P}(v_{0,1}\in\cdot \mid v_{0,1}>0)$ невырождено и $\mathbf{E}\exp (Cv_{0,1})<\infty$ при некотором $C=\mathrm{const} >0$, изучается асимптотическое поведение случайной последовательности $w_{0,n}$ при стремлении $n\to\infty$. В области нормальных и умеренно больших уклонений получена локальная предельная теорема в случае, когда распределение случайных величин $v_{i,j}$ является арифметическим, и интегро-локальная предельная теорема, если это распределение является нерешетчатым.

Ключевые слова: направленный граф, максимальный вес пути, осевые и стержневые вершины, нормальные и умеренно большие уклонения, (интегро-)локальная предельная теорема.

УДК: 621.391 : 519.175.4 : 519.214

Поступила в редакцию: 19.11.2020
После переработки: 01.02.2021
Принята к печати: 08.02.2021

DOI: 10.31857/S0555292321020054


 Англоязычная версия: Problems of Information Transmission, 2021, 57:2, 161–177

Реферативные базы данных:


© МИАН, 2024