Inequalities for the Time Constant in First-Passage Percolation

Consider first-passage percolation on Zd. 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<.1<.2.a<b, the time constant for the uniform distribution on [a..2,b+.1] is strictly smaller than for the uniform distribution on [a,b]. We assume throughout that all our distributions have finite first moments.