| Título: | Density classification on infinite lattices and trees |
| Autores: |
Bušić, Ana; INRIA & ÉNS Fatès, Nazim; Inria & Nancy Université Mairesse, Jean; Université Paris Diderot - Paris 7 Marcovici, Irène; Université Paris Diderot - Paris 7 |
| Fecha: | 2013-01-04 |
| Publicador: | Electronic journal of probability |
| Fuente: |
 |
| Tipo: | Peer-reviewed Article |
| Tema: |
Cellular automata, interacting particle systems, density classification. Primary: 60K35; 68Q80. Secondary: 37B15; 60J05. |
| Descripción: | Consider an infinite graph with nodes initially labeled by independent Bernoullirandom variables of parameter p. We address the density classification problem, that is, we want to design a (probabilistic or deterministic)cellular automaton or a finite-range interacting particle system that evolves on this graph and decides whether p is smaller or larger than 1/2. Precisely, the trajectories should converge to the uniform configuration with only 0's if p<1/2, and only 1's if p>1/2. We present solutions to the problem on the regular grids of dimension d, for any d>1, and on the regular infinite trees. For the bi-infinite line, we propose some candidates that weback up with numerical simulations. |
| Idioma: | Inglés |
1 Lévy Classes and Self-Normalization por Khoshnevisan, Davar; University of Utah | 6 Time-Space Analysis of the Cluster-Formation in Interacting Diffusions por Fleischmann, Klaus; Weierstrass Institute for Applied Analysis and Stochastics,Greven, Andreas; Universitat Erlangen-Nurnberg |
2 Hausdorff Dimension of Cut Points for Brownian Motion por Lawler, Gregory F.; Duke University and Cornell University | 7 Conditional Moment Representations for Dependent Random Variables por Bryc, Wlodzimierz; University of Cincinnati |
3 Eigenvalue Expansions for Brownian Motion with an Application to Occupation Times por Bass, Richard F.; University of Washington,Burdzy, Krzysztof; University of Washington | 8 Almost Sure Exponential Stability of Neutral Differential Difference Equations with Damped Stochastic Perturbations por Liao, Xiao Xin; University of Strathclyde,Mao, Xuerong; University of Strathclyde |
4 Random Discrete Distributions Derived from Self-Similar Random Sets por Pitman, Jim; University of California, Berkeley,Yor, Marc; Université Pierre et Marie Curie | 9 Quantitative Bounds for Convergence Rates of Continuous Time Markov Processes por Roberts, Gareth O.; University of Cambridge,Rosenthal, Jeffrey S.; University of Toronto |
5 A Microscopic Model for the Burgers Equation and Longest Increasing Subsequences por Seppäläinen, Timo; Iowa State University | 10 Metastability of the Three Dimensional Ising Model on a Torus at Very Low Temperatures por Ben Arous, Gérard; Ecole Normale Supérieure,Cerf, Raphaël; Université Paris Sud |