A Microscopic Model for the Burgers Equation and Longest Increasing Subsequences

Timo Seppäläinen (Iowa State University)


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 also an alternative view of Hammersley's particle system that Aldous and Diaconis used to give a new solution to Ulam's problem. Along the way to the scaling limit we produce another independent 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, known as the Lax formula. In a separate appendix we use the Lax formula to give an existence and uniqueness proof for scalar conservation laws with initial data given by a Radon measure.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-51

Publication Date: March 6, 1996

DOI: 10.1214/EJP.v1-5


  1. D. Aldous and P. Diaconis, Hammersley's interacting particle process and longest increasing subsequences, Probab. Theory Relat. Fields 103, (1995), 199--213. Math Review article not available.
  2. R. Durrett, Probability: Theory and Examples, Wadsworth, Pacific Grove (1991). Math Review link
  3. M. Ekhaus and T. Sepp"al"ainen, Stochastic dynamics macroscopically governed by the porous medium equation for isothermal flow, Ann. Acad. Sci. Fenn. Ser. A I Math (to appear). Math Review article not available.
  4. S. N. Ethier and T. G. Kurtz, Markov Processes: Characterization and Convergence, Wiley, New York (1985). Math Review link
  5. S. Feng, I. Iscoe, and T. Sepp"al"ainen, A class of stochastic evolutions that scale to the porous medium equation, J. Statist. Phys. ( to appear). Math Review article not available.
  6. P. A. Ferrari, Shocks in one-dimensional processes with drift, Probability and Phase Transitions, ed. G. Grimmett, Kluwer Academic Publishers (1994). Math Review link
  7. J. M. Hammersley, A few seedlings of research, Proc. Sixth Berkeley Symp. Math. Stat. Probab. Vol. I, (1972), 345--394. Math Review link
  8. C. Kipnis, Central limit theorems for infinite series of queues and applications to simple exclusion, Ann. Probab. 14, (1986), 397--408. Math Review link
  9. P. Lax, Hyperbolic systems of conservation laws II, Comm. Pure Appl. Math. 10, (1957), 537--566. Math Review link
  10. P. Lax, Hyperbolic Systems of Conservation Laws and the Mathematical Theory of Shock Waves, SIAM, Philadelphia, (1973). Math Review link
  11. T. M. Liggett, Interacting Particle Systems, Springer-Verlag, New York, (1985). Math Review link
  12. P. L. Lions, Generalized Solutions of Hamilton-Jacobi Equations, Pitman, London (1982). Math Review link
  13. F. Rezakhanlou, Hydrodynamic limit for attractive particle systems on $mmZ^d$, Comm. Math. Phys. 140, (1991), 417--448. Math Review link
  14. R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, (1970). Math Review link
  15. H. Rost, Non-equilibrium behaviour of a many particle process: Density profile and local equilibrium, Z. Wahrsch. Verw. Gebiete 58, (1981), 41--53. Math Review link
  16. J. Smoller, Shock Waves and Reaction-Diffusion Equations, Springer-Verlag, New York, (1983). Math Review link
  17. Y. Suzuki and K. Uchiyama, Hydrodynamic limit for a spin system on a multidimensional lattice, Probab. Theory Relat. Fields 95, (1993), 47--74. Math Review link

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.