Greedy lattice animals: Negative values and unconstrained maxima

Amir Dembo, Alberto Gandolfi, Harry Kesten

Research output: Contribution to journalArticlepeer-review


Let {Xν, ν ∈ ℤd} be i.i.d. random variables, and S(ξ) = ∑ν∈ξ Xν be the weight of a lattice animal ξ. Let Nn = max{S(ξ): \ξ\ = n and ξ contains the origin} and Gn = max{S(ξ) : ξ ⊆ [-n, n]d}. We show that, regardless of the negative tail of the distribution of Xν, if E(X+ν)d(log+(X+ ν))d+a < +∞ for some a > 0, then first, limn n-1 Nn = N exists, is finite and constant a.e.; and, second, there is a transition in the asymptotic behavior of Gn depending on the sign of N: if N > 0 then Gn ≈ nd, and if N < 0 then Gn ≤ cn, for some c > 0. The exact behavior of Gn in this last case depends on the positive tail of the distribution of Xν; we show that if it is nontrivial and has exponential moments, then Gn ≈ log n, with a transition from Gn ≈ nd occurring in general not as predicted by large deviations estimates. Finally, if xd (1 - F(x)) → ∞ as x → ∞, then no transition takes place.

Original languageEnglish (US)
Pages (from-to)205-241
Number of pages37
JournalAnnals of Probability
Issue number1
StatePublished - Jan 2001


  • Lattice animals
  • Optimization
  • Percolation

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty


Dive into the research topics of 'Greedy lattice animals: Negative values and unconstrained maxima'. Together they form a unique fingerprint.

Cite this