Dyck Paths, Motzkin Paths and Traffic Jams

Abstract

It has recently been observed that the normalization of a one-dimensional out-of-equilibrium model, the Asymmetric Exclusion Process (ASEP) with random sequential dynamics, is exactly equivalent to the partition function of a two-dimensional lattice path model of one-transit walks, or equivalently Dyck paths. This explains the applicability of the Lee-Yang theory of partition function zeros to the ASEP normalization. In this paper we consider the exact solution of the parallel-update ASEP, a special case of the Nagel-Schreckenberg model for traffic flow, in which the ASEP phase transitions can be intepreted as jamming transitions, and find that Lee-Yang theory still applies. We show that the parallel-update ASEP normalization can be expressed as one of several equivalent two-dimensional lattice path problems involving weighted Dyck or Motzkin paths. We introduce the notion of thermodynamic equivalence for such paths and show that the robustness of the general form of the ASEP phase diagram under various update dynamics is a consequence of this thermodynamic equivalence.

Version accepted for publication

References in corpus (18)

• Nonequilibrium Critical Phenomena and Phase Transitions into Absorbing States
• Phase transitions in an exactly soluble one-dimensional exclusion process
• Steady-state selection in driven diffusive systems with open boundaries
• Exact solution of a cellular automaton for traffic
• Exact solution of a partially asymmetric exclusion model using a deformed oscillator algebra
• Exact Stationary State for an ASEP with Fully Parallel Dynamics
• Lee-Yang zeros and phase transitions in nonequilibrium steady states
• The Lee-Yang theory of equilibrium and nonequilibrium phase transitions
• Matrix Product Eigenstates for One-Dimensional Stochastic Models and Quantum Spin Chains
• Yang-Lee Theory for a Nonequilibrium Phase Transition
• The asymmetric Exclusion Process and Brownian Excursions
• Asymmetric Exclusion Model and Weighted Lattice Paths
• Nonequilibrium Dynamics in Low Dimensional Systems
• The raise and peel model of a fluctuating interface
• Yang-Lee zeros for a nonequilibrium phase transition
• Nonequilibrium stationary states and equilibrium models with long range interactions
• Yang-Lee zeroes for an urn model for the separation of sand
• First Order Phase Transition in a Reaction-Diffusion Model With Open Boundary: The Yang-Lee Theory Approach

Cited by in corpus (14)

• Nonequilibrium Steady States of Matrix Product Form: A Solver's Guide
• Matrix representation of the stationary measure for the multispecies TASEP
• Continued Fractions and the Partially Asymmetric Exclusion Process
• Temporal evolution of product shock measures in TASEP with sublattice-parallel update
• Motzkin numbers out of Random Domino Automaton
• The totally asymmetric exclusion process on a ring: Exact relaxation dynamics and associated model of clustering transition
• Combinatorial mappings of exclusion processes
• An introduction to phase transitions in stochastic dynamical systems
• The parallel TASEP, fixed particle number and weighted Motzkin paths
• Equivalence of a one-dimensional driven-diffusive system and an equilibrium two-dimensional walk model
• Boundary drive induced formation of aggregate condensates in stochastic transport with short-range interactions
• Partition function zeros of zeta-urns
• Partition Function Zeros of Paths and Normalization Zeros of ASEPS
• Relaxation time in a non-conserving driven-diffusive system with parallel dynamics