Linear growth for greedy lattice animals

Let d greater than or equal to 2, and let {X-v, v is an element of Z(d)} be an i.i.d. family of non-negative random variables with common distribution F. Let N(n) be the maximum value of Sigma(vis an element ofxi)X(v) over all connected subsets of Zd of size n which contain the origin. This model of greedy lattice animals was introduced by Cox et al. (Ann. Appl. Probab. 3 (1993) 1151) and Gandolfi and Kesten (Ann. Appl. Probab. 4 (1994) 76), who showed that if EX0d(log(+) X-0)(d+epsilon) < &INFIN; for some ε > 0, then N(n)/n --> N a.s. and in L-1 for some N < &INFIN;o. Using related but partly simpler methods, we derive the same conclusion under the slightly weaker condition that &INT;(infinity)(0) - F(x))(1/d) dx < &INFIN;, and show that N &LE; c &INT;(infinity)(0) (1 - F(x))(1/d) dx for some constant c. We also give analogous results for the related greedy lattice paths model. (C) 2001 Published by Elsevier Science B.V.