comes to a halt (breaking out of the repeat loop at “stop”).
Take the first epoch: it is itself divided into subintervals by
the coupling times t1 < . . . < tl at which the set of wet agents
grows: Wtk Wtk+ 1. If Wt denotes the length of the smallest interval enclosing Wt, it can be shown by induction that
Wtk+ 1 ≤ 1 –ρk. It then follows that E1(s) = 0 and, for n ≥ 2,
En (s) ≤ 2nEn – 1 (s) + ( 1–ρn)s En(s) + n3,
which implies ( 2) for s < 1.
4. biRD fLocKinG
We briefly discuss a classic instance of a nondiffusive
influence system, bird flocking, and report the results
from Chazelle4. The alignment model we use8, 13, 24 is a
figure 3. the deflating matrix polytope.
trimmed-down version of Reynolds’s original model21. In
this influence system, d = 6 and each bird i is specified by
its position zi and velocity vi. The undirected communication graph G (x) joins any two birds within a certain fixed distance of each other (Figure 4). The birds in any connected
component form a flock. Reordering the coordinates of the
6n-dimensional state vector x as (z, v), we specify the dynamics as
where Q(x) is the n-by-n “velocity” stochastic matrix of a
(lazy) random walk on the graph G (x) and ⊗ is the Kronecker
product that distributes the action along each coordinate
axis. The matrix P is 2n-by-2n, so each entry is multiplied not
by a single coordinate in x but by a 3-tuple; in other words,
P(x) acts not on R2n but on (R3)2n. Although the velocities can
be inferred from the positions, they need to be included in
the phase space to keep the system Markovian.
figure 4. the bird at the center of the circle is influenced by its two
neighbors in it.