Self-Organization of a Long-Range Schelling-Type Interacting Particle System
Skip to main content
eScholarship
Open Access Publications from the University of California

UC San Diego

UC San Diego Electronic Theses and Dissertations bannerUC San Diego

Self-Organization of a Long-Range Schelling-Type Interacting Particle System

  • Author(s): Omidvar, Hamed
  • Advisor(s): Franceschetti, Massimo
  • et al.
Abstract

Inspired by the Schelling model of self-organized segregation in social sciences and economics, we consider a long-range interacting particle system in which binary particles -- whose initial states are chosen uniformly at random -- are located at the nodes of a flat torus~$(\mathbb{Z}/h\mathbb{Z})^2$. Each node of the torus is connected to all the nodes located in an $l_\infty$-ball of radius $w$ in the toroidal space centered at itself and we assume that $h$ is exponentially larger than $w^2$. Based on the states of the neighboring particles and on the value of a common intolerance threshold $\tau$, every particle is labeled "stable," or "unstable." Every unstable particle that can become stable by flipping its state is labeled "p-stable." Finally, unstable particles that remain p-stable for a random, independent and identically distributed waiting time, flip their states and become stable. When the waiting times have an exponential distribution and $\tau \le 1/2$, this model is equivalent to a Schelling model of self-organized segregation in an open system, a zero-temperature Ising model with Glauber dynamics, or an Asynchronous Cellular Automaton (ACA) with extended Moore neighborhoods.

In this dissertation, we provide several results regarding the limiting configuration of the above model as well as its initial configuration and its dynamics over the time. First, we significantly extend the previously known results on the expected size of the monochromatic balls formed at the end of the process by showing that for all ${\tau \in (\tau_1^*,1-\tau_1^*) \setminus \{1/2\}} $ where ${\tau_1^* \approx 0.433}$ the expected size of these balls is exponential in the size of the local neighborhood of interaction~$N$.We then further extend this interval to ${(\tau_2^*,1-\tau_2^*) \setminus \{1/2\}}$ where ${\tau_2^* \approx 0.344}$ by considering "almost monochromatic" balls, namely balls where the ratio of the number of particles of one type and the number of particles of the other type quickly vanishes as the size of the neighborhood grows. More notably, we then prove a concentration bound and a shape theorem for the ``spreading'' of the ``affected'' nodes -- namely nodes on which a particle of a given state would be p-stable. Furthermore, we show that when the process reaches a limiting configuration and no more state changes occur, for all ${\tau \in (\tau^*,1-\tau^*) \setminus \{1/2\}}$ where ${\tau^* \approx 0.488}$, w.h.p. any particle is contained in a large monochromatic ball of cardinality exponential in $N$. When particles are placed on the infinite lattice $\mathbb{Z}^2$ rather than on a flat torus, for the values of $\tau$ mentioned above, after a sufficiently long evolution time, w.h.p. any particle is contained in a large monochromatic ball of cardinality exponential in~$N$. Finally, we improve these results by showing that the interval of $\tau$ can be extended to ${ (\tau^{**},1-\tau^{**}) \setminus \{1/2\}}$ where ${\tau^{**} \approx 0.433}$.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View