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

Research output: Contribution to journalArticlepeer-review

## Abstract

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.

Original language English 161-177 17 Problems of Information Transmission 57 2 https://doi.org/10.1134/S0032946021020058 Published - Apr 2021

## Keywords

• (integro-)local limit theorem
• directed graph
• maximal path weight
• normal and moderate large deviations
• skeleton and renewal points

## OECD FOS+WOS

• 1.02 COMPUTER AND INFORMATION SCIENCES
• 1.01 MATHEMATICS

## Fingerprint

Dive into the research topics of 'Limit Theorems for the Maximal Path Weight in a Directed Graph on the Line with Random Weights of Edges'. Together they form a unique fingerprint.