Timo Seppalainen
A Microscopic Model for the Burgers Equation
and Longest Increasing Subsequences
(127K, AMS-TeX)
ABSTRACT. We introduce
an interacting random process
related to Ulam's problem, or finding
the limit of the normalized longest
increasing subsequence of a random permutation.
The process describes the evolution of a
configuration of sticks on the sites of the
one-dimensional integer lattice.
Our main result is a hydrodynamic scaling limit:
The empirical stick profile converges
to a weak solution of the inviscid Burgers equation under
a scaling of lattice space and time.
The stick process is an alternative view of
Hammersley's particle system recently used by Aldous
and Diaconis to give a new solution to Ulam's problem.
Along the way to the scaling limit we also
produce a solution to this
question.
The heart
of the proof is that
individual paths of the stochastic process
evolve under a semigroup action which under the scaling
turns into the corresponding action for
the Burgers equation. This semigroup
action
for nonlinear scalar
conservation laws in one space variable is developed
in a separate appendix, where we give an existence result
and a uniqueness criterion for solutions of
such equations with initial
data given by a Radon measure.