j$ (the curvilinear lines
may have vertical segments). To simplify the notation we shall say that
$S_l(x)$ is monotonous on $[i_-,i_+]$.
Consider the interval of monotonicuty $[i_{-},i_{+}]$ which starts
from $l$, i.e. $i_{-}=l$. We set $\xi$ to be equal to the minimum
of the number of not occupied positions in $x^{(1)}$ ahead of the
site $i_-$ (which is occupied by 1). Then under the action of
$\map_v$ the particle at the site $i_-$ of the 1-st lane moves by
$\xi$ positions to the right. Observe that all particles on the
other lanes in the segment $[i_-,i_+]$ have at least $\xi$ not
occupied positions ahead of them, and therefore all these
particles will move at least $\xi$ positions to the right. Thus to
prove that the monotonicity is preserved it is enough to note that
the particle on the lane $M$ cannot move further to the right
than the first particle on the first lane of the next interval of
monotonicity. Indeed, the latter is a trivial consequence of the
definition of intervals of monotonicity. This finishes the proof
of the statement (d) except the last part, which follows from the
statement (c). %\met
To prove the statement (e), observe that by the definition of the
map $\map_{1,M}$ (see Section~\ref{s:intro}) a particle at the
site $i$ of the lane $j$ can switch to the lane $j'$ if and only
if $x^{(j)}[i,i+1]=11$ and $x^{(j')}[i,i+1]=00$, which
contradicts to the definition of the intervals of monotonicity.
Therefore under the sawtooth redirection no particle in $S_l(x)$
will change its lane. \qed
\begin{corollary} The sawtooth redirection gives a simple constructive
way to rearrange vehicles in a multi lane traffic flow between lanes
(preserving their positions in the flow) to achieve the maximal
available flux.
\end{corollary}
According to Theorem~\ref{t:sawtooth},(d) the map
$x\to\sum_{j}\map_{v}(S_{l}x)^{(j)}$ is well defined as a map
from $X_M$ into itself and does not depend on the choice of the
starting site $l\in\IZ$. Moreover, it can be shown that this
formula coincides with (\ref{def:fast-one}) in the case $v=1$,
and it clearly coincides with $\map_v$ in the case $M=1$.
Therefore we use this relation as a definition of the dynamics
of a general multi lane flow in the case $v,M>1$, namely we set
$\map_{v,M}x:=\sum_{j}\map_{v}(S_{0}x)^{(j)}$.
\bigskip
\n{\bf Proof} of Theorem~\ref{t:density-pres} for the case
$v,M\ge1$ and $A\subset X$ follows now from the sawtooth
redirection, which gives the reduction to the one-lane case. It
remains to show that the statistics of more general words
$A\subset X_M$ with $|A|=1$ might be not preserved under
dynamics. The reason of this is that if $M>1$ the multiplicities
might be not preserved. Indeed, let
$a\in\cA_{M}\setminus\{0,1\}$. Then
$\rho(\per{a(M-a+1)0},a)=\frac13(1+\intp{(M-a+1)/a}+0)$, while%
\bea{ \rho(\map_{1,M}\per{a(M-a+1)0},a)
\a= \rho(\per{1(a-1)(M-a+1)},a) \\
\a= \frac13(0+0+\intp{(M-a+1)/a}+0) < \rho(\per{a(M-a+1)0},a) .}%
\qed
\n{\bf Proof} of Theorems~\ref{t:conf-conv},\ref{t:flux-conv}
for the case $v,M>1$. Consider a configuration $x\in X_M$.
According to Theorem~\ref{t:sawtooth},(b) for
$S_0x\equiv\{x^{(j)}\}_{i=1}^M$ we have $\forall n,m\in\IZ_+$ that
$$ |\rho(x^{(j)}[-n,m],1) - \rho(x^{(j')}[-n,m],1)|\le\frac1{m+n+1} .$$
Thus going to the limit as $n,m\to\infty$ and using
Theorem~\ref{t:sawtooth},(a) we get
$\rho_\pm(x^{(j)},1)=\frac1M \rho_\pm(x,1)$ for each $j\in\{1,\dots,M\}$.
Therefore the application of the results obtained in
Sections~\ref{s:slow},\ref{s:fast} in the case of one-lane flows (i.e.
in the case of the map $\map_v$) proves the statements under question. \qed
\section{Rate of convergence: (space) periodic, regular, and typical \\
initial configurations} \label{s:rate}
In this section we study the rate of convergence of various
statistics to the corresponding limit values whose existence have
been established in Theorems~\ref{t:flux-conv},\ref{t:conf-conv}.
Since we have shown that the analysis of $\map_{v,M}$ in all
cases can be reduced to the case of $v=M=1$, we consider in this
section only the dynamics of slow particles and shall consider the
proof of Theorem~\ref{t:typ-conv} only for this case.
We start with periodic in space configurations. Clearly each
$n$-periodic in space configuration $x\in X$ can be represented
in the form $x:=\per{A}$ with a binary word $A$ of length $|A|=n$.
\begin{lemma} Let $x:=\per{A}$ with $|A|=n$, then
$\rho_\pm(x,a)=\rho(A,a)$ for $a\in\{0,1\}$. The space of
$n$-periodic in space configurations is invariant under
the action of the map $\map$ and after at most $\intp{n/2}+1$
iterations any configuration from this space belongs to
$\Free\cup\c\Free$. \end{lemma}
\proof Straightforward. \qed
The only nontrivial question related to this space is the length
of the transient period for a given configuration $x\in X$.
\begin{lemma} Let $x:=\per{A}$ with $|A|=n$ and $\rho(A,1)\le1/2$
and let $B$ be the longest minimal word in $A$. Then the length
of the transient perion is equal to $|B|/2-1$.
\end{lemma}
\proof This is an immediate consequence of Lemma~\ref{l:life-time}.
\qed
Consider now a generalization of the space of periodic in space
configurations -- the space of regular configurations, proposed
in \cite{Bl-var,Bl-jam}. This space is defined as follows:
$$ \Reg(r,\psi) := \{x\in X: ~ |\rho(x[-n,m],1) - r|\le\psi(n+m)
~~ \forall n,m\in\IZ_+\} ,$$
where $r\in[0,1]$ is a constant, and the nonnegative function
$\psi(n)\toas{n\to\infty}0$ is assumed to be a strictly decreasing.
\begin{lemma} Let $x\in\Reg(r,\psi)$, then the density $\rho(x,1):=r$
is well defined, and if $\ne1/2$ then there is a constant $\tau$ such
that the life-time of any cluster of particles in $x$ does not exceed $\tau$.
\end{lemma}
\proof First, observe that if $x\in\Reg(r,\psi)$ then we have
$$ \rho_\pm(x,1)=\blim{\pm}{n,m\to\infty}\rho(x[-n,m],1)=r ,$$
and thus $\rho(x,1)=r$ is well defined. Assume now that $x\in\Reg(r,\psi)$
with $r<1/2$, then, since $\psi(n)\toas{n\to\infty}0$, we deduce that
there is a positive integer $\tau$ such that $\phi(\tau) < 1/2 - r$.
Then we have $\rho(x[n,n+\tau],1)<1/2$ for any $n\in\IZ$, which yields
the claim of the lemma due to Lemma~\ref{l:conv-low}. The case $r>1/2$
follows from the same argument but applying Lemma~\ref{l:conv-high}
instead. \qed
Now we proceed to study more general initial configurations.
\begin{lemma}\label{l:conv-simple}
Let $x\in X$ satisfies the assumption that there exists a number
$\gamma\in(0,1)$ such that $\forall n\in\IZ_{+}$ and any word
$A\subseteq x[-n,n]$ with $|A|>2\gamma n$ we have
$\rho(A,1)\le1/2$. Then
$\dist(\map^{t}x,\Free)\le2^{-t/\gamma +1}$ for any $t\in\IZ_+$.
If $\c{x}$ satisfies the same assumption, then we have
$\dist(\map^{t}x,\c\Free)\le2^{-t/\gamma +1}$.
\end{lemma}
\proof Consider only those $n\in\IZ_{+}$ for which the largest minimal
words containing a cluster of particles in $x[-n,n]$ also belong to
$x[-n,n]$. By the assumption of Lemma the length of the largest minimal
interval containing in the segment $x[-n,n]$ does not exceed $2\gamma n$.
Therefore the corresponding clusters of particles with disappear after
at most $\gamma n$ iterations, and thus for all sufficiently
large $t\in\IZ_{+}$ all particles in the segment
$\map^{t}x[-t/\gamma, t/\gamma]$ will become free. Thus the closest to
the origin nonfree particle can appear not earlier as at site $t/\gamma$,
which gives the desired estimate of the rate of convergence. The second
statement follows from the same argument applied to the dual map.
\qed
\begin{lemma}\label{l:conv-flux}
Let $x\in X$ satisfies the same assumption as in
Lemma~\ref{l:conv-simple}, then
$$ \blim+{n\to\infty}\frac1{2n}\sum_{i=-n}^nV(\map^nx,1)
= F_{1,1}(\rho(x,1)) .$$
\end{lemma}
\proof Observe that $\frac1{2n}\sum_{i=-n}^nV(x,1)=\rho(x[-n,n],10)$.
Applying the same argument as in the proof of Lemma~\ref{l:conv-simple}
we see that after $n$ iterations the segment $\map^{n}x[-n/\gamma, n/\gamma]$
contains only free particles. Therefore $\rho(x[-n,n],10)=\rho(x[-n,n],1)$,
which yields the desired equality. \qed
\begin{corollary} The statements of
Lemmata~\ref{l:conv-simple},\ref{l:conv-flux} remain valid if instead of
$\forall n\in\IZ_{+}$ we assume that $n$ belongs to the subset of
$\IZ_{+}$ of density 1.
\end{corollary}
\begin{lemma}\label{l:typ-conf} $\forall \gamma\in(0,1)$ for
$\mu_p$-a.a. configurations $x\in X$ the set of $n\in\IZ_{+}$,
for which any word $A\subseteq x[-n,n]$ with $|A|>2\gamma n$
satisfies the inequality $\rho(A,1)\le1/2$, has the density 1.
\end{lemma}
\proof\hskip-9pt\footnote{The idea of this construction, based on
the large deviation principle, was proposed by A.~Puhal'skii.}
%
Let $\{x_i\}_{-\infty}^{\infty}$ be a Bernoulli sequence with
the density $\cP(x_i=1)=p<1/2$ for all $i\in\IZ$. Introduce
a sequence of functions
$y_n(\tau):=\frac1{2n+1}\sum_{i=-n}^{-n+\intp{2n\tau}}x_i$
depending on a real variable $\tau\in[\gamma,1]$, and consider
a functional
$$ \phi(y(\tau)) := \sup_{\tau\in[0,1-\gamma]}
\sup_{\gamma\le s\le1-\tau}\frac1s(y(\tau+s)-y(\tau)) $$
defined in Skorohod space of functions $y(\tau)$.
Then the quantity under question is the probability
$\cP(\phi(y_n(\tau))\le1/2 ~~ \forall\tau\in[\gamma,1])$.
Since $y_n(\tau)$ converges in probability for a given $\tau$ to
$\tilde y(\tau):=p\tau$ and the functional $\phi$ is continuous,
$\phi(y_n(\tau))$ converges to $\phi(\tilde y(\tau))$ (functional law
of large numbers). Thus we have
$$ \cP(\phi(y_n(\tau))\le1/2 ~~ \forall\tau\in[\gamma,1])
\to \cP(\phi(\tilde y(1))\le 1/2) = 1 ,$$
where the rate of convergence
$(\cP(\phi(y_n(1))>1/2))^{1/n} \toas{n\to\infty} \sqrt{2p(1-p)}$
follows by the combination of the large deviation principle for the
functions $y_n(\tau)$ and the contraction principle (see, e.g., \cite{DZ}).
\qed
\begin{corollary} Results of
Lemmata~\ref{l:conv-simple},\ref{l:conv-flux},\ref{l:typ-conf}
prove Theorem~\ref{t:typ-conv} in the case $v=M=1$.
\end{corollary}
\section{Dynamics of measures and chaoticity}
\label{s:measure}
In this section we shall study the action of the map $\map_{v,M}$
in the space $\cM(X_{M})$ of probabilistic measures on $X_{M}$.
This action is defined as follows:
$\map_{v,M}\mu(Y):=\mu(\map_{v,M}^{-1}Y)$ for a measure
$\mu\in\cM(X_{M})$ and a measurable subset $Y\subseteq X_{M}$. A
measure $\mu\in\cM(X_{M})$ is called translation invariant if
it is invariant with respect to the action of the shift map
$\sigma:X_{M}\to X_{M}$.
\begin{lemma} If $\mu\in\cM(X_{M})$ is translation invariant
then this property holds for $\map_{v,M}^{t}\mu ~ \forall
t\in\IZ_{+}$.
\end{lemma}
\proof We have $\map_{v,M}^{t}\mu(Y) = \mu(\map_{v,M}^{-t}Y) =
\mu(\sigma\map_{v,M}^{-t}Y) =
\mu(\map_{v,M}^{-t}\sigma Y) = \map_{v,M}^{t}\mu(\sigma Y)$.
\qed
One might expect that under the action of the map $\map_{v,M}$
any translation invariant measure should converge to a Bernoulli
one. Indeed,%
\bea{\map\mu_p(x\in X: ~ x_0=1)
\a= \mu_p(x\in X: ~ x[0,1]=11) + \mu_p(x\in X: ~ x[-1,0]=10) \\
\a= \mu_p(x\in X: ~ x[0,1]=11) + \mu_p(x\in X: ~ x[0,1]=10)
= \mu_p(x\in X: ~ x_0=1) .}%
On the other hand, the product structure is not preserved
even in the case of the model of slow particles.
\begin{lemma} The measure $\map\mu_p$ is not a product one
for any $01$ even the average value
$\mu_p(x\in X: ~ x_0=1)$ is not preserved under dynamics. Indeed,
\bea{\map_v\mu_p(x\in X: ~ x_0=1)
\a= \mu_p(x\in X: ~ x[0,1]=11) + \sum_{i=1}^v\mu_p(x\in X: ~ x[-1,0]=10_i) \\
\a= p^2 + p(1-p) + \dots + p(1-p)^v = p + p\sum_{i=2}^v(1-p)^i \\
\a> p = \mu_p(x\in X: ~ x_0=1) .}%
Note that in the case of the slow particles model $(\map_{1,1},X)$
some results about the set of $\map_{1,1}$-invariant measures and
mathematical expectations of the limit flux with respect to them
were studied in \cite{BKNS}.
\smallskip
In \cite{Bl-var} it has been proven that the dynamical system
$(\map_{1,M},X_M)$ is chaotic in the sense that its topological
entropy is positive. Moreover this paper gives an asymptotically
exact (as $M\to\infty$) representation for the entropy. The extension
of this result to the case $(\map_{v,M},X_M)$ with $v>1$ is
straightforward.
\section{Passive tracer in the 1-lane flow of fast particles}\label{s:tracer}
Let $\map_v^tx$, $v\ge1$ describes the 1-lane flow of particles and
let at time $t$ the passive tracer occupies the position $i$. Then before
the next time step of the model of the flow the tracer moves in its
chosen direction to the closest (in this direction) position of a
particle of the configuration $\map_v^tx$. For example, if the going
forward tracer occupies the position 2 and the closest particle
in this direction occupies the position 5, then the tracer moves
to the position 5. Then the next iteration of the flow occurs,
the tracer moves to its new position, etc.
To be precise let us fixed a configuration $x\in X$ with
$\rho_-(x,1)>0$ and introduce the maps $\tau_{x}^{\pm}:\IZ\to\IZ$
defined as follows:
$$ \tau_{x}^{+}i := \min\{j: \; ij, \; x_j=1\} .$$
Then the simultaneous dynamics of the configuration of particles
(describing the flow) and the tracer is defined by the skew product of
two maps -- the map $\map_v$ and one of the maps $\tau_{\cdot}^{\pm}$, i.e.
$$ (x,i) \to {\cal T}_{\pm}(x,i) := (\map_v x, \tau_{x}^{\pm}i) ,$$
acting on the extended phase space $X\times\IZ$. The sign $+$ or
$-$ here corresponds to the motion along or against the flow.
We define the {\em average (in time) velocity} of the tracer $V(t,x)$
as $S(t)/t$, where $S(t)$ denotes the total distance covered by the
tracer (which starts at the site 0) up to the moment $t$ with the
positive sign if the tracer moves forward, and the negative sign otherwise.
\begin{theorem}\label{t:tracer}
Let $x\in\{x\in X: ~ \dist(\map_v^tx,\Free\cup\c\Free)\le2^{-t/\gamma+1}\}$
for all $t\in\IZ_+$ and some $0<\gamma<1$.
If $0<\rho_+(x,1)\le\frac1{v+1}$, then $V(t,x)\toas{t\to\infty}v$ if
the tracer moves along the flow (i.e. in the case ${\cal T}_+$), and
$\blim\pm{t\to\infty}V(t,x)=\frac{-1}{\rho_\pm(x,1)}+1$ in the opposite
case. If $\rho_-(x,1)>1-\frac1{v+1}$ and the tracer moves
against the flow then $V(t,x)\toas{t\to\infty}-1$.
\end{theorem}
\n{\bf Remark}. The assumption about the initial configurations is satisfied
for $\mu_p$-a.a. $x\in X_M$ (see Theorem~\ref{t:typ-conv}).
\smallskip
\proof Since we assume that $\map_v^tx$ converges to the attractor
$\Free\cup\c\Free$ with the exponentially fast rate, then at the moment
$t\in\IZ_+$ we have an exponentially long (in $t$) interval of the
configuration $\map_v^tx$ consisting of only free particles or
free holes (depending on the density). As we shall show that $V(t,x)$
converges to a constant, then to study its value we can restrict
the analysis to the case $x\in\Free\cup\c\Free$.
Under the assumption $0<\rho_+(x,1)\le\frac1{v+1}$ we have
$\map_v^tx\toas{t\to\infty}\Free_v$.
In the case of ${\cal T}_+$ the tracer will run down one of the
particles and will follow it, but cannot outstrip. Indeed after
each iteration of the flow this free particle occurs exactly
$v$ positions aheed of the tracer. Thus $V(t,x)\toas{t\to\infty}v$.
Consider now the case when the tracer moves backward with respect
to the flow. Then each time when the tracer encounters a particle,
on the next time step this particle moves in the opposite direction
and does not interfere with the movement of the tracer. We assume
again that $x\in\Free_v$ and consider the case
$0<\rho_+(x,1)\le\frac1{v+1}$.
If on the spread of length $n$ there are $m$ particles,
i.e. $m$ obstacles for the tracer then the average velocity on
this segment is equal to $\frac{n-m}{m}$. Going to the limit as
$n\to\infty$ we obtain the desired estimate.
It remains to consider the case $\rho_-(x,1)>1-\frac1{v+1}$ and thus
$\map_v^tx\toas{t\to\infty}\c{\Free_v}$, i.e. to the flow where all
holes move at maximal velocity $-v$. Thus after each iteration the
tracer moves exactly by one position to the left (since it never can
encounter a hole), which gives the limit velocity $-1$. \qed
Observe that the motion against the flow is efficient only in the
case of low density of particles when $\rho_+(x,1)\le\frac1{v+1}$.
On the other hand, in the high density region in the case of the motion
along the flow and in the region $\frac1{v+1}<\rho_-(x,1)<1-\frac1{v+1}$
in the case of the motion against the flow the limit velocity of the
tracer depends not only on the densities, but also on the fine structure
of the configuration $x$. Moreover, this concerns also the case of
`untypical' initial configurations with $0<\rho_-(x,1)<1/2<\rho_+(x,1)$,
when there might be arbitrary long (even infinite) minimal words for
both particles and holes.
%\newpage
%\small
\begin{thebibliography}{99}
\bibitem{BKNS} V.~Belitsky, J.~Krug, E.~Jordao Neves, G.M.~Schutz,
{\em A Cellular Automaton Model for Two-Lane Traffic},
J. Stat. Phys. {\bf 103}:5/6 (2001), 945-971.
\bibitem{Bl-var} M.~Blank,
{\em Variational principles in the analysis of traffic
flows. (Why it is worth to go against the flow.)},
Markov Processes and Related Fields, {\bf 6}:3(2000), 287-304.
\bibitem{Bl-jam} M.~Blank,
{\em Dynamics of traffic jams: order and chaos},
Moscow Math. J., {\bf 1}:1 (2001), 1-26.
\bibitem{CSS} D.~Chowdhury, L.~Santen, A.~Schadschneider,
{\em Statistical physics of vehicular traffic and some related systems},
Physics Reports 329 (2000), 199-329. ~
%http://xxx.lanl.gov/abs/cond-mat/0007053
\bibitem{DZ} A.~Dembo, O.~Zeitouni,
{\em Large deviations techniques and applications},
2nd ed., Springer, NY, 1998.
\bibitem{DLS} B.~Derrida, J.L.~Lebowitz, E.R.~Speer
{\em Shock profiles for the asymmetric simple exclusion process
in one dimension},
J. Stat. Phys., {\bf 89}:1/2 (1997), 135-166.
\bibitem{Fu} H.~Fuks,
{\em Exact results for deterministic cellular automata traffic models},
Phys. Rev. E {\bf 60} (1999), 197-202. %~ comp-gas/9902001
\bibitem{GG} L.~Gray, D.~Griffeath,
{\em The ergodic theory of traffic jams},
J. Stat. Phys., {\bf 105}:3/4 (2001), 413-452.
%~ (http://psoup.math.wisc.edu/traffic/)
\bibitem{Li} T.M. Liggett,
{\em Stochastic interacting systems: contact, voter, and exclusion
processes}, Springer-Verlag, NY, 1999.
\bibitem{Mi} J.~Milnor,
{\em On the concept of attractor},
Comm. Math. Phys., {\bf 99} (1985), 177-195.
\bibitem{NS} K.~Nagel, M.~Schreckenberg,
{\em A cellular automaton model for freeway traffic},
J. Physique I, {\bf 2} (1992), 2221-2229.
\bibitem{NT} K.~Nishinari, D.~Takahashi,
{\em Analytical properties of ultradiscrete Burgers equation and
rule-184 cellular automaton},
J. Phys. A {\bf 31}:24 (1998), 5439-5450.
\end{thebibliography}
\end{document}