Inequalities for the Time Constant in First-Passage Percolation

Consider first-passage percolation on Zᵈ. A classical result says, roughly speaking, that the shortest travel time from (0, 0,…, 0) to (n, 0, …, 0) is asymptotically equal to n μ, for some constant μ, which is called the time constant, and which depends on the distribution of the time coordinates. Except for very special cases, the value of μ is not known. We show that certain changes of the time coordinate distribution lead to a decrease of μ; usually μ will strictly decrease. Two examples of our results are: (i) If F and G are distribution functions with F ≤ G, F ≡ G, then, under mild conditions, the time constant for G is strictly smaller than that for F. (ii) For 0 < ε₁ < ε₂ ≤ a < b, the time constant for the uniform distribution on a - ε₂, b + ε₁ is strictly smaller than for the uniform distribution on a, b. We assume throughout that all our distributions have finite first moments.