Limit Theorems for the Maximal Path Weight in a Directed Graph on the Line with Random Weights of Edges

Результат исследования: Научные публикации в периодических изданияхстатьярецензирование

Аннотация

We consider an infinite directed graph with vertices numbered by integers . . . ,−2, −1, 0, 1, 2, . . . , where any pair of vertices j < k is connected by an edge (j, k) that is directed from j to k and has a random weight vj,k ∈ [−∞,∞). Here, {vj,k, j < k} is a family of independent and identically distributed random variables that take either finite values (of any sign) or the value −∞. A path in the graph is a sequence of connected edges (j0, j1), (j1, j2), . . . , (jm−1, jm) (where j0 < j1 < . . . < jm), and its weight is the sum (Formula presented.). of the weights of the edges. Let w0,n be the maximal weight of all paths from 0 to n. Assuming that P(v0,1 > 0) > 0, that the conditional distribution of P(v0,1 ∈ · | v0,1 > 0) is nondegenerate, and that Eexp(Cv0,1) < ∞ for some C = const > 0, we study the asymptotic behavior of random sequence w0,n as n → ∞. In the domain of the normal and moderately large deviations we obtain a local limit theorem when the distribution of random variables vi,j is arithmetic and an integro-local limit theorem if this distribution is non-lattice. Key words: directed graph, maximal path weight, skeleton and renewal points, normal and moderate large deviations, (integro-)local limit theorem.

Язык оригиналаанглийский
Страницы (с-по)161-177
Число страниц17
ЖурналProblems of Information Transmission
Том57
Номер выпуска2
DOI
СостояниеОпубликовано - апр 2021

Предметные области OECD FOS+WOS

  • 1.02 КОМПЬЮТЕРНЫЕ И ИНФОРМАЦИОННЫЕ НАУКИ
  • 1.01 МАТЕМАТИКА

Fingerprint

Подробные сведения о темах исследования «Limit Theorems for the Maximal Path Weight in a Directed Graph on the Line with Random Weights of Edges». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать