2. 3. What could go wrong?

There are two arguments against the feasibility of a domain-independent theory of natural algorithms. One is an intrinsic lack of structure. But the same can be said of graphs, a subject whose ties to algebra, geometry, and topology have met with resounding success, including the emergence of universality. A more serious objection is that, before we can analyze a natural algorithm, we must be able to specify it. The bottom-up, reductionist approach, which consists of specifying the functionality and communicability of each agent by hand (as is commonly done in swarming models), might not always work. Sometimes, only a top-down, phenomenological approach will get us started on the right track. We have seen this before: the laws of thermodynamics were not derived as abstractions of Newton’s laws—though that is what they are—but as rules governing observable macrostates (P, V, T, and all that). Likewise, a good flocking model might want to toss aside anthropomorphic rules (“stay aligned,” “don’t stray,” etc.) and choose optimized statistical rules inferred experimentally. The specs of the natural algorithm would then be derived algorithmically. This is why we have placed virtually no restriction on the communication function G in our present analysis of diffusive influence systems.

2. 4. outline

We open the discussion in Section 3 with the total s-energy, a key analytical device used throughout. We turn to bird flocking in Section 4, which constitutes the archetypical nondiffusive influence system. We take on the diffusive case in Section 5, with the notion of algorithmic calculus discussed in Section 6.d General diffusive influence systems are Turing-complete, yet the mildest perturbation creates periodic behavior. This is disconcerting. Influence systems model how people change opinions over time as a result of human interaction and knowledge acquisition. Instead of ascending their way toward enlightenment, however, people are doomed to recycle the same opinions in perpetuity—there is a deep philosophical insight there, somewhere.

3. the -eneRGY

This section builds the tools needed for the bidirectional case and can be read separately from the rest. Let (Pt)t≥0 be an infinite sequence of n-by-n stochastic matrices; stochastic means that the entries are nonnegative and the rows sum up to 1. Leaving aside influence systems for a moment, we make no assumption about the sequence, not even that it is produced endogenously. We ask a simple question about matrix sequences: under what conditions does P<t : = Pt – 1 . . . P0 converge as t → ∞ Certainly not if The problem here is lack of self-confidence: the two agents in the system do not trust themselves and follow their d Unless noted otherwise, the results discussed are from Chazelle5 for Section 3; Chazelle4 for Section 4; Chazelle6 for sections 5 and 6.

neighbors blindly. So let us assume that the diagonal entries of Pt are positive. Alas, this still does not do the trick: the matrices grant the agents self-confidence, yet composing them in alternation exchanges the vectors (0, 1, 1/4) and (0, 1, 3/4) endlessly. The oscillation is caused by the lack of bidirectionality: for example, the recurring link from agent 3 to agent 1 is never reciprocated. The fix is to require the graphs to be undirected or, equivalently, the matrices to be type-symmetric,e which instills mutual confidence among the agents. With both self-confidence and bidirectionality in place, the sequence P<t always converges12, 14, 16. (Interestingly, this is not true of forward products P0 . . . Pt in general.) With nothing keeping (Pt )t ≥ 0 from “stalling” by featuring arbitrarily long repeats of the identity matrix, bounding the convergence rate is obviously impossible. Yet an analytical device, the total s-energy5, allows us to do just that for bidirectional diffusive influence systems. The trick is to show that they cannot stall too long without dying off.

3. 1. Preliminaries

Fix a small r > 0 and let (Pt )t ≥ 0 be a sequence of stochastic
matrices such that r ≤ (Pt )ii ≤ 1 − r and (Pt )ij > 0 ⇒ (Pt)ji > 0.
Let Gt be the (undirected) graph whose edges are the positive
entries in Pt. With x(t + 1) = Pt x(t) and x(0) = x ∈ [0, 1]n, the
total s-energy is defined as
( 1)

We use the s-energy in much the same way one uses Chernoff’s inequalities to bound the tails of product distributions. Being a generalized Dirichlet series, the s-energy can be inverted and constitutes a lossless encoding of the edge lengths. Why this unusual choice? Because, as with the most famous Dirichlet series of all, the Riemann zeta function Σn–s, the system’s underlying structure is multiplicative: indeed, just as n is a product of primes, xi(t) − xj(t) is a product of the form v T Pt− 1 . . . P0 x. Let En(s) denote the maximum value of E(s) over all x ∈ [0, 1] n. One should expect the function En(s) to encode all sorts of symmetries. This is visible in the case n = 2 by observing that it can be continued meromorphically in the whole complex plane (Figure 1).

The sequence formed by (Pt )t ≥0 is called reversible if Gt is connected and there is a probability distribution (p1, . . . , pn) such that pi(Pt )ij = pj(Pt )ji for any t; see detailed definition in Chazelle5. This gives us a way to weight the agents so that their mass center never moves. The notion generalizes the concept of reversible Markov chains, with which it shares some of the benefits, including faster convergence to equilibrium.

e The zero-entries of a type-symmetric matrix and its transpose occur at the same locations.