论文标题
在及最后一段渗透中的极限常数中
On Limit Constants in Last Passage Percolation in Transitive Tournaments
论文作者
论文摘要
在边缘权重是独立的Bernoulli随机变量的情况下，我们研究了\ emph {最后一个通道渗透}问题。鉴于边缘上有随机权重的$ n $节点上的及时锦标赛，最后一个段落的渗透问题旨在找到最重的路径的重量$ x_n $，其中路径的重量是边缘上的权重的总和。我们给出了复发关系，并使用它来获得$ x_n $的概率生成函数（双变量）生成功能。这还提供了$ \ mathbb {e} [x_n] $的精确组合表达式，该$由Yuster [\ Emph {disc。应用。数学。}，2017年]。我们进一步确定$ x_n $的限制定律中的扩展常数。定义$β_{tr}（p）：= \ lim_ {n \ to \ infty} \ frac {\ mathbb {e} [x_n]} {n-1} $。使用奇异性分析，我们显示\ [β_{tr}（p）= \ left（\ sum_ {n \ geq 1}（1-p）^{n \ select 2} \ right）^{ - 1}。特别是，$β_{tr}（0.5）= \ left（\ sum_ {n \ geq 1} 2} 2^{ - {n \ select 2}}} \ right）^{ - 1} = 0.60914971106 ... $。这解决了确定由Yuster发起的$β_{tr}（0.5）$的值的问题。 $β_{tr}（p）$也是Foss，Martin和Schmidt [\ Emph {Ann的强大定律中$ x_n $的大定律的限制值。应用。 probab。}，2014年]。我们还在Foss等人证明的$ x_n $的功能中心限制定理中得出缩放常数。
We investigate the \emph{last passage percolation} problem on transitive tournaments, in the case when the edge weights are independent Bernoulli random variables. Given a transitive tournament on $n$ nodes with random weights on its edges, the last passage percolation problem seeks to find the weight $X_n$ of the heaviest path, where the weight of a path is the sum of the weights on its edges. We give a recurrence relation and use it to obtain a (bivariate) generating function for the probability generating function of $X_n$. This also gives exact combinatorial expressions for $\mathbb{E}[X_n]$, which was stated as an open problem by Yuster [\emph{Disc. Appl. Math.}, 2017]. We further determine scaling constants in the limit laws for $X_n$. Define $β_{tr}(p) := \lim_{n\to \infty} \frac{\mathbb{E}[X_n]}{n-1}$. Using singularity analysis, we show \[ β_{tr}(p) = \left(\sum_{n\geq 1}(1-p)^{n\choose 2}\right)^{-1}. \] In particular, $β_{tr}(0.5) = \left(\sum_{n\geq 1} 2^{-{n\choose 2}}\right)^{-1} = 0.60914971106...$. This settles the question of determining the value of $β_{tr}(0.5)$, initiated by Yuster. $β_{tr}(p)$ is also the limiting value in the strong law of large numbers for $X_n$, given by Foss, Martin, and Schmidt [\emph{Ann. Appl. Probab.}, 2014]. We also derive the scaling constants in the functional central limit theorem for $X_n$ proved by Foss et al.
