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

T. Konstantopoulos, A. V. Logachov, A. A. Mogulskii, S. G. Foss

Research output: Contribution to journalArticlepeer-review


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 languageEnglish
Pages (from-to)161-177
Number of pages17
JournalProblems of Information Transmission
Issue number2
Publication statusPublished - 7 Jul 2021


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

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computer Networks and Communications


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.

Cite this