×

Random growth models with polygonal shapes. (English) Zbl 1090.60077

Summary: We consider discrete-time random perturbations of monotone cellular automata (CA) in two dimensions. Under general conditions, we prove the existence of half-space velocities, and then establish the validity of the Wulff construction for asymptotic shapes arising from finite initial seeds. Such a shape converges to the polygonal invariant shape of the corresponding deterministic model as the perturbation decreases. In many cases, exact stability is observed. That is, for small perturbations, the shapes of the deterministic and random processes agree exactly. We give a complete characterization of such cases, and show that they are prevalent among threshold growth CA with box neighborhood. We also design a nontrivial family of CA in which the shape is exactly computable for all values of its probability parameter.

MSC:

60K35 Interacting random processes; statistical mechanics type models; percolation theory
11N25 Distribution of integers with specified multiplicative constraints
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aigner, M. and Ziegler, G. M. (2001). Proofs from the Book , 2nd ed. Springer, New York. · Zbl 0978.00002
[2] Alexander, K. S. (1997). Approximation of subadditive functions and convergence rates in limiting-shape results. Ann. Probab. 25 30–55. · Zbl 0882.60090 · doi:10.1214/aop/1024404277
[3] Bohman, T. and Gravner, J. (1999). Random threshold growth dynamics. Random Structures Algorithms 15 93–111. · Zbl 0932.60086 · doi:10.1002/(SICI)1098-2418(199908)15:1<93::AID-RSA4>3.0.CO;2-K
[4] Bramson, M. and Gray, L. (1991). A useful renormalization argument. In Random Walks, Brownian Motion, and Interacting Particle Systems. Festshrift in Honor of Frank Spitzer (R. Durrett and H. Kesten, eds.) 113–152. Birkhäuser, Boston. · Zbl 0745.60103
[5] Durrett, R. (1988). Lecture Notes on Particle Systems and Percolation . Brooks-Cole, Belmont, MA. · Zbl 0659.60129
[6] Durrett, R. and Liggett, T. M. (1981). The shape of the limit set in Richardson’s growth model. Ann. Probab. 9 186–193. JSTOR: · Zbl 0457.60083 · doi:10.1214/aop/1176994460
[7] Eden, M. (1961). A two-dimensional growth process. Proc. Fourth Berkeley Symp. Math. Statist. Probab. 4 223–239. Univ. California Press, Berkeley. · Zbl 0104.13801
[8] Gravner, J. (1999). Recurrent ring dynamics in two-dimensional excitable cellular automata. J. Appl. Probab. 36 492–511. · Zbl 0945.60092 · doi:10.1239/jap/1032374467
[9] Gravner, J. and Griffeath, D. (1993). Threshold growth dynamics. Trans. Amer. Math. Soc. 340 837–870. JSTOR: · Zbl 0791.58053 · doi:10.2307/2154679
[10] Gravner, J. and Griffeath, D. (1996). First passage times for discrete threshold growth dynamics. Ann. Probab. 24 1752–1778. · Zbl 0872.60077 · doi:10.1214/aop/1041903205
[11] Gravner, J. and Griffeath, D. (1997). Multitype threshold voter model and convergence to Poisson–Voronoi tessellation. Ann. Appl. Probab. 7 615–647. · Zbl 0892.60096 · doi:10.1214/aoap/1034801246
[12] Gravner, J. and Griffeath, D. (1998). Cellular automaton growth on \(\mathbb Z^2\): Theorems, examples and problems. Adv. in Appl. Math. 21 241–304. · Zbl 0919.68090 · doi:10.1006/aama.1998.0599
[13] Gravner, J. and Griffeath, D. (1999). Reverse shapes in first-passage percolation and related growth models. In Perplexing Problems in Probability. Festshrift in Honor of Harry Kesten (M. Bramson and R. Durrett, eds.) 121–142. Birkhäuser, Boston. · Zbl 0948.60096
[14] Gravner, J., Tracy, C. and Widom, H. (2001). Limit theorems for height fluctuations in a class of discrete space and time growth models. J. Statist. Phys. 102 1085–1132. · Zbl 0989.82030 · doi:10.1023/A:1004879725949
[15] Griffeath, D. (1981). The basic contact process. Stochastic Process. Appl. 11 151–186. · Zbl 0463.60085 · doi:10.1016/0304-4149(81)90002-8
[16] Griffeath, D. Primordial soup kitchen. Available at http://psoup.math.wisc.edu.
[17] Hall, R. R. and Tenenbaum, G. (1988). Divisors . Cambridge Univ. Press. · Zbl 0653.10001
[18] Hammersley, J. M. and Welsh, D. J. (1965). First-passage percolation, subadditive processes, stochastic networks, and generalized renewal theory. In Bernoulli, Bayes, Laplace Anniversary Volume (J. Neyman and L. LeCam, eds.) 61–110. Springer, New York. · Zbl 0143.40402
[19] Janson, S., Luczak, T. and Rucinski, A. (2000). Random Graphs . Wiley, New York.
[20] Johansson, K. (2000). Shape fluctuations and random matrices. Comm. Math. Phys. 209 437–476. · Zbl 0969.15008 · doi:10.1007/s002200050027
[21] Kesten, H. (1993). On the speed of convergence in first-passage percolation. Ann. Appl. Probab. 3 296–338. JSTOR: · Zbl 0783.60103 · doi:10.1214/aoap/1177005426
[22] Kesten, H. and Schonmann, R. H. (1995). On some growth models with a small parameter. Probab. Theory Related Fields 101 435–468. · Zbl 0820.60084 · doi:10.1007/BF01202779
[23] Korshunov, A. D. and Shmulevich, I. (2002). On the distribution of the number of monotone Boolean functions relative to the number of lower units. Discrete Math. 257 463–479. · Zbl 1006.90056 · doi:10.1016/S0012-365X(02)00507-1
[24] Liggett, T. M., Schonmann, R. H. and Stacey, A. M. (1997). Domination by product measures. Ann. Probab. 25 71–95. · Zbl 0882.60046 · doi:10.1214/aop/1024404279
[25] Marchand, R. (2002). Strict inequalities for the time constant in first passage percolation. Ann. Appl. Probab. 12 1001–1038. · Zbl 1062.60100 · doi:10.1214/aoap/1031863179
[26] Meakin, P. (1998). Fractals, Scaling and Growth far from Equilibrium. Cambridge Univ. Press. · Zbl 1064.37500
[27] Newman, C. M. and Piza, M. S. T. (1995). Divergence of shape fluctuations in two dimensions. Ann. Probab. 23 977–1005. JSTOR: · Zbl 0835.60087 · doi:10.1214/aop/1176988171
[28] Pimpinelli, A. and Villain, J. (1999). Physics of Crystal Growth. Cambridge Univ. Press.
[29] Richardson, D. (1973). Random growth in a tessellation. Proc. Cambridge Philos. Soc. 74 515–528. · Zbl 0295.62094 · doi:10.1017/S0305004100077288
[30] Seppäläinen, T. (1998). Exact limiting shape for a simplified model of first-passage percolation on the plane. Ann. Probab. 26 1232–1250. · Zbl 0935.60093 · doi:10.1214/aop/1022855751
[31] Seppäläinen, T. (1999). Existence of hydrodynamics for the totally asymmetric simple \(K\)-exclusion process. Ann. Probab. 27 361–415. · Zbl 0947.60088 · doi:10.1214/aop/1022677266
[32] Sethna, J. Equilibrium crystal shapes. Available at http://www.lassp.cornell.edu/sethna/CrystalShapes/.
[33] Steele, J. M. (1997). Probability Theory and Combinatorial Optimization. SIAM, Philadelphia. · Zbl 0916.90233
[34] Steele, J. M. and Zhang, Y. (2003). Nondifferentiability of the time constants of first-passage percolation. Ann. Probab. 31 1028–1051. · Zbl 1029.82017 · doi:10.1214/aop/1048516544
[35] Toom, A. L. (1974). Nonergodic multidimensional systems of automata. Probl. Inf. Transm. 10 239–246. · Zbl 0315.94053
[36] Toom, A. L. (1980). Stable and attractive trajectories in multicomponent systems. In Advances in Probability and Related Topics (R. L. Dobrushin and Ya. G. Sinai, eds.) 6 549–575. Dekker, New York. · Zbl 0441.68053
[37] Willson, S. J. (1978). On convergence of configurations. Discrete Math. 23 279–300. · Zbl 0395.52005 · doi:10.1016/0012-365X(78)90009-2
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.