论文标题
限制具有随机重量边缘的有向图中最大路径重量的定理
Limit theorems for the maximal path weight in a directed graph on the line with random weights of edges
论文作者
论文摘要
我们将带有顶点的无限的有向图考虑整数...，-2，-1,0,1,2，...。令V为随机变量，以有限值或值“减无穷大”。考虑随机权重V（J，K），由具有J <K的整数对（J，K）索引，并假设它们是I.I.D. v。副本的副本是图的集合是集合（j，k），j <k。从顶点j到顶点K，j <k的图路径是边缘（j（0），j（1）），（j（1），j（1），j（2）），...，（j（m-1），j（m），j（m），j（0），j（0）= j（0）= j和j（m）= j;该路径的重量被视为其边缘权重的总和V（J（1））+V（J（1），J（1），J（1），J（1），J（1），J（1），J（M-1），J（M-1），J（M））。令W（0，n）为从0到n的所有路径的最大重量。我们研究序列w（0，n），n = 1，2，...的渐近行为是n倾向于无穷大的，在假设p（v> 0）> 0的假设下，v的条件分布（给定v> 0）不是退化的，而e exp（cv）是有限的c> 0。在V具有算术分布的情况下，我们在正常和中等较大的偏差方案中得出局部极限定理。在V具有非晶格分布的情况下，我们还得出了一个本地定理。
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.
