J Stat Phys (2015) 158:903–949 DOI 10.1007/s10955-014-1146-0

Directed Last Passage Percolation with Discontinuous Weights Jeff Calder

Received: 18 February 2014 / Accepted: 4 November 2014 / Published online: 18 November 2014 © Springer Science+Business Media New York 2014

Abstract We prove that a directed last passage percolation model with discontinuous macroscopic (non-random) inhomogeneities has a continuum limit that corresponds to solving a Hamilton–Jacobi equation in the viscosity sense. This Hamilton–Jacobi equation is closely related to the conservation law for the hydrodynamic limit of the totally asymmetric simple exclusion process. We also prove convergence of a numerical scheme for the Hamilton– Jacobi equation and present an algorithm based on dynamic programming for finding the asymptotic shapes of maximal directed paths. Keywords Directed last passage percolation · Hamilton–Jacobi equations · Viscosity solutions · Variational problems · Totally asymmetric simple exclusion process · Hydrodynamic limit Mathematics Subject Classification

35D40 · 60F99 · 65N06 · 60K35

1 Introduction The directed last passage percolation (DLPP) problem can be formulated as follows: Let X (i, j) be nonnegative independent random variables defined on the lattice N2 , and define the last passage time from (1, 1) to (M, N ) by  X (i, j), (1) L(M, N ) = max p∈ M,N

(i, j)∈ p

where  M,N denotes the set of up/right paths from (1, 1) to (M, N ) in N2 . Of interest are the asymptotics of L as M, N → ∞, and their first order fluctuations. DLPP is an example of a stochastic growth model, and has many applications in mathematical and scientific contexts. For example, DLPP is equivalent to zero-temperature directed J. Calder (B) Department of Mathematics, University of California, Berkeley, USA e-mail: [email protected]

123

904

J. Calder

polymer growth in a random environment—an important model in statistical mechanics [10,14,23,24]. The model describes a hydrophilic polymer chain wafting in a water solution containing randomly placed hydrophobic molecules (impurities) that repel the individual monomers in the polymer chain. Due to thermal fluctuations and the random positions of impurities, the shape of the polymer chain is best understood as a random object. The statistical mechanical model for a directed polymer assumes that the shape of the polymer can be described by a directed path p ∈  M,N , thus suppressing entanglement and U-turns. The presence, or strength, of an impurity at site (i, j) is described by a random variable X (i, j), and the energy of a path p ∈  M,N is given by  X (i, j), (2) −β (i, j)∈ p

where β = 1/T > 0 is the inverse temperature. The typical shape of a polymer is one that minimizes (2). Of interest is the quenched polymer distribution on paths defined by ⎞ ⎛  1 (3) Q( p; M, N ) = X (i, j)⎠, exp ⎝β Z (M, N ) (i, j)∈ p

where p ∈  M,N and the normalization factor Z (M, N ) is called the partition function, and is given by ⎛ ⎞   (4) exp ⎝β X (i, j)⎠. Z (M, N ) = p∈ M,N

(i, j)∈ p

In the zero-temperature limit, i.e., β → ∞, the quenched polymer distribution concentrates around paths maximizing (2), and we formally have  1 lim log (Z (M, N )) = max X (i, j) = L(M, N ), β→∞ β p∈ M,N (i, j)∈ p

Directed polymers are related to several other stochastic models for growing surfaces, such as directed invasion percolation, ballistic deposition, polynuclear growth, and low temperature Ising models [28]. DLPP with independent and identically distributed (i.i.d.) exponential weights X (i, j) is equivalent to the totally asymmetric simple exclusion process (TASEP), which is an important stochastic interacting particle system [20,34], and to randomly growing Young diagrams [26, 35,38]. Briefly, the dynamics of TASEP involve a particle configuration on the lattice Z, evolving in time, with the dynamical rule that a particle jumps to the right after an exponential waiting time if the right neighboring site is empty. The correspondence between DLPP and TASEP proceeds via the following stochastic corner growth model: Partition R2 into squares defined by the edges of the lattice Z2 . Imagine that at time t = 0, all the squares in [0, ∞)2 are colored white, while the remaining squares are colored black. For each (i, j) ∈ N2 , assign a passage time random variable X (i, j) to the square with (i, j) on the northeast corner. The dynamic rule governing the growth process is the following: A white square at location (i, j) is colored black exactly X (i, j) time units after both its south and west neighbors become black. The time until square (M, N ) is colored black is exactly L(M, N )—the last passage time from (1, 1) to (M, N )—and the set of all black squares is a randomly growing Young diagram. There is a one-to-one correspondence between TASEP configurations, and configurations of black and white squares in the corner growth model. The idea is that when a white square

123

Directed Last Passage Percolation

905

is colored black, it corresponds to a particle jumping from a site j to its necessarily vacant neighbor j + 1. The explicit correspondence is as follows: For every edge separating a white and black square, assign a value of 1 to vertical edges, and a value of 0 to horizontal edges. The TASEP configuration corresponds exactly to reading these binary values sequentially from (1, ∞) to (∞, 1). We give this correspondence more rigorously in Sect. 1.2 (see Fig. 2). There are further applications of DLPP in queueing theory [1,22], and the model is also related to greedy lattice animals [29]. One quantity of interest in DLPP is the time constant, U , given by U (x) := lim

N →∞

1 L (N x) , N

(5)

where x = (x1 , x2 ) ∈ [0, ∞)2 . The exact form of U is known for i.i.d. geometric weights [26], and i.i.d. exponential weights [34], and is given by √ U (x) = μ(x1 + x2 ) + 2σ x1 x2 , (6) where μ and σ 2 are the mean and variance, respectively, of the either geometric or exponential weights. For more general distributions, Martin [30] showed that U is continuous on [0, ∞)2 and gave the following asymptotics at the boundary: √ √ U (1, α) = μ + 2σ α + o( α). In similar fashion to the longest increasing subsequence problem [3], the fluctuations of L for geometric and exponential weights are non-Gaussian, and instead follow the Tracy-Widom distribution asymptotically [26]. It is an open problem to determine U (x) and the fluctuations of L for weights other than geometric and exponential. We study the DLPP problem with independent weights X (i, j) that are either geometric or exponential, but not identically distributed. For exponential DLPP, we assume that X (i, j) is exponentially distributed with mean λ(i N −1 , j N −1 ) where λ : [0, ∞)2 → [0, ∞), and we consider the aymptotics as N → ∞. The setup is identical for geometric DLPP, except that the macroscopic inhomogeneity is in the parameter q of the geometric distribution. For directed polymers, this models a macroscopic (non-random) inhomogeneity in the strength of impurities; while for TASEP, it corresponds to an inhomogeneity in the rate at which particles move to the right. Our main result, presented in Sect. 1.1, is a Hamilton–Jacobi equation for the continuum limit of this DLPP problem. In the exponential case with continuous λ, Rolla and Teixeira [33] showed that U has a variational interpretation. Their result is in many ways analogous to the variational problem for the longest chain problem [18] that we exploited in our previous work [12,13]. Macroscopic inhomogeneities have also been considered for TASEP [21], and for other similar growth models [32]. In particular, Georgiou et al. [21] proved a hydrodynamic limit for TASEP with a spatially (but not temporally) inhomogeneous jump rate c, which may admit discontinuities. Their result gives the limiting density profile in terms of a variational problem, and they connected this to a conservation law in the special case that the rate c(s) is piecewise constant with one jump, i.e.,  c , s≤0 c(s) = 1 c2 , s > 0. In the context of exponential DLPP, this would be equivalent to assuming that the macroscopic mean λ : [0, ∞)2 → [0, ∞) is given by λ(x) = c1−1 for x1 ≥ x2 and λ(x) = c2−1 otherwise. Our main result, Theorem 1, gives a Hamilton–Jacobi equation for the limiting time constant

123

906

J. Calder

in DLPP when the macroscopic inhomogeneity λ is piecewise Lipschitz. In the context of TASEP, this allows for a discontinuous inhomogeneous jump rate which has a spatial and temporal dependence. 1.1 Main Result Let us mention the conventions used in this paper. We say X is geometrically distributed with parameter q if P(X = k) = (1 − q)k q,

for k ∈ {0, 1, 2, 3, . . . } and 0 < q ≤ 1, so that we have E(X ) =

1−q 1−q . and Var(X ) = q q2

(7)

We say that X is exponentially distributed with mean λ ≥ 0 if for λ > 0 we have P(X ∈ d x) =

1 −x e λ d x for x ∈ [0, ∞), λ

and when λ = 0 we have X = 0 with probability one. Here we have E(X ) = λ and Var(X ) = λ2 .

(8)

In order to ensure that our results are applicable to both exponential and geometric DLPP, we parameterize these distributions instead by their mean μ. For the exponential distribution there is no change; we have λ = μ. For the geometric distribution, we have by (7) that a geometric random variable with mean μ ≥ 0 has parameter q=

1 . 1+μ

(9)

For both cases, the variance is of course a function of√the mean; in the exponential case we have σ = μ, and in the geometric case we have σ = μ(1 + μ). Let us now present our main result. We consider the following two-sided DLPP model, similar to [2,5,9,11,15]. Let X (i, j) be independent nonnegative random variables defined on the lattice N20 , where N0 = {0, 1, 2, . . . }. Let L(M, N ; Q, P) denote the last passage time from (M, N ) ∈ N20 to (Q, P) ∈ N20 , where M ≤ Q and N ≤ P. This is defined as follows:  L(M, N ; Q, P) = max X (i, j), (10) p∈(M,N ),(Q,P)

(i, j)∈ p

where (M,N ),(Q,P) denotes the set of up/right paths from (M, N ) to (Q, P) in N20 . The macroscopic inhomogeneity is described by functions μ : [0, ∞)2 → [0, ∞) and μs : ∂ R2+ → [0, ∞), where R+ = (0, ∞). Specifically, given a parameter N we make the following assumption: The weights X (i, j) are independent with mean  μ(i N −1 , j N −1 ), E(X (i, j)) = μ(i N −1 , j N −1 ) + μs (i N −1 , j N −1 ),

if (i, j) ∈ N2 , if i = 0 or j = 0.

(11)

The term μ corresponds to the macroscopic mean within the bulk R2+ , and the term μs corresponds to an additional source active only on the boundary ∂ R2+ .

123

Directed Last Passage Percolation

907

We also assume the weights X (i, j) are either all geometrically distributed, or all expontially distributed. We can construct the random variables X (i, j) on a common probability space as follows. Let Y (i, j) be i.i.d. exponential random variables with mean λ = 1, where i, j ∈ N0 . In the exponential case, we can simply set  μ(i N −1 , j N −1 )Y (i, j), if (i, j) ∈ N2 , X (i, j) =  μ(i N −1 , j N −1 ) + μs (i N −1 , j N −1 ) Y (i, j), if i = 0 or j = 0. This setup is similar to [33]. In the geometric case, we note that if Y is an exponential random variable with mean λ = 1, then for any ν > 0, X = νY  is geometrically distributed 1 with parameter q = 1 − e− ν . In order to obtain E(X ) = μ > 0, we need that 1 1 = q = 1 − e− ν , 1+μ

which gives that ν = 1/(log(1 + μ) − log(μ)). If μ = 0, then we set ν = 0. Hence, let us set ν(x) = 1/(log(1 + μ(x)) − log(μ(x))) for μ(x) > 0 and ν(x) = 0 when μ(x) = 0. We make a similar definition for νs . Setting

 ν(i N −1 , j N −1 )Y (i, j) , if (i, j) ∈ N2 , X (i, j) =  ν(i N −1 , j N −1 ) + νs (i N −1 , j N −1 ) Y (i, j) , if i = 0 or j = 0, we see that X (i, j) are independent geometric random variables satisfying (11). Before stating the, somewhat technical, hypotheses on μ and μs , we need to introduce some notation. We say a curve Γ in R2 is continuous and strictly increasing if it can be parameterized in the form Γ : t → (t, f (t)) for t ∈ I, where f : I → R is continuous and strictly increasing, and I is an interval in R. We make a similar definition for strictly decreasing. Notice that a continuous strictly increasing (resp. decreasing) curve can also be parameterized in the form t → ( f (t), t) where f : I → R is continuous and strictly increasing (resp. decreasing). For simplicity, we will also use Γ to denote the locus of points that lie on the curve Γ . Let Γ be a continuous strictly decreasing curve in [0, 1]2 with endpoints (1, 0) and (0, 1), and let Ω ⊂ [0, ∞)2 denote the bounded component of the complement of Γ in [0, ∞)2 . Let {Γi }i∈Z be a locally finite non-intersecting collection of continuous strictly increasing curves. For each i we assume one endpoint of Γi is on ∂([0, ∞)2 \ Ω) and the other endpoint is at ∞, i.e., the curve is unbounded. The complement of ∪i Γi in [0, ∞)2 \ Ω therefore consists of a family {Ωi }i∈Z of connected components. Each curve Γi is on the boundary of exactly two components, which we may assume are labeled Ωi and Ωi−1 . See Fig. 1 for an illustration of these quantities. We place the following assumptions on μ and μs : (F1) The function μ : [0, ∞)2 → [0, ∞) is bounded and upper semicontinuous, μ|Ω = 0, and there exists a constant Cli p such that for every i ∈ Z, μ|Ωi is Lipschitz continuous with constant Cli p . (F2) The source term μs : ∂ R2+ → [0, ∞) is bounded and upper semicontinuous with a locally finite set of discontinuities. Throughout the paper we will regard μs as a function on [0, ∞)2 by setting μs = 0 on R2+ . We also make the following technical assumption:

123

908

J. Calder

Fig. 1 Depiction of quantities Ωi and Γi . The function μ is assumed to be Lipschitz with constant Clip when restricted to any Ωi , and μ = 0 on Ω

(F3) For every i ∈ Z and x ∈ Γi , there exists ε > 0 and ζ ∈ {−1, +1} such that for all y ∈ Bε (x) ∩ Γi we have 

(12) ζ lim μ(z) − lim μ(z) ≥ 0. Ωi−1 z→y

Ωi z→y

Our main result is the following continuum limit: Theorem 1 Let μ : [0, ∞)2 → [0, ∞) satisfy (F1) and (F3), and let μs : ∂ R2+ → [0, ∞) satisfy (F2). Suppose that the weights X (i, j) satisfy (11) and are either all exponential, or all geometric random variables, constructed on a common probability √ space as above. In the exponential case, set σ = μ, and in the geometric case, set σ = μ(1 + μ). Then with probability one we have 1 L(0; N ·) −→ U locally uniformly on [0, ∞)2 , N where U is the unique monotone viscosity solution of

on R2+ , (Ux1 − μ)+ (Ux2 − μ)+ = σ 2 (P) U =ϕ on ∂ R2+ , 1 and ϕ(x) = (x1 + x2 ) 0 μ(t x) + μs (t x) dt.

(13)

Here, Ux1 and Ux2 denote the partial derivatives of U , t+ denotes the positive part of t given by max(t, 0), and by monotone we mean that U is monotone non-decreasing with respect to all variables. Theorem 1 is an extension of our previous work [12,13], in which we proved a similar result for the longest chain problem. This result can be viewed as a type of stochastic homogenization [37], where the effective Hamiltonian is given in (P). A similar stochastic homogenization result has been obtained recently for first passage percolation [27], though in that case the exact form of the effective Hamiltonian is unknown. The Hamilton–Jacobi

123

Directed Last Passage Percolation

909

equation (P) is also closely related to the conservation law for the hydrodynamic limit of TASEP [21], and in Sect. 1.2 we show a formal equivalence between the two continuum limits. We believe this new Hamilton–Jacobi equation will prove to be a useful tool for studying the DLPP problem, both theoretically and numerically. As an example, in Sect. 5.2 we show how to combine the numerical solution of this Hamilton–Jacobi equation with dynamic programming to find the asymptotic shapes of optimal paths. We also believe that this work will provide a new perspective on the hydrodynamic limit of TASEP, and may be useful for studying the corresponding conservation law. Some remarks on the hypotheses (F1), (F2), and (F3) are in order. First, the assumption that μ and μs are bounded in (F1) and (F2) is made for simplicity. It can be replaced by the assumption that μ and μs are bounded on compact sets, with minor changes to the proofs. Recall that in the exponential case, we have σ 2 = μ2 , and in the geometric case, we have σ 2 = μ(1 + μ). Thus, if μ satisfies (F1), (F3), then so will σ 2 , though possibly with a larger Lipschitz constant Cli p . Since it is convenient for the analysis, we will often regard μ and σ 2 as independent functions both satisfying (F1) and (F3). We will only need to recall the relationship between μ and σ at a few key points. In particular, the uniqueness proof for (P) (see Sect. 3) requires that μ and σ 2 satisfy (F3) simultaneously with the same choice of ζ . This is of course always true, since σ is a monotone increasing function of μ in both the exponential and geometric cases. Let us briefly comment on the significance of Γ and Ω. The correspondence between exponential DLPP and TASEP (described in detail in Sect. 1.2) implies that the initial macroscopic density ρ0 for TASEP is encoded into the curve Γ . If Γ and Ω are not present, then we have TASEP with the common step initial condition ρ0 (s) = 1 for s ≤ 0 and ρ0 (s) = 0 for s > 0. Suppose now that Γ and Ω are present, and parameterize Γ by t → (t, f (t)) where f is continuous and strictly decreasing with f (0) = 1 and f (1) = 0. Let us assume additionally that f is continuously differentiable. Based on the correspondence between TASEP and exponential DLPP, the initial density will be given by ⎧ if s ≤ −1 ⎨ 1, ρ0 (s) = − f  (ts )/(1 − f  (ts )), if s ∈ (−1, 1) ⎩ 0, if s ≥ 1. where for s ∈ (−1, 1), ts is the unique t ∈ (0, 1) satisfying s = t − f (t). Thus by choosing f appropriately, one can obtain a large class of initial densities ρ0 for TASEP with this setup. The rest of the paper is organized as follows: In Sect. 1.2 we show formally that (P) is equivalent to the conservation law for the hydrodynamic limit of TASEP [21]. The proof of Theorem 1 is given in Sect. 4 after some preliminary results. In particular, in Sect. 2 we present and analyze a variational problem for (P), and in Sect. 3, we prove a comparison principle for (P), which generalizes our previous work [13]. In Sect. 5, we present a fast numerical scheme for computing the viscosity solution of (P), and we present the results of various numerical simulations in Sect. 5.1. Finally, in Sect. 5.2, we give an algorithm based on dynamic programming for finding the asymptotic shape of optimal DLPP paths, and in Sect. 6 we discuss possible directions for future work. 1.2 Formal Equivalence to Hydrodynamic Limit of TASEP We show here a formal equivalence between (P) and the hydrodynamic limit of TASEP, given in [21]. TASEP is an interacting stochastic particle system on Z with state space {0, 1}Z , whose elements, η, represent particle configurations. If a particle is present at site j ∈ Z, then η j = 1,

123

910

J. Calder

and if no particle is present, then η j = 0. The process is exclusionary in the sense that at most one particle can occupy each site at a given time. The stochastic dynamics proceed as follows: a particle at site j jumps to site j + 1 after an exponential waiting time, provided the site j + 1 is empty. The exponential waiting times are independent and begin at the exact moment the right neighboring site is vacated. These dynamics, along with an initial condition η(0) : Z → {0, 1}, generate the stochastic process η = {ηi (t) : i ∈ Z, t ∈ [0, ∞)}. In the standard TASEP model, the exponential waiting times are independent with rate c = 1. As in [21], we allow the rates to have a macroscopic spatial (and temporal) dependence, i.e., the rate at position j ∈ Z and time t ∈ [0, ∞) is c( j N −1 , t N −1 ), where c : R ×[0, ∞) → (0, ∞), and N is a parameter that we will send to ∞. A central object of study is the macroscopic density ρ(s, t), which is the almost sure limit (assuming it exists) of the discrete densities as follows:  b N b  1 lim ηi (N t) = ρ(s, t) ds. (14) N →∞ N a i=N a+1

Georgiou et al. [21] showed that for c(s, t) = c(s) =



c1 , c2 ,

s≤0 s > 0,

ρ can be identified as the unique entropy solution of the scalar conservation law ρt + (c(s)ρ(1 − ρ))s = 0, ρ(s, 0) = ρ0 (s),

(15)

where ρ0 denotes the initial macroscopic density. We are using s for the spatial variable in (15) to avoid confusion with the spatial variables in (P). In what follows, we show formally that the conservation law (15) is equivalent to (P). For simplicity, we will ignore the initial condition ρ0 and the boundary condition in (P), and restrict ourselves to showing that the (P) and (15) are equivalent in the bulk. We shall also assume that ρ ∈ C 1 . Consider now the exponential DLPP model with macroscopic mean λ : [0, ∞)2 → (0, ∞), i.e., μ = σ = λ. Let L denote the last passage time given by (10), and let us write L(m, n) = L(1, 1; m, n) for convenience. Let U be the unique monotone viscosity solution of (P), and let us assume that U ∈ C 1 and λ > 0 so that Ux1 , Ux2 > λ > 0. Of course, the viscosity solution of a Hamilton–Jacobi equation is in general not C 1 ; the argument we give here is purely formal. By Theorem 1 we have 1 L(N x) −→ U (x) with probability one. N We also note that (P) can be rearranged as follows: Ux1 (x)Ux2 (x) = λ(x). Ux1 (x) + Ux2 (x)

(16)

(17)

Let us now describe in detail the correspondence between TASEP and DLPP, which can also be found here [4,31]. We assign to a TASEP configuration η the site counter I j (t) = number of particles that have jumped from site j to site j + 1 up to time t. (18) and the height function

⎧ j  ⎪ ⎨ 2I0 (t) + i=1 1 − 2ηi (t) , h j (t) = 2I0 (t),  ⎪ ⎩ 2I (t) + 0 0 i= j+1 1 − 2ηi (t) ,

123

j ≥ 1, j = 0, j ≤ −1.

(19)

Directed Last Passage Percolation

911

Fig. 2 A visual depiction of the correspondence between TASEP and DLPP. On the left, the gray region is the set A(t)—the t sub-level set of L—and on the right we show the corresponding TASEP height function h j (t) obtained by rotating the boundary of A(t) by π/4

Then we have h 0 (0) = 0, and h j (t) − h j (0) = 2I j (t). The height function h j (t) is a stochastically growing interface, and is related to the corner growth model described in Sect. 1. Roughly speaking, the dynamical rule for the growth of h j (t) is that when a particle jumps to the right (from j to j + 1), a valley  turns into a mountain , and the height at site j increases by 2. See Fig. 2 for reference. Let us now define the random set   A(t) = (m, n) ∈ Z2+ : L(m, n) ≤ t . Since L is non-decreasing in both arguments, it implicitly defines its own height function,  h j (t), which describes the boundary of A(t) as follows:   h m−n (t) ≥ m + n . A(t) = (m, n) ∈ Z2+ :  The correspondence between TASEP and DLPP is the identification  h j (t) = h j (t) in the sense of joint distributions. This connection is made rigorous by choosing appropriate boundary rates for DLPP here [31]. Visually, the correspondence is obtained by rotating the boundary of A(t) by π/4 to obtain the height function h j (t) (see Fig. 2). The correspondence between TASEP and DLPP says, at least formally, that     (m, n) ∈ Z2+ : L(m, n) ≤ t = (m, n) ∈ Z2+ : h m−n (t) ≥ m + n . (20) By (14) and (19), h j (t) has a macroscopic continuum limit, h ∞ , such that  s 1 ρ(s  , t) ds  , h s N  (t N ) −→ h ∞ (s, t) = g(t) + s − 2 N 0

(21)

with probability one, where g(t) := lim N →∞ 2N −1 I0 (t N ). It follows from (21) that h∞ s (s, t) = 1 − 2ρ(s, t). Combining (16), (20), and (21) we have that     x ∈ R2+ : U (x) = t = x ∈ R2+ : h ∞ (x1 − x2 , t) = x1 + x2 .

(22)

(23)

123

912

J. Calder

It follows from (23) that

 h ∞ x1 − x2 , U (x) = x1 + x2 .

(24)

This is in some sense the “master equation” relating the continuum limits of TASEP and DLPP. Let us illustrate how to use (24) to derive the conservation law (15) from (P); deriving (P) from (15) follows in a similar fashion. Differentiating (24) in both x1 and x2 we have ∞ h∞ s (s, t) + h t (s, t)U x1 (x) = 1

∞ −h ∞ s (s, t) + h t (s, t)U x2 (x)

= 1.

(25) (26)

where t = U (x) and s = x1 − x2 . Adding (25) and (26) we have h∞ t (s, t) =

2 . Ux1 (x) + Ux2 (x)

(27)

Similarly, by rearranging and dividing (25) by (26) we have Ux1 (x) ρ(s, t) 1 − h∞ s (s, t) (22) = = . Ux2 (x) 1 + h∞ (s, t) 1 − ρ(s, t) s

(28)

This equality can also be obtained by noting that the slope of the level set {U (x) = t} is given locally by the ratio of ones to zeros in the TASEP configuration. Solving for ρ in (28) we have ρ = Ux1 /(Ux1 + Ux2 ), which yields  ρ(s, t) 1 − ρ(s, t) =

Ux1 (x)Ux2 (x) λ(x) (17) = , 2 (Ux1 (x) + Ux2 (x)) Ux1 (x) + Ux2 (x)

(29)

where we invoked the Hamilton–Jacobi equation (P) in the second equality above. Since U is strictly monotone increasing in both x1 and x2 , there is a one-to-one correspondence between the coordinates x = (x1 , x2 ) and (s, t) = (x1 − x2 , U (x)). Let us write c(s, t) := λ(x)−1 . Since λ is the exponential mean, c is the exponential rate for TASEP. Then combining (29) with (27) we have  h∞ (30) t (s, t) = 2c(s, t)ρ(s, t) 1 − ρ(s, t) . Differentiating with respect to s on both sides of (30) and applying (22) we have  −2ρt (s, t) = 2 c(s, t)ρ(s, t)(1 − ρ(s, t)) s ,

(31)

which is precisely the conservation law (15). Furthermore, by combining (30) and (22), we have the following Hamilton–Jacobi equation for h ∞ : c(s, t)  2 1 − h∞ (32) s (s, t) . 2 It seems to us that this formal computation could be made precise when ρ and U are indeed C 1 functions. This is the case, for example, when λ is constant. In the general case where ρ and U are not C 1 , it may be possible to make this formal computation precise using the machinery of viscosity solutions, and we plan to investigate this in a future work. h∞ t (s, t) =

2 Variational Problem In this section we give a variational interpretation for U and analyze its relevant properties. This variational problem first appeared in [33], in a different form, for exponential DLPP

123

Directed Last Passage Percolation

913

with a continuous macroscopic rate λ, and is similar to the well-known variational problem for the longest chain problem [12,13,18]. Let us first introduce some notation. We denote by  the coordinatewise partial order on Rd , i.e., x  y if and only if xi ≤ yi for all i, where x = (x 1 , . . . , x d ), y ∈ Rd . We write x ≤ y if x  y and x  = y, and we write x < y if xi < yi for all i. For x, y ∈ Rd with x  y, we will often use the following interval notation   [x, y] = z ∈ Rd : x  z  y , and

  (x, y] = z ∈ Rd : x < z ≤ y ,

with similar definitions for [x, y) and (x, y). Let A denote the set of C 1 monotone curves, given by   A = γ ∈ C 1 ([0, 1]; [0, ∞)2 ) : γ  (t)  0 for all t ∈ [0, 1] .

(33)

We write γ (t) = (γ1 (t), γ2 (t)) to denote the components of γ . For μ, σ : [0, ∞)2 → R, let us define μ,σ : [0, ∞)2 × [0, ∞)2 → [0, ∞) by √ μ,σ (x, p) = μ(x)( p1 + p2 ) + 2σ (x) p1 p2 , (34) and for γ ∈ A we set

 Jμ,σ (γ ) =

1

0

μ,σ (γ (t), γ  (t)) dt.

(35)

Notice that μ,σ (x, kp) = kμ,σ (x, p) for any k ≥ 0, hence Jμ,σ (γ ) is independent of the parametrization of γ . We finally define   Uμ,σ (x) = sup Jμ,σ (γ ) : γ ∈ A , γ (0) = 0, and γ (1) = x , (36) for x ∈ [0, ∞)2 . Borrowing language from optimal control theory [6], we will call Uμ,σ the value function for this variational problem. We will often write J,  and U in place of Jμ,σ , μ,σ and Uμ,σ , respectively, when it is clear from the context what μ and σ are. Notice that when x ∈ ∂ R2+ with x2 = 0 we have  x1 U (x) = μ(t, 0) dt. (37) 0

with x1 = 0, and in general we can write  1 U (x) = (x1 + x2 ) μ(t x) dt,

A similar formula holds when x ∈

∂ R2+

(38)

0

for x ∈ ∂ R2+ . We also define

  Wμ,σ (x, y) = sup Jμ,σ (γ ) : γ ∈ A , γ (0) = x, and γ (1) = y ,

(39)

for x, y ∈ [0, ∞)2 with x  y. As before, we will often drop the subscripts on Wμ,σ when convenient. Similar to (37)–(38), when x, y ∈ [0, ∞)2 with x  y and x2 = y2 , we can write  y 1

W (x, y) =

μ(t, x2 ) dt,

(40)

x1

123

914

J. Calder

with a similar formula holding when x1 = y1 . In general, whenever x  y but xi = yi for some i we can write  1 W (x, y) = (y1 − x1 + y2 − x2 ) μ(x + (y − x)t) dt. (41) 0

The remainder of this section is organized as follows. In Sect. 2.1 we prove that U and W are uniformly continuous, under assumptions on μ and σ that are similar to (F1) and (F3), but slightly weaker. Then in Sect. 2.2, we show that Uμ+μs ,σ is a viscosity solution of (P), and prove a similar result for Wμ,σ . This result, Theorem 3 in Sect. 2.2, follows from classical optimal control theory [6], and (P) is exactly the Hamilton–Jacobi–Bellman equation for the variational (optimal-control) problem (36). For more information on Hamilton–Jacobi equations and optimal control, we refer the reader to [6]. 2.1 Regularity Hölder or Lipschitz regularity of the value function in optimal control theory is a standard classical result [6]. However, it is typically assumed that x → μ,σ (x, p) is uniformly continuous, which is not compatible with (F1). We show here that the specific form of μ,σ allows us to show that Uμ+μs ,σ and Wμ,σ are uniformly continuous, provided the discontinuities in μ occur along monotone increasing curves. Since it is useful later, we will slightly weaken the hypothesis (F1), and allow μ to be “badly behaved” within a narrow tube of the monotone curves Γi . This weakened hypothesis is specifically designed so that the regularity result applies to inf- and sup-convolutions of functions satisfying (F1). Inf- and sup-convolutions are commonly used for regularization in the theory of viscosity solutions [6,16]. The weakened hypothesis requires the following notation; for θ ≥ 0 define   Γi,θ = x ∈ [0, ∞)2 : dist(x, Γi ) ≤ θ , (42)   Ωi,θ = x ∈ Ωi : dist(x, Γi ) > θ and dist(x, Γi+1 ) > θ , (43)   (44) Γθ = x ∈ [0, ∞)2 : dist(x, Γ ) ≤ θ ,   (45) Ωθ = x ∈ Ω : dist(x, Γ ) > θ . The weakened version of (F1) is the following: (F1*) The function μ : [0, ∞)2 → [0, ∞) is bounded and upper semicontinuous, μ|Ωθ = 0, and there exists a constant Cli p such that for every i ∈ Z, μ|Ωi,θ is Lipschitz continuous with constant Cli p . We now give the regularity result for W . Theorem 2 Suppose that μ satisfies (F1*) for θ ≥ 0, and suppose that σ : [0, ∞)2 → [0, ∞) is bounded and Borel-measurable. Then for every R > 0 there exist a modulus of continuity ω, and a constant C = C(Cli p , μ∞ , σ ∞ , R) > 0 such that   |Wμ,σ (z, x) − Wμ,σ (z, y)| ≤ C |x − y| + ω(|x − y|) + ω(θ ) , (46) for all x, y, z ∈ [0, R]2 with x, y  z. Furthermore, ω depends only on Γ, {Γi }i∈Z and R > 0.

123

Directed Last Passage Percolation

915

Proof Let R > 0. We will prove the result for z = 0; the case of z  = 0 is very similar. For simplicity of notation, let us set V (x) = Wμ,σ (0, x). Notice that we can reduce the proof to the case where x, y ∈ [0, R]2 with x  y. Indeed, let x, y ∈ [0, R]2 and set x  = (min(x1 , y1 ), min(x2 , y2 )). Then we have |U (x) − U (y)| ≤ |U (x) − U (x  )| + |U (y) − U (x  )|, and x   x and x   y. Thus let us assume that x  y. Let ε > 0 and let γ ∈ A such that γ (0) = 0, γ (1) = y, and V (y) ≤ J (γ ) + ε. Define     s1 = sup t > 0 : γ (t)  x and s2 = inf t > 0 : γ (t)  x . Without loss of generality, we may assume that γ2 (s2 ) = x2 . Define    γ (t) = min x1 , γ1 (t) , γ2 (t) for t ∈ [0, s2 ]. The proof is split into two steps now. 1. We claim that



|V (x) − V (y)| ≤

s2

s1

 |μ(γ (t)) − μ(γ (t))| γ2 (t) dt + C |x − y| + ε.

where C = C(μ∞ , σ ∞ , R). To see this: First note that γ (s2 )  x and γ (1) = y. It follows that  1  1  (γ (t), γ  (t)) dt ≤ μ∞ γ1 (t) + γ2 (t) dt + 2σ ∞ s2

s2



≤ 2μ∞ |x − y| + 2σ ∞

1

s2

1

s2

γ1 (t) dt



1

s2

(47)

γ1 (t)γ2 (t) dt

γ2 (t) dt

 21

≤ 2μ∞ |x − y| + 2σ ∞ |x − y| = 2(μ∞ + σ ∞ )|x − y|,

(48)

where the second line follows from Hölder’s inequality. We claim now that γ1 (s1 ) = x1 . To see this: suppose to the contrary that γ1 (s1 ) < x1 , which implies that s1 < s2 . By the definition of s1 we must have γ2 (s1 ) = x2 and γ2 (s) > x2 for s > s1 . This contradicts our assumption that γ2 (s2 ) = x2 . Hence γ1 (s1 ) = x1 . Now we have  s2 γ1 (t) dt = γ1 (s2 ) − γ1 (s1 ) ≤ y1 − x1 ≤ |x − y|. (49) s1

Since γ = γ on [0, s1 ] and γ (s2 ) = x we have  s2 (γ (t), γ  (t)) dt V (y) − V (x) ≤ J (γ ) + ε −  =

0 s2





(γ (t), γ (t)) − (γ (t), γ (t)) dt +



≤



1

(γ (t), γ  (t)) dt + ε

s2

s1 (48)



s2

s1

(γ (t), γ  (t)) − (γ (t), γ  (t)) dt +C|x − y| + ε, ! "

(50)

A

123

916

J. Calder

where C = C(μ∞ , σ ∞ ). If s1 = s2 then the claim (47) follows from (50). So suppose that s1 < s2 . Since γ 1 (t) = 0 and γ 2 (t) = γ2 (t) for t ∈ (s1 , s2 ), we have  s2  A= (μ(γ (t)) − μ(γ (t))) γ2 (t) + μ(γ (t))γ1 (t) + 2σ (γ (t)) γ1 (t)γ2 (t) dt s  s2  1s2  |μ(γ (t)) − μ(γ (t))| γ2 (t) dt + μ∞ γ1 (t) dt ≤ s1



+ 2σ ∞ (49)



s2

≤

s1

s2 s1

γ1 (t) dt



s2

s1

γ2 (t) dt

1

s1

2

 |μ(γ (t)) − μ(γ (t))| γ2 (t) dt + C(μ∞ , σ ∞ , R) |x − y|,

(51)

which establishes (47). 2. We claim that  s2   |μ(γ (t)) − μ(γ (t))| γ2 (t) dt ≤ C |x − y| + ω(|x − y|) + ω(θ ) + θ , (52) s1

where C = C(Cli p , R, μ∞ , σ ∞ ). Notice that once (52) is established, the proof is completed by combining (52) with (47) and sending ε → 0. ∞ Since the collection of curves {Γi }i=−∞ is locally finite, we may assume that Γ1,θ , . . . , Γ M,θ are the only tubular neighborhoods that have a non-empty intersection with [0, R]2 . Since Γi is continuous and strictly increasing, we can parameterize the portion of Γi that intersects [0, R]2 as follows:

Γi : t → (t, f i (t)), t ∈ Ii , where f i : Ii → [0, ∞) is continuous and strictly increasing, and Ii is a closed interval in [0, R]. Similarly we can parameterize Γ as Γ : t → (t, f (t)), t ∈ [0, 1], where f : [0, 1] → [0, 1] is continuous and strictly decreasing. Note that the functions f 1 , . . . , f M , f share a common modulus of continuity ω, by virtue of their compact domains. We also note that ω and M depend only on Γ, {i }i∈Z , and R > 0. To prove (52), first set c = ω(θ ) + θ . A simple computation shows that dist((t, f i (t) + c), Γi ) > θ

and

dist((t, f i (t) − c), Γi ) > θ,

(53)

for any t ∈ Ii . A similar statement holds for Γ and f . For each i ∈ {1, . . . , M}, we define m i+ = and

sup

Ii ∩[x1 ,y1 ]

f i , and m i− =

inf

Ii ∩[x1 ,y1 ]

fi ,

  K i = t ∈ (s1 , s2 ) : (x1 , m i− − c)  γ (t)  (y1 , m i+ + c) .

(54)

Similarly we set m+ =

sup

[0,1]∩[x1 ,y1 ]

f, and m − =

inf

[0,1]∩[x1 ,y1 ]

f,

  K = t ∈ (s1 , s2 ) : (x1 , m − − c)  γ (t)  (y1 , m + + c) .

123

(55)

Directed Last Passage Percolation

917

and H = (s1 , s2 ) \ (K ∪ K 1 ∪ · · · ∪ K M )

(56)

By the definition of m i± and m ± we have m i+ − m i− ≤ ω(y1 − x1 ) and m + − m − ≤ ω(y1 − x1 ).

(57)

It follows from (53)–(56), (F1*), and the fact that γ is monotone, that whenever t ∈ H we have either μ(γ (t)) = μ(γ (t)) = 0 or μ(γ (t)) − μ(γ (t)) = μi,θ (γ (t)) − μi,θ (γ (t)), for some i ∈ {0, . . . , M}. Thus, invoking (F1*), we have |μ(γ (t)) − μ(γ (t))| ≤ Cli p |γ (t) − γ (t)| ≤ Cli p |x − y|,

(58)

for all t ∈ H . For any i ∈ {1, . . . , M}, we have   |μ(γ (t)) − μ(γ (t))|γ2 (t) dt ≤ 2μ∞

γ2 (t) dt Ki ≤ 2μ∞ |m i+ − m i− + 2c| (57) ≤ 2μ∞ ω(|x − y|) + 4μ∞ (ω(θ ) + θ ).

Ki

(59)

We have an identical estimate when K i is replaced by K . Combining (58) with (59) we have  s2 |μ(γ (t)) − μ(γ (t))| γ2 (t) dt s1   |μ(γ (t)) − μ(γ (t))| γ2 (t) dt + |μ(γ (t)) − μ(γ (t))| γ2 (t) dt = H



≤ Cli p |x − y|

s2

s1

 + K

γ2 (t) dt +

K ∪K 1 ∪···∪K M

M   i=1

Ki

|μ(γ (t)) − μ(γ (t))| γ2 (t) dt

|μ(γ (t)) − μ(γ (t))| γ2 (t) dt

≤ Cli p R|x − y| + 2(M + 1)μ∞ ω(|x − y|) + 4(M + 1)μ∞ (ω(θ ) + θ ), (60) which establishes (52) and completes the proof.

 

Corollary 1 Suppose that μ satisfies (F1*) for θ ≥ 0, and suppose that σ is bounded and Borel-measurable. Then for every R > 0 there exist a modulus of continuity ω, and a constant C = C(Cli p , μ∞ , σ ∞ , R) > 0 such that   |x − y| + ω(|x − y|) + ω(θ ) , (61) |Wμ,σ (x, z) − Wμ,σ (y, z)| ≤ C for all x, y, z ∈ [0, R]2 with x, y  z. As in Theorem 2, ω depends only on Γ, {Γi }i∈Z and R > 0. Proof The proof follows from Theorem 2 by symmetry.

 

123

918

J. Calder

Remark 1 Notice in Theorem 2 that if θ = 0 then we have the estimate   |Wμ,σ (z, x) − Wμ,σ (z, y)| ≤ C |x − y| + ω(|x − y|) ,

(62)

for all x, y, z ∈ [0, R]2 with x, y ≥ z. Inspecting the proof of Theorem 2, we see that ω is the modulus of continuity of the curves Γ, {Γi }i∈Z as functions over both coordinate axes. Thus, the regularity of W is inherited from the regularity of the curves Γ, {Γi }i∈Z . For example, if the curves Γ, {Γi }i∈Z are Hölder-continuous with exponent α ≤ 1/2 as functions over both coordinate axes, then we have that W (z, ·) ∈ C 0,α ([z 1 , R] × [z 2 , R]) for every R > 0 and its Hölder seminorm depends only on μ∞ , σ ∞ , R, and Cli p . The same remark holds for Corollary 1 and (61). We now plan to use Theorem 2 to prove a similar regularity result for Uμ+μs ,σ . To do this, we relate W and U via the following dynamic programming principle: Proposition 1 Suppose that μ satisfies (F1*) for θ ≥ 0, μs satisfies (F2), and suppose that σ is bounded and Borel-measurable. Then for any y ∈ [0, ∞)2 we have   Uμ+μs ,σ (x) + Wμ,σ (x, y) . max (63) Uμ+μs ,σ (y) = x∈∂ R2+ : x  y

Notice that the boundary source μs is absent in the term Wμ,σ in (63). This allows us to concentrate much of our analysis on Wμ,σ , which involves only the macroscopic inhomogeneities in the bulk R2+ , and then extend our results to hold for Uμ+μs ,σ via the dynamic programming principle (63). Proof We first note that the maximum in (63) is indeed attained, due to the continuity of Uμ+μs ,σ restricted to ∂ R2+ and Corollary 1. If y ∈ ∂ R2+ , then in light of (38), (41) and the fact that μs ≥ 0, the maximum in (63) is attained at x = y and the validity of (63) is trivial. Suppose now that y ∈ R2+ and let v(y) denote the right hand side in (63), and set U = Uμ+μs ,σ . We first show that U ≤ v. Let ε > 0 and γ ∈ A such that γ (0) = 0, γ (1) = y and Jμ+μs ,σ (γ ) ≥ U (y) − ε. Let   s = sup t ∈ [0, 1] : γ (t) ∈ ∂ R2+ . Then we have 0 ≤ s < 1. Set x = γ (s) and

 γ 1 (t) = γ (st) and γ 2 (t) = γ s + t (1 − s) ,

for t ∈ [0, 1]. Then we have U (y) ≤ Jμ+μs ,σ (γ ) + ε = Jμ+μs ,σ (γ 1 ) + Jμ,σ (γ 2 ) + ε ≤ U (x) + W (x, y) + ε. Sending ε → 0 we have U ≤ v. We now show that v ≤ U . Let x ∈ ∂ R2+ be a point at which the maximum is attained in (63) and let ε > 0. Let γ 1 ∈ A with γ 1 (0) = 0, γ 1 (1) = x such that U (x) ≤ Jμ+μs ,σ (γ 1 ) + 3ε . Let z ∈ [x, y] such that z ∈ R2+ and W (x, y) ≤ W (z, y) + 3ε . Let γ 2 ∈ A with γ 2 (0) = z, γ 2 (1) = y such that W (z, y) ≤ Jμ,σ (γ 2 ) + 3ε . We can stitch together γ 1 and γ 2 as follows ⎧ 1 γ (3t), if 0 ≤ t < 13 , ⎪ ⎪ ⎨ γ (t) = x + (3t − 1)(z − x), if 13 ≤ t < 23 , ⎪ ⎪ ⎩ 2 γ (3t − 2), if 23 ≤ t ≤ 1.

123

Directed Last Passage Percolation

919

Then we have ε 3 ≤ Jμ+μs ,σ (γ 1 ) + Jμ,σ (γ 2 ) + ε ≤ Jμ+μs ,σ (γ ) + ε ≤ U (y) + ε,

v(y) = U (x) + W (x, y) ≤ U (x) + W (z, y) +

where we used the fact that γ 2 (t) ∈ R2+ for all t, hence Jμ,σ (γ 2 ) = Jμ+μs ,σ (γ 2 ). Sending ε → 0 we have v ≤ U .   Before continuing with the regularity result for Uμ+μs ,σ , let us introduce a bit of notation. For ξ ∈ Rd+ , let πξ : Rd → [0, ξ ] denote the projection mapping Rd onto the convex set [0, ξ ]. For x ∈ [0, ∞)d , πξ is given explicitly by   πξ (x) = min(x1 , ξ1 ), . . . , min(xd , ξd ) . (64) Corollary 2 Suppose that μ satisfies (F1*) for θ ≥ 0, μs satisfies (F2), and suppose that σ is bounded and Borel-measurable. Then for every R > 0 there exists a modulus of continuity ω, and a constant C = C(Cli p , μ∞ , σ ∞ , μs ∞ , R) > 0 such that   |Uμ+μs ,σ (x) − Uμ+μs ,σ (y)| ≤ C |x − y| + ω(|x − y|) + ω(θ ) , (65) for all x, y ∈ [0, R]2 . As in Theorem 2, ω depends only on Γ, {Γi }i∈Z and R > 0. Proof Let x, y ∈ [0, R]2 and set U = Uμ+μs ,σ and W = Wμ,σ . As in Theorem 2 we may assume that x  y. By Proposition 1, there exists y  ∈ ∂ R2+ with y   y such that U (y) = U (y  ) + W (y  , y). Set

x

= πx

(y  ).

Then since

x

∈

∂ R2+

and

x

(66)

 x, we have by Proposition 1 that

U (x) ≥ U (x  ) + W (x  , x).

(67)

By subtracting (67) from (66) and recalling (38) we have |U (x) − U (y)| = U (y) − U (x) ≤ U (y  ) − U (x  ) + W (y  , y) − W (x  , x) ≤ μ + μs ∞ |x  − y  | + |W (y  , y) − W (x  , y)| + |W (x  , y) − W (x  , x)|. The proof is completed by applying Theorem 2 and Corollary 1 and noting that |x  − y  | ≤ |x − y|.   Of course, Remark 1 holds with obvious modifications for U and (65). Remark 2 The hypothesis that the curves Γi are continuous and strictly increasing cannot in general be weakened to continuous and non-decreasing. For example, consider the case where μ = σ = 1 on [0.5, 1] × [0, 1] and μ = σ = 0 on [0, 0.5) × [0, 1]. Then we have  0, if x ∈ [0, 0.5) × [0, 1], √ Uμ,σ (x) = x1 + x2 − 0.5 + 2 (x1 − 0.5)x2 , if x ∈ [0.5, 1] × [0, 1], which has a discontinuity along the vertical line {x 1 = 0.5}, which would correspond to one of the curves Γi on which μ is discontinuous.

123

920

J. Calder

2.2 Hamilton–Jacobi–Bellman Equation In this section we show in Theorem 3 that Uμ+μs ,σ is a viscosity solution of (P). In fact, (P) is the Hamilton–Jacobi–Bellman equation for the simple optimal control problem [6] defined by Uμ+μs ,σ . For more information on the connection between Hamilton–Jacobi equations and optimal control problems, we refer the reader to [6]. Let us pause momentarily to recall the definition of viscosity solution of H (x, Du) = 0

on

O,

(68)

where O ⊂ Rd is open, H : O × Rd → R is locally bounded with p → H (x, p) continuous for every x ∈ O , and u : O → R is the unknown function. For more information on viscosity solutions of Hamilton–Jacobi equations, we refer the reader to [6,16]. We denote by USC(O ) (resp. LSC(O )) the set of upper semicontinuous (resp. lower semicontinuous) functions on O . For u : O → R, the superdifferential of u at x ∈ O , denoted D + u(x), is the set of all p ∈ Rd satisfying u(y) ≤ u(x) +  p, y − x + o(|x − y|) as O  y → x.

(69)

Similarly, the subdifferential of u at x ∈ O , denoted D − u(x), is the set of all p ∈ Rd satisfying u(y) ≥ u(x) +  p, y − x + o(|x − y|) as O  y → x. (70) Equivalently, we may set D + u(x) = {Dϕ(x) : ϕ ∈ C 1 (O ) and u − ϕ has a local max atx}, and D − u(x) = {Dϕ(x) : ϕ ∈ C 1 (O )

and u − ϕ has a local min at x}.

Definition 1 A viscosity subsolution of (68) is a function u ∈ USC(O ) satisfying lim inf H (y, p) =: H∗ (x, p) ≤ 0 for all x ∈ O and p ∈ D + u(x). y→x

(71)

Similarly, a viscosity supersolution of (68) is a function u ∈ LSC(O ) satisfying lim sup H (y, p) =: H ∗ (x, p) ≥ 0 for all x ∈ O and p ∈ D − u(x).

(72)

y→x

The functions H∗ and H ∗ are the lower and upper semicontinuous envelopes of H with respect to the spatial variable, respectively. We will often say u is a viscosity solution of H (x, Du) ≤ 0 (resp. H (x, Du) ≥ 0) on O , to indicate that u is a viscosity subsolution (resp. supersolution) of (68). If u is a viscosity subsolution and supersolution of (68), then we say that u is a viscosity solution of (68). Notice that viscosity solutions defined in this way are necessarily continuous. Theorem 3 Suppose that μ, σ : [0, ∞)2 → [0, ∞) are Borel-measurable and bounded. Let z ∈ [0, ∞)2 and set V (x) = Wμ,σ (z, x) for x ∈ [z, ∞). If V is continuous then V satisfies # (Vx1 − μ)+ (Vx2 − μ)+ = σ 2 on (z, ∞), (73) min(Vx1 , Vx2 ) ≥ μ on (z, ∞), in the viscosity sense. Recall that [z, ∞) = {y ∈ R2 : y  z}, and (z, ∞) = {y ∈ R2 : y > z}.

123

Directed Last Passage Percolation

921

Proof The proof is based on a standard technique from optimal control theory for relating variational problems to Hamilton–Jacobi equations [6]. The proof is very similar to [13, Theorem 2]. We will only sketch parts of the proof here. The proof is based on the following dynamic programming principle   V (y) = sup V (x) + W (x, y) , (74) x∈∂ Br (y) : x  y

which holds for y ∈ (z, ∞) and r > 0 small enough so that Br (y) ⊂ (z, ∞). The proof of (74) is very similar to the proof of Proposition 1. We now show that V is a viscosity solution of (73). Let y ∈ (z, ∞) and let p ∈ D − V (y). As in [13], we can use the dynamic programing principle to obtain  $  % √ (75) sup − p − μ∗ (y)(1, 1), a + 2σ∗ (y) a1 a2 ≤ 0. a∈R2+

Suppose now that σ∗ (y) = 0. Then we automatically have ( p1 − μ∗ (y))+ ( p2 − μ∗ (y))+ ≥ 0 = σ∗2 (y). Furthermore, it follows from (75) that min( p1 , p2 ) ≥ μ∗ (y), so we are done. Consider now σ∗ (y) > 0. Setting a1 = 1 in (75) we have  √  sup − ( p1 − μ∗ (y)) − ( p2 − μ∗ (y))a2 + 2σ∗ (y) a2 ≤ 0. a2 >0

It follows that p2 > μ∗ (y). By a similar argument we have p1 > μ∗ (y), and hence we have min( p1 , p2 ) > μ∗ (y). This establishes that V is a viscosity solution of min(Vx1 , Vx2 ) ≥ μ on (z, ∞). &

Now set a1 =

p2 − μ∗ (y) and a2 = p1 − μ∗ (y)

&

p1 − μ∗ (y) p2 − μ∗ (y)

(76)

in (75) and simplify to find that ( p1 − μ∗ (y))( p2 − μ∗ (y)) ≥ σ∗ 2 (y). Therefore V is a viscosity solution of (Vx1 − μ)+ (Vx2 − μ)+ ≥ σ 2 on (z, ∞). Let y ∈ (z, ∞) and let p ∈ D + V (y). Utilizing the dynamic programing principle (74) again we have  $  % sup − p − μ∗ (y)(1, 1), a + 2σ ∗ (y) ≥ 0. (77) a∈R2+ : a1 a2 =1

If min( p1 , p2 ) ≤ μ∗ (y) then we immediately have ( p1 − μ∗ (y))+ ( p2 − μ∗ (y))+ = 0 ≤ σ ∗ (y)2 . If min( p1 , p2 ) > μ∗ (y) then we have that $ % lim sup − p − μ∗ (y)(1, 1), a + 2σ ∗ (y) = −∞. |a|→∞ : a∈R2+

123

922

J. Calder

It follows that the supremum in (77) is attained at some a ∗ ∈ R2+ . Introducing a Lagrange multiplier λ > 0, the necessary conditions for a ∗ to be a maximizer of the constrained maximization problem (77) are a1∗ = λ( p2 − μ∗ (y)), a2∗ = λ( p1 − μ∗ (y)), and a1∗ a2∗ = 1. 1

1

It follows that λ = ( p1 − μ∗ (y))− 2 ( p2 − μ∗ (y)) 2 and a ∗ is given by (76). Substituting this into (77) we find that ( p1 − μ∗ (y))( p2 − μ∗ (y)) ≤ σ ∗ 2 (y), and hence V is a viscosity solution of (Vx1 − μ)+ (Vx2 − μ)+ ≤ σ 2 on (z, ∞),  

which completes the proof.

Remark 3 It follows from Theorem 3 that U = Uμ+μs ,σ is a viscosity solution of (P) and satisfies min(Ux1 , Ux2 ) ≥ μ on R2+ (78) in the viscosity sense. Indeed, we can simply apply Theorem 3 with μ + μs in place of μ and z = 0, in which case we have U (x) = Wμ+μs ,σ (0, x). 3 Comparison Principle We study here the general Hamilton–Jacobi equation H (x, Du) = 0 u=ϕ

on (z, ∞),

#

on ∂(z, ∞).

(79)

Here, z ∈ [0, ∞)d , ϕ : ∂(z, ∞) → R is continuous and monotone, H : Rd+ × Rd → R is the Hamiltonian, and u : [z, ∞) → R is the unknown function. For simplicity of notation, we will set z = 0 throughout much of this section. The case where z  = 0 follows by a simple translation argument. We place the following assumptions on H : (H1) For every x ∈ Rd+ , the mapping H (x, ·) : Rd → R is monotone non-decreasing. (H2) There exists a modulus of continuity m such that H (x, p) − H (y, p) ≤ m(| p||x − y| + |x − y|)

(80)

for all p ∈ [0, ∞)d and x, y ∈ Rd+ . The assumption (H1) is clearly satisfied by (P), and generalizes the comparison results in our previous work [13], which was focused on the special case of H (x, p) = p1 · · · pd − f (x). The assumption (H2) is standard in the theory of viscosity solutions [16]. We now give a comparison principle for Hamiltonians H satisfying (H1) and (H2). Theorem 4 Suppose that H satisfies (H1) and (H2). Let u ∈ USC([0, ∞)d ) be a viscosity solution of H (x, Du) ≤ 0 in Rd+ , (81)

123

Directed Last Passage Percolation

923

let v ∈ LSC([0, ∞)d ) be a monotone viscosity solution of H (x, Dv) ≥ a in Rd+ ,

(82)

where a > 0, and suppose that u ≤ v on ∂ Rd+ . Then u ≤ v on Rd+ . The proof of Theorem 4 is based on the auxiliary function technique, which is standard in the theory of viscosity solutions [6,16], with modifications to incorporate the lack of compactness resulting from the unbounded domain Rd+ . A standard technique for dealing with unbounded domains is to assume the Hamiltonian H is uniformly continuous in the gradient p and modify the auxiliary function (see, for example [6, Theorem 3.5]). Since (P) is not uniformly continuous in the gradient, we cannot use this technique. In our previous work [13], we included an additional boundary condition at infinity to induce compactness. It turns out that this is not necessary, and in the proof of Theorem 4, we instead heavily exploit the structure of the Hamiltonian, namely (H1), to produce the required compactness. Proof Since v is monotone (i.e., non-decreasing), it is bounded below by v(0). Without loss of generality we may assume that v(0) = 0. Let h > 0 and set vh (x) = v(x) + h(x1 + x2 ). It follows from (H1) that vh is a viscosity solution of (82). Assume by way of contradiction that supRd (u − vh ) > 0. Let Ψ : R → R be a C 1 function satisfying + ⎫ Ψ (t) = t for all t ≤ 1, ⎪ ⎬ Ψ (t) ≤ 2 for all t ∈ R, (83) ⎪ ⎭  0 < Ψ (t) ≤ 1 for all t ∈ R. For c > 0 set u(x) = cΨ (c−1 u(x)), and choose c large enough so that δ := sup(u − vh ) > 0. Rd+

Since Ψ is C 1 and Ψ  > 0, it is a standard application of the chain rule [6] to show that u is a viscosity solution of  H x, Ψ  (c−1 u(x))−1 Du ≤ 0 on Rd+ . (84) Since Ψ  (t) ∈ (0, 1] for all t ≥ 0, we can apply (H1) to (84) to find that u is a viscosity solution of (81). For α > 0 we define α Φα (x, y) = u(x) − vh (y) − |x − y|2 , (85) 2 and Mα = supRd ×Rd Φα . Since u ≤ 2c and vh ≥ 0, we have by (85) that +

+

√ 2 c |x − y| ≤ √ whenever Φα (x, y) ≥ 0. α

(86)

Since vh (y) ≥ h(y1 + y2 ) we have Φα (x, y) ≤ 2c − h(y1 + y2 ).

(87)

Since Φα is upper semicontinuous and Mα ≥ δ > 0, it follows from (86) and (87) that for every α > 0 there exist xα , yα ∈ [0, ∞)d such that Φα (xα , yα ) = Mα ≥ δ > 0,

(88)

123

924

J. Calder

and yα,1 + yα,2 ≤

2c . h

(89)

Furthermore, by (86) and (89) we see that, upon passing to a subsequence if necessary, we have xα , yα → x0 as α → ∞ for some x0 ∈ [0, ∞)d . Since (x, y) → u(x) − vh (y) is upper semicontinuous we have lim sup Mα ≤ lim sup u(xα ) − vh (yα ) ≤ u(x0 ) − vh (x0 ). α→∞

α→∞

Since Mα ≥ u(x0 ) − vh (x0 ) for all α we have that Mα → u(x0 ) − v(x0 ) = δ > 0 as α → ∞ and hence α|xα − yα |2 −→ 0. (90) Since u ≤ vh on ∂ Rd+ we must have x0 ∈ Rd+ , and therefore xα , yα ∈ Rd+ for α large enough. Set p = α(xα − yα ). By (88) we have that p ∈ D + u(xα ) ∩ D − vh (yα ). Therefore we have H (xα , p) ≤ 0 and H (yα , p) ≥ a. Subtracting the above inequalities and invoking (H2) we have 0 < a ≤ H (yα , p) − H (xα , p) ≤ m(| p||xα − yα | + |xα − yα |) ≤ m(α|xα − yα |2 + |xα − yα |). Sending α → ∞ we arrive at a contradiction. Therefore u ≤ vh , and sending h → 0+ completes the proof.   We now aim to extend this comparison principle to Hamiltonians with discontinuous spatial dependence. The techniques we use here are a generalization of our previous work on the longest chain problem [13]. We make the following definitions. Definition 2 Given a function u : [z, ∞) → R and ξ ∈ [z, ∞), we define the ξ -truncation of u by u ξ := u ◦ πξ , where πξ is the projection mapping Rd onto [0, ξ ] defined in (64). Definition 3 Let u be a viscosity solution of H (x, Du) ≤ 0 on (z, ∞).

(91)

We say that u is truncatable if for every ξ ∈ (z, ∞), the ξ -truncation u ξ is a viscosity solution of (91). This notion of truncatability is in spirit the same as [13, Definition 2.7], though the exact definition is slightly different for notational convenience. We first show that the value function W is truncatable. Proposition 2 Suppose that μ, σ : [0, ∞)2 → [0, ∞) are Borel-measurable and bounded. Let z ∈ [0, ∞)2 and define V (x) = Wμ,σ (z, x) for x ∈ [z, ∞). If V is continuous then V is a truncatable viscosity solution of (Vx1 − μ)+ (Vx2 − μ)+ = σ 2 on (z, ∞).

123

(92)

Directed Last Passage Percolation

925

Proof It follows from Theorem 3 that V is a viscosity solution of (92). We need only show that V is truncatable. Let ξ ∈ (z, ∞), let χ : [0, ∞)2 → {0, 1} denote the characteristic function of [z, ξ ], and set V = Wχ ·μ,χ ·σ (z, ·). By the definition of V and χ we have V (x) = V (x) = V ξ (x) for any x ∈ [z, ξ ]. Let x ∈ [z, ∞) \ [z, ξ ], ε > 0, and let γ ∈ A with γ (0) = z, γ (1) = x such that V (x) ≤ Jχ ·μ,χ ·σ (γ ) + ε. Let γ 1 denote the portion of γ inside [z, ξ ], let γ 2 denote the remaining portion of γ , and reparametrize γ 1 and γ 2 so that γ 1 , γ 2 : [0, 1] → R2 . Letting y = γ 1 (1) ∈ [z, ξ ] we have V (x) ≤ Jχ ·μ,χ ·σ (γ 1 ) + Jχ ·μ,χ ·σ (γ 2 ) + ε = Jμ,σ (γ 1 ) + ε ≤ V (y) + ε. Since y  x and y ∈ [z, ξ ], we also have V (x) ≥ V (y) = V (y). It follows that V (x) =

sup y∈[z,ξ ] : y x

V (y).

By continuity of V , the supremum above is attained, and the maximizing argument of y is exactly y = πξ (x)—the projection of x onto [0, ξ ]. Therefore we have V (x) = V (πξ (x)). Since x is arbitrary, we see that V = V ◦ πξ = V ξ , the ξ -truncation of V . Since V ξ = V ◦πξ is continuous, it follows from Theorem 3 that V ξ is a viscosity solution of (Vx1 − χμ)+ (Vx2 − χμ)+ ≤ χσ 2 on (z, ∞). Since 0 ≤ χ ≤ 1 and t → ( p1 − t)+ ( p2 − t)+ is monotone decreasing, it follows that V ξ is viscosity subsolution of (92), which completes the proof.   We now show that truncatability enjoys a useful L ∞ -stability property. Proposition 3 Let z ∈ R2+ and for each k ≥ 1 suppose that u k ∈ C([z, ∞)) is a truncatable viscosity solution of Hk (x, Du k ) ≤ 0 on (z, ∞). (93) If u k → u locally uniformly, for some u ∈ C([z, ∞)), then u is a truncatable viscosity solution of H (x, Du) ≤ 0 on (z, ∞), (94) where H (x, p) := lim inf Hk (y, p). k→∞ y→x

We should note that the lim inf operation defining H is taken jointly as k → ∞ and y → x. This is a standard operation in the theory of viscosity solutions (see [16, Sect. 6]), and it can be written more precisely for a function f : O → R as *  1 . lim inf f k (y) = lim inf f k (x) : k ≥ j, x ∈ O and |y − x| ≤ k→∞ j→∞ j y→x

Proof It is a standard result (see [16, Remark 6.3]) that u is a viscosity solution of (94). To ξ see that u is truncatable: Fix ξ ∈ (z, ∞), let u ξ be the ξ -truncation of u, and let u k be the ξ ξ -truncation of u k . Since u k is truncatable, we have that u k is a viscosity solution of (93) for ξ every k. Furthermore, we have u k → u ξ locally uniformly, and therefore u ξ is a viscosity solution of (94). Thus u is truncatable.  

123

926

J. Calder

We now relax (H2) and allow H to have discontinuous spatial dependence. Given a set O ⊂ Rd+ we assume H satisfies (H3)O There exists a modulus of continuity m such that for all ξ ∈ O there exists εξ > 0 and vξ ∈ Sd−1 such that H (y, p) − H (y + εv, p) ≤ m(| p|ε + ε) for all p ∈

Rd ,

y ∈ Bεξ (ξ ), ε ∈ (0, εξ ), and v ∈

Sd−1

(95)

with |v − vξ | < εξ .

This hypothesis is similar to one used by Deckelnick and Elliott [17] to prove uniqueness of viscosity solutions to Eikonal-type Hamilton–Jacobi equations with discontinuous spatial dependence. It is also a generalization of the cone condition used in our previous work [13]. If we assume the subsolution is truncatable, then we can prove the following comparison principle, which holds for Hamiltonians H with discontinuous spatial dependence. Theorem 5 Suppose that H satisfies (H3)O for some O ⊂ Rd+ . Let u ∈ C([0, ∞)d ) be a truncatable viscosity solution of (81) and let v ∈ C([0, ∞)d ) be a monotone viscosity solution of (82). Suppose that u ≤ v on [0, ∞)d \ O . Then u ≤ v on Rd+ . The proof of Theorem 5 is similar to [13, Theorem 2.8], so we postpone it to the appendix. For the remainder of the section we set H (x, p) = ( p1 − μ(x))+ ( p2 − μ(x))+ − σ 2 (x).

(96)

Our aim now is to apply the comparison principles from Theorems 4 and 5 to obtain a comparison principle, and a perturbation result, for the Hamilton–Jacobi equation (P). First we need to show that (H2) and (H3)O are satisfied by H given in (96). Proposition 4 Suppose that μ, σ : [0, ∞)2 → [0, ∞), and let H be given by (96). Then for any x, y ∈ R2+ H (y, p) − H (x, p) ≤ 2| p|(μ(x) − μ(y))+ + σ 2 (x) − σ 2 (y).

(97)

Proof Let p ∈ [0, ∞)2 , and set h(t) = ( p1 − t)+ ( p2 − t)+ so that H (x, p) = h(μ(x)) − σ 2 (x). Suppose first that μ(y) < min( p1 , p2 ). Since h is convex, we have h(μ(x)) − h(μ(y)) ≥ h  (μ(y))(μ(x) − μ(y)) = −( p1 + p2 − 2μ(y))(μ(x) − μ(y)). Since p1 + p2 − 2μ(y) ≥ 0 we have h(μ(y)) − h(μ(x)) ≤ ( p1 + p2 − 2μ(y))(μ(x) − μ(y)) ≤ ( p1 + p2 − 2μ(y))(μ(x) − μ(y))+ ≤ ( p1 + p2 )(μ(x) − μ(y))+ . Therefore we have h(μ(y)) − h(μ(x)) ≤ 2| p|(μ(x) − μ(y))+ . If μ(y) ≥ min( p1 , p2 ) then we have h(μ(y)) = 0 ≤ h(μ(x)), and hence (98) holds.

(98)  

Remark 4 It follows from Proposition 4 that H satisfies (H2) if μ and σ 2 are globally Lipschitz continuous on R2+ .

123

Directed Last Passage Percolation

927

Corollary 3 Suppose that μ and σ 2 are non-negative and globally Lipschitz continuous on R2+ . Let u ∈ USC([0, ∞)2 ) be a viscosity solution of (u x1 − μ)+ (u x2 − μ)+ ≤ σ 2 on R2+ ,

(99)

and let v ∈ LSC([0, ∞)2 ) be a monotone viscosity solution of (vx1 − μ)+ (vx2 − μ)+ ≥ σ 2 on R2+ .

(100)

Furthermore, suppose that     x ∈ R2+ : μ(x) = 0 ⊃ x ∈ R2+ : σ (x) = 0 .

(101)

Then u ≤ v on ∂ R2+ implies u ≤ v on R2+ . Proof We claim that min(vx1 , vx2 ) ≥ μ on R2+ ,

(102)

in the viscosity sense. To see this, let x ∈ R2+ and let p ∈ D − v(x). Then we have ( p1 − μ(x))+ ( p2 − μ(x))+ ≥ σ (x)2 . If σ (x) > 0, then we must have min( p1 , p2 ) ≥ μ(x) as desired. If σ (x) = 0, then by (101) we have μ(x) = 0, and we have min( p1 , p2 ) ≥ 0 = μ(x) by virtue of the monotonicity of v. √ Let a > 0 and set v(x) = v(x) + a(x1 + x2 ). By (100) and (102) we see that v is a viscosity solution of (v x1 − μ)+ (v x2 − μ)+ ≥ σ 2 + a on R2+ . By Proposition 4 and Remark 4 we see that (H1) and (H2) are satisfied. Therefore we can apply Theorem 4 to find that u ≤ v. Sending a → 0 completes the proof.   Recall that μ and σ 2 are not independent functions in the DLPP problem, even though we have treated them as such for much of the analysis. From this point on, we will need to recall their relationship, as it is important for proving uniqueness in (P). Specifically, we need to assume that μ and σ 2 satisfy (F3) for the same choice of ζ at each x ∈ Γi . When this holds, we√say that μ and σ 2 simultaneously satisfy (F3). Since σ = μ for exponential DLPP and σ = μ(1 + μ) for geometric DLPP, σ is always a monotone increasing function of μ, and hence μ and σ 2 simultaneously satisfy (F3) in both cases. We recall that Ω, i , Γi , and (F1)–(F3) are defined in Sect. 1.1, and that μ ≡ 0 on Ω. Proposition 5 Let μ and σ 2 simultaneously satisfy (F1) and (F3). Then H given by (96) satisfies (H3)O with O = R2+ \ Ω. Proof Let ξ ∈ O . If ξ ∈ Ωi , then we can choose εξ small enough so that B2εξ (ξ ) ⊂ Ωi . By Proposition 4 we see that any choice for vξ will suffice since μ and σ 2 are Lipschitz with constant Cli p when restricted to Ωi . If ξ ∈ Γi for some√i, then let ζ be as given in (F3). Assume for now that ζ = −1, and set vξ = (1, −1)/ 2. Let εξ > 0 be less than half the value of ε from (F3), and then choose εξ > 0 smaller, if necessary, so that B2εξ (ξ ) has an empty intersection with Γ and all other Γ j , and εξ ≤ 1/2. Let μi and σi2 denote the Lipschitz extensions of μ|Ωi and σ 2 |Ωi 2 . Then (F3) implies to Ωi , respectively, and make the same definitions for μi−1 and σi−1

123

928

J. Calder

2 on B 2 that μi ≥ μi−1 and σi2 ≥ σi−1 2εξ (ξ ) ∩ Γi . Furthermore, since μ and σ are upper semicontinuous, we have μ = μi and σ = σi on B2εξ (ξ ) ∩ Γi . Let y ∈ Bεξ (ξ ), ε < εξ , p ∈ R2 , and v ∈ Sd−1 with |v − vξ | < εξ . If y + εv ∈ Ωi , then since Γi is monotone, |v − vξ | ≤ 21 , and y ∈ B2εξ (ξ ), we must have that y ∈ Ωi . Since μi and σi2 are Lipschitz on Ωi ∩ B2εξ (ξ ), we can invoke Proposition 4 to show that (H3)O holds. Now suppose that y + εv ∈ Ωi−1 . If y ∈ Ωi−1 , then (H3)O holds as before, so assume that y ∈ Ωi . Let ε  > 0 such that y + ε  v ∈ Γi . Then we have

μ(y + εv) − μ(y) = μi−1 (y + εv) − μi (y + ε  v) + μi (y + ε  v) − μi (y) ≤ μi−1 (y + εv) − μi−1 (y + ε  v) + μi (y + ε  v) − μi (y) ≤ 2Cli p ε, where we used the fact that μi ≥ μi−1 on Γi ∩ B2εξ (ξ ). We have an identical estimate for   σ 2 , and the proof is completed by invoking Proposition 4. Corollary 4 Let μ and σ 2 simultaneously satisfy (F1) and (F3). Let u ∈ C([0, ∞)2 ) be a truncatable viscosity solution of (99), let v ∈ C([0, ∞)2 ) be a monotone viscosity solution of (100), and suppose that (101) holds. Then u ≤ v on Ω ∪ ∂ R2+ implies u ≤ v on R2+ . The proof of Corollary 4 is similar to Corollary 3. We now prove an important perturbation result. Roughly speaking, it says that if we smooth out the macroscopic mean μ and variance σ (i.e., remove the discontinuities), then the resulting change in the value function W is uniformly small. This result is used in the proof of our main result, Theorem 1. The proof relies on the uniqueness of truncatable viscosity solutions of (P) (Theorem 5 and Corollary 4), and the result can then be used to prove a comparison principle for (P) without the truncatability assumption (see Theorem 7). Theorem 6 Let μ and σ 2 satisfy (101) and simultaneously satisfy (F1), (F3). Let μk , σk2 ∈ C 0,1 ([0, ∞)2 ) satisfy (F1*) with θ = k1 . Furthermore suppose that μ∗ (x) ≤ lim inf μk (y), μ∗ (x) ≥ lim sup μk (y),

(103)

σ∗ (x) ≤ lim inf σk (y), σ ∗ (x) ≥ lim sup σk (y),

(104)

k→∞ y→x

and

k→∞ y→x

k→∞ y→x

k→∞ y→x

for all x ∈ R2+ . Then for every z ∈ [0, ∞)2 we have Wμk ,σk (z, ·) −→ Wμ,σ (z, ·) locally uniformly on [z, ∞). Proof For simplicity, let us set Vk (x) = Wμk ,σk (z, x) and V (x) = Wμ,σ (z, x) for x ∈ [z, ∞). Since μk , σk2 ∈ C 0,1 ([0, ∞)2 ), we can apply Theorem 2 with θ = 0 to find that Vk is continuous on [z, ∞). We can apply Theorem 2 again with θ = 1/k to show that for every R > max(z 1 , z 2 ), there exists C = C(Cli p , μ∞ , σ ∞ , R) and a modulus of continuity ω such that  |Vk (x) − Vk (y)| ≤ C( |x − y| + ω(|x − y|) + ω(k −1 )) (105) for all x, y ∈ [z 1 , R] × [z 2 , R]. This approximate Hölder estimate is sufficient to apply a slightly modified version of the Arzelà-Ascoli theorem (see, for instance, [12, Theorem 2]). Therefore, by passing to a subsequence if necessary, there exists v ∈ C([z, ∞)) such

123

Directed Last Passage Percolation

929

that Vk → v locally uniformly on [z, ∞). By Proposition 2, Vk is a monotone truncatable viscosity solution of (Vk,x1 − μk )+ (Vk,x2 − μk )+ = σk 2 on (z, ∞).

(106)

Since Vk → v locally uniformly and (103)–(104) hold, we can apply Proposition 3, and classical results from the theory of viscosity solutions [16], to find that v is a monotone truncatable viscosity solution of (vx1 − μ)+ (vx2 − μ)+ = σ 2 on (z, ∞).

(107)

We claim that v = V on ∂(z, ∞). To see this: Let x ∈ ∂(z, ∞), hence xi = z i for some i. Without loss of generality, assume that x1 = z 1 . Then by (40) and Fatou’s lemma we have  x2 v(x) = lim Vk (x) = lim μk (z 1 , t) dt k→∞ k→∞ z  x2 2 lim sup μk (z 1 , t) dt ≤  ≤

z2 k→∞ x2

μ(z 1 , t) dt = V (x),

z2

where the last line follows from (103) and the fact that μ is upper semicontinuous. By a similar argument with Fatou’s lemma we have  x2 v(x) ≥ μ∗ (z 1 , t) dt. (108) z2

Notice that (F1) implies that μ∗ = μ on Ωi for all i and on Ω. Hence, all the points x ∈ [0, ∞)2 for which μ∗ (x)  = μ(x) are contained in ∪i∈Z Γi ∪ Γ . Since the curves Γi are strictly increasing and Γ is strictly decreasing, the curve t → (z 1 , t) for t ∈ [z 2 , x2 ] has a finite number of intersections with ∪i∈Z Γi ∪ Γ . It follows that  x2  x2 (108) μ∗ (z 1 , t) dt = μ(z 1 , t) dt = V (x), v(x) ≥ z2

z2

and hence v(x) = V (x), which establishes the claim. By Proposition 5, H given by (96) satisfies (H3)O for O = R2+ \ Ω. By (F1*) and (39) we have Vk (x) = 0 for x ∈ Ωθ ∩ [z, ∞), and hence v(x) = 0 for x ∈ Ω ∩ [z, ∞). Similarly, we have that V (x) = 0 for x ∈ Ω ∩ [z, ∞). It follows that v = V on [z, ∞) \ O , and by applying a translated form of Corollary 4 to find that v = V on [z, ∞)2 .   Remark 5 Sequences generated by inf- and sup-convolutions of μ and σ 2 satisfy the hypotheses of Theorem 6. Recall that the sup-convolution of μ : [0, ∞)2 → R is defined by   μ(y) − k|x − y| , (109) μk (x) = sup y∈[0,∞)2

and the inf-convolution by μk := −(−μ)k . Corollary 5 Let μ and σ 2 simultaneously satisfy (F1), (F3) and (101), let μk , σk2 ∈ C 0,1 ([0, ∞)2 ) satisfy (F1*) with θ = k1 , and let μs satisfy (F2). If (103)–(104) hold for all x ∈ R2+ then Uμk +μs ,σk −→ Uμ+μs ,σ locally uniformly on [0, ∞)2 .

123

930

J. Calder

Proof Fix y ∈ [0, ∞)2 . By Proposition 1 we have   Uμk +μs ,σk (x) + Wμk ,σk (x, y) , max Uμk +μs ,σk (y) = x∈∂ R2+ : x  y

and Uμ+μs ,σ (y) =

max

x∈∂ R2+ : x  y

  Uμ+μs ,σ (x) + Wμ,σ (x, y) .

(110)

(111)

Arguing by symmetry, it follows from Theorem 6 that Wμk ,σk (·, y) −→ W (·, y) uniformly on [0, y].

(112)

It follows from (37) and a similar argument as in Theorem 6 that Uμk +μs ,σk (x) → Uμ+μs ,σ (x) for any x ∈ ∂ R2+ . By the Arzelà-Ascoli Theorem we find that Uμk +μs ,σk −→ Uμ+μs ,σ uniformly on [0, y] ∩ ∂ R2+ .

(113)

Combining (110)–(113), we have that Uμk +μs ,σk (y) → Uμ+μs ,σ (y). Locally uniform convergence follows again from the Arzelà-Ascoli Theorem.   Theorem 7 Let μ and σ 2 simultaneously satisfy (F1), (F3) and (101), and let μs satisfy (F2). Let u ∈ C([0, ∞)2 ) be a viscosity solution of (99) and let v ∈ C([0, ∞)2 ) be a monotone viscosity solution of (100). Then if u ≤ ϕ ≤ v on ∂ R2+ , where ϕ is given in the statement of Theorem 1, then u ≤ v on R2+ . Proof Let μk , σ 2,k and μk , σk2 be the sup- and inf-convolutions of μ and σ 2 as defined in (109) (see Remark 5), respectively. To simplify notation, let us write U k := Uμk +μs ,σ k , Uk := Uμk +μs ,σk , and U := Uμ+μs ,σ . By definition we have Uk ≤ U ≤ U k , and by Corollary 5 and Remark 5 we have Uk , U k → U locally uniformly on [0, ∞)2 as k → ∞. Since μk ≤ μ and σk ≤ σ we have that v is a viscosity solution of (vx1 − μk )+ (vx2 − μk )+ ≥ σk 2 on R2+ . By Theorem 3, Uk is a viscosity solution of (Uk,x1 − μk )+ (Uk,x2 − μk )+ = σk 2 on R2+ .

1 Furthermore, we have Uk = ϕk ≤ ϕ ≤ v on ∂ R2+ where ϕk (x) = (x1 + x2 ) 0 μk (t x) + μs (t x) dt. Since μk and σk2 are globally Lipschitz we can apply Corollary 3 to obtain Uk ≤ v. Sending k → ∞ we have U ≤ v. By a similar argument we can prove that u ≤ U , which completes the proof.  

4 Proof of Main Result In this section we give the proof of our main result, Theorem 1. We first have a preliminary convergence result on the interior (0, ∞)2 , which we later adapt to account for the boundary source μs . For N ≥ 1 we define   (114) w N (x, y) := L N x + 1x ; N y , where and L is defined in (10).

123

 1x = 1{x1 =0} , 1{x2 =0} ,

(115)

Directed Last Passage Percolation

931

Lemma 1 Assume μ satisfies (F1) and (F3). Suppose that the weights X (i, j) satisfy (11) and are either all exponential, or all geometric random variables, consructed as in Sect. 1.1. √ In the exponential case, set σ = μ, and in the geometric case, set σ = μ(1 + μ). Then for every y ∈ (0, ∞)2 we have 1 w N (·, y) −→ Wμ,σ (·, y) uniformly on [0, y], N with probability one. Proof Let y ∈ (0, ∞)2 . Let μk and μk be the sup- and inf-convolutions of μ, defined in (109) (see Remark 5).In the exponential case,√set σ k = μk and σk = μk , and in the geometric case, set σ k = μk (1 + μk ) and σk = μk (1 + μk ). To simplify notation, let us also set W k := Wμk ,σ k , Wk := Wμk ,σk , and W := Wμ,σ , and note that Wk ≤ W ≤ W k . Notice that by the definition of σ , we have that (101) holds for both the exponential and geometric cases. We can therefore invoke Theorem 6 to find that Wk (x, y) −→ W (x, y) and W k (x, y) −→ W (x, y) for all x ∈ [0, y].

(116)

Let N ≥ 1. In the exponential case, for (i, j) ∈ N2 let X k (i, j) be independent and exponentially distributed with parameter λ = μk (i N −1 , j N −1 ), and let X k (i, j) be independent and exponentially distributed with parameter λ = μk (i N −1 , j N −1 ). In the geometric case, for (i, j) ∈ N2 let X k (i, j) be independent and geometrically distributed with parameter q = (1 + μk (i N −1 , j N −1 ))−1 , and let X k (i, j) be independent and geometrically distributed with parameter q = (1 + μk (i N −1 , j N −1 ))−1 . In either case, set  max X k (i, j), (117) L k (M, N ; Q, P) = p∈(M,N ),(Q,P)

L (M, N ; Q, P) = k

max

p∈(M,N ),(Q,P)

(i, j)∈ p



X k (i, j),

(118)

(i, j)∈ p

and set

    wk,N (x, y) := L k N x + 1x ; N y , and w kN (x, y) := L k N x + 1x ; N y . (119) X k (i,

We can define X k (i, j) and j) on the same probability space as X (i, j) in such a way that X k (i, j) ≤ X (i, j) ≤ X k (i, j) for all (i, j) ∈ N2 with probability one. We therefore have wk,N ≤ w N ≤ w kN with probability one. Since μk , σk , μk , and σ k are continuous on [0, ∞)2 , we can invoke Theorem [33, Theorem 1] to find that 1 1 k wk,N (x, y) −→ Wk (x, y) and w (x, y) −→ W k (x, y), N N N with probability one, for fixed x ∈ [0, y]. We should note that [33, Theorem 1] as stated applies only to exponential DLPP. The proof for geometric DLPP (with weights constructed as in Sect. 1.1) is very similar, with only minor modifications. It follows that for every k ≥ 1 we have 1 1 Wk (x, y) ≤ lim inf w N (x, y) ≤ lim sup w N (x, y) ≤ W k (x, y), N →∞ N N N →∞ with probability one. Sending k → ∞ and recalling (116) we have for every x ∈ [0, y] that 1 w N (x, y) −→ W (x, y) with probability one. N

(120)

123

932

J. Calder

Uniform convergence follows from the fact that x → w N (x, y) and x → W (x, y) are monotone decreasing and x → W (x, y) is uniformly continuous on [0, y]; the proof is similar to [13, Theorem 1].   To incorporate the boundary source μs we need the following lemma, which follows from the law of large numbers. Lemma 2 Let Y1 , . . . , Yn , . . . be a sequence of i.i.d. exponential random variables with mean λ = 1. Let ν : [0, ∞) → [0, ∞) be bounded with a locally finite set of discontinuities, and let f : [0, ∞) → [0, ∞) be non-decreasing with at most polynomial growth. Then we have with probability one that  1 n 1 f (ν(n −1 i)Yi ) −→ E( f (ν(t)Y )) dt as n → ∞, (121) n 0 i=1

where Y is a random variable with the exponential distribution with mean λ = 1. Note that Lemma 2 mimics the constructions of the weights X (i, j) given in Sect. 1.1. When X (i, j) are exponential random variables, we have f (t) = t, and ν = μ + μs , and when X (i, j) are geometric random variables, f (t) = t and ν is defined according to the construction in Sect. 1.1. Proof Let K be a positive integer. Consider the partition of [0, 1] given by 0 = t0 < t1 < · · · < t K −1 < t K = 1, where t j = j/K , and let k j = nt j . Set m j = inf (t j−1 ,t j ] ν and M j = sup(t j−1 ,t j ] ν. Then we have that kj 

n K 1 1 f (ν(n −1 i)Yi ) = n n

f (ν(n

−1

j=1 i=k j−1 +1

i=1

K  1 i)Yi ) ≤ n j=1

kj 

f (M j Yi ), (122)

i=k j−1 +1

where the last inequality follows from the monotonicity of f . Fix j and let Z i = f (M j Yi ). Then Z 1 , . . . , Z n , . . . are i.i.d., and the polynomial growth restriction on f guarantees that the moments of Z i are finite. We therefore have by the law of large numbers that kj nt j  

nt j  1 1  Zi = Z i −→ t j E( f (M j Y )), n n nt j  i=1

i=1

with probability one as n → ∞. Similarly, we have k j−1 1 Z i −→ t j−1 E( f (M j Y )), n i=1

with probability one as n → ∞. It follows that 1 n

kj 

f (M j Yi ) =

i=k j−1 +1

kj k j−1 1 1 Zi − Z i −→ (t j − t j−1 )E( f (M j Y )), n n i=1

i=1

with probability one as n → ∞. Since the above holds for every j = 1, . . . , K , we have from (122) that lim sup n→∞

123

n K  1 f (ν(n −1 i)Yi ) ≤ (t j − t j−1 )E( f (M j Y )), n i=1

j=1

Directed Last Passage Percolation

933

with probability one. By the assumptions on f and ν, t → E( f (ν(t)Y )) is continuous except possibly at points of discontinuity of ν, which are locally finite. Thus t → E( f (ν(t)Y )) is Riemann integrable, and taking K → ∞ we have  1 n 1 f (ν(n −1 i)Yi ) ≤ E( f (ν(t)Y )) dt, lim sup n→∞ n 0 i=1

 

with probability one. The proof of the analogous lim inf inequality is similar. We now have the proof of Theorem 1.

Proof Let x ∈ ∂ R2+ , and suppose that x2 = 0. If x1 = 0, then N −1 L(0; 0) = N −1 X (0, 0) → 0 = ϕ(0) with probability one as N → ∞. If x1 > 0 then we have N x  1 1 1 L(0; N x) = X (i, 0). N N i=0

It follows from Lemma 2 and the construction of the weights X (i, j) in Sect. 1.1 that  1 1 μ(x1 t, 0) + μs (x1 t, 0) dt = ϕ(x), L(0; N x) −→ x1 N 0 with probability one as N → ∞. The case where x1 = 0 and x2 > 0 is similar. As in Lemma 1, we can use the fact that L and ϕ are monotone non-decreasing, and ϕ is uniformly continuous, to show that we actually have 1 L(0; N ·) −→ U = ϕ N

(123)

locally uniformly on ∂ R2+ with probability one. Let y ∈ R2+ . From the definition of L we have the following dynamic programming principle   L(0; N y) = max L(0; N x) + w N (x, y) . (124) x∈∂ R2+ : x  y

Combining Lemma 1, Proposition 1, and (123), we can pass to the limit in (124) to obtain   1 U (x) + W (x, y) = U (y), L(0; N y) −→ max N x∈∂ R2+ : x  y with probability one. As in Lemma 1, locally uniform convergence follows from the monotonicity of U and x → N −1 L(0; N x), along with the uniform continuity given by Theorem 2.  

5 Numerical Scheme We present here a fast numerical scheme for computing the viscosity solution U of (P). The scheme is a minor modification of the scheme used in [12,13]. Since information propagates along coordinate axes in the definition of the variational problem (39) for U , it is natural to consider using backward difference quotients to approximate (P). Letting Ui,h j denote the numerical solution on the grid h N20 of spacing h, we have     h Ui,h j − Ui,h j−1 − hμi, j Ui,h j − Ui−1, = h 2 σi,2 j , (125) j − hμi, j +

+

123

934

J. Calder

h h where μi, j = μ(hi, h j) + μs (hi, h j) and σi, j = σ (hi, h j). Given Ui−1, j and Ui, j−1 , we h h h can solve (125) for Ui, j ≥ max(Ui−1, j + hμi, j , Ui, j−1 + hμi, j ) via the quadratic formula to obtain +  2 1 h 1  h Ui−1, j + Ui,h j−1 + hμi, j + Ui,h j = Ui−1, j − Ui,h j−1 + 4h 2 σi,2 j , (126) 2 2

for i, j ≥ 1. The choice of the positive root in (126) reflects the monotonicity of the scheme, and ensures that it captures the viscosity solution of (P). When i = 0 or j = 0, we recall the boundary condition (37) to obtain h h h h U0, j = U0, j−1 + hμ0, j and Ui,0 = Ui−1,0 + hμi,0 .

(127)

h Notice that when i = 0, if we set U−1, j = 0 and σi, j = 0 in (126), then (126) and (127) are equivalent. In fact, even when σi, j  = 0, (126) and (127) are asymptotically equivalent as h  h. The same observations hold when j = 0 if we set U h h → 0 provided U0, j i,−1 = 0. Thus, to account for the boundary condition in (P), we can simply set

Ui,h j = 0 for (i, j)  ∈ N20 ,

(128)

and compute Ui,h j via (126) for all (i, j) ∈ N20 ∩ [0, R]2 , for any R > 0. In summary, we propose the following numerical scheme for approximating viscosity solutions of (P): ⎧  ⎨ U h = 1 U h + U h + hμ + 1 U h − U h 2 + 4h 2 σ 2 , if (i, j) ∈ N2 i,j i,j i,j–1 i,j i–1,j i,j–1 0 (S) 2 i–1,j 2 ⎩ U h = 0, otherwise. i,j

Note that we can visit the grid points in any sweeping pattern that visits (i − 1, j) and (i, j − 1) before (i, j), which reflects the cone of influence in the percolation problem. This scheme requires visiting each grid point exactly once and hence has linear complexity. Our first result guarantees that the simple boundary condition in (S) agrees with the boundary condition in (P) as h → 0. Lemma 3 Let Ui,h j satisfy the scheme (S) and suppose that σi, j is bounded by M for all (i, j) ∈ N20 ∩ ∂ R2+ . If i, j ≤ h −1 R then there exists a constant C > 0 such that , , , ,, , j i , , ,   √ , , h , , h 2 , U U , − h μ − h μ (129) , i,0 k,0 , , 0, j 0,k , ≤ C(1 + R M ) h. , , , , k=0 k=0 Proof Let us give the proof for i = 0. The case of j = 0 is similar. Define  √  h ≤ h . J := sup j ≥ 0 : U0, j For j ≥ J it follows from the scheme (S) and a Taylor expansion that    3  3 1 h 1 h h 2 M2 = U h 2 M2 . = + hμ + + O h + hμ + O h U U U0, 0, j 0, j j 0, j−1 2 0, j−1 2 0, j−1 Iterating we have ⎞ ⎞ ⎛ ⎛ j j √    3   3 h h ⎠ ⎠ ⎝ 2 j M2 = h ⎝ 2 M2 . + U + O = h μ + O h μ h + j h U0, 0,k 0,k j 0,J k=J +1

123

k=J +1

Directed Last Passage Percolation

Since j ≤ h −1 R we have h U0, j

935

⎞ ⎛ j   √  ≤h⎝ μ0,k ⎠ + O 1 + R M 2 h .

(130)

k=0

Noting the equivalence of (126) and (127) when σ0, j = 0, we can set σ0, j = 0 in (126) and iterate as before to obtain ⎞ ⎛ j  h U0, j ≥ h ⎝ μ0,k ⎠ . k=0

 

Combining this with (130) completes the proof.

Theorem 8 Suppose that μ and σ 2 are non-negative, globally Lipschitz continuous on [0, ∞)2 and satisfy (101), and let μs satisfy (F2). For h > 0 let U h (x) = Uh −1 x1 ,h −1 x2  denote the extension of the numerical solution Ui,h j of (S) to [0, ∞)2 . Then we have U h −→ U locally uniformly on [0, ∞)2 ,

(131)

where U is the unique monotone viscosity solution of (P). Proof The proof follows the standard framework outlined by Barles and Souganidis [7]. This general theory guarantees convergence of any scheme that is monotone, stable, and consistent, provided the PDE enjoys strong uniqueness—a comparison principle for semicontinuous suband supersolutions. Corollary 3 is the required strong uniqueness result, and it is easy to see that the scheme (125) is both monotone and consistent. Indeed, for any ψ ∈ C 1 ([0, ∞)2 ) we have    1 ψ(x) − ψ(x − he1 ) − hμ(x) ψ(x) − ψ(x − he2 ) − hμ(x) 2 + + h     ψx2 (x) − μ(x) , −→ ψx1 (x) − μ(x) +

+

as h → 0, which is the required consistency. To show monotonicity, let u, v : [0, ∞)2 such that u(x) = v(x) and u ≤ v. Then we have     v(x) − v(x − he1 ) − hμ(x) v(x) − v(x − he2 ) − hμ(x) + +     u(x) − v(x − he2 ) − hμ(x) = u(x) − v(x − he1 ) − hμ(x) + +     u(x) − u(x − he2 ) − hμ(x) , ≤ u(x) − u(x − he1 ) − hμ(x) +

+

where the last line follows from the monotonicity of t → ( p1 − t)+ ( p2 − t)+ . Therefore, to complete the proof, we need to show that the scheme is stable, and that the boundary condition is satisfied. Stability refers to a bound on U h , independent of h. By Lemma 3, (F2), and the continuity of μ, we have that U h −→ ϕ locally uniformly on ∂ R2+ as h → 0, (132) 1 where ϕ(x) = (x1 + x2 ) 0 μ(t x) + μs (t x) dt, which verifies the boundary condition. Stability follows from a comparison principle for (S), and is similar to [12, Lemma 3.3]. We give the argument here for completeness. Let √ V (x) = μ + μs ∞ (x1 + x2 ) + 2σ ∞ x1 x2 + 1.

123

936

J. Calder

We claim that U h (x) ≤ V (x). To see this, suppose to the contrary that U h (x) > V (x) for some x ∈ [0, R]2 , R > 0. First note that ϕ(x) ≤ (x1 + x2 )μ + μs ∞ = V (x) − 1, for x ∈ ∂ R2+ . Therefore, by (132), we have that U h ≤ V − enough. Therefore, there exists z ∈ [h, R]2 such that

1 2

on [0, R]2 ∩ ∂ R2+ for h small

U h (z) > V (z) and U h (z − hei ) ≤ V (z − hei ) for i = 1, 2. √ Note that by the concavity of t → t we have that √ z1 z2 V (z) − V (z − hei ) ≥ hμ + μs ∞ + hσ ∞ . zi

(133)

It follows that    V (z) − V (z − he1 ) − hμ + μs ∞ V (z) − V (z − he2 ) − hμ + μs ∞ ≥ h 2 σ 2∞ . By monotonicity of t → ( p1 − t)+ ( p2 − t)+ we therefore have    V (z) − V (z − he1 ) − hμ(z) V (z) − V (z − he2 ) − hμ(z) ≥ h 2 σ 2∞    ≥ U h (z) − U h (z − he1 ) − hμ(z) U h (z) − U h (z − he2 ) − hμ(z) .

(134)

This contradicts (133), hence U h ≤ V . The proof is completed by invoking [7, Theorem 2.1].   We now extend the numerical convergence result to μ σ 2 satisfying (F1) and (F3). Corollary 6 Suppose that μ and σ 2 simultaneously satisfy (F1), (F3) and (101), and let μs satisfy (F2). Define U h as in Theorem 8. Then we have U h −→ U locally uniformly on [0, ∞)2 ,

(135)

where U is the unique monotone viscosity solution of (P). Proof Define μk , σ k , μk , σk , Uk and U k as in the proof of Theorem 7. By definition we have Uk ≤ U ≤ U k , and by Corollary 5 and Remark 5 we have Uk , U k → U locally uniformly on [0, ∞)2 as k → ∞. Let Ukh and U k,h denote the numerical solutions defined by (S) for μk + μs , σk and k μ + μs , σ k , respectively, extended to [0, ∞)2 as in Theorem 8. Since μk , σ 2,k , μk , and σk2 are Lipschitz continuous and μs satisfies (F2), we can apply Theorem 8 to show that Ukh −→ Uk and U k,h −→ U k ,

(136)

locally uniformly on [0, ∞)2 as h → 0. Since μk ≤ μ ≤ μk and σk ≤ σ ≤ σ k , we can make an argument, as in Theorem 8, based on a comparison principle for (S), to show that Ukh ≤ U h ≤ U k,h for all h, k. The proof is completed by combining this with (136) and the locally uniform convergence Uk , U k → U .  

123

Directed Last Passage Percolation

937

5.1 Numerical Simulations We present here some numerical simulations comparing the numerical solutions of (P), computed by (S), to realizations of directed last passage percolation (DLPP). We restrict our attention to the box [0, 1]2 for simplicity. For the case of exponential DLPP, we consider three macroscopic means, λ1 , λ2 , and λ3 given by

1, if x1 ≥ 0.5 or x2 ≥ 0.5, (137) λ1 (x) = 0, otherwise,   λ2 (x) = exp −10 |x − (0.25, 0.75)|2 + exp −10 |x − (0.75, 0.25)|2 , (138)

and λ3 (x) =

0.5, if |x − (1, 0)|2 ≤ 0.49 or |x − (0, 1)|2 ≤ 0.49, 1, otherwise.

(139)

Since the results are very similar for geometric DLPP, we consider only one macroscopic parameter q given by

0.5, if x1 ≥ 0.5 or x2 ≥ 0.5, q(x) = (140) 1, otherwise. Figure 3 compares the level sets of the numerical solutions of (P) with simulations of exponential/geometric DLPP on a 1,000 × 1,000 grid. The smooth curves correspond to the level sets of the numerical solution of (P) while the rough curves correspond to the level sets of the last passage time from the DLPP simulation. Figure 4 shows the same comparison, except for DLPP simulations on a 5,000 × 5,000 grid. In both cases, the numerical solutions of (P) were computed on a 1,000 × 1,000 grid. To give an idea of the computational complexity, it takes approximately a quarter of a second to numerically solve the PDE on this grid in MATLAB on an average laptop. 5.2 Finding Maximal Curves We now propose an algorithm based on dynamic programming for finding maximizing curves, and we prove in Theorem 9 and Corollary 7 that the curve produced by our algorithm is approximately optimal for the variational problem (36) defining U . Other approaches to finding maximizing curves, such as the method of characteristics [19], or solving the EulerLagrange equations [33], are not guaranteed to produce optimal curves, due to crossing characteristics, and the possibility of local minima. Our method is related to the method of synthesis in optimal control theory for computing optimal controls from solutions of Hamilton–Jacobi–Bellman equations [6]. Our algorithm has a parameter ε > 0 and a starting point x ∈ R2+ , and computes a curve γε with γε (0) = 0 and γε (1) = x that nearly maximizes J . The algorithm works by starting at x and tracing our way back to the origin by solving a series of dynamic programming problems. We set x0 = x, and generate x1 , . . . , xk , . . . as follows: Given we are at step k ≥ 0, we use a dynamic programming principle (similar to Proposition 1) to write   U (xk ) = max U (y(s)) + W (y(s), xk ) , (141) s∈[0,1]

where y(s) = xk − (1 − s, s)ε. An application of Hölder’s inequality yields  J (γ ) ≤ μ∗ (xk )ε + 2σ ∗ (xk )ε s(1 − s) + o(ε),

(142)

123

938

J. Calder

1

1

0.9

0.9

0.8

0.8

0.7

0.7

0.6

0.6

0.5

0.5

0.4

0.4

0.3

0.3

0.2

0.2

0.1

0.1

0

0 0

0.1

0.2

0.3

0.4

0.5 0.6

0.7

0.8

0.9

1

0

(a) Exponential DLPP with mean λ1 1

1

0.9

0.9

0.8

0.8

0.7

0.7

0.6

0.6

0.5

0.5

0.4

0.4

0.3

0.3

0.2

0.2

0.1

0.1 0

0 0

0.1

0.2

0.3

0.4

0.5 0.6

0.7

0.8

0.1

0.2

0.3

0.4

0.5 0.6

0.7

0.8

0.9

1

(b) Geometric DLPP with parameter q

0.9

1

(c) Exponential DLPP with mean λ2

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

(d) Exponential DLPP with mean λ3

Fig. 3 Comparisons of the level sets of numerical solutions of (P), computed via (S), and the level sets of exponential/geometric DLPP simulations on a 1,000 × 1,000 grid. The smooth lines correspond to the numerical solutions of (P), while the rough lines correspond to the DLPP simulations

for any γ ∈ A with γ (0) = y(s) and γ (1) = xk . When μ and σ are continuous, this upper bound can be attained (in the limit as ε → 0) by the diagonal curve γ (t) = (1 − t)y(s) + x k t. Thus we are justified in making the following approximation  sup J (γ ) ≈ μ(xk )ε + 2σ (xk )ε s(1 − s). (143) W (y(s), xk ) = γ ∈A : γ (0)=y(s),γ (1)=xk

Substituting (143) into (141) we find that U (xk ) ≈ μ(xk )ε + max

s∈[0,1]

We then define sk∗

   U (y(s)) + 2σ (xk )ε s(1 − s) .

xk+1 := y(sk∗ )+ = (xk − (1 − sk∗ , sk∗ )ε)+ ,

(144)

(145)

where ∈ [0, 1] is the maximizing argument in (144) and x+ = (max(x1 , 0), max(x2 , 0)). The algorithm is terminated as soon as xk ∈ ∂ R2+ and we append the final terminal point xk+1 = 0. In (144), we set U (y(s)) = 0 whenever y(s)  ∈ [0, ∞)2 . The algorithm is summarized in Algorithm 1. Notice that the boundary source μs does not appear explicitly in Algorithm 1, though it does appear implicitly through the solution U of (P). Each step of the algorithm moves a

123

Directed Last Passage Percolation

939

1

1

0.9

0.9

0.8

0.8

0.7

0.7

0.6

0.6

0.5

0.5

0.4

0.4

0.3

0.3

0.2

0.2

0.1

0.1

0

0

0.1

0.2

0.3

0.4

0.5 0.6

0.7

0.8

0.9

1

0 0

(a) Exponential DLPP with mean λ1 1

1

0.9

0.9

0.8

0.8

0.7

0.7

0.6

0.6

0.5

0.5

0.4

0.4

0.3

0.3

0.2

0.2

0.1

0.1

0 0

0.1

0.2

0.3

0.4

0.5 0.6

0.7

0.8

0.9

(c) Exponential DLPP with mean λ2

0.1

0.2

0.3

0.4

0.5 0.6

0.7

0.8

0.9

1

(b) Geometric DLPP with parameter q

1

0

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

(d) Exponential DLPP with mean λ3

Fig. 4 Comparisons of the level sets of numerical solutions of (P), computed via (S), and the level sets of exponential/geometric DLPP simulations on a 5,000 × 5,000 grid

Algorithm 1: Find ε-optimal curve Given a step size ε > 0 and x0 ∈ R2+ , we generate x1 , . . . , xk , . . . as follows: k = 0; while xk ∈ R2+ do   √ sk∗ = argmaxs∈[0,1] U (xk − (1 − s, s)ε) + 2σ (xk )ε s(1 − s) ; xk+1 = (xk − (1 − sk∗ , sk∗ )ε)+ ; end xk+1 = 0;

distance of at least ε/2 in the direction (−1, 0) or (0, −1). If x0 ∈ [0, R]2 , then the algorithm will terminate in at most 4R/ε steps. Furthermore, when μ and σ 2 are Lipschitz, we can show that the polygonal curve γε generated by Algorithm 1 has energy within O(ε) of the maximizing curve. This is summarized in the following result. Theorem 9 Let R > 0, suppose that μ and σ 2 are non-negative, globally Lipschitz continuous on [0, R]2 with constant Cli p > 0, and suppose that μs satisfies (F2). Let ε > 0, x0 ∈ (0, R]2 , and let x1 , . . . , x K be the points generated by Algorithm 1. Let γε : [0, 1] → [0, ∞)2 be the monotone polygonal curve passing through x K , x K −1 , . . . , x1 , x0 . Then there

123

940

J. Calder

exists a constant C = C(μ∞ , σ ∞ ) > 0 such that Uμ+μs ,σ (x0 ) ≤ Jμ+μs ,σ (γε ) + C(1 + Cli p R)ε.

(146)

Proof For convenience, we set U = Uμ+μs ,σ , J = Jμ+μs ,σ , and we extend μ, σ and U to functions on R2 by setting μ(x) = σ (x) = U (x) = 0 for x  ∈ [0, ∞)2 . Writing t = 1/K and t j = jt for j = 0, . . . , K , we can parameterize γε so that γε (t) =

1 ε (x K − j − x K − j+1 ) = (1 − s K∗ − j , s K∗ − j ), t t

for t ∈ (t j−1 , t j ) and j ≥ 3. It follows that  1 (γε (t), γε (t)) dt t2

=

K  

tj

j=3 t j−1

(147)

(148)

(γε (t), γε (t)) dt

 tj K   1 μ(γε (t)) + 2σ (γε (t)) (1 − s K∗ − j )s K∗ − j dt t t j−1 j=3 .  tj K   1 μ(x K − j ) + 2σ (x K − j ) (1 − s K∗ − j )s K∗ − j dt − 3Cli p ε ≥ε t t j−1 j=3 ⎛ ⎞ K   =⎝ μ(x K − j ) + 2σ (x K − j ) (1 − s K∗ − j )s K∗ − j ⎠ ε − 3K Cli p ε 2 . (149) =ε

j=3

An application of Hölder’s inequality gives    J (γ ) ≤ μ(x K − j ) + 2σ (x K − j ) s(1 − s) ε + 3Cli p ε 2 ,

(150)

for j ≥ 2 and any γ ∈ A with γ (0) = y(s) and γ (1) = x K − j . Combining this with the dynamic programming principle (141) we have    U (x K − j ) ≤ μ(x K − j )ε + max U (y(s)) + 2σ (x K − j )ε s(1 − s)) + 3Cli p ε 2 , (151) s∈[0,1]

for all j ≥ 2. By the definition of s K∗ − j we have    U (x K − j ) ≤U (x K − j+1 )+ε μ(x K − j )+2σ (x K − j ) (1 − s K∗ − j )s K∗ − j + 3Cli p ε 2 , (152) for j ≥ 3. By iterating this inequality for j = K , . . . , 3 we have ⎛ ⎞ K   U (x0 ) ≤ U (x K −2 ) + ⎝ μ(x K − j ) + 2σ (x K − j ) (1 − s K∗ − j )s K∗ − j ⎠ ε + 3K Cli p ε 2 j=3 (148)

≤ U (x K −2 ) +



1

t2

(γε (t), γε (t)) dt + 6K Cli p ε 2 .

(153)

We have two cases now. Suppose first that y(s K∗ −2 )  ∈ [0, ∞)2 . Then U (y(s K∗ −2 )) = 0 and by (151) we have that U (x K −2 ) ≤ Cε. Combining this with (153) we have

123

Directed Last Passage Percolation

941

U (x0 ) ≤ J (γε ) + Cε + 6K Cli p ε 2 .

(154)

The proof is completed by noting that K ≤ 4R/ε. Suppose now that y(s K∗ −2 ) ∈ [0, ∞)2 . Then (152) holds for j = 2 and combining this with (153) we have  1 (γε (t), γε (t)) dt + 6(K + 1)Cli p ε 2 . (155) U (x0 ) ≤ U (x K −1 ) + t2

Since x K = 0 we must have x K −1 ∈ ∂ R2+ . It follows that  t1 (γε (t), γε (t)) dt = U (x K −1 ). 0

Inserting this into (155) we see that U (x0 ) ≤ J (γε ) + 6(K + 1)Cli p ε 2 .   If μ and σ 2 are not globally Lipschitz continuous, then Algorithm 1 is not guaranteed to yield optimal curves. However, it can be easily modified to give an algorithm that does. Corollary 7 Suppose that μ and σ 2 simultaneously satisfy (F1), (F3) and (101), and let μs satisfy (F2). Let μk and σk be sequences of functions such that μk and σk2 are Lipschitz with constant k, μk ≤ μ, σk ≤ σ and Uμk +μs ,σk → Uμ+μs ,σ locally uniformly. Let x0 ∈ (0, R]2 and let γk : [0, 1] → [0, ∞)2 be the monotone polygonal curve generated by applying Algorithm 1 to x0 , μk , σk and Uk with ε = k −1 (Uμ+μs ,σ (x0 ) − Uμk +μs ,σk (x0 )). Then we have U (x0 ) ≤ J (γk ) + o(1) as k → ∞. (156) Proof Let us set Jk = Jμk +μs ,σk , J = Jμ+μs ,σ , Uk = Uμk +μs ,σk , and U = Uμ+μs ,σ . By Theorem 9 there exists a constant C = C(μ∞ , σ ∞ ) > 0 such that Uk (x0 ) ≤ Jk (γk )+C(1+k R)k −1 (U (x0 )−Uk (x0 )) ≤ J (γk ) + C(1 + R)(U (x0 ) − Uk (x0 )). It follows that U (x0 ) ≤ J (γk ) + C(2 + R)(U (x0 ) − Uk (x0 )).   We now show some simulation results using Algorithm 1 to compute approximately optimal curves for the exponential/geometric DLPP simulations presented in Sect. 5.1. Figure 5 shows the curves generated by Algorithm 1 along with optimal paths for 10 realizations of DLPP on a 1,000 × 1,000 grid. We also show the level sets of the numerical solutions of (P) to give points of reference. In all cases, we used a step size of ε = 0.01 and computed sk∗ in Algorithm 1 by an exhaustive search with a grid size of 0.01. With these choices of parameters, Algorithm 1 runs in approximately a quarter of a second, assuming the numerical solution U is already available. Note also that we implemented Algorithm 1 exactly as written, even when μ and σ are discontinuous, and do not substitute continuous versions as in Corollary 7. As in [33], it is expected that the optimal paths for DLPP will asymptotically concentrate around optimal curves for the variational problem, and this is clearly reflected in the simulations in Fig. 5. Notice that for exponential DLPP with means λ1 , λ2 and geometric DLPP with parameter q, there are multiple maximizing curves for any terminal point x along

123

942

J. Calder

1

1

0.9

0.9

0.8

0.8

0.7

0.7

0.6

0.6

0.5

0.5

0.4

0.4

0.3

0.3

0.2

0.2

0.1

0.1

0 0

0.1

0.2

0.3

0.4

0.5 0.6

0.7

0.8

0.9

1

(a) Exponential DLPP with mean λ1

0

1

1 0.9

0.8

0.8

0.7

0.7

0.6

0.6

0.5

0.5

0.4

0.4

0.3

0.3

0.2

0.2

0.1

0.1 0.1

(c)

0.2

0.3

0.4

0.5 0.6

0.7

0.8

0.9

Exponential DLPP with mean λ2

0.1

0.2

0.3

0.4

0.5 0.6

0.7

0.8

0.9

1

(b) Geometric DLPP with parameter q

0.9

0 0

0

1

0

0

0.1

(d)

0.2

0.3

0.4

0.5 0.6

0.7

0.8

0.9

1

Exponential DLPP with mean λ3

Fig. 5 Comparisons of the curve γε (ε = 0.01) generated by Algorithm 1 to the optimal paths from 10 realizations of DLPP for the macroscopic weights considered in Sect. 5.1. In each experiment, we show the curve γε and optimal paths for several different terminal points x0 ∈ (0, 1)2 . Notice that in a, b and c, there are multiple optimizing curves, and Algorithm 1 finds only one curve, depending on the choice one makes when there are multiple maximizing arguments for sk∗ . The DLPP simulations were performed on a 1,000 × 1,000 grid, sk∗ was computed via an exhaustive search with a grid size of 0.01

the diagonal {x1 = x2 }. We see that some of the DLPP realizations concentrate around one optimal path, while the remaining realizations concentrate around the other. Algorithm 1 will of course only find one of the maximizing curves, depending on the choice one makes when there are multiple maximizing arguments in the definition of sk∗ . We now show some simulations with a source term μs . Here we consider exponential DLPP with mean λ = 1 on [0, 1] × (0, 1] and λ = 3 on [0, 1] × {0}. Figure 6a shows the optimal curve generated by Algorithm 1, along with the level sets of the numerical solution of (P) and the optimal paths from 10 realizations of exponential DLPP on a 1,000 × 1,000 grid. Although our assumptions only allow sources on the boundary ∂ R2+ , many of the results in the paper can be shown to hold for sources along horizontal or vertical lines in R2+ . The idea is to find the appropriate dynamic programming principle that plays the role of Proposition 1, so that the effect of the weights in the bulk is separated from the source. In the case of a source along the line {x2 = α} for α ∈ (0, 1), and assuming no boundary sources, the dynamic programming principle would be

123

Directed Last Passage Percolation

943

1

1

0.9

0.9

0.8

0.8

0.7

0.7

0.6

0.6

0.5

0.5

0.4

0.4

0.3

0.3

0.2

0.2

0.1

0.1

0

0

0.1

0.2

0.3

0.4

0.5 0.6

0.7

0.8

0.9

1

0

0

0.1

(a) Source at {x2 = 0} 1

1

0.9

0.9

0.8

0.8

0.7

0.7

0.6

0.6

0.5

0.5

0.4

0.4

0.3

0.3

0.2

0.2

0.1

0.1

0

0

0.1

0.2

0.3

0.4

0.5 0.6

0.7

0.2

0.3

0.4

0.5 0.6

0.7

0.8

0.9

1

0.9

1

(b) Source at {x2 = 0.25}

0.8

0.9

1

(c) Source at {x2 = 0.5}

0

0

0.1

0.2

0.3

0.4

0.5 0.6

0.7

0.8

(d) Source at {x2 = 0.75}

Fig. 6 Comparisons of the optimal curve γε (ε = 0.01) generated by Algorithm 1 to the optimal paths from 10 realizations of exponential DLPP. The macroscopic weight functions are constant μ = 1 on [0, 1]2 plus a source term μs = 2 concentrated on a horizontal line. The simulations were performed on a 1,000 × 1,000 grid

U (y) =

max

0≤x1 ≤x1 ≤y1

 W (0, (x1 , α)) +

x1 x1

# μ(t, α) + μs (t, α) dt +

W ((x1 , α),

y) ,

where U = Uμ+μs ,σ , W = Wμ,σ , μ and σ 2 are, say, Lipschitz on [0, ∞)2 , and μs represents the source, which is nonzero only on the line {x2 = α}. We can then use this dynamic programming principle and its discrete version (similar to (124)) in the proof of Theorem 1. The one caveat is that U is in general discontinuous along the line containing the source, though U remains locally uniformly continuous on each of the components of R2+ obtained by removing the source line. Thus, U can only be identified via the variational problem (39), since we have not proven uniqueness of discontinuous viscosity solutions of (P). However, our numerical results suggest that either uniqueness holds for (P) in some special cases where U is discontinuous, or at the very least our numerical scheme for (P) selects the “correct” viscosity solution for the percolation problem. Figure 6b, c, and d show the optimal curve generated by Algorithm 1, along with DLPP simulations for sources on the horizontal lines {x2 = 0.25}, {x2 = 0.5}, and {x2 = 0.75}, respectively.

123

944

J. Calder

5.3 TASEP with Slow Bond Rate Finally, we consider the totally asymmetric simple exclusion process (TASEP) with a slow bond rate at the origin. This model was originally introduced by Janowsky and Lebowitz [25], and some partial results were obtained more recently by Seppäläinen [36]. The process of interest is the usual TASEP with exponential rates of 1 at all locations in Z except for the origin, which has a slower rate of r ∈ (0, 1]. One can think of this as modeling traffic flow on a road with a single toll both that every car must pass through. Through the correspondence with DLPP, the slow bond rate corresponds to a source on the diagonal {x1 = x2 }. In the context of our paper, we would have

1/r, if x1 = x2 , μ(x) = (157) 1, otherwise. Notice that μ does not satisfy the assumptions of Theorem 1, and we do not expect the continuum limit (P) to hold in this case. A quantity of interest is κ(r ) := lim

N →∞

1 L(N , N ) for r ≤ 1, N

which corresponds to the reciprocal of the maximum TASEP current [36]. It is known that κ(1) = 4 and Seppäläinen [36] proved the following bounds: *  1 r 2 + 2(1 + r ) ≤ κ(r ) ≤ 3 + . (158) max 4, 2r (1 + r ) r It is an open problem to determine κ(r ) for r < 1. In particular, one is interested in whether κ(r ) > 4 for all r < 1, or if there are some values of r close to r = 1 for which the inverse current κ(r ) remains unchanged. Even though we do not expect our continuum limit Hamilton–Jacobi equation to hold for the slow bond rate problem, it is nevertheless interesting to see what our results would say about this open problem were they to hold. It is easy to see that Uμ,σ (1, 1) = 4/r for μ = σ given by (157). Indeed, one can see that the optimal curve in the variational problem (36) must lie on the diagonal {x1 = x2 }, which gives the energy 4/r . This would suggest that κ(r ) = lim

N →∞

1 4 L(N , N ) = Uμ,σ (1, 1) = . N r

Notice that this violates the bounds in (158), which indicates that the Hamilton–Jacobi equation continuum limit (Theorem 1) does not hold for sources along diagonal lines. It has recently come to our attention that the slow bond rate problem has been setteled by Basu, Sidoravicius, and Sly [8]. They show that the inverse current is always affected when r < 1, but do not give an explicit formula for κ(r ).

6 Discussion and Future Work In this work, we identified a Hamilton–Jacobi equation for the continuum limit of a macroscopic two-sided directed last passage percolation (DLPP) problem. We rigorously proved the continuum limit when the macroscopic rates are discontinuous. Furthermore, we presented a numerical scheme for solving the Hamilton–Jacobi equation, and an algorithm for

123

Directed Last Passage Percolation

945

finding optimal curves based on a dynamic programming principle. Below we make some remarks, discuss simple extensions of this work, and ideas for future work. – Regularity of μ, σ There are many simple modifications of (F1) under which one can prove Theorem 1. For example, the existence of the set Ω bounded by the strictly decreasing curve Γ and ∂ R2+ on which μ = σ = 0 is not necessary, and one can check that the proofs hold without this assumption. This would correspond to a TASEP model with step initial condition. The curves Γi on which μ and σ may admit discontinuities can all be chosen to be strictly decreasing instead of increasing, with appropriate modifications in the proofs. In fact, we can even allow the curves to switch from strictly increasing to strictly decreasing, provided the critical point is isolated, and we make an additional cone condition assumption at this point. However, the curves Γi cannot have any positive measure flat regions, as this can induce discontinuities in U , as shown in Remark 2. – Discontinuous viscosity solutions The regularity assumption (F1) was chosen to ensure that U is locally uniformly continuous. This is essential for invoking the Arzelà-Ascoli Theorem in the proof of Theorem 6, and in the proof of the comparison principle for (P) (Theorem 5). We believe that Theorem 1 holds under far more general assumptions on μ, allowing U to be discontinuous. Presently, we do not know how to prove this. The largest obstacle seems to be proving uniqueness of viscosity solutions of (P) when the solutions U and the macroscopic weights μ are discontinuous. Our numerical results seem to support this conjecture, as the numerical scheme is able to very accurately capture discontinuities in U . – Hydrodynamic limit of TASEP As we showed in Sect. 1.2, the Hamilton–Jacobi equation (P) is formally equivalent to the conservation law governing the hydrodynamic limit of TASEP [21,35]. It would be very interesting to make this connection rigorous. – Higher dimensions The main obstacle in generalizing the Hamilton–Jacobi equation (P), and the results in this paper, to dimensions d ≥ 3, is the fact that the exact form of the time constant (5) for i.i.d. random variables X (i, j) is unknown. If an exact form for the time constant U were to be discovered for d ≥ 3, then we anticipate no problems in generalizing the results in this paper to higher dimensions. We should note that although the exact form of U is unknown for d ≥ 3, it is known that U is continuous, 1-homogeneous, symmetric in all variables, and superadditive, under fairly broad assumptions on the distribution of X (i, j) [30]. This is enough to show that U is the viscosity solution of some Hamilton–Jacobi equation, but the explicit form of the equation is unknown. Acknowledgments The author would like to thank Jinho Baik for suggesting the problem and for stimulating discussions. The author would also like to thank the anonymous referee whose comments and suggestions have greatly improved this manuscript. The research in this paper was partially supported by NSF Grant DMS-0914567.

Appendix: Proof of Theorem 5 For completeness we give the proof of Theorem 5 here. The proof is similar to [13, Theorem 2.8]. Proof Suppose that λ := sup(u − v) > 0. Rd+

123

946

J. Calder

Let

*  λ R = sup r > 0 : u ≤ v + on Dr , 2

(159)

Dr = {x ∈ Rd+ : x1 + · · · + xd < r }.

(160)

where Since O ∈ Rd+ , we have by hypothesis that u ≤ v on ∂ Rd+ . Therefore, since u and v are continuous we have R ∈ (0, ∞). By (159) there exists ξ0 ∈ Rd+ ∩ ∂ D R such that u(ξ0 ) = v(ξ0 ) +

λ and 2

every neighborhood of ξ0 contains some y ∈ Rd+ with u(y) > v(y) +

λ . 2

(161)

For t > 0 set ξ = ξ0 + (t, . . . , t) and G = {x ∈ [0, ∞)d : x  ξ }.

(162)

Let u ξ denote the ξ -truncation of u. By (161) and (159) we see that δ := sup(u ξ − v) > Rd+

λ >0 2

(163)

By (161) we have u(ξ0 ) > v(ξ0 ), and hence ξ0 ∈ O . Let εξ0 and vξ0 ∈ S1 be as given in (H3)O . Choose t > 0 small enough, and εξ0 > 0 smaller if necessary, so that G \ D R ∈ Bεξ0 (ξ0 ) ⊂ Rd+ . For α > 0 define ,2 , , α ,, 1 Φα (x, y) = u (x) − v(y) − ,x − y − √ vξ0 ,, . 2 α ξ

(164)

We claim that for α large enough, there exists xα , yα ∈ Bεξ0 (ξ0 ) such that Mα := sup Φα = Φα (xα , yα ).

(165)

Rd+ ×Rd+

To see this, first substitute y = x −

√1 vξ0 α

into (165) to find



1 Mα ≥ u ξ (x) − v x − √ vξ0 , α for any x ∈ Rd+ such that x − √1α ∈ Rd+ . Since u ξ and v are continuous, it follows from (163) that λ lim inf Mα ≥ sup(u ξ − v) = δ > > 0. (166) α→∞ 2 d R +

Since

uξ

is bounded, and v is monotone, we have by (164) that C |x − y| ≤ √ whenever Φα (x, y) ≥ 0. α

(167)

/ = πξ (w), and define Let x, y ∈ Rd+ such that Φα (x, y) ≥ 0. Set w = πx (y) = π y (x) and w / x = x +w / − w and / y = y+w / − w.

123

(168)

Directed Last Passage Percolation

947

A short calculation shows that πξ (x) = πξ (/ x ). Since u ξ = u ◦ πξ we have x ) = u ξ (πξ (/ x )) = u ξ (πξ (x)) = u ξ (x). u ξ (/

(169)

Since v is Pareto-monotone and / y  y we have by (169) that x ) − v(/ y) ≥ u ξ (x) − v(y) u ξ (/

(170)

Since / x −/ y = x − y, we see from (170) and (164) that x,/ y) ≥ Φα (x, y). Φα (/

(171)

Furthermore, by (167) we have C |/ x −w /| = |x − w| ≤ |x − y| ≤ √ . α Similarly we have |/ y−w /| ≤

√C . α

Since w /  ξ we have

*  C / x,/ y ∈ Gα := x  ∈ [0, ∞)d : x   ξ + √ (1, . . . , 1) . α It follows from this and (171) that for every α > 0 there exists xα , yα ∈ Gα such that Mα = Φα (xα , yα ). By (167) we may pass to a subsequence if necessary to find x0 ∈ G such that xα , yα → x0 as α → ∞. Then we have lim sup Mα ≤ lim u ξ (xα ) − v(yα ) ≤ δ. α→∞

α→∞

Combining this with (166) we have Mα → δ = u ξ (x0 ) − v(x0 ) and ,2 , , 1 α ,, xα − yα − √ vξ0 ,, −→ 0. 2, α

(172)

Since δ > λ/2, it follows from the definition of R (159) that x0 ∈ G \ D R ⊂ Bεξ0 (ξ0 ). Therefore, for α > 0 large enough we have xα , yα ∈ Bεξ0 (ξ0 ), which establishes the claim.   Letting p = α xα − yα − √1α we have by (165) that p ∈ D + u ξ (xα ) ∩ D − v(yα ). By hypothesis we have (173) H ∗ (yα , p) ≥ a. Since u is truncatable, u ξ is a viscosity solution of (81) and therefore H∗ (xα , p) ≤ 0.

(174)

a ≤ H ∗ (yα , p) − H∗ (xα , p).

(175)

Subtracting (174) from (173) we have

Let wα = xα − yα −

√1 vξ0 α

and note that xα = yα + εv,

where

√ √ vξ0 + αwα 1 ε = √ |vξ0 + αwα | = |xα − yα | and v = . √ |vξ0 + αwα | α

123

948

J. Calder

√ By (172) we have αwα → 0. Therefore, for α large enough we have |vξ0 − v| < εξ0 and ε < εξ0 . Since yα ∈ Bεξ0 (ξ0 ) we can invoke (H3)O to find that H ∗ (yα , p)−H∗ (xα , p) = H ∗ (yα , p)−H∗ (yα +εv, p) ≤ m(| p||xα −yα |+|xα −yα |). (176) Note that

, , , , 1 | p||xα − yα | = α ,,xα − yα − √ vξ0 ,, |xα − yα | α , ,, , , ,, , 1 1 1 = α ,,xα − yα − √ vξ0 ,, ,,xα − yα − √ vξ0 + √ vξ0 ,, α α α √ 2 ≤ αwα + αwα .

Combining this with (176) and (175) we have √ 0 < a ≤ m(αwα2 + αwα + |xα − yα |). Sending α → ∞ yields a contradiction.

 

References 1. Baccelli, F., Borovkov, A., Mairesse, J.: Asymptotic results on infinite tandem queueing networks. Probab. Theory Relat. Fields 118(3), 365–405 (2000) 2. Baik, J. Ben Arous, G. Péché, S.: Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices. Ann. Probab. 1643–1697 (2005) 3. Baik, J., Deift, P., Johansson, K.: On the distribution of the length of the longest increasing subsequence of random permutations. J. Am. Math. Soc. 12(4), 1119–1178 (1999) 4. Baik, J. Ferrari, P.L., Péché, S.: Convergence of the two-point function of the stationary TASEP. arXiv:1209.0116 (2012) 5. Baik, J., Rains, E.M.: Limiting distributions for a polynuclear growth model with external sources. J. Stat. Phys. 100(3–4), 523–541 (2000) 6. Bardi, M., Dolcetta, I.: Optimal Control and Viscosity Solutions of Hamilton–Jacobi–Bellman Equations. Springer, New York (1997) 7. Barles, G., Souganidis, P.E.: Convergence of approximation schemes for fully nonlinear second order equations. Asymptot. Anal. 4(3), 271–283 (1991) 8. Basu, R. Sidoravicius, V., Sly, A.: Last passage percolation with a defect line and the solution of the slow bond problem. arXiv:1408.3464 (2014) 9. Ben Arous, G., Corwin, I.: Current fluctuations for TASEP: a proof of the prähofer-spohn conjecture. Ann. Probab. 39(1), 104–138 (2011) 10. Bolthausen, E.: A note on the diffusion of directed polymers in a random environment. Commun. Math. Phys. 123(4), 529–534 (1989) 11. Borodin, A., Péché, S.: Airy kernel with two sets of parameters in directed percolation and random matrix theory. J. Stat. Phys. 132(2), 275–290 (2008) 12. Calder, J., Esedoglu, S.: and A . O. Hero. A PDE-based approach to non-dominated sorting. SIAM J. Numer. Anal. (2013, to appear) 13. Calder, J., Esedoglu, S., Hero, A.O.: A Hamilton–Jacobi equation for the continuum limit of nondominated sorting. SIAM J. Math. Anal. 46(1), 603–638 (2014) 14. Comets, F., Shiga, T., Yoshida, N.: Probabilistic analysis of directed polymers in a random environment: a review. Adv. Stud. Pure Math. 39, 115–142 (2004) 15. Corwin, I., Ferrari, P.L., Péché, S.: Limit processes for TASEP with shocks and rarefaction fans. J. Stat. Phys. 140(2), 232–267 (2010) 16. Crandall, M., Ishii, H., Lions, P.: User’s guide to viscosity solutions of second order partial differential equations. Bull. Am. Math. Soc. 27(1), 1–67 (1992) 17. Deckelnick, K., Elliott, C.M.: Uniqueness and error analysis for Hamilton–Jacobi equations with discontinuities. Interfaces Free Bound. 6(3), 329–349 (2004) 18. Deuschel, J.-D., Zeitouni, O.: Limiting curves for I.I.D. records. Ann. Probab. 23(2), 852–878 (1995)

123

Directed Last Passage Percolation

949

19. Evans, L.C.: Partial Differential Equations. Graduate Studies in Mathematics, 2nd edn. American Mathematical Society, New York (1998) 20. Ferrari, P.L., Spohn, H.: Scaling limit for the space-time covariance of the stationary totally asymmetric simple exclusion process. Commun. Math. Phys. 265(1), 1–44 (2006) 21. Georgiou, N., Kumar, R., Seppäläinen, T.: TASEP with discontinuous jump rates. Latin Am. J. Probab. Math. Stat. 7, 293–318 (2010) 22. Glynn, P. W., Whitt, W.: Departures from many queues in series. Ann. Appl. Probab., 546–572 (1991) 23. Huse, D.A., Henley, C.L.: Pinning and roughening of domain walls in ising systems due to random impurities. Phys. Rev. Lett. 54(25), 2708 (1985) 24. Imbrie, J.Z., Spencer, T.: Diffusion of directed polymers in a random environment. J. Stat. Phys. 52(3–4), 609–626 (1988) 25. Janowsky, S., Lebowitz, J.: Exact results for the asymmetric simple exclusion process with a blockage. J. Stat. Phys. 77(1–2), 35–51 (1994) 26. Johansson, K.: Shape fluctuations and random matrices. Commun. Math. Phys. 209(2), 437–476 (2000) 27. Krishnan, A.: Variational formula for the time-constant of first-passage percolation I: homogenization. arXiv:1311.0316 (2013) 28. Krug, H., Spohn, H.: Kinetic roughening of growing surfaces. In: Godre`che, C. (ed) Solids Far from Equilibrium. Cambridge University Press, Cambridge (1991) 29. Martin, J.B.: Linear growth for greedy lattice animals. Stoch. Process. Appl. 98(1), 43–66 (2002) 30. Martin, J.B.: Limiting shape for directed percolation models. Ann. Probab. 32(4), 2908–2937 (2004) 31. Prähofer, M., Spohn, H.: Current fluctuations for the totally asymmetric simple exclusion process. In: In and Out of Equilibrium, pp. 185–204. Springer, New York (2002) 32. Rezakhanlou, F.: Continuum limit for some growth models. Stoch. Process. Appl. 101(1), 1–41 (2002) 33. Rolla, L.T., Teixeira, A.Q.: Last passage percolation in macroscopically inhomogeneous media. Electr. Commun. Probab. 13, 131–139 (2008) 34. Rost, H.: Non-equilibrium behaviour of a many particle process: density profile and local equilibria. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 58(1), 41–53 (1981) 35. Seppäläinen, T.: Hydrodynamic scaling, convex duality, and asymptotic shapes of growth models. Markov Process. Relat. Fields 4, 1–26 (1996) 36. Seppäläinen, T.: Hydrodynamic profiles for the totally asymmetric exclusion process with a slow bond. J. Stat. Phys. 102(1–2), 69–96 (2001) 37. Souganidis, P.E.: Stochastic homogenization of Hamilton–Jacobi equations and some applications. Asymptot. Anal. 20(1), 1–11 (1999) 38. Vershik, A.M.: Asymptotic combinatorics and algebraic analysis. In: Proceedings of the International Congress of Mathematicians, pp. 1384–1394. Springer, New York (1995)

123