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.