COMPUTING SCIENCE
Up a Lazy River
Meandering through a classic theory of why rivers meander
Brian Hayes
River of Randomness
The random-walk model of river meandering is one example of how a
local rule—in this case aimless wandering—might give
rise to large-scale regularity. The premise is that over decades or
centuries, a river channel can drift over its floodplain, twisting
and shifting at random (although always subject to certain
constraints, such as not flowing uphill). Any configuration is
possible, but all of the most likely ones, according to Leopold,
look something like a sine-generated curve.
The mention of random walks in this context both intrigued and
confused me. Random walks have become a common notion in recent
years, and yet the kind of walk that yields the sine-generated curve
was not one I had encountered before. From Leopold's description I
was not able to grasp all the details. He referred to earlier work
by Hermann von Schelling, but the crucial document was a 1964
technical report from the General Electric Company, which I had a
hard time tracking down. Eventually I found a copy at the Smith
College library.
The process studied by von Schelling is one in which a walker takes
a step of unit length, turns through a randomly selected angle,
takes another step in the new direction, and so on. Not just any
such walk qualifies, however. To be admitted, a walk must begin by
leaving point a at a specified angle; it must end by
reaching point b; and in between it must cover a specified
distance L. Among random paths that satisfy these
constraints, von Schelling asked what the most frequent or likely
paths might look like. If the walker chooses each step's direction
from a uniform probability distribution (so that any angle is
equally likely), von Schelling got no nontrivial answer. But he did
find a solution for a walk where the turning angle at each step is
drawn at random from a normal, or Gaussian, distribution with a mean
of zero.
Von Schelling's mathematical solution takes the form of an integral
that he found difficult to evaluate. The sine-generated curve is an
approximation to the value of this integral—inexact, but quite
close within the range of parameter values of interest for river
meanders. Strictly speaking, the properties of minimal squared
curvature and minimal directional variance have been proved only for
the exact curve defined by the integral, not for the approximation.
At the level of detail needed for describing river channels,
however, the discrepancy is of no consequence.
From a computational point of view, the trouble with these
most-frequent random walks is that they're not nearly frequent
enough. The naive algorithm for generating examples of such paths
calls for launching many walkers from point a, all in the
appropriate initial direction, and then discarding all walks except
those that happen to reach point bafter exactly
Lunit-length steps. There are infinitely many walks that
satisfy these criteria, and yet the probability of ever seeing one
is zero. Life is too short to wait for such events.
In order to get some rough idea of what individual von Schelling
walks might look like, I have tried a sloppier algorithm. Instead of
insisting that a walk end precisely at point b, I accept
any walk that takes the requisite number of steps and lands within
one further step of b. Even with this relaxed criterion,
the algorithm is practical only for fairly short walks.
Superimposing a few hundred of these walks produces quite a frizzy
hairball, but taking the average of all the paths yields a smooth
arc that resembles a sine-generated curve. One peculiarity of the
average walk is its asymmetry: It leans one way or the other,
depending on the departure angle at point a. The reason is
that we have specified the direction of the initial segment but put
no constraint on the final step at b. This may have been an
oversight in the way the problem was formulated by von Schelling.
(On the other hand, for what it's worth, many river meanders exhibit
systematic asymmetry, typically crossing the valley at a sharper
angle on the upstream leg.)
A deeper perplexity awaits when we go in search of von Schelling's
"most likely" or "most frequent" random walk.
Should we look for it among the individual walk trajectories, or in
the average of all such walks? Which of these is the right model for
a river meander? Often, the terms "typical" and
"average" are nearly synonymous, and Leopold clearly
thought that the average would be representative of the population;
"the most probable path is the average path of a random
walk," he wrote. In other words, if you choose a random walk at
random, it will probably be much like the average of all random
walks. Von Schelling offered an analogy with thermodynamics, where
uncommon events (such as perfume returning to its bottle) are so
utterly improbable that we invent laws of physics to forbid them.
It's a fundamental assumption, he wrote, "that in our
environment random walks are approaching most frequent paths in an
overwhelming majority of cases." But then he added: "This
is far from being self-evident."
It's certainly not evident in the little sample of walks I
generated. Not one of the individual walks looks anything like the
average of all the walks. If we imagine a river channel wandering
over a floodplain according to this algorithm, wouldn't a snapshot
made at some arbitrary moment be likely to resemble a single random
walk, rather than the average? But it's the average of the walks
that corresponds more closely to the sine-generated curve and to the
shapes seen in real landscapes.
Admittedly, the algorithm that generated these specimens is inexact,
at best. Von Schelling's calculations call for taking a limit as the
step size goes to zero, and my simulations are nowhere near that
limit. Also, it should be noted that individual walks can be made
more like the average walk by reducing the standard deviation of the
angular distribution—by squeezing the randomness out of the
random walk. Still, as von Schelling noted, it's far from
self-evident that the typical path will ever come to resemble the
average path.
» Post Comment