Limit theorems for the maximal path weight in a directed graph on the line with random weights of edges

DOI10.1134/S0032946021020058MaRDI QIDQ2044129zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 4 August 2021

Published in Problems of Information Transmission (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2011.09981

zbMATH Keywords

directed graphintegro-local limit theoremmaximal path weightnormal and moderate large deviationsskeleton and renewal points

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Signed and weighted graphs (05C22) Paths and cycles (05C38)

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.

Recommendations

• Long-range last-passage percolation on the line
• Limiting properties of random graph models with vertex and edge weights
• Convergence of directed random graphs to the Poisson-weighted infinite tree
• Limit theorems for a random directed slab graph
• Convergence to the Tracy-Widom distribution for longest paths in a directed random graph

Cites work

• Chain Lengths in Certain Random Directed Graphs
• scientific article; zbMATH DE number 46924 (Why is no real title available?)
• scientific article; zbMATH DE number 2051870 (Why is no real title available?)
• scientific article; zbMATH DE number 3374724 (Why is no real title available?)
• Limit theorems for a random directed slab graph
• Limiting properties of random graph models with vertex and edge weights
• Local theorems for arithmetic multidimensional compound renewal processes under Cramér's condition
• Long-range last-passage percolation on the line
• On the asymptotics for the minimal distance between extreme vertices in a generalised Barak-Erdős graph
• Speed of parallel processing for random task graphs
• The rate function and the fundamental function for multidimensional compound renewal process

Cited in

(10)

• Limiting properties of random graph models with vertex and edge weights
• Long-range last-passage percolation on the line
• Impulsive processes on the weighted directed graphs
• Convergence of directed random graphs to the Poisson-weighted infinite tree
• Limit theorems for a random directed slab graph
• scientific article; zbMATH DE number 850345 (Why is no real title available?)
• The Distribution of Path Lengths On Directed Weighted Graphs
• Scaling properties of paths on graphs
• Probabilistic and analytical properties of the last passage percolation constant in a weighted random directed graph
• Last passage percolation and limit theorems in Barak-Erdős directed random graphs and related models

This page was built for publication: Limit theorems for the maximal path weight in a directed graph on the line with random weights of edges

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2044129)