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 v_j,k ∈ [−∞,∞). Here, {v_j,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 (j₀, j₁), (j₁, j₂), . . . , (j_m−1, j_m) (where j₀ < j₁ < . . . < j_m), and its weight is the sum (Formula presented.). of the weights of the edges. Let w_0,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(v_0,1 ∈ · | v_0,1 > 0) is nondegenerate, and that Eexp(C_v0,1) < ∞ for some C = const > 0, we study the asymptotic behavior of random sequence w_0,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 v_i,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.