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

Konstantopoulos, T, Logachov, AV, Mogulskii, AA and Foss, SG (2021) Limit Theorems for the Maximal Path Weight in a Directed Graph on the Line with Random Weights of Edges. PROBLEMS OF INFORMATION TRANSMISSION, 57 (2). pp. 161-177.

Text
2011.09981v3.pdf - Author Accepted Manuscript
Download (385kB) | Preview

Official URL: http://dx.doi.org/10.1134/S00329460210200??

Abstract

We consider the infinite directed graph with vertices the set of integers ...,-2,-1,0,1,2,... . Let v be a random variable taking either finite values or value "minus infinity". Consider random weights v(j,k), indexed by pairs (j,k) of integers with j<k, and assume that they are i.i.d. copies of v. The set of edges of the graph is the set (j,k), j<k. A path in the graph from vertex j to vertex k, j<k, is a finite sequence of edges (j(0), j(1)), (j(1), j(2)), ..., (j(m-1), j(m)) with j(0)=j and j(m)=j; the weight of this path is taken to be the sum v(j(0),j(1))+v(j(1),j(2))+...+v(j(m-1),j(m)) of the weights of its edges. Let w(0,n) be the maximal weight of all paths from 0 to n. We study the asymptotic behaviour of the sequence w(0,n), n=1, 2, ..., as n tends to infinity, under the assumptions that P(v>0)>0, the conditional distribution of v, given v>0, is not degenerate, and that E exp(Cv) is finite, for some C>0. We derive local limit theorems in the normal and moderate large deviations regimes in the case where v has an arithmetic distribution. We also derive an integro-local theorem in the case where v has a non-lattice distribution.

Item Type:	Article
Additional Information:	16 pages, 1 figure
Uncontrolled Keywords:	directed graph, maximal path weight, skeleton and renewal points, normal and moderate large deviations, (integro-)local limit theorem
Divisions:	Faculty of Science and Engineering > School of Physical Sciences
Depositing User:	Symplectic Admin
Date Deposited:	26 Jul 2022 15:54
Last Modified:	18 Jan 2023 20:54
DOI:	10.1134/S0032946021020058
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3159599