Greedy lattice animals. I: Upper bounds. (English) Zbl 0818.60039

Let \(\{X_ v, v \in Z^ d\}\) be an i.i.d. family of positive random variables. For each set \(\xi\) of vertices of \(Z^ d\), its weight is defined as \(S(\xi) = \sum_{v \in \xi} X_ v\). A greedy lattice animal of size \(n\) is a connected subset of \(Z^ d\) of \(n\) vertices containing the origin, and whose weight is maximal among all such sets. Denote by \(N_ n\) this maximal weight. The authors prove that, if the expectation of \(X^ d_ v (\log^ + X_ v)^{d + \alpha}\) is finite for some \(\alpha > 0\), then with probability 1, \(N_ n \leq Mn\) eventually for some finite constant \(M\). They also derive estimates for the tail of the distribution of \(N_ n\). It is shown that this model fits a number of optimization problems among which we cite PERT networks, \(\rho\)- percolation [M. V. Menshikov and S. A. Zuev, in: Probabilistic methods in discrete mathematics, Prog. Pure & Appl. Discret. Math. 1, 337-347 (1993)] and random colorings [L. Fontes and Ch. M. Newman, Ann. Appl. Probab. 3, No. 3, 746-762 (1993; Zbl 0780.60101)].


60G50 Sums of independent random variables; random walks
60K35 Interacting random processes; statistical mechanics type models; percolation theory


Zbl 0780.60101
Full Text: DOI