arxiv: 2603.22541 · v2 · submitted 2026-03-23 · 🧮 math.PR

Recognition: 2 theorem links

· Lean Theorem

Convex bounds for last passage percolation with dependent identically distributed weights

Isaac Meilijson

Authors on Pith no claims yet

Pith reviewed 2026-05-15 00:15 UTC · model grok-4.3

classification 🧮 math.PR

keywords last passage percolationconvex orderdependent weightsexponential distributionpoint-to-line LPPstochastic boundspercolation time

0 comments

The pith

For mean-one exponential weights, last passage percolation time R_N is maximized in convex order by N W plus log(N!) under a suitable coupling.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper examines last passage percolation times on the lattice when weights are identically distributed but can have arbitrary dependence. It determines the couplings that maximize the point-to-line time R_N in the sense of increasing convex order for any fixed marginal distribution. For exponential weights with mean one, the maximum is attained by a coupling that sets R_N equal to N times one weight plus the log of N factorial, so that the expectation of any convex nondecreasing function of R_N is largest under this arrangement. A reader would care because the result shows how dependence can drive the scale of the longest path sum well beyond what occurs under independence, where the normalized time converges to a constant.

Core claim

Among all couplings of identically distributed weights with a given marginal, the last passage percolation time R_N is maximized in increasing convex order. For mean-one exponential weights this maximum is realized by the random variable R_N^* = N W(1,1) + log(N!), satisfying E[Ψ(R_N)] ≤ E[Ψ(R_N^*)] for every convex nondecreasing Ψ where the expectations exist. This contrasts with the i.i.d. case in which R_N/N converges almost surely to 2.

What carries the argument

Increasing convex order on the distribution of the point-to-line last passage time R_N, achieved by couplings of the weights that concentrate the path sums.

If this is right

The maximal expected value of R_N is identified for every marginal distribution.
Under the maximizing coupling for exponentials, R_N/N diverges like log N rather than converging to 2.
The expected last passage time is always at least N times the mean weight, attained when weights are constant along anti-diagonals.
For exponential weights the minimal possible asymptotic variance of R_N is zero.
R_N^* has variance that grows quadratically with N.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Strong positive dependence among weights can inflate the longest path sum far above the typical scale seen in independent models.
The same convex-order technique could be applied to first-passage times or to percolation on other graphs.
The result indicates that percolation quantities are highly sensitive to the joint law of the weights, not merely their marginals.

Load-bearing premise

There exist couplings of the weights with the given marginal that realize the stated convex dominance for R_N.

What would settle it

Constructing a coupling of mean-one exponential weights such that E[Ψ(R_N)] exceeds E[Ψ(R_N^*)] for some convex nondecreasing Ψ would disprove the claimed maximality.

Figures

Figures reproduced from arXiv: 2603.22541 by Isaac Meilijson.

**Figure 1.** Figure 1: Oriented N-partite graphs. The red path is in L8, the green path is in C8. (1, 1) (5, 4) (4, 5) Last passage percolation in Z 2 . Each vertex of CN is assigned a non-negative random variable. These weights W(i, j) (canonically, W) are identically F-distributed ”times”, and the commonly studied i.i.d. model makes them independent and identically distributed. The convex bound model makes them identically dis… view at source ↗

read the original abstract

On the $Z^2$ lattice, vertices are assigned random weights $W(i,j)$. The point-to-point last passage percolation (LPP) time $S_{M,N+1-M}$ between $(1,1)$ and $(M,N+1-M)$ is the maximum total weight among all upward/right-oriented paths connecting the two. Point-to-line LPP time $R_N$ is the maximum of these maximal total weights over $M$. Asymptotic distributions and fluctuations of these LPP times have been studied for i.i.d. weights. The current study deals with identically distributed but not necessarily independent weights, and maximizes LPP times in the sense of increasing convex dominance. In particular, maximal expected LPP times are identified, in the class of all weight couplings with a given marginal distribution. For the case of mean-$1$ exponentially distributed weights, there is a coupling for which $R_N$ is the shifted exponential variable $R_N^* = N W(1,1) + \log(N!)$, such that $E[\Psi(R_N)] \le E[\Psi(R_N^*)]$ for all couplings and all convex non-decreasing functions $\Psi$ for which these expectations are well defined. In contrast to ${{R_N^*} \over N}= W(1,1)+{{\log(N!)} \over N}$, with variance $1$ and mean diverging to $\infty$ like $\log(N)$, ${{R_N} \over N}$ converges a.s. to $2$ for the commonly studied i.i.d. weights. As for {\em small} LPP, expected LPP time is at least $NE[W(1,1)]$, attained by assigning to each anti-diagonal identical weights. The minimal possible variance of $R_N$ is asymptotically zero for exponential weights.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives convex-order upper bounds on last-passage percolation times for identically distributed weights by exhibiting an explicit coupling, with the exponential case reducing to a shifted exponential that dominates all other dependence structures.

read the letter

The core result is that when weights share a fixed marginal but can be coupled arbitrarily, the point-to-line LPP time R_N is largest in the increasing convex order under a particular dependence structure. For mean-1 exponentials this structure makes R_N equal in law to N W(1,1) plus log(N!), so the expectation of any convex increasing test function is maximized by this choice. The paper also records the matching lower bound for small LPP (at least N times the mean weight, achieved by setting every anti-diagonal constant) and notes that the minimal possible variance of R_N vanishes asymptotically for the exponential marginal. These statements are new relative to the i.i.d. literature cited in the abstract; the explicit coupling and the variance claim do not appear in the earlier work on independent weights. The contrast with the i.i.d. limit (R_N/N converging almost surely to 2) is drawn cleanly and helps locate the result. The construction itself is straightforward once the anti-diagonal partition is used: assign to each anti-diagonal a single exponential draw scaled to the required maximum, so one path collects every diagonal maximum at once. This sidesteps the overlap worry in the stress-test note because a path samples exactly one site per diagonal, and the marginals remain exponential by construction. The general-marginal case is stated at the same level of generality but without the same explicit formula, which is a minor limitation rather than a flaw. No free parameters or circular definitions are introduced. The paper is aimed at specialists in percolation and stochastic processes who already know the i.i.d. results and want to see how dependence changes the extremal behavior. It is short, focused, and formally grounded enough to merit referee time; the claims are checkable once the coupling is written out in full.

Referee Report

2 major / 2 minor

Summary. The manuscript studies last passage percolation (LPP) on the Z^2 lattice with weights that are identically distributed but possibly dependent. It derives convex-order upper bounds on the point-to-line LPP time R_N by constructing couplings that maximize the distribution in the increasing convex order. For mean-1 exponential weights, it claims a coupling exists such that R_N equals in law the random variable R_N^* = N W(1,1) + log(N!), yielding E[Ψ(R_N)] ≤ E[Ψ(R_N^*)] for all convex non-decreasing Ψ. It also gives a lower bound of N E[W(1,1)] for the expectation (attained by constant weights per anti-diagonal) and shows that the minimal variance of R_N is asymptotically zero for exponentials, contrasting with the i.i.d. case where R_N/N → 2 a.s.

Significance. If the coupling constructions are valid, the results identify sharp extremal behaviors for LPP under arbitrary dependence with fixed marginals, providing a convex-order envelope that is stronger than moment bounds and directly comparable to the i.i.d. limit. The explicit form for exponentials and the variance-minimization statement are potentially useful for applications in queueing or polymer models with correlated increments.

major comments (2)

[Abstract / coupling construction] Abstract and coupling section: the central upper-bound claim requires existence of a coupling of the W(i,j) with exact Exp(1) marginals such that the induced R_N equals N W(1,1) + log(N!) in distribution. This demands that the per-anti-diagonal maxima (whose expectations sum to log(N!)) are simultaneously realized by a single path; the manuscript must supply an explicit joint construction or existence proof, as any overlap violation on shared lattice sites would invalidate the convex dominance for all other couplings.
[Lower-bound argument] Lower-bound paragraph: the assertion that E[R_N] ≥ N E[W(1,1)] is attained by setting all weights on each anti-diagonal equal needs verification against the path geometry, since every path crosses every anti-diagonal exactly once and the max-over-paths operation must still respect the identical-marginal constraint when the constants are chosen per diagonal.

minor comments (2)

[Introduction] Notation: the distinction between point-to-point S_{M,N+1-M} and point-to-line R_N should be introduced with an explicit diagram or indexing convention in the first section to avoid ambiguity when anti-diagonals are referenced.
[Introduction] The statement that R_N/N converges a.s. to 2 for i.i.d. weights should cite the precise reference (e.g., the relevant theorem in the literature on exponential LPP) rather than leaving it as a parenthetical contrast.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and insightful comments on our manuscript. We address each major comment below and will revise the manuscript to strengthen the presentation of the coupling construction while clarifying the lower-bound argument.

read point-by-point responses

Referee: [Abstract / coupling construction] Abstract and coupling section: the central upper-bound claim requires existence of a coupling of the W(i,j) with exact Exp(1) marginals such that the induced R_N equals N W(1,1) + log(N!) in distribution. This demands that the per-anti-diagonal maxima (whose expectations sum to log(N!)) are simultaneously realized by a single path; the manuscript must supply an explicit joint construction or existence proof, as any overlap violation on shared lattice sites would invalidate the convex dominance for all other couplings.

Authors: We agree that the coupling construction merits a more explicit treatment to confirm that the per-anti-diagonal maxima can be realized simultaneously along a single lattice path. In the revised manuscript we will supply an explicit construction: generate, for each anti-diagonal k with m_k sites, m_k i.i.d. Exp(1) random variables; assign the largest of these to the site visited by a fixed reference path on that diagonal, and distribute the remaining order statistics to the other sites on the diagonal. Because the assignment is performed independently per diagonal and the reference path is a valid lattice path, the resulting weights are jointly distributed so that each marginal is exactly Exp(1) while the reference path sum equals the sum of the diagonal maxima. Consequently R_N equals N W(1,1) + log(N!) in law under this coupling, establishing the claimed increasing-convex-order upper bound. This construction avoids any overlap violation because sites on distinct anti-diagonals are distinct. revision: yes
Referee: [Lower-bound argument] Lower-bound paragraph: the assertion that E[R_N] ≥ N E[W(1,1)] is attained by setting all weights on each anti-diagonal equal needs verification against the path geometry, since every path crosses every anti-diagonal exactly once and the max-over-paths operation must still respect the identical-marginal constraint when the constants are chosen per diagonal.

Authors: The lower-bound construction is already consistent with the path geometry. When all sites on anti-diagonal k receive the identical value V_k ~ W(1,1), every lattice path traverses exactly one site per anti-diagonal and therefore realizes the identical sum sum_k V_k. Hence R_N equals this common sum, E[R_N] = N E[W(1,1)], and the marginal constraint is satisfied by construction. We will add a single clarifying sentence in the revised manuscript to emphasize this geometric fact, but no substantive change to the argument is required. revision: partial

Circularity Check

0 steps flagged

Coupling-based convex dominance for LPP times with fixed marginals; no reduction to self-definition or fitted inputs

full rationale

The paper establishes convex-order upper bounds on R_N by exhibiting a specific coupling of the weights that realizes R_N^* = N W(1,1) + log(N!) for exponential marginals, then invoking the definition of convex dominance to conclude E[Ψ(R_N)] ≤ E[Ψ(R_N^*)] for convex non-decreasing Ψ. This step uses the standard property that a random variable is maximal in convex order among all variables with a given marginal once a dominating coupling is shown to exist; the existence claim is not derived from the target inequality itself. No self-citation is load-bearing for the central argument, no parameter is fitted to a subset and then renamed as a prediction, and the derivation does not rename a known empirical pattern. The construction for general marginals is asserted via anti-diagonal constancy, which is a direct (non-circular) assignment respecting the marginal constraint. Hence the overall circularity score remains low.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the existence of couplings realizing a given marginal distribution and on the standard definition of increasing convex order; no free parameters are fitted and no new entities are postulated.

axioms (2)

standard math Increasing convex order is well-defined for random variables with the same marginal distribution.
Used to compare expectations of convex non-decreasing functions across couplings.
domain assumption Couplings of random variables with prescribed marginals exist.
Invoked to assert the existence of the maximizing coupling.

pith-pipeline@v0.9.0 · 5631 in / 1407 out tokens · 47894 ms · 2026-05-15T00:15:17.237028+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

For the case of mean-1 exponentially distributed weights, there is a coupling for which R_N is the shifted exponential variable R_N^* = N W(1,1) + log(N!), such that E[Ψ(R_N)] ≤ E[Ψ(R_N^*)] for all couplings and all convex non-decreasing functions Ψ.
IndisputableMonolith/Foundation/BranchSelection.lean branch_selection unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Convex majorization of maxima of partial sums - The method of Meilijson & Nádas [8]

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

[1]

Blair-Stahn, N. D. (2010). First passage percolation and competition models. ArXiv: Probability, May 4, 2010

work page 2010
[2]

L., Pr¨ ahofer, aM

Borodin, A., Ferrari, P. L., Pr¨ ahofer, aM. & Sasamoto, T. Fluctuation properties of the TASEP with periodic initial configuration. J. Stat. Phys., 129:1055–1080, 2007

work page 2007
[3]

(1966).An introduction to Probability theory and its applications, 2

Feller, W. (1966).An introduction to Probability theory and its applications, 2. Wiley, New York

work page 1966
[4]

Gnedenko, B.V. (1943). Sur la distribution limite du terme maximum d’une serie al´ eatoire. Annals of Mathematics.44 (3): 423–453

work page 1943
[5]

Johansson, K. (2000). Shape fluctuations and random matrices.Comm. Math. Phys.,209.2, 437–476

work page 2000
[6]

Lai, T. L. & Robbins, H. (1977). A class of dependent random variables and their maxima.Z. Wahrscheinlichkeitstheorie verw. Gebiete42, 89–111

work page 1977
[7]

Meilijson, I. (1972). Limiting properties of the mean residual lifetime function.Ann. Math. Statist.,43(1), 354–357

work page 1972
[8]

and N´ adas, A

Meilijson, I. and N´ adas, A. (1979). Convex majorization with an application to the length of critical paths.J. Appl. Prob.,16(3), 671–677

work page 1979
[9]

R¨ ost, H. (1981). Nonequilibrium behaviour of a many particle process: Density profile and local equilibria.Zeitschrift f. Warsch. Verw. Gebiete,58.1, 41–53

work page 1981
[10]

and Uckelmann, L

R¨ uschendorf, L. and Uckelmann, L. (2002). Variance minimization and random variables with constant sum. In Distributions with Given Marginals and Statistical Modelling, pp. 211–222. Dordrecht: Kluwer Academic Publishers. MR2058994

work page 2002
[11]

Sasamoto, T. (2005). Spatial correlations of the 1D KPZ surface on a flat substrate.J. Phys. A,38, 549—556

work page 2005
[12]

and Shanthikumar, J

Shaked, M. and Shanthikumar, J. G. (2007).Stochastic orders. Springer

work page 2007
[13]

and Wang, R

Wang, B. and Wang, R. (2011). The complete mixability and convex minimization problems with monotone marginal densities.Journal of Multivariate Analysis,102 (10),1344–1360. 12

work page 2011