Dyck paths, Motzkin paths and traffic jams

R. A. Blythe, W. Janke, D. A. Johnston, Ralph Kenna

Research output: Contribution to journalArticle

14 Citations (Scopus)
1 Downloads (Pure)

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 interpreted 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.
Original languageEnglish
Article numberP10007
JournalJournal of Statistical Mechanics: Theory and Experiment
Volume2004
DOIs
Publication statusPublished - 21 Oct 2004

Fingerprint

Motzkin Paths
Dyck Paths
Asymmetric Exclusion Process
Traffic Jam
exclusion
traffic
Normalization
Lattice Paths
Update
Partition Function
equivalence
partitions
Thermodynamics
Equivalence
thermodynamics
jamming
Equilibrium Model
Jamming
transit
Traffic Flow

Bibliographical note

The full text is also available from: http://de.arxiv.org/abs/cond-mat/0405314
This is an author-created, un-copyedited version of an article accepted for publication/published in Journal of Statistical Mechanics: Theory and Experiment. IOP Publishing Ltd is not responsible for any errors or omissions in this version of the manuscript or any version derived from it. The Version of Record is available online at http://dx.doi.org/10.1088/1742-5468/2004/10/P10007.

Cite this

Dyck paths, Motzkin paths and traffic jams. / Blythe, R. A.; Janke, W.; Johnston, D. A.; Kenna, Ralph.

In: Journal of Statistical Mechanics: Theory and Experiment, Vol. 2004, P10007, 21.10.2004.

Research output: Contribution to journalArticle

@article{b69049f893d9407a8cdb08b5eee77779,
title = "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 interpreted 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.",
author = "Blythe, {R. A.} and W. Janke and Johnston, {D. A.} and Ralph Kenna",
note = "The full text is also available from: http://de.arxiv.org/abs/cond-mat/0405314 This is an author-created, un-copyedited version of an article accepted for publication/published in Journal of Statistical Mechanics: Theory and Experiment. IOP Publishing Ltd is not responsible for any errors or omissions in this version of the manuscript or any version derived from it. The Version of Record is available online at http://dx.doi.org/10.1088/1742-5468/2004/10/P10007.",
year = "2004",
month = "10",
day = "21",
doi = "10.1088/1742-5468/2004/10/P10007",
language = "English",
volume = "2004",
journal = "Journal of Statistical Mechanics: Theory and Experiment",
issn = "1742-5468",
publisher = "IOP Publishing",

}

TY - JOUR

T1 - Dyck paths, Motzkin paths and traffic jams

AU - Blythe, R. A.

AU - Janke, W.

AU - Johnston, D. A.

AU - Kenna, Ralph

N1 - The full text is also available from: http://de.arxiv.org/abs/cond-mat/0405314 This is an author-created, un-copyedited version of an article accepted for publication/published in Journal of Statistical Mechanics: Theory and Experiment. IOP Publishing Ltd is not responsible for any errors or omissions in this version of the manuscript or any version derived from it. The Version of Record is available online at http://dx.doi.org/10.1088/1742-5468/2004/10/P10007.

PY - 2004/10/21

Y1 - 2004/10/21

N2 - 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 interpreted 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.

AB - 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 interpreted 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.

U2 - 10.1088/1742-5468/2004/10/P10007

DO - 10.1088/1742-5468/2004/10/P10007

M3 - Article

VL - 2004

JO - Journal of Statistical Mechanics: Theory and Experiment

JF - Journal of Statistical Mechanics: Theory and Experiment

SN - 1742-5468

M1 - P10007

ER -