This post explains how the Markov chain dichotomy of transience and recurrence implies dichotomous behavior for certain models of collective motion.

One way to model the motion of a collective with $n$ individuals is as a Markov chain on $n$-element subsets of a grid.¹ This approach has been validated by correctly predicting aspects of the collection motion of a swarm of robots.² Harmonic activation and transport (HAT), which I briefly described in an older post, also fits this description.³

Collective states 🔗

In this context, it is often natural to view collective states up to translation, such as when assessing dispersion or aggregation, or when forming shapes.⁴ For example, consider the state space $$ \Omega := \{ A \subset \mathbb{Z}^d: |A| = n\} $$ for positive integers $d$ and $n$. Define the equivalence relation $\sim$ on $\Omega$ according to $A \sim B$ if and only if $A$ is a translate of $B,$ i.e., $$ A \sim B \quad \iff \quad \exists \, z \in \mathbb{Z}^d: B = \{a+z: a \in A\}. $$ Denote by $\widehat{A}$ the class of elements of $\Omega$ which are translates of $A$ and define $\mathrm{diam} (\widehat{A})$ to be the diameter of any representative of the class $\widehat{A}$.

The key difference between $\Omega$ and $\widehat{\Omega}$ is that there are only finitely many elements of $\widehat{\Omega}$ with a given diameter, which is not true of $\Omega$. This fact, paired with the Markov chain dichotomy, will imply a dichotomy in the behavior of the diameter of collective states.

Markov chain dichotomy 🔗

A standard result in Markov chain theory states that an irreducible (time-homogeneous) Markov chain $$ (X(0), X(1), \dots) $$ on a countable state space $\Sigma$ is either transient or recurrent. Define the number of visits it makes to $\sigma \in \Sigma$ by $$ V (\sigma) := \sum_{t=0}^\infty \mathbf{1}_{\{ X(t) = \sigma\}}. $$ Transience means that $${\color{red} \forall \, \sigma \in \Sigma, \quad \mathbb{P} \big( V(\sigma) < \infty \bigm\vert X(0) = \sigma \big) = 1}, $$ while recurrence means $${\color{blue} \forall \, \sigma \in \Sigma, \quad \mathbb{P} \big( V(\sigma) = \infty \bigm\vert X(0) = \sigma \big) = 1}. $$

Dichotomous behavior of collective diameter 🔗

Assume that the dynamics of the collective is described by a (time-homogeneous) Markov chain $$ (U(0), U(1), \dots) $$ that is irreducible on $\Omega$, in which case the corresponding Markov chain on states viewed up to translation,
$$ (\widehat{U}(0), \widehat{U}(1), \dots), $$ is an irreducible Markov chain on $\widehat{\Omega}$.

The Markov chain dichotomy states that $(\widehat{U}(t))_{t\geq 0}$ is either transient or recurrent. Because there are only finitely many states in $\widehat{\Omega}$ with a given diameter, the dichotomy implies that the limit infimum of the diameter of the collective is either infinite or finite, almost surely. To see why, consider the two cases.

Transience

Suppose that $(\widehat{U}(t))_{t\geq 0}$ is transient. For any real number $r$, there are only finitely many classes in $\widehat{\Omega}$ with diameter of $r$ or less, i.e., in $$ \{ \widehat{\omega} \in \widehat{\Omega}: \mathrm{diam} (\widehat{\omega}) \leq r \}. $$ By the definition of transience, these finitely many states are each visited only finitely many times almost surely, hence $$ \forall \, \widehat{\omega} \in \widehat{\Omega}, \quad \mathbb{P} \big( \liminf_t \mathrm{diam} (\widehat{U} (t)) > r \bigm\vert \widehat{U} (0) = \widehat{\omega} \big) = 1. $$ This conclusion holds for any $r$ and, since the event in question is decreasing as $r$ increases, it implies $${\color{red} \forall \, \widehat{\omega} \in \widehat{\Omega}, \quad \mathbb{P} \big( \liminf_t \mathrm{diam} (\widehat{U} (t)) = \infty \bigm\vert \widehat{U} (0) = \widehat{\omega} \big) = 1}. $$

Recurrence

Suppose instead that $(\widehat{U}(t))_{t\geq 0}$ is recurrent. While the diameter of $\widehat{U} (t)$ may become arbitrarily large, it nevertheless visits states with finite diameter infinitely often. Hence $${\color{blue} \forall \, \widehat{\omega} \in \widehat{\Omega}, \quad \mathbb{P} \big( \liminf_t \mathrm{diam} ( \widehat{U} (t) ) < \infty \bigm\vert \widehat{U} (0) = \widehat{\omega} \big) = 1.} $$

Discussion 🔗

Some collectives can exhibit both behaviors of diameter as $n$ varies

The pairs of red and blue statements show how the dichotomy of transience and recurrence implies a dichotomy in the behavior of diameter for Markov chain models of collective motion. For some models, like those which require the state to be a connected set, this dichotomy is irrelevant because the diameter is bounded in terms of the number of elements.¹ However, other models can realize both behaviors of diameter as $d$ and $n$ vary.

Indeed, for some values of $d$ and $n$, if HAT starts in a state with sufficiently large diameter, $r$, it tends to reach a state with a diameter of roughly $\log r$ over roughly $\log r$ steps.³ For other values of $d$ and $n$, HAT reaches a state consisting of well separated “clusters” of elements, which then grow increasingly separated, leading to unchecked diameter growth.⁵ The remarkable fact that the number of individuals mediates the different collective behaviors of HAT is the subject of an older post.

This change in behavior differs from familiar phase transitions

When a family of Markov chains indexed by $d$ and $n$ exhibits the two behaviors of diameter, the transition between them is an abrupt change in collective behavior akin to a phase transition. However, it differs in key ways from phase transitions in equilibrium statistical mechanics. For example, instead of being mediated by an inverse temperature parameter taking continuous values, the phase transition in HAT is mediated by discrete parameters, $d$ and $n$. Moreover, instead of occurring in a limit as $n \to \infty$, the phase transition in diameter occurs for finite $n$.

Li et al. used an Ising model–like phase transition to program a robot swarm to assume dispersed or aggregated phases, depending on the value of an inverse temperature parameter.² To do so, they encoded a bias toward aggregated states in the stationary distribution of a Markov chain, the dynamics of which the robot swarm implemented. In other words, the phase transition is reflected in two, stationary—hence recurrent—behaviors of the Markov chain.⁶ This contrasts the diameter dichotomy, which is associated with a recurrent behavior and a transient behavior. In this sense, the phase transition in HAT is occurring between classes whereas the one used by Li et al. is occurring within one class.

Takeaway: Some models of collective motion, depending on $n$, the number of individuals in the collective, must exhibit exactly one of two behaviors of the collective’s diameter. As $n$ varies, it is possible for the collective motion to switch between these behaviors. This is like a phase transition, but it differs in key ways from those of equilibrium statistical mechanics and those recently used to program robot swarms.