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
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
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
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