TY - JOUR

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

AU - Konstantopoulos, T.

AU - Logachov, A. V.

AU - Mogulskii, A. A.

AU - Foss, S. G.

N1 - Funding Information: The research of T. Konstantopoulos and S.G. Foss was supported in part by the joint Russian–French grant of the Russian Foundation for Basic Research and French National Centre for Scientific Research (project nos. RFBR-CNRS-19-51-15001 and CNRS-193-382). The research of A.V. Logachov, A.A. Mogulskii, and S.G. Foss was carried out at the Mathematical Center in Akademgorodok, Novosibirsk, agreement no. 075-15-2019-1675 with the Ministry of Science and Higher Education of the Russian Federation. Publisher Copyright: © 2021, Pleiades Publishing, Inc.

PY - 2021/4

Y1 - 2021/4

N2 - 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.

AB - 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.

KW - (integro-)local limit theorem

KW - directed graph

KW - maximal path weight

KW - normal and moderate large deviations

KW - skeleton and renewal points

UR - http://www.scopus.com/inward/record.url?scp=85109633722&partnerID=8YFLogxK

U2 - 10.1134/S0032946021020058

DO - 10.1134/S0032946021020058

M3 - Article

AN - SCOPUS:85109633722

VL - 57

SP - 161

EP - 177

JO - Problems of Information Transmission

JF - Problems of Information Transmission

SN - 0032-9460

IS - 2

ER -