Approximation of subadditive functions and convergence rates in limiting-shape results. (English) Zbl 0882.60090

Summary: For a nonnegative subadditive function \(h\) on \(\mathbb{Z}^d\), with limiting approximation \[ g(x)= \lim_n h(nx)/n, \] it is of interest to obtain bounds on the discrepancy between \(g(x)\) and \(h(x)\), typically of order \(|x|^\nu\) with \(\nu<1\). For certain subadditive \(h(x)\), particularly those which are expectations associated with optimal random paths from 0 to \(x\), in a somewhat standardized way a more natural and seemingly weaker property can be established: every \(x\) is in a bounded multiple of the convex hull of the set of sites satisfying a similar bound. We show that this convex-hull property implies the desired bound for all \(x\). Applications include rates of convergence in limiting-shape results for first-passage percolation (standard and oriented) and longest common subsequences and bounds on the error in the exponential-decay approximation to the off-axis connectivity function for subcritical Bernoulli bond percolation on the integer lattice.


60K35 Interacting random processes; statistical mechanics type models; percolation theory
82B43 Percolation
41A25 Rate of convergence, degree of approximation
60C05 Combinatorial probability
Full Text: DOI


[1] ALEXANDER, K. S. 1990. Lower bounds on the connectivity function in all directions for Bernoulli percolation in two and three dimensions. Ann. Probab. 18 1547 1562. · Zbl 0718.60110
[2] ALEXANDER, K. S. 1993. A note on some rates of convergence in first-passage percolation. Ann. Appl. Probab. 3 81 90. · Zbl 0771.60090
[3] ALEXANDER, K. S. 1994. The rate of convergence of the mean length of the longest common subsequence. Ann. Appl. Probab. 4 1074 1082. · Zbl 0812.60014
[4] ALEXANDER, K. S., CHAYES, J. T. and CHAYES, L. 1990. The Wulff construction and asymptotics of the finite cluster distribution for two-dimensional Bernoulli percolation. Comm. Math. Phys. 131 1 50. · Zbl 0698.60098
[5] ARRATIA, R. and WATERMAN, M. S. 1994. A phase transition for the score in matching random sequences allowing deletions. Ann. Appl. Probab. 4 200 225. · Zbl 0809.62008
[6] AZUMA, K. 1967. Weighted sums of certain dependent random variables. Tohuku Math. J. 19 357 367. · Zbl 0178.21103
[7] BRICMONT, J. and FROHLICH, J. 1985a. Statistical mechanical methods in particle structure änalysis of lattice field theories. I. General results. Nuclear Phys. B 251 517 552. · Zbl 0994.60066
[8] BRICMONT, J. and FROHLICH, J. 1985b. Statistical mechanical methods in particle structure änalysis of lattice field theories. II. Scalar and surface models. Comm. Math. Phys. 98 553 578. · Zbl 0994.60066
[9] CAMPANINO, M., CHAYES, J. T. and CHAYES, L. 1991. Gaussian fluctuations of connectivities in the subcritical regime of percolation. Probab. Theory Related Fields 88 269 341. · Zbl 0691.60090
[10] CHAYES, J. T. and CHAYES, L. 1986. Ornstein Zernike behavior for self-avoiding walks at all noncritical temperatures. Comm. Math. Phys. 105 221 238.
[11] COX, J. T. and DURRETT, R. 1981. Some limit theorems for percolation processes with necessary and sufficient conditions. Ann. Probab. 9 583 603.DANCiK, V. and PATERSON, M. 1994. Upper bound for the expected length of a longest common śubsequence of two binary sequences. Random Structures and Algorithms 6 449 458. Z. · Zbl 0462.60012
[12] DEKEN, J. 1979. Some limit results for longest common subsequences. Discrete Math. 26 17 31. · Zbl 0403.68064
[13] EDEN, M. 1961. A two-dimensional growth process. Proc. Fourth Berkeley Symp. Math. Statist. Probab. 4 223 239. Univ. California Press, Berkeley. JSTOR: · Zbl 0104.13801
[14] HARRIS, T. E. 1960. A lower bound for the critical probability in a certain percolation process. Proc. Cambridge Philos. Soc. 56 13 20. · Zbl 0122.36403
[15] GRIMMETT, G. 1989. Percolation. Springer, New York. · Zbl 0691.60089
[16] KESTEN, H. 1986. Aspects of first passage percolation. Ecole d’Ete de Probabilites de Saint \' \' Flour XIV 1984. Lecture Notes in Math. 1180 125 264. Springer, New York. · Zbl 0602.60098
[17] KESTEN, H. 1993. On the speed of convergence in first-passage percolation. Ann. Appl. Probab. 3 296 338. · Zbl 0783.60103
[18] KINGMAN, J. F. C. 1968. The ergodic theory of subadditive stochastic processes. J. Roy. Statist. Soc. Ser. B 30 499 510. · Zbl 0182.22802
[19] ORNSTEIN, L. S. and ZERNIKE, F. 1914. Accidental deviations of density and opalescence at the Z critical point of a single substance. Proceedings of the Section of Sciences Academy of. Sciences, Amsterdam 17 793 806.
[20] RICHARDSON, D. 1973. Random growth in a tesselation. Proc. Cambridge Philos. Soc. 74 515 528.
[21] SANKOFF, D. and KRUSKAL, J. B., eds. 1983. Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison. Addison-Wesley, Reading, MA.
[22] SMYTHE, R. and WIERMAN, J. C. 1977. First Passage Percolation on the Square Lattice, Lecture Notes in Math. 671. Springer, Berlin. · Zbl 0379.60001
[23] LOS ANGELES, CALIFORNIA 90089-1113 E-MAIL: alexandr@math.usc.edu
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.