{'fraction_non_alphanumeric': 0.04241624030368048, 'fraction_numerical': 0.012658854596468065, 'mean_word_length': 4.281642259414226, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The asymmetric exclusion process: Comparison of update procedures

The asymmetric exclusion process (ASEP) has attracted a lot of interest not only because its many applications, e.g. in the context of the kinetics of biopolymerization and traffic flow theory, but also because it is a paradigmatic model for nonequilibrium systems. Here we study the ASEP for different types of updates, namely random-sequential, sequential, sublattice-parallel and parallel. In order to compare the effects of the different update procedures on the properties of the stationary state, we use large-scale Monte Carlo simulations and analytical methods, especially the so-called matrix-product Ansatz (MPA). We present in detail the exact solution for the model with sublattice-parallel and sequential updates using the MPA. For the case of parallel update, which is important for applications like traffic flow theory, we determine the phase diagram, the current, and density profiles based on Monte Carlo simulations. We furthermore suggest a MPA for that case and derive the corresponding matrix algebra.


Introduction
For nonequilibrium systems in low dimensions an understanding can often be gained by studying rather simple models [1][2][3][4][5][6]. The one-dimensional asymmetric exclusion process (ASEP) has been used to describe various problems in different fields of interest, such as the kinetics of biopolymerization [7] and traffic [8]. On the other hand, the ASEP is so simple that it has achieved a paradigmatic status for nonequilibrium systems [9]. It can be mapped onto a surface growth model known as the single-step model [10] and in the appropriate hydrodynamical limit its density profile obeys the Burgers equation which is itself closely related to the KPZ equation [11]. The ASEP can also be viewed as a prototype for so-called boundary-induced phase transitions [12]: the boundaries, which can inject and remove particles from the system, govern -in a subtle interplay with the local dynamical rules -the macroscopic behaviour of the model and can produce different phases and phase transitions.
In [13] recursion relations on the system size have been derived for the ASEP with randomsequential update and open boundary conditions. Open boundaries here and in the following mean that particles are injected at one end of a chain of L sites with probability α and are removed at the other end with probability β. In [13] these recursion relations were solved for the special case α = β = 1. This solution was later extended in [14] to general α and β. A very elegant solution of the general case was given at the same time in [15] using a matrix product Ansatz (MPA) for the weights of the stationary configurations similar to the matrix product groundstate of certain quantum spin chains [16]. This Ansatz can be used to compute density profiles and correlation functions. The relationship between the MPA for quantum spin chains and one-dimensional models of statistical physics will be discussed in this paper.
Since then the MPA was extended to find the transient of the model [17], to describe the ASEP with a defect in form of an additional particle with a different hopping rate [18] or a blockage [19], to solve the case of oppositely charged particles (with hard-core repulsion), which move in opposite directions (driven by an external electric field) and can interchange their charge if they meet [20]. The MPA was also used to recover solutions of certain integrable reaction-diffusion models [21].
Most of these solutions have been found for random-sequential dynamics. In that case the master equation can be rewritten as a Schrödinger-like equation for a "Hamiltonian" with interactions between nearest-neighbours only [22]. Other updates lead to more complicated master equations with non-local interactions.
It also turned out that the MPA is not just an Ansatz. The stationary state of an onedimensional stochastic model with arbitrary nearest-neighbor interactions and randomsequential update can always be written as a matrix product [23]. This is also true for an ordered-sequential or sublattice-parallel update, which can be shown to be intimately related [24]. The matrices in the MPA are generally infinite-dimensional. Therefore, evaluating physical quantities such as density profiles is still a formidable task, but often it is at least possible to obtain asymptotic expressions. However, in certain regions of the parameter space the matrices can reduce to low-dimensional variables. A simple example is the case of one-dimensional matrices, which is equivalent to a mean-field solution.
The implementation of the order of application of the local transition rates for a given model (the type of update) is an essential part of the definition of the model, since the transient and even the stationary state may differ dramatically [25]. In the following, the ASEP will be studied with types of update that are often more useful for Monte Carlo simulations than the random-sequential update. The aim of this paper is to use the ASEP as a case study to investigate the consequences of different types of updates onto the stationary state of a nonequilibrium model with open boundaries. Concerning the analytical treatment, the MPA turns out to be a useful tool.
Hinrichsen [26] was the first to apply the MPA to the ASEP with sublattice-parallel update and deterministic bulk dynamics. He could confirm earlier conjectures for the correlation functions [27]. It is important to note that this update is substantially different from the fully-parallel update used for example for modeling traffic flow. Nevertheless, to our knowledge this is the first model with a discrete-time update which has been solved using the MPA. The results presented here build partially on our previous work [28], where we found a mapping of the ASEP with ordered-sequential and sublattice-parallel update onto the random-sequential case. For sublattice-parallel update this was done independently by Honecker and Peschel [29]. We will explain the mapping in more detail and give a physical interpretation of the underlying Ansatz. As a by-product, we solve the model on a ring.
We also study numerically and analytically the ASEP with parallel update and present new results like the phase diagram and the current. We show that the model can be described by a matrix-product structure at least for small systems. The underlying algebra is somewhat different to the other ones because a third state appears, which is neccessary to decompose the transfer matrix into a more simple product. This paper is organized as follows: Section 2 gives the definitions of the model and the updates used and establishes a precise relationship between the MPA for the stationary state of a stochastic model and for the groundstate of quantum spin chains. Section 3 is devoted to the MPA for the ASEP with discrete-time updates. In Section 3.1 the matrix algebra for the ordered-sequential and the sublattice-parallel update is derived. In Section 3.2 we propose a MPA for the parallel update by mapping the model onto a 3-state model with an ordered-sequential update. Furthermore, we find a special line in parameter space where the 2-cluster approximation becomes exact. In Section 4 we use the mathematical results of Section 3 and Monte Carlo simulations to calculate the current, density profiles and correlation functions for the discrete-time updates. Finally, Section 5 contains a concluding discussion. We have included several appendices, which mainly list details of the calculations.
2 Definition of the ASEP and the MPA 3

The ASEP and the different updates
Consider sites located on a chain of length L. Each site i (1 ≤ i ≤ L) is either occupied by a particle (τ i = 1), or it is empty (τ i = 0). We have three basic mechanisms (see Fig. 1): Hopping: We look at the pair (i, i + 1). If we find a particle at site i and no particle ("hole") at site i + 1, we move the particle one site to the right with probability p. In the remaining cases, nothing happens. Injection and removal: At the boundaries particles/holes can be injected and/or removed. At the left boundary a particle can be injected with probability α if site 1 is empty. At the right end of the chain a particle will be removed with probability β. The model can be generalized to allow hopping in both directions by introducing a probability q for hopping onto an unoccupied site to the left. Furthermore, one can also inject particles at the right end and remove particles at the left end. These modifications do not change the basic features of the model and will not be considered in the following.
We now have to define the order in which to perform the hopping, the injection and the removal in terms of time and space. There are four basic ways to do that: (a) random-sequential update: We pick at random a site i. If 2 ≤ i ≤ L − 1, each particle has a probability pdt of jumping to the right (if this site is empty). If i = 1 , we allow for hopping to the right with probability pdt and particle injection with rate α if this site is empty. For i = L a particle is removed with rate β if the site is occupied. This update is the realization of the usual master equation in continuous time. A different p would simply result in a rescaling of time (see Sect. 3). As a consequence, the phase diagram of the ASEP with update (a) depends only trivially on p. Therefore one can set p = 1 which is most efficient for computer simulations. The following three updates are discrete in time. (b) sublattice-parallel update: We first use our rule for injection (removal) at site 1(L). We then perform our rules for hopping on the pairs (2, 3), (4,5) etc. After that, we update the pairs (1, 2), (3,4) etc (L has to be even). This update can be used efficiently for computer simulations. Its main advantage for theoretical purposes is that its transfer matrix can be written as a product of local terms. (c) ordered-sequential update: We start at the right end of the chain and remove a particle at site i = L with probability β. We then update the pair (i = L − 1, i = L). We continue with pair (i = L−2, i = L−1) and so forth, until the left end of the chain is reached. After the update of pair (i = 1, i = 2), we allow for injection at site i = 1. For models where particles only hop to the right this update may also be called more precisely 'backwardordered-sequential update'. Obviously, the order of update can also be reversed. For the ASEP, these two updates are connected by a particle-hole symmetry: injecting particles can be regarded as removing holes, and vice versa. Therefore it is sufficient to study just one of the ordered-sequential updates. We would like to point out that in principle one has to distinguish two different types of ordered-sequential updates which one could name site-ordered-sequential and particle-4 ordered-sequential, respectively. In contrast to the site-ordered-sequential update described in (c) above, in the particle-ordered-sequential update the rules are only applied to occupied sites, i.e. to particles. This might have a strong effect, as can be seen most easily for the case of small particle numbers and the completely asymmetric deterministic case p = 1. In the case of site-sequential update a single particle injected at the left end moves through the lattice in one timestep (i.e., one sweep through the lattice). For the particle-sequential update a timestep means updating occupied sites only and so the particle moves only one site. By looking at a lattice with two particles, one can already see that the two different updates might introduce rather different correlations. Starting with particles separated by d empty sites, in the site-ordered-sequential update the left particle will move to the right until it reaches the right particle, which then starts to move. On the other hand, in the case of particle-ordered-sequential update the particles will stay always d or d − 1 sites apart. For general values of p the situation is similar. The differences between these two sequential update procedures manifest itself also in the solution for periodic boundary conditions. We will come back to this point in Section 4.1. In the following we will always consider the site-ordered-sequential updateuntil stated otherwiseto which we will refer as ordered-sequential update for brevity. (d) parallel update: The rules for hopping, injection, and removal are applied simultaneously to all sites of the whole chain 1 . The parallel update usually produces the strongest correlations and is used for traffic simulations [8]. In the case of the ASEP, it is nearly identical to the particle-orderedsequential update. If the ASEP with updates (a)-(c) is put on a ring (no injection/removing of particles and periodic boundary conditions), a trivial stationary state (where correlations are absent, see below) is reached, while update (d) produces a particle-hole attraction [36]. This already shows that different updates might yield a different behaviour.
For analytic calculations usually the random-sequential update is most convenient since it can be formulated in terms of a "Hamiltonian" with nearest-neighbour interaction. In Monte Carlo simulations, however, ordered-sequential updates can be implemented more effectively.
At this point it is necessary to point out the existence of some confusion in the nomenclature of the different updates. The random-sequential update (a) is sometimes simply called 'sequential update', as is the ordered-sequential one. In several publications the sublatticeparallel update (b) is called 'parallel' which makes it necessary to refer to the parallel update (d) as 'fully-parallel'. We urge the reader to check carefully which type of update is actually used when consulting the literature. In order to avoid further confusion we will use the terminology which seems to us the most precise.

Master equation and quantum formalism
Our starting point is the master equation for an arbitrary one-dimensional stochastic process. Following [22] we rewrite this equation as a Schrödinger-like equation in imaginary time. We consider a chain of L sites j with state variables τ j = 0, 1. Generalizations to the case where the state variables can take more than two values are straightforward. A configuration of the whole system will be denoted by {τ } = {τ 1 , τ 2 , ..., τ L }, its weight by P ({τ }, t).
The master equation then has the form where w(τ → τ ′ ) denotes the rate for a transition from {τ } to {τ ′ }.
Let us now define a ket state |P (t) in the following way. We take an orthonormal basis in the configuration space {τ }, with τ ′ |τ = δ τ ′ ,τ and define i.e. we have P ({τ }, t) = τ |P (t) . It is then easy to see that holds, with the (generally non-hermitean) "Hamiltonian" H given by for the off-diagonal elements (τ = τ ′ ) and by for the diagonal elements. From (4) one can see that the stationary state |P 0 of the stochastic model corresponds to the "groundstate" with "groundstate energy" zero (E 0 = 0) of the "quantum spin chain" defined by (5), (6), i.e.
H|P 0 = 0. 6 The conditions (5), (6) guarantee that the real parts of the other eigenvalues E λ of H are non-negative. Using the bra groundstate 0| = {τ } τ |, the average of an observable A({τ }) at time t is given by Expanding the initial state |P (t = 0) = λ a λ |ψ λ in terms of the eigenkets |ψ λ with eigenvalues E λ of H this can be rewritten as This shows that the behaviour for large times t is governed by the low-lying excitations. We now restrict ourselves to stochastic processes with random-sequential dynamics and local and homogenous transition rates Γ τ ′ j τ ′ j+1 τ j τ j+1 (denoting the rate for a local transition of sites j and j + 1 from (τ ′ j τ ′ j+1 ) to (τ j τ j+1 )), which do not depend on time. In this case H is a sum of local Hamiltonians with nearest-neighbour interaction only [22]: (the basis is (00),(01),(10), (11)). Each column of h j adds up to 0, because the probability has to be conserved. For the updates (b)-(d) it is generally not possible to write H in the form (10) since one would have to include terms acting on sites which are not neighboured. It is then more suitable to use directly the transfer matrix T describing the update of the whole chain during one timestep. In the case of the ordered-sequential update, T is simply a product of the local transfer matrices t j = h j − 1. It follows which means that in order to find the stationary state, one has to solve for the eigenvector of T with eigenvalue 1.

Optimum groundstates and MPA for quantum spin chains
The construction of optimum ground states for quantum spin chains via matrix products was introduced in [16] (see also [30,31] and [32] for further references). Let us consider a Hamiltonian for a quantum spin chain (with periodic boundary conditions) of the form where h ′ j is the local hermitian Hamiltonian and independent of j, acting only on spin j and j + 1. It is always possible to set the lowest eigenvalue of h ′ j equal to zero by adding a suitable constant. Then h ′ j is positive-semidefinite and since H ′ is the sum of positive-semidefinite operators, it follows that zero is a lower bound for the ground state energy E 0 of H ′ , i.e. E 0 ≥ 0. Usually, E 0 is greater than zero (E 0 > 0) and the global groundstate involves also excited states of h ′ j . Therefore, a construction of the global groundstate is usually very difficult. However, there are special cases where E 0 is equal to zero, and therefore for all j h ′ j |ψ 0 = 0.
A state |ψ 0 is called optimum groundstate of H ′ if and only if condition (14) holds. This implies that the groundstate energy is independent of the system size, i.e. there are no finite-size corrections. The idea is now to construct groundstates by means of a product of matrices, where the entries of matrix m j are spin-1 single-site states and the symbol ⊗ denotes the usual matrix multiplication of matrices with a tensor product of the matrix elements. Note that m 1 ⊗ m 2 ⊗ ... ⊗ m L is still of the same size as the matrices m j , but its elements are large linear combinations of tensor product states. The trace assures the translation invariance of the groundstate. For non-periodic boundary conditions it has to be replaced by a suitable linear combination of the elements of m 1 ⊗ m 2 ⊗ ... ⊗ m L . As an example [16], the ground state of a large class of antiferomagnetic spin-1 chains can be constructed using the S z eigenstates |0 j and |± j by where the a, b, c, d are real numbers. Condition (14) requires i.e. all four elements of m j ⊗ m j+1 are local groundstates of h j . Let us now write 8 with suitable 2 × 2 matrices A 0 and A ± . The '·' denotes a product of each entry of the matrix to the left with the single-site state on the right. It is obvious that (15) can be written equivalently as or, defining a column vector as The condition (17) then be rewritten as This means that there are two equivalent ways to write |ψ 0 . While (15) uses a product of matrices with vectors as entries (the usual notation for quantum spin chains), (21) expresses |ψ 0 as a product of vectors with matrices as entries. The original idea of Derrida et.al. [15] was to construct the stationary state |P 0 of a stochastic process defined by (10) as a suitable linear form of a product of matrices where each matrix corresponds to a single-site state precisely as in (21).

MPA for stochastic systems
In the following we want to describe how the MPA can be applied to stationary states |P 0 of stochastic systems. In contrast to the case of quantum spin chains we already know the corresponding "groundstate energy" of the stochastic Hamiltonian H defined by (5) and (6). From (4) we see that H|P 0 = 0 and therefore the groundstate energy is zero, independent of the system size. This hints at the applicability of the MPA and a possible generalization of the optimum groundstate concept.
Indeed it turns out that, using an MPA of the form (21), (14) can be replaced by a more general condition by allowing for a divergence-like term [21], i.e.
where the vectorĀ can be different from the vector A. It is easy to see that (for periodic boundary conditions) the divergence-like terms cancel after summing over j. Hence, the stationary state of the stochastic process described by (5) and (6) is of the form (21).
For hermitian Hamiltonians one always hasĀ = A and (23) reduces to (22). Therefore one can regard (23) as the generalization of the optimum groundstate concept to non-hermitian Hamiltonians.
Again it is possible to generalize these ideas to treat non-periodic boundary conditions. As an example we briefly review the solution of the ASEP with random-sequential update and open boundary conditions. The "Hamiltonian" reads (hopping rate p, feeding and removal rates α,β): with the boundary termsh and the bulk "Hamiltonian" From (9) we can see that p only rescales time (and α and β) and that it would therefore be sufficient to study p = 1.
Following the MPA, the matrix for the particle (hole) is denoted by D (E), so that A = E D . Since the ASEP with open boundary conditions has (in general) no translational invariance, the trace in (21) is replaced with a scalar product: where the normalization constant Z L is equal to The brackets ... indicate that the scalar product is taken in each entry of the vector More explicitly (27) means that the weight P (τ 1 , . . . , τ L ) of a configuration {τ } in the stationary state is given by Thus one has a simple recipe for the calculation of the (unnormalized) weight of an arbitrary configuration {τ }: Translate the configuration into a product of matrices by identifying an empty site (τ j = 0) with E and an occupied site (τ j = 1) with D. For example, the configuration 011001 · · · corresponds to the product EDDEED · · · = ED 2 E 2 D · · · . Then multiply by the vectors w|, |v from the left and right, respectively.
We assume thatĀ in (23) is of the formĀ = Ē D whereĒ andD denote matrices acting in the same vectorspace as E and D. Executing the sum (10) in (23) leads to a cancelation of all terms in the bulk of the chain. The remaining terms at the boundaries vanish if the vectors W | and |V are chosen appropriately: Inserting (25) and (26) into (23), (29) we get a system of quadratic equations in E, D,Ē andD which is called the algebra of Ansatz (23). The dimension of the matrices is not determined by the Ansatz. However, takingĒ = 1 = −D, the equations reduce to the "DEHP algebra" [15] p Equation (30) can be guessed intuitively: the current J L (j) (describing the flux of particles through bond j of a chain of length L) has to be constant throughout the chain. J L (j) is given by [15] and we see that DE ∝ C = E + D is the simplest way to achieve a constant current. It is possible to derive explicit expressions for D, E, W | and |V [15]. It turns out, that one finds one-dimensional representations if and only if In all the other cases, the matrices are infinite-dimensional. Up to this point, the MPA appears to be just an Ansatz for the stationary state. However, it can be shown [23] that the MPA (27) with the "cancellation-mechanism" (23) is an equivalent reformulation of the master equation for a stochastic process with randomsequential update and nearest-neighbour interaction. Therefore it is of general interest to study the quadratic algebras which are produced by (23) and to try to find explicit representations [33][34][35].
In the next section, we will construct the stationary state for the ASEP with sequential and sublattice parallel update. Note that we do not have a "Hamiltonian" of the form (10) in this case and that the "cancellation mechanism" will not be appropriate.

MPA for the ASEP with updates in discrete time
In this section we will generalize the results for the random-sequential update to discretetime updates. In Section 3.1 we solve the ASEP for sublattice-parallel and sequential updates using the MPA. In Section 3.2 we conjecture a MPA for the parallel update.
Let us briefly discuss the precise connection between the random-sequential update and the ordered-sequential update, say from the right to the left, for an arbitray one-dimensional stochastic process with nearest neighbor interaction. We have seen, that in this case the "Hamiltonian" describing the random-sequential dynamics is of the form (10), H = L j=1 h j , while for the ordered-sequential udpate one has to use the transfer matrix with local matrices t j connecting the sites j and j + 1. From (10) and (9) it is clear that one of the parameters can be used to rescale the time unit; in the case of the ASEP this leads to expressions which are independent of the hopping probability p. For the update (35) with discrete time, this is obviously impossible and we expect the phase diagram of the ASEP to depend on p nontrivially. Only in the limit of vanishing densities these two updates can be mapped onto each other [29] by inserting t j = h j − 1 (where 1 denotes the identity matrix) into (35) and expanding the product. For nonvanishing densities, the equations (10) and (35) are connected nontrivially via additional, non-locals terms.

Sublattice-parallel and ordered-sequential update
We now solve the ASEP with ordered-sequential (update (c)) and sublattice-parallel (update (b)) dynamics. So far, the ASEP with the latter update and deterministic hopping has been studied by Schütz [27] and Hinrichsen [26]. A brief account of our work has been given in [28]. For simplicity, we will first concentrate on the ordered-sequential update (c) from the right to the left. Since this update is discrete in time, a stochastic "Hamiltonian" of the form (10) is not at hand. Therefore, the transfer matrix T ← has to be used. This means by definition The stationary state |P 0 must not change under the action of the T ← and therefore is eigenvector with eigenvalue 1 of T ← : Let us now explicitly write down T ← . The boundary conditions can be represented by operators R and L acting on site j = L and j = 1, respectively: 12 The basis chosen for R and L is (0, 1). The update-rule for any pair of sites (j, j + 1) can be written as The basis is (00, 01, 10, 11), and we have where 1 denotes the identity matrix. Formally, a "Hamiltonian" can be defined as H ← = 1 − T ← . However, H ← cannot be written simply as a sum of local "Hamiltonians". This means that while we can try a MPG Ansatz (27) we cannot use the "cancellation"-mechanism (23). However, the sequential nature of T ← suggests another mechanism: This means that a "defect"Â -corresponding to a local perturbation of the stationary state defined by (37) -is created in the beginning of an update at site j = L, which is then transported through the chain, until it reaches the left end and disappears. Equation (42) leads to the following bulk algebra: The ordered-sequential update in the opposite direction (left to right) can be treated in the same way. The stationary state is given by with the same mechanism (42) and (43). However, it is more convenient to use the particlehole symmetry for the calculation of averages.
For completeness let us briefly discuss the sublattice-parallel update (b). In this case the transfer matrix has the structure [26,29] with and the MPA for the stationary state is of the form One can now use exactly the same mechanism (42), (43) as in the ordered-sequential case and thus obtains the same algebra (44), (45). For p = 1 the algebra was first derived and solved by Hinrichsen [26] using a two-dimensional representation for E, D,Ê,D, W |, |V .
The fact that the ordered-sequential and the sublattice-parallel update lead to the same algebra (44), (45) implies the existence of an intimate relationship between the averages of observables. Although the stationary states themselves are different, they are connected via transformations, and it can be shown that the density profile of the ordered-sequential update from the left (right) to the right (left) corresponds to the density of the even (odd) sites produced by the sublattice-parallel update [24]. This result holds for arbitrary stochastic models with nearest neighbor interactions. One can check that for a one-dimensional solution of the algebra exists 2 . This equation defines a line in the phase diagram where the mean-field solution becomes exact. It turns out that this line touches all phases. This makes it possible to calculate quantitites such as the current very easily, because the analytic expression for the current does not change inside a phase.
For general values of α, β and p the algebra (44) and (45) can be mapped onto the generalized DEHP-algebra [28]. This is shown in App. A and will be used later in Section 4.2. App. B discusses the consequences of the particle-hole symmetry for the two orderedsequential updates in more detail. App. C deals with the special case of symmetric diffusion.

Parallel update
As far as analytic approaches are concerned, this update poses the greatest difficulties, since it produces the strongest correlations. In the case of the ASEP, this becomes obvious when looking at the model put on ring: All updates, except the parallel [36] and particlesequential [37] one, lead to a trivial state where correlations are absent. In the case of the parallel update, it is known [36] that a particle-hole attraction appears: the probability to find an empty site in front of an occupied site is enhanced compared to the mean-field result.
The model with parallel update and periodic boundary conditions has first been solved exactly in [8,36] using a cluster approximation (see below). Here the weights are decomposed into products of pairs of sites overlapping just one site. It turned out that this 2-cluster approximation becomes exact for periodic boundary conditions. We now make an analogous calculation for the model with open boundary conditions. The goal is to find the parameter set for which the density profile is flat. Note that a flat density profile does not necessarily mean that there are no correlations between the sites. We denote the probability for the pair configuration τ i τ i+1 at site i, i + 1 by P τ i τ i+1 (τ i = 1, 0 and i = 1, ..., L). Let us assume that such a probability for a certain pair configuration is independent of the position of the pair. The condition P 01 = P 10 leads to a flat density profile ( τ 1 = τ 2 = ... = τ L ), but P τ i τ i+1 is not necessarily equal to P τ i · P τ i+1 . The 2-cluster approximation corresponds to a factorization of the weight P (τ 1 , τ 2 , ..., τ L ): where the R's reflect the influence of the boundaries; they can be set to R 0 = 1 and R 1 = r. It is sufficient to study a system of 3 sites. The generalization to larger systems is straightforward [36]. The (exact) master equation for the stationary state reads x = T x where x is a vector containing the 8 possible configurations, and T is the 8 × 8-dimensional transfer matrix for L = 3. By inserting Ansatz (51) into this master equation it is straightforward to show that (51) is exact if and only if This means that the condition we have found for a constant density profile is exactly the same as for the other discrete-time updates, see (50). The reason for this coincidence is still unkown. Note that (52) is not a simple mean-field line.
In the following we will propose a MPA for the parallel update. (51) suggests that matrices denoting pairs of particles and/or holes should be used. The main problem is that the resulting algebra will be very complex, since it will contain many variables (matrices). On the other hand, if we use a MPA of the form (27), a simple mean-field solution will not be found, e.g. there will be no scalar solution for the algebra. However, such an Ansatz could produce (51) under condition (52) in the form of a low-dimensional representation. Furthermore, even if a choice for the MPG is made, we still have to find a mechanism which ensures stationarity. The transfer matrix, however, cannot be decomposed easily in products or sums of local terms. The main difference between the parallel update and the ordered-sequential update from the left to the right is that in the parallel update, a particle can move only one site to the right (per update of the chain). This enables us to use the ordered-sequential update, if we introduce a third state for particles that have been moved. The local (sequential) update operator then has to transform a third-state particle into a "normal" particle in the following update step. We write down the Ansatz which has to satisfy The update-rule T for any pair of sites (i, i + 1) is now nine-dimensional. However, since the third state must not appear after the update, the last four rows and every third column are irrelevant (here set to zero). The explicit expression for T can be found in Appendix E. We have with The mechanism for stationarity reads now with the new third-state matrixF . This leads to an algebra, which can be found in Appendix F. Note that the last bulk equation 0 = DF excludes a scalar solution for the algebra. This is consistent with our earlier observation that there is no simple mean-field solution of the model. First, we can check the relations which connect the densities at the ends of the chain with the current J. This calculation can be done for arbitrary system sizes and is presented in Appendix G. Second, it is possible to show that the algebra correctly describes a system of three sites. This can be done by taking the expressions for the weights of the eight possible configurations of the stationary state given by (54) and by applying several times the algebraic rules. Thereby each weight can be expressed as a linear combination of the other weights 3 .
The resulting system of linear equations turns out to be identical to those obtained from the transfer matrix T . Thirdly, it can be checked whether the algebra can be reduced to a generalized DEHPalgebra of the type with some numbers a, b. This equation induces certain relations between weights for a system of size L and L − 1, which can be checked using the exact solutions. It turned out that (58) cannot be valid. We found a two-dimensional representation for the bulk algebra [38], but despite intensive effort, we could not solve the complete algebra 4 . Therefore, Monte Carlo simulations have been performed [39]. The results will be presented in Section 4.2.

Comparative study of physical quantities
In the following we will investigate the consequences of the mathematical description developed in the previous section. First we investigate the ASEP with periodic boundary conditions for the different updates. This will allow us later to distinguish between "pure" bulk effects and "boundary-induced" bulk effects. After that we will derive and compare the phase diagrams, density profiles and other physical quantities for the various updates.

Periodic boundary conditions
For random-sequential dynamics the stationary state of the ASEP with periodic boundary conditions is given by |P 0 = 1 Z L Tr(A ⊗ · · · ⊗ A) where the elements E and D of the vector A satisfy the algebra (30) and the normalization is given by Z L = Tr C L with C = E + D. Since the boundary equations (31) and (32) do not have to be considered, it is possible to find a one-dimensional representation of the matrices E and D which then become real numbers e, d. The current is calculated from J L = p Z L Tr(C j−1 DEC L−j−1 ) = 1 c , where we have used (30) and Z L = c L with c = e + d. In contrast to the case of open boundary conditions, the density ρ is now fixed and the density profile is constant, ρ = τ j , independent of j. With one finds ρ = d/c. Therefore the current is given by This is exactly the mean-field result, because in mean-field approximation a site is occupied with probability ρ and its right neighbour is empty with probability 1 − ρ. Since hopping then occurs with probability p, one obtains (60). This result is not surprising as the existence of a one-dimensional representation implies the absence of correlations between neighbouring sites, i.e. the MPA reduces to mean-field theory.
We now turn to the ASEP with backward-sequential update on a ring. The state is obviously translation-invariant and, because of (42), stationary (the argument of the trace is a vector with a product of matrices in each component; the trace has to be applied to each component). The algebra can be directly solved with one-dimensional matrices (see Appendix D). The current J ← (ρ, p) for the ordered-sequential update is not given by (33), but by 5 For the case of periodic boundary conditions one finds 6 Fig. 3 illustrates this result. Again this result can be obtained directly using a mean-field argument. The site to the right of an occupied site is empty with probability 1 − (ρ − J ← ).
Here one has to take into account that the density is reduced by J ← after the update of that site. Therefore the current satisfies J ← = pρ(1 − (ρ − J ← )) which leads to (63). The maximal flow (p fixed) is reached for a density ρ max ← (p) = 1 p (1 − √ 1 − p) ≥ 1/2. The sequential update T ← "likes" high p and high densities. The particle-hole symmetry can be used to determine these quantities for T → simply by replacing ρ with 1 − ρ: T → "prefers" high p and low densities. It is interesting to compare (63) with the well-known result [36] for parallel update, For the parallel update a mean-field theory for the distances between consecutive particles becomes exact [40]. Similar results have been obtained recently by Evans [37], who solved the ASEP with periodic boundary conditions in the presence of disorder 7 with parallel update and a particle-sequential update by generalizing the approach of [31]. J (ρ, p) is obviously symmetrical with respect to ρ = 1/2. It is maximal at ρ max = 1/2 for all values of p, while ρ max ← is always higher than 1/2 (except for p = 0). Hence, the maximal currents (for a given p) are J ← (ρ max , p) and it can be verified easily.
Let us now return to the model with open boundary conditions.

Phase diagram
The phase diagram for random-sequential dynamics has been determined for p = 1 in [13][14][15]. This is no restriction since, as mentioned before, p only rescales time (and α → α/p, β → β/p). Since it will turn out that the phase diagrams for the different updates are rather similar we will not repeat the results for the random-sequential update here. Instead we will first determine the phase diagram for the ASEP with open boundary conditions and discrete time by using the results of Section 3.1 and discuss the differences to the random-sequential case later. In Appendix A it is shown how the algebra (44), (45) can be projected onto the DEHP-algebra. The representations of this algebra (and the resulting phase diagram) are known for all parameter values α, β, p, q [33,34,43]. Therefore, we have obtained explicit expressions for the matrices and vectors, and have thus constructed the stationary state of our model; we do not have to be concerned about representations any more that might not satisfy (A.3) since the projection onto the DEHP-algebra already covers the whole parameter space. Furthermore, it is straightforward to calculate observables such as the current and the density, at least in principle. The mapping of App. A strongly suggests that the well-known phase diagram of the ASEP with random-sequential update and stochastic hopping in both directions [33,34,43] will also be valid for the ASEP with ordered-sequential update. This is indeed correct and has been proven directly in [29]. The phase diagram is shown in Fig. 4. The mean-field line is the curved dashed line. Also shown are density profiles calculated from Monte Carlo simulations. All well-known features of the phase diagram (high-density phase, low-density phase, maximum current phase, coexistence line with linear density profile) are recovered. The intersection of the mean-field line (50) with the line α = β defines the endpoint α c (=β c ) of the coexistence line. This yields In the case of deterministic hopping (p = 1), the maximum current phase vanishes, and we recover the result of Hinrichsen [26]. It is known that for the DEHP-algebra, the mean-field expressions for the current are exact. Since the mean-field line touches all three phases, we can calculate the corresponding currents and bulk densities for our model. Our results are which is in excellent agreement with our numerical data. Since the relation J(α, β, p) = βρ(α, β, p, x = L) is exact, we immediately get the bulk density in the high-density phase: The bulk density in the low-density phase will be obtained below. Fig. 5 shows a space-time diagram for a point on the coexistence line (p = 0.75, α = β = 0.3) produced by the Monte Carlo simulation. The well-known fluctuating shock can nicely be observed. Typical space-time diagrams for the different phases can be found in Fig. 6. The "jams" in the high-density phase move from the right to the left. In the low-density phase, groups of particles (small jams) move from the left to the right.
For the case of parallel dynamics extensive Monte Carlo simulations have been performed [39] which revealed that the phase diagram looks essentially the same as before (Fig. 4). Again, we find a high-(low-) density and a maximum current phase and a linear density profile along the line α = β, until the 2-cluster line (52) is touched. Since we have a particle-hole symmetry in the model, the density for α = β and odd lattice sizes has to be 1/2 for site L+1 2 . Therefore, the 'bulk density' ρ(α, β, p, x = L+1 2 ) in the maximum current phase must be 1/2. Equations (51) and (52) can be used to calculate the current 8 in the high-density phase, and the remaining bulk densities ρ bulk = α(1−α) p−α 2 (low-density) and ρ bulk = p−β p−β 2 (highdensity phase). These results are exact on the 2-cluster line (52). For general values of α and β we find an excellent agreement with the numerical data. Fig. 6 presents typical space-time diagrams in the various phases. The particle-hole attraction is apparent.
Note that for every update the maximal current J(ρ max , p) on the ring (as calculated in Section 4.1) is equal to the value of the current in the maximum current phase for that update. The value of ρ max gives the corresponding bulk density. This shows that the current in the maximum current phase is determined by the 'capacity' of the ring.

Density profiles and phase transitions
For the parallel update we performed extensive Monte Carlo simulations in order to determine quantities like density profiles and correlation functions. In this section we will compare these results with those obtained analytically and numerically for the other update types.
The results presented in Section 4.2 show that one can distinguish at least three different phases with respect to the flow. In the low-(high-) density phase the current depends for a given value of p only on α (β) and in the maximum current phase the current is independent of the chosen in-and output rates. This basic structure of the phase diagram is the same for all types of update although the bulk properties change drastically.
A more detailed analysis of ASEP with random-sequential update has shown [14] that the system is governed by two independent length scales ξ α and ξ β , which represent the influence of the boundaries. At the critical value of α and β these length scales diverge and a phase transition occurs. This divergence produces two additional phases compared to the mean-field results. Thus the parameter space is divided into five different phases. The low-density phases AI and AII, where the bulk properties are determined by the value of α, the high-density phases BI and BII, where the output rate β determines the flow, and the maximum current phase where the flow is independent of α and β. The phases AI and AII (BI and BII) are distinguished by the behaviour of the density profile near the boundaries (see below).
We checked this scenario for the parallel and ordered-sequential update. In order to avoid difficulties due to the p-dependent scale factor of the phase diagram we analyzed the density profiles for p = 0.75. Our simulation results are obtained for systems with 320 sites. Since finite-size corrections are rather small, this size is already sufficient to obtain the behaviour in the limit of large L.
We first measured the density profile in the low-density phases AI and AII. In [14,15] it has been shown that for large L the asymptotic behaviour near the boundaries changes from a pure exponential decay in the phase AI to the enhanced exponential decay according to exp(−(L − x)/ξ α )/ √ L − x in the phase AII. This change of the behaviour near the boundaries is due to the divergence of the length scale ξ β at the transition line. ξ β remains infinite throughout the whole phase AII. Unfortunately, the divergence of ξ β cannot be calculated directly because the relevant length scale ξ, which determines the exponential decay in AI, is given by Thus the correlation length ξ remains finite at the transition line from AI to AII. In contrast to the divergence of ξ β , the asymptotics of the density profile can be checked against the numerical results. Fig. 7 shows that the density profile for α = 0.40, β = 0.42 and parallel update can be nicely fitted by a pure exponential decay, but within the phase AII the enhanced exponential form has to be used (see also the insert in Fig. 4). Another characteristic line crossing the low-density phase AII is the mean-field line, where the density profile is completely flat. This line separates the monotonously decreasing density profiles from monotonously increasing profiles, but the asymptotic behaviour is left unchanged. The behaviour of the density profiles in the high-density phases BI and BII can be obtained using the particle symmetry of the model.
The transition between the high-and low-density phases is driven by the diverging length scale ξ. This divergence occurs although both length scales are finite, because at the transition line ξ α and ξ β coincide. The qualitative agreement of the density profile strongly suggest that the relevant length scale in the low-density phase is given by (68) also for discrete-time updates. Moreover, the comparison of the numerically estimated correlation length shows that the correlation lengths of the parallel and ordered-sequential update are identical and differ from those obtained for the random-sequential only by a constant factor (Fig. 8). Exactly at the transition line α = β, one finds a linear density profile as shown in Fig. 9. This linear profile is result of a fluctuating shock front which separates for a given time a high-density region from a low-density region. The position of the shock front fluctuates through the whole lattice such that a time average over all single time profiles gives a linear profile.
The transition from the low-(high-) density phase AII (BII) to the maximum current phase is characterized by a change of the asymptotic behaviour of the density profile from the enhanced exponential to a pure algebraic decay. The transition is driven by the divergence of the length scale ξ α (ξ β ) for α → α c (β → β c ). Both length scales are infinite not only at the transition line but for all values of α and β larger than the critical value. Therefore an algebraic decay of the density profile can be observed in the whole maximum current phase. Fig. 10 shows the diverging correlation length for different update types. Again the length scales of the updates with discrete time agree and the length scales produced by the random-sequential update are larger if one considers the same in-and output rates.
The flow is generated by the (10)-clusters (the mobile pairs), while the other 2-cluster configurations exclude hopping of particles. Therefore, we measured density profiles of the probabilities P τ i τ i+1 of 2-cluster configurations τ i τ i+1 . One gets a flat profile of the mobile pairs P 1 i 0 i+1 (see Fig. 11) which is a consequence of eq. (33) for the current in the case of parallel dynamics 9 . The nontrivial part of the density profile is produced by the immobile pairs. The identity P 1 i 0 i+1 = P 0 i 1 i+1 , which is already known from the periodic system [8], is only true for flat density profiles. One observes qualitatively the same behaviour for the random-sequential, but not for the ordered-sequential update.
For the ordered-sequential update the transport of a local defect changes the behaviour of the P τ i τ i+1 profiles: The density of particles in front of hole at the defect site (in the case of backward-sequential update) determines the flow and therefore none of the 2-cluster configurations is in general translation-invariant after a sweep through the lattice.

Discussion
We have presented an extensive comparative study of the ASEP with different updates. The purpose of this investigation is threefold: First of all, despite the importance of the ASEP, not much has been known about its properties for discrete-time updates. Second, we tried to obtain a better understanding of the similarities and differences of the different updates. Finally, there is also a practical aspect. In [25,44] it has been shown that different dynamics perform quite differently in Monte Carlo simulations. In order to save computational time it might therefore be useful to choose a certain update. Then it is also necessary to know how to translate the results into those for other updating schemes.
The main tool that we used in our investigations was the MPA which allows for an analytical solution for the cases of random-sequential, ordered-sequential and sublattice-parallel updates. We also proposed a MPA for the important case of parallel dynamics, but unfortunately we were not able to find a general representation of the resulting matrix algebra. Therefore extensive Monte Carlo simulations have been performed in order to determine the phase diagram. These numerical results, together with an analytical solution for a special line in parameter space, allowed us to conjecture analytical expressions for the phase diagram.
Our results show that the phase diagram has the same basic structure for all the updates investigated here. One finds three different phases characterized by the value of the current. For α > β and β < β c (p) the system is in the so-called high-density phase. Here the current depends only on the removal rate β since particles are inserted much more efficiently than they are removed. Just the opposite situation is found in the low-density phase, α < β and α < α c (p). Here the removal is much more effective than the insertion and the current depends only on α. Note that for each update α c (p) = β c (p) and the functional forms of the currents in the high-and low-density phases are identical (see Table 1).
Finally, for α > α c (p) and β > β c (p) one finds the maximum current phase. Here the current is independent of α and β. Both insertion and removal are so effective that the current is only limited by the "bulk capacity". Indeed, the current in this phase is identical to the maximal current of the corresponding system with periodic boundary conditions.
Phase transitions between these phases are driven by diverging length scales ξ α or ξ β within the high-and low-density phases. These length scales depend on the rates α and β, respectively. In contrast to that, the periodic systems exhibit only extremely shortranged correlations. The strongest correlations are found for the parallel update, but even here already the 2-cluster approximation is exact. This leads to exponentially decaying correlation functions with a rather short correlation length (except for ρ ≈ 1/2 and p ≈ 1) [45]. So the long-ranged correlations found for the open system are due to the boundary conditions and the transitions are genuine "boundary-induced phase transitions". This makes it also understandable why the phase diagrams for the different updates look so similar, the only difference being the location of the transitions and the functional form of the observables. Furthermore the numerical analysis shows that the update type does not change the "universal" properties of the model: We observe the same asymptotics of the density profiles in the different phases and also the qualitative behaviour of the length scales near the phase boundaries does not depend on the update. For the discrete updates the length scales agree even quantitatively.
Recently, for the case of periodic boundary conditions there has been some progress in the understanding of the differences between random-sequential and parallel update [46]. For the latter so-called "Garden of Eden" (GoE) states 10 exist. These states can not be reached dynamically, they do not have a predecessor. By eliminating these states one finds in the reduced configuration space that mean-field theory becomes exact, as it is for the case of random-sequential update (but here in the full configuration space since Garden of Eden states do not exist). Therefore the existence of GoE states is the reason for the correlations in the ASEP with parallel dynamics and periodic boundary conditions. Since the bulk dynamics for the ASEP with open boundaries is the same as for the periodic case, we expect the GoE states to play an important role also in that case.
In this paper, valuable information has been gained by means of low-dimensional representations of the matrix algebras. A one-dimensional representation clearly corresponds to a simple mean-field approximation. However, in the case of two (or higher) dimensional representations, nothing is known about the physical interpretation of these solutions. For example, it could be possible that there is a close connection between cluster approximations and these representations; we remark that it is possible to write the expectation values of densities and correlations of any exact (stationary) solution of a 2-cluster approximation as a product of two-dimensional matrices precisely in the form resulting from a MPA.
Recent investigations have shown that the ASEP is capable of reproducing the essential features of traffic in a city such as Geneva [47]. The authors studied a simple extension of the one-dimensional ASEP to two dimensions 11 . Therefore, it would be most interesting to generalize the MPA to higher dimensions 12 . A first step would be to study the ASEP on a ladder. The analytical method used in this paper is directly applicable to "stochastic" ladders [52]. Since the groundstates of certain quantum spin ladders have been constructed recently [53,54] using optimum groundstates (see Section 2.3), there seems to be a good chance to find low-dimensional representations of the corresponding algebras. This would lead to a better analytical understanding of the fascinating phenomena that occur in higherdimensional nonequilibrium systems [2,55].

Acknowledgments
This is the algebra for the ASEP with random-sequential update and hopping in both directions (with probability p and q, respectively), but with the same local transfer matrix and the same boundary conditions as in our model. The algebra was solved for p = 1 and q = 0 by Derrida et al. [15] with infinite-dimensional matrices. Note that the vectors W | and |V of their solution have to be rescaled with 1−α 1−p and 1 1−q , respectively. A thorough discussion of the algebra (A.6) can be found in [33,34,43,56].
We write down an explicit representation of the algebra (A.4) with λ = 1 in the case q = 0: As expected, constraint (50) leads to an effectively one-dimensional representation.
B Symmetries of the density profiles for the orderedsequential updates As shown in Section 3 the stationary state for T → is simply given by (46). When inserting (A.5) into (46), we get a connection between the density profiles 13 of the stationary states produced by T ← and T → : One also has J(α, β, p) = βρ(α, β, x = L) which leads to ρ → (α, β, p, x) is therefore always lower than ρ ← (α, β, p, x). The current J is not x-dependent. This means that the density profile of the ordered-sequential model for a given set of parameters α, β, p is, up to a constant (the current), the same for both directions of the order of update. The stationary states produced by T → and T ← for a given set of parameters are always in the same phase. It is obvious that the "crucial step" (A.3) is the simplest way to obtain such a behaviour. When using the particle-hole symmetry we immediately see that the density profile on the line α = β has to be symmetric with respect to point L/2. For this case, we further obtain ρ ← (α, p, L+1 2 ) = 1+J(α,p) 2 . Finally, by using (B.2) and (B.3), and the results for the current and ρ bulk in the high-density region, the bulk density in the low-density region ρ bulk = α/p is obtained.

C Symmetric diffusion
We briefly discuss the case of symmetric diffusion (p = q) for the ordered-sequential update. The density ρ(α, β, p, x) at site x (1 ≤ x ≤ L) is given by This means that the density can be calculated immediately by commuting D with the help of (C.2) through the chain in (C.1). By using the boundary conditions, the density can easily be calculated, which in turn makes it possible to estimate the current [29]. It is intuitively clear that the current vanishes in the thermodynamical limit L → ∞ for arbitrary values of α, β, p.

D ASEP with ordered-sequential update on a ring
Since we expect that the periodic system can be described by an one-dimensional representation of the algebra (A.1), we are looking for solutions of (A.1) with real numbers e, d,ê,d: The normalized density ρ is given by .
There is some freedom how to choose e, d,ê,d. We set e + d =ê +d = 1. Therefore, (D.1) yieldsê The current J is given by J = pdê − qed and one obtains Obviously, J(p, q) = 0 for the case of symmetric diffusion, p = q.
Finally, we like to point out that the fact that the periodic system is described by a one-dimensional representation implies that in this case mean-field theory is exact.
E T in a three-state notation The operators R,L can be written as: The basis chosen for R and L is (0, 1, −1). The local transfer-matrix T i for any pair of sites (i, i + 1) is nine-dimensional. Since the third state (−1) may not appear after the update of the whole chain, the last four rows and every third column are irrelevant and here set to zero: The basis is (00, 01, 0 − 1, 10, 11, 1 − 1, −10, −11, −1 − 1).

F Matrix algebra for parallel dynamics
The MPA for parallel update proposed in Section 3.2 leads to the following algebra: Note that the last bulk equation 0 = DF excludes a scalar solution for the algebra. This is consistent with our earlier observation that there is no simple mean-field solution of the model.

G Check of current-density relations
Defining C = E + D andĈ =Ê +D +F it is easy to see that [C,Ĉ] = 0 (G.1) holds. This is implied by probability conservation (the columns of T i add up to one) and the exchange mechanism (57). The boundary equations lead to We can now check the relations which connect the densities at the ends of the chain and the current J which has to be constant throughout the chain: J(α, β, p) = βρ(α, β, p, x = L) (G.5) J(α, β, p) = α[1 − ρ(α, β, p, x = 1)] . (G.6) Note that the first (second) equation would not hold for the sequential update from the left (right) to the right (left) and that in fact we have only to prove one of these equations because we can make use of the particle-hole symmetry of the model. We therefore write, using the algebra (equations (F.11), (F.3)): ρ(α, β, p, x = L) = 1 Z L W |C L−1 D|V (G.7) Making use of (G.4), commutingĈ to the left end of the chain (G.1), transforming it to C there (G.2), and using J(α, β, p) = 1 Z L p W |C L−2 DE|V we get           Density profiles near the first order transition at α = β = 0.3 for the random sequential update using the exact results of [15]. Again α + β = 0.6 holds.       Figure 9: Density profiles near the first order transition at α = β = 0.3 for the random sequential update using the exact results of [15]. Again α + β = 0.6 holds. i P 0 i 0 i+1 P 0 i 1 i+1 P 1 i 0 i+1 P 1 i 1 i+1 Figure 11: Density profile of the pair probabilities P τ i τ i+1 for the parallel update in the low density phase AII (α = 0.40, β = 0.75, p = 0.75).