\documentclass[10pt]{article} %[Final version] \makeatletter \def\draft{\textheight=10.5truein \textwidth=7.5truein \parindent=8pt \voffset=-1truein \topmargin=0Truein \ifcase \@ptsize \hoffset=-1.5truein \or \hoffset=-1.35truein \or \hoffset=-1.15truein \fi} \def\quality{\textheight=240mm \textwidth=150mm \topmargin=0Truein \ifcase \@ptsize \hoffset=-23mm \or \hoffset=-20mm \or \hoffset=-15mm \fi} \makeatother \quality \def\cB{{\cal B}} \def\cM{{\cal M}} \def\SBR{{\bf SBR }} \def\BV{{\bf BV}} \def\cP{{\cal P}} \def\Var{{\rm Var}} \def\CML{{\bf CML }} \def\Tor{{\bf Tor}} \def\IR{\hbox{\rm I\kern-.2em\hbox{\rm R}}} \def\IC{{\bf C}} \def\IL{{\bf L}} \def\IP{{\bf P}} \def\var{\, {\rm var}} \def\IZ{\hbox{{\rm Z}\kern-.3em{\rm Z}}} \def\const{\, {\rm Const} \,} \def\mod1{\,({\rm mod\ } 1)\,} \def\ep{\varepsilon} \def\phi{\varphi} \def\rmap{{\overline T}} \def\cM{{\cal M}} \def\La{\Lambda} \def\la{\lambda} \def\E#1{{\bf E}\left[#1\right]} \def\lr#1{\left\{ #1 \right\}} \def\CR{$$ $$} \def\n{\noindent} %\def\cite#1{[{\bf#1}]} % only for the draft phase \def\nB#1{\norm{#1}{\cB}} \def\sp{{\rm sp}} \def\esssp{{\rm _{ess}sp}} \def\nN#1{\norm{#1}{}} \def\nn#1{\norm{#1}{_w}} \def\bV{{\bf V}} \def\cC{{\cal C}} \def\cF{{\cal F}} \def\map{T} \def\ME#1{{\bf E}_{_{#1}}} \def\TP{{\bf TP}} \def\PTP{{\bf PTP}} \def\Z{{\cal Z}} \def\cZ{{\cal Z}} \def\mlbscale{1pt} %to change: \renewcommand\mlbscale{1.3pt} \def\bline(#1,#2)(#3,#4)(#5){\put(#1,#2){\line(#3,#4){#5}}} \def\Bfig(#1,#2)#3#4{\begin{figure} \begin{center} \setlength{\unitlength}{\mlbscale} \begin{picture}(#1,#2)#3 \end{picture} \end{center} \caption{ }#4 \end{figure}} % #1=X_Length #2=Y_Length #3=Body #4=Caption & Label \def\bpic(#1,#2)#3{\setlength{\unitlength}{\mlbscale} \begin{picture}(#1,#2) #3 \end{picture}} % #1=X_Length #2=Y_Length #3=Body (noncentered) \newcount\myDx \newcount\myDy \newcount\myxy \def\bdline[#1,#2](#3,#4)(#5,#6)(#7){ %\bdline[6,8](10,35)(1,2)(72) \myDx=#5 \multiply\myDx by #2 \myDy=#6 \multiply\myDy by #2 \myxy=#7 \divide\myxy by #2 %\advance\myxy by 1 %\typeout{dx, dy, n:, \the\myDx, \the\myDy, \the\myxy} \multiput(#3,#4)(\myDx,\myDy){\myxy}{\line(#5,#6){#1}} \myDx=#5 \multiply\myDx by #7 \advance\myDx by #3 \myDy=#6 \multiply\myDy by #7 \advance\myDy by #4 \put(\myDx,\myDy){\line(-#5,-#6){#1}} } \def\beq#1#2{\begin{equation} \label{#1} #2 \end{equation}} \def\bea#1{\begin{eqnarray*} #1 \end{eqnarray*}} \def\a{\!\!\!&\!\!\!\!&} \def\function#1{\left\{\!\!\!\begin{array}{ll} #1 \end{array} \right.} \def\norm#1#2{\left|\left|#1\right|\right|_{#2}} % ||#1||_{#2} \def\na#1#2{\norm{#1}{_{(#2)}}} \def\n{\noindent} \def\1#1{\hbox{\large \bf 1}_{#1}} % 1_{#1} \newtheorem{theorem}{Theorem}[section] %Numbering: Theorem--Other section \newtheorem{lemma}{Lemma}[section] %{lemma}[theorem]{Lemma} section \newtheorem{proposition}[lemma]{Proposition} %lemma \newtheorem{corollary}[lemma]{Corollary} %lemma \newtheorem{example}[lemma]{\exname} \def\exname{Example} \newtheorem{dftn}{Definition}[section] \newenvironment{definition}{\begin{dftn}\rm}{\end{dftn}} %section \newtheorem{rmrk}[lemma]{Remark} \newenvironment{remark}{\begin{rmrk}\rm}{\end{rmrk}} %lemma \renewcommand\theequation{\thesection.\arabic{equation}} %#eq-s: sect.num \catcode`@=11 \@addtoreset{equation}{section} \catcode`@=12 \def\proof{\smallskip \noindent {\bf Proof. \ }} \newcommand\filledsquare{\ \vrule width 1.5ex height 1.2ex} %filled square \def\qed{\hfill\filledsquare\linebreak\smallskip\par} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{document} \title{Perron-Frobenius spectrum for random maps \\ and its approximation} \author{Michael Blank\thanks{Russian Academy of Sciences, Inst. for Information Transmission Problems, B.~Karetnij 19, 101447, Moscow, Russia, and Observatoire de la Cote d'Azur, BP 4229, F-06304 Nice Cedex 4, France; e-mail: blank@obs-nice.fr} } \date{April 20, 2001}%\today} \maketitle \n {\bf Abstract.} To study the convergence to equilibrium in random maps we developed the spectral theory of the corresponding transfer (Perron-Frobenius) operators acting in a certain Banach space of generalized functions. The random maps under study in a sense fill the gap between expanding and hyperbolic systems since among their (deterministic) components there are both expanding and contracting ones. We prove stochastic stability of the Perron-Frobenius spectrum and developed its finite rank operator approximations by means of a ``stochastically smoothed'' Ulam approximation scheme. A counterexample to the original Ulam conjecture about the approximation of the SBR measure and the discussion of the instability of spectral approximations by means of the original Ulam scheme are presented as well. %%%%%%%%% \section{Introduction}\label{sec:intro} Let $\{\map_{i}\}$ be a collection of nonsingular maps from a $d$-dimensional smooth manifold $X$ into itself with a metrics $\rho$ on it, and let $\{p_{i}\}$ be a collection of nonnegative integers, such that $\sum_{i}p_{i}=1$. A {\em random dynamical system} on the space $X$ is a stationary stochastic process $\map_1,\map_2,\cdots: X\to X$ (i.e., with values in a space of maps), see for instance \cite{Kif}. There are several approaches in further detalization of this object and in the sequel we shall use the following Markov one. %\begin{definition}\label{i:rmap} By a {\em random map} $\rmap$ we shall mean the Markov random process on $X$ given by the following family of transition probabilities $\cP(x,A) := \sum_{i} p_{i} \1{\map_{i}^{-1}(A)}(x)$ from a point $x\in X$ to a subset $A\subseteq X$. %\end{definition} In other words, on every time step the map $\map_{i}$ is chosen from the collection $\{\map_{i}\}$ independently from the previous choices with the probability given by the distribution $\{p_{i}\}$. In the literature (especially physical) the above defined random map is often called by the {\em iterated function system} (with probabilities). Naturally, a pure deterministic setup was studied as well. This can be done as follows. According to the given collection of maps $\{\map_i\}$ one can define a new multivalued map $\tilde\map:X\to X$ as $\tilde\map x:=\cup_i\map_ix$. Assuming that the maps $\map_i$ are continuous and strictly contracting one can show \cite{Hut} that the multivalued map $\tilde\map$ possesses a global attractor $X_{\tilde\map}\subset X$, namely the Hausdorff distance between the sets $\tilde\map^nY$ and $X_{\tilde\map}$ decreases exponentially fast for any closed nonempty set $Y\subset X$. It is worth note that our aim in this paper is not to study the most general setup (for example, one can consider an infinite (continual) collection of maps $\{\map_{i}\}$, while the distribution $\{p_{i}\}$ might be place dependent (on the space variable), but rather to give a deeper analysis of dynamical and statistical properties of these systems related to the convergence to equilibrium, i.e. on spectral problems of the corresponding transfer operators practically not studied in the literature (except \cite{Bl-mon}). Therefore we shall not consider well studied problems of the dimensional analysis of invariant sets and measures. The reader can find results and further references of this type, e.g. in \cite{Fal}. One can always realize the random map under study as a deterministic one on the extended phase space. Denote by $\bar\Omega$ the space of one-side sequences $\bar\omega:=\{\omega_{1},\omega_{2},\dots\}\in\bar\Omega$, where each $\omega_{i}$ belongs to the set of indices of the collection $\map_{i}$. On the space $\bar\Omega$ one defines the left-shift map $\sigma:\bar\Omega\to\bar\Omega$ according to the rule $(\sigma\bar\omega)_{i} := \omega_{i+1}$. The topology in the space $\bar\Omega$ is defined as the direct product of discrete topologies, acting on the set of indices, and a Borel measure $\mu_{p}$ on $\bar\Omega$ is defined as the product of distributions $\{p_{i}\}$ on the set of indices. Naturally there exists an one-to-one correspondence between the sequences of maps $\map_{i}$ and the elements of the space $\bar\Omega$. On the extended space $\bar\Omega\times X$ one can define a new map -- a skew product upon the left-shift map: $\tilde\map(\bar\omega,x) := (\sigma\bar\omega, \map_{\omega_{1}}x)$. Let us give a few simple examples of random maps, demonstrating that even in the simplest cases the dynamics of random maps might be rather nontrivial. For the sake of simplicity in all our examples both here and in the sequel the collection of maps will consist of only two maps $\map_{1}, \map_{2}$ from the unit interval into itself and thus the corresponding distribution is described by the one parameter $p:=p_{1}$. \begin{example}\label{ex:1} Pure contractive maps: $\map_{1}(x):= x/2$, $\map_{2}(x):=x/2 + 1/2$. \end{example}% According to \cite{Hut} (see also the next section) for each value of the parameter $0
\frac12$ the invariant measure becomes non unique but there exists a unique absolutely continuous invariant one, whose density $h_{\rmap}$ is such that $h_{\rmap}|I_{k}=\gamma_k$ for any $k=1,2,\dots$ and intervals $I_{k}:=(2^{-(k-1)},2^{-k}]$. However the constants $\gamma_k$ are bounded on $k$ while $2/3
0 .$$
It is straightforward to show that the transfer operator
corresponding to the random map $\rmap$ in the space $\IL_1$ can
be written as
$$ \IP_{\rmap} := \sum_i p_i \IP_i ,$$
where $\IP_i$ is the Perron-Frobenius operator, corresponding to
the map $\map_i$ and describing the dynamics of densities of measures
under its action (see a detailed discussion of properties of these
operators for example in \cite{Bl-mon}).
Denoting by $\Omega$ the set of values of the index $i$, we consider
for a given number $\La$ the sequence of sets
$$ \Omega^{(n)}(\La)
:= \{\omega \in \Omega: \; |(\rmap_\omega^n x)'| > \La^n
\; {\rm for \ a. a.} \; x \in X \} ,$$
where
$$ \rmap_\omega^n x
:= \map_{\omega_n} \circ \map_{\omega_{n-1}} \circ \dots
\circ \map_{\omega_1} x $$
is the $n$-th point of a realization of a trajectory of the random map
$\rmap$ starting from the point $x$, and introduce the following
{\em regularity assumption}\label{i:reg-r}: there exist two constants
$\Lambda>1$ and $C<\infty$ such that%
\beq{reg-ass}{ \cP\{\Omega^{(n)}(\La) \} \ge 1 - Ce^{-\sqrt{n}} }%
for each positive integer $n$.
Denote by $\var(\cdot)$ the standard one-dimensional variation o
a function and by $\BV$ the space of functions of bounded variation
equipped with the norm $||\cdot||_{\BV}:=\var(\cdot) + ||\cdot||_{\IL_{1}}$.
The following result gives the decomposition for the transfer operator
under the considered assumptions.
\begin{theorem}\label{random-decomposition-exp}\cite{Mo,Bl-mon}
Let the regularity assumption (\ref{reg-ass}) holds. Then for
each pair of positive integers $n,k$ the following decomposition
takes place for the random map $\rmap$:
$$ \IP_\rmap^n = P_{n,k} + Q_{n,k} ,$$
and
\beq{r-exp-decom'}{ \var(P_{n,k} h)
\le \const \left( \alpha^n\var(h) + \beta^k ||h|| \right) ,}
\beq{r-exp-decomp2}{||Q_{n,k}h|| < \const \sqrt{k}e^{-\sqrt{k}}
||h|| ,} for each function $h \in \BV$ and
$0<\alpha<1<\beta<\infty$. All constants above depend on the
choice of the map $\map_i$, but do not depend on $n$ and $k$.
\end{theorem}
One can find in the literature dedicated to the question of the
existence of absolutely continuous invariant measures in our
setting two types of sufficient conditions for this existence.
The first of these conditions obtained in \cite{Pe1} corresponds
to the strong expansion on
average \label{i:pel}%
\beq{Pel-ineq}{ \sum_{i} \frac{p_{i}}{\la_{\map_{i}}} < 1 ,}%
while the second, described in \cite{Mo}, is a weaker condition:%
\beq{Mor-ineq}{ \prod_{i} \la_{\map_{i}}^{p_{i}} > 1 .}%
One can easily show that the first of these assumption yields the
second one. On the other hand, as we shall show there is an
important difference between properties of invariant measures and
respectively random maps under these assumptions. To explain the
difference let us return to our regularity assumption and show
that it is even more general with respect the inequality
(\ref{Mor-ineq}). For this purpose we shall need the following
simple technical estimate.
\begin{lemma}\label{ineq-exp-random} Let $\{\xi_{i}\}_i$ be a
sequence of independent identically distributed (iid) random
variables having exponential moments up to some positive order
$s_0$, i.e. $\E{e^{s\xi}}<\infty$ for all $0 0$ the set
$$ \sp(\IP) \cap \{z\in\IC: \; |z|\ge \rho_{\cB,{\rm ess}}(\IP) + \ep\} $$
consists of a finite number eigenvalues
$\la_1,\la_2,\dots,\la_{M(\ep)}$ of the operator $\IP$.
Schematically on the complex plane the spectrum can be
represented as a disk of radius $\rho_{\cB,{\rm ess}}(\IP)$
centered at the origin (describing the essential spectrum) and
(not more than countable) collection of points between this disk
and the circle of radius $\rho_\cB(\IP)$ also centered at the
origin.
%%%%%%%
\subsection{Spectrum for the case of contracting on average random maps}
In Section~\ref{s:contract} it was shown that a contracting on
average random map $\rmap$ possesses the only one invariant
measure $\mu_{\rmap}$ to which the sequence of iterations
$\{\rmap^{n}\mu\}$ converges (exponentially fast in the
Hutchinson metrics) for each probabilistic initial measure $\mu$.
>From the point of view of dynamical system theory the following
question after this is the analysis of the spectrum of this
convergence. The problem here is that typically the limit measure
$\mu_{\rmap}$ is not absolutely continuous, which rules out the
description of the transfer operator $\IP_{\rmap}$ in a space of
a reasonably `good' functions, for example, in the space of
functions of bounded variation. To overcome this difficulty we
shall study the action of the operator $\IP_{\rmap}$ in a much
larger space of generalized functions equipped with a norm
induced by the Hutchinson metrics.
Let $(X,\rho)$ be a $d$-dimensional smooth manifold with a finite
collection of continuous maps $\{\map_{i}\}$ having bounded
Lipschitz constants $\La_{\map_{i}}$ from $X$ into itself, and a
collection of probabilities $\{p_{i}\}$, defining the random map
$\rmap$. Remind that the contraction on average means that
$$ \La_{\rmap} := \sum_{i} p_{i} \La_{\map_{i}} < 1 .$$
Before to define our space of generalized functions we need first
to define the class of test-functions $\phi:X\to\IR^{1}$. For
this purpose we introduce the following functionals:%
\bea{H_{\alpha}(\phi) \a:= \sup_{x,y\in X,\;
\rho(x,y)\le\nu} \frac{|\phi(x) - \phi(y)|}{\rho^{\alpha}(x,y)} ,\\
V_{\alpha}(\phi) \a:= H_{\alpha}(\phi) + |\phi|_{\infty} ,}%
where $|\phi|_{\infty}:={\rm esssup}|\phi|$, and the constant
$\nu\in(0,1]$. The first of these functionals is the H\"older
constant with the exponent $\alpha<1$, while the second one for
each finite nonnegative value of the parameter $a$ is the norm in
the Banach space of $\alpha$-H\"older functions on $X$, which we
shall denote by $\IC^{\alpha}$. Without the loss of generality we
shall assume that the diameter of the phase space $\sup_{x,y\in
X}\rho(x,y)\le1$. Note that the another restriction
$\rho(x,y)\le\nu$ is introduced only to be able to work with the
exponential map on general smooth manifolds: in the case of a
flat torus this restriction can be omitted (or simply one can set
$\nu=1$).
Consider now the space of generalized functions $\cF$ on $X$ with
the norm defined in terms of the test-functions from the space
$\IC^{\alpha}$:
$$ \na{h}{\alpha} := \sup_{V_{\alpha}(\phi)\le1} \int h\phi .$$
The proof that the functional $\na{\cdot}{\alpha}$ is indeed a norm in
this space is standard and we leave it for the reader.
Denote by $\cF_{\alpha}$ the closure of the set of bounded in the
norm $\na{\cdot}{\alpha}$ generalized functions from $\cF$.
\begin{lemma}\label{l:holder} $\cF_{\beta} \subseteq\cF_{\alpha}$
for any numbers $0<\alpha\le\beta\le1$ and each function $\phi\in\IC^\beta$
the inequality $V_\beta(\phi) \le V_\alpha(\phi)$ holds.
\end{lemma}
\proof Indeed,
$$ \frac{|\phi(x) - \phi(y)|}{\rho^{\beta}(x,y)}
= \frac{|\phi(x) - \phi(y)|}{\rho^{\alpha}(x,y)}
\rho^{\beta-\alpha}(x,y) \le H_{\alpha}(\phi) .$$
\qed
Extending the standard definition of the Perron-Frobeniusa
operator to the action in the space of generalized functions we
get the representation
$$ \int \IP_{\rmap} h \cdot \phi
= \int h \cdot \sum_{i} p_i \, \phi \circ \map_{i}
=: \int h \cdot (\phi\circ\rmap) $$
for each test-function from $\phi\in\IC^{\alpha}$.
Let us fix some constants $0<\alpha<\beta\le1$, $02$
and for any $h\in\cF_{\alpha}$ and $n\in\IZ_+$
the Lasota-Yorke inequality holds: %
\beq{LY-random-ifs}{
\na{\IP_{\rmap}^nh}{\alpha}
\le \kappa\La_\rmap^n(\alpha) \na{h}{\alpha}
+ \const\cdot (\kappa-2)^{-1/\alpha} \na{h}{\beta} .}
\end{theorem}
\proof We start from the proof of the following two inequalities:%
\beq{LY-random-ifs-1}{ \na{\IP_{\rmap}h}{\beta} \le \na{h}{\beta} ,}%
\beq{LY-random-ifs-2}{
\na{\IP_{\rmap}h}{\alpha}
\le \kappa\La_\rmap(\alpha) \na{h}{\alpha}
+ \const\cdot (\kappa-2)^{-1/\alpha} \na{h}{\beta} .}%
By the definition of the H\"older constant we have:
$$ \frac{|\phi(\map_i x) - \phi(\map_i y)|}{\rho^\alpha(x,y)}
= \frac{\rho^\alpha(\map_i x, \map_i y)}{\rho^\alpha(x,y)}
\frac{|\phi(\map_i x) - \phi(\map_i y)|}{\rho^\alpha(\map_i x, \map_i y)}
\le \La_{\map_i}^\alpha H_\alpha(\phi) .$$
Hence,
$$ \frac{\sum_i p_i |\phi(\map_i x) - \phi(\map_i y)|}{\rho^\alpha(x,y)}
\le \sum_i p_i \La_{\map_i}^\alpha H_\alpha(\phi) .$$
Thus,
$$ H_\alpha\left(\sum_i p_i (\phi\circ\map_i)\right)
\le \La_\rmap(\alpha) H_\alpha(\phi) < H_\alpha(\phi) .$$
On the other hand, since
$$ |\phi\circ\map_i|_\infty \le |\phi|_\infty ,$$
then
$$ \sum_i p_i |\phi\circ\map_i|_\infty \le |\phi|_\infty .$$
Therefore for each $\beta\in(0,1]$ we have
$$ V_\beta\left(\sum_i p_i |\phi\circ\map_i|\right) \le V_\beta(\phi) ,$$
which implies the inequality~(\ref{LY-random-ifs-1})
for each $\beta\in(0,1]$ and a function $h\in\cF_\beta$.
To prove the second inequality~(\ref{LY-random-ifs-2}) we need
more delicate estimates.
Introduce the following notation:
$$ B_\delta(x) := \{y\in X:\; \rho(x,y)\le\delta \} \qquad
B_\delta := \{\xi\in {\cal T}_x X: \; |\xi|\le\delta\} ,$$
i.e. $B_\delta(x)$ is the ball of radius $\delta$ centered at the
point $x$ in the space $X$, while $B_\delta$ is the ball of radius
$\delta$ centered at the origin in the tangent space ${\cal T}_x X$.
For each point $x\in X$ consider the exponential map
$$ \Psi_x := \exp_x : B_\delta \subseteq {\cal T}_x X \to X .$$
Choosing $\delta>0$ small enough we always can assume that
$\Psi_x B_\delta \subset B_\nu(x)$.
Denoting by $m$ the Lebesgue measure on $X$, we introduce the
following smoothing operator
$$ Q_\delta \phi(x)
:= \frac{\int_{\Psi_x B_\delta} \phi(y) m(dy)}{m(\Psi_x B_\delta)}
= \frac{\int_{B_\delta} \phi(\Psi_x z)\cdot J\Psi_x(z) \, dz}
{\int_{B_\delta} J\Psi_x(z) \, dz} ,$$
where $J\Psi_x$ is the Jacobian of the map $\Psi_x$.
Let us estimate the H\"older constant of the function $Q_\delta \phi$:%
\bea{|Q_\delta \phi(x) - Q_\delta \phi(y)|
\a\le \left| \int_{B_\delta} J\Psi_x(z) \, dz
- \int_{B_\delta} J\Psi_y(z) \, dz \right| \cdot
\left| \frac{\int_{B_\delta} \phi(\Psi_y z)\cdot J\Psi_y(z) \, dz}
{\int_{B_\delta} J\Psi_x(z) \, dz \cdot
\int_{B_\delta} J\Psi_y(z) \, dz} \right| \\
\a~ + \frac1{\int_{B_\delta} J\Psi_x(z) \, dz} \cdot
\left| \int_{B_\delta} \phi(\Psi_x z)\cdot J\Psi_x(z) \, dz
- \int_{B_\delta} \phi(\Psi_y z)\cdot J\Psi_y(z) \, dz \right| \\
\a\le 2\left( \sup_x J\Psi_x \right)^2 \cdot |\phi|_\infty \cdot
\frac{|B_\delta\setminus\Psi_x^{-1}\Psi_y B_\delta|
+ |\Psi_x^{-1}\Psi_y B_\delta \setminus B_\delta|}{|B_\delta|} \\
\a\le \frac1\delta C_1 |\phi|_\infty \rho(x,y) ,}%
where the constant $C_1$ depends only on the properties of the manifold $X$.
Now we estimate how much the operator $Q_\delta$ differs from the
identical operator:
$$ |Q_\delta\phi(x) - \phi(x)|
\le \frac{\int_{B_\delta} |\phi(\Psi_x(z)) - \phi(x)| \cdot J\Psi_x(z) \, dz}
{\int_{B_\delta} J\Psi_x(z) \, dz}
\le C_2 \delta^\alpha H_\alpha(\phi) ,$$
where the constant $C_2$ also depends only on the properties of the
manifold $X$.
On the other hand,%
\bea{\a H_\alpha\left(\sum_i p_i (\phi\circ\map_i)
- Q_\delta\left(\sum_i p_i (\phi\circ\map_i)\right)\right) \\
\a~\le H_\alpha\left(\sum_i p_i (\phi\circ\map_i)\right)
+ H_\alpha\left(Q_\delta\left(\sum_i p_i (\phi\circ\map_i)\right)\right) \\
\a~\le 2\La_\rmap(\alpha) H_\alpha(\phi) .}%
Thus,
$$ V_\alpha\left(\sum_i p_i (\phi\circ\map_i)
- Q_\delta\left(\sum_i p_i (\phi\circ\map_i)\right)\right) \CR
\le 2\La_\rmap(\alpha) H_\alpha(\phi)
+ C_2 \delta^\alpha H_\alpha(\phi) .$$
Gathering the obtained estimates and using Lemma~\ref{l:holder} we come to%
\bea{\na{\IP_\rmap h}{\alpha}
\a\le \sup_{V_\alpha(\phi) \le 1}
\int h \cdot Q_\delta\left(\sum_i p_i (\phi\circ\map_i)\right) %\\
+ \sup_{V_\alpha(\phi) \le 1}
\int h \cdot \sum_i p_i \left(\phi\circ\map_i
- Q_\delta(\phi\circ\map_i)\right) \\
\a\le \sup_{V_\beta(\phi) \le 1}
V_\alpha\left(Q_\delta\left(\sum_i p_i
(\phi\circ\map_i)\right)\right)
\na{h}{\beta} \\
\a~ + \sup_{V_\alpha(\phi) \le 1}
V_\alpha\left( \sum_i p_i \left(\phi\circ\map_i
- Q_\delta(\phi\circ\map_i)\right) )\right)
\na{h}{\alpha} \\
\a\le \frac{C_1}\delta \na{h}{\beta}
+ \left( 2\La_\rmap(\alpha) + C_2\delta^\alpha \right) \na{h}{\alpha} .}%
Therefore choosing the value of the parameter $\delta$ such small that
$C_2\delta^\alpha = \kappa-2$, we get the inequality~(\ref{LY-random-ifs-2}).
Now according to Lemma~\ref{l:holder-sup} and above inequalities we get%
\bea{\na{\IP_{\rmap}^n h}{\alpha}
\a= \na{\IP_{\rmap^n} h}{\alpha}
\le \kappa\La_{\rmap^n}(\alpha) \na{h}{\alpha}
+ \const\delta^{-1} \na{h}{\beta} \\
\a\le \kappa\La_{\rmap}^n(\alpha) \na{h}{\alpha}
+ \const\cdot (\kappa-2)^{-1/\alpha} \na{h}{\beta} ,}%
which finishes the proof of the inequality~(\ref{LY-random-ifs}). \qed
\begin{lemma}\label{l:convex-unique}
The function $\La_{\rmap}(\cdot)$ is convex, takes values
strictly less than $1$ in the interval $(0,1]$, and under the condition%
\beq{ne:uniq-rand}{\prod_i \La_{\map_{i}}^{p_i \La_{\map_{i}}} < 1}%
its unique point of minima either lies inside of this interval, or
is larger than $1$ otherwise.
\end{lemma}
\proof By the definition of the contraction on average we have
$\La_{\rmap}(1)=\La_{\rmap}<1$. On the other hand, $\La_{\rmap}(0)=1$,
and
$$ \frac{d^{2}}{dq^{2}} \La_{\rmap}(q)
= \sum_{i}p_{i} \La_{\map_{i}}^{q}
\cdot \left(\ln \La_{\map_{i}} \right)^{2} > 0 .$$
Thus the function $\La_{\rmap}(q)$ is strictly convex and for
any $q\in(0,1]$ it is less than $1$. Let us show that this function
strictly decreases at $0$. Indeed,
$$ \frac{d}{dq} \La_{\rmap}(0) = \sum_{i} p_{i} \ln\La_{\map_{i}} .$$
On the other hand, from the contraction on average
$$ \sum_{i} p_i \La_{\map_{i}} < 1 $$
using the convexity of the logarithmic function, we get:
$$ \sum_{i} p_{i} \ln\La_{\map_{i}} < \ln1 =0 ,$$
which proves that $\frac{d}{dq} \La_{\rmap}(0) < 0$.
It remains to check the last statement.
$$ \frac{d}{dq} \La_{\rmap}(1)
= \sum_i p_i \La_{\map_{i}}\cdot \ln\La_{\map_{i}}
= \sum_i \ln\La_{\map_{i}}^{p_i \La_{\map_{i}}}
= \ln\left( \prod_i \La_{\map_{i}}^{p_i \La_{\map_{i}}} \right) .$$
Thus due to the inequality~(\ref{ne:uniq-rand}) the unique (due to the
strict convexity of the function $\La_\rmap(\cdot)$) solution of the
equation $\frac{d}{dq} \La_{\rmap}(q)=0$ (the point of minima of the
function $\La_\rmap(\cdot)$) belongs to the interval $(0,1)$. On the
other hand, if the inequality~(\ref{ne:uniq-rand}) does not hold this
solution is greater than $1$.
\qed
A typical behavior of the function $\La_{\rmap}(q)$ is shown
Fig.~\ref{convex-q}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Picture for $\La_{\rmap}(q)$
\Bfig(150,150)
{\bline(0,0)(1,0)(150) \bline(0,0)(0,1)(150)
\bline(0,150)(1,0)(150) \bline(150,0)(0,1)(150)
\bline(20,20)(1,0)(110) \bline(20,20)(0,1)(110)
\bline(120,20)(0,1)(70) \bline(86,20)(0,1)(47)
\bezier{500}(20,120)(80,30)(120,90)
\put(15,15){$0$} \put(135,20){$q$} \put(15,135){$\La_{\rmap}(q)$}
\put(13,117){$1$} \put(117,10){$1$} \put(83,10){$\tilde q$}
}{A typical behavior of the function $\La_{\rmap}(q)$. \label{convex-q}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Denote by $\tilde q$ the value of the parameter $q$ corresponding
to the unique (due to the strict convexity) minima of the
function $\La_{\rmap}(q)$. The value $\tilde q$ is positive since
$\frac{d}{dq} \La_{\rmap}(0)<0$. The position of $\tilde q$ with
respect to $1$ is defined by the sign of the derivative of the
function $\La_{\rmap}(q)$ at $1$ which might be both positive and
negative. For example, if all the maps are contractive then this
sign is negative and the function $\La_{\rmap}(q)$ strictly
decreases on the interval $[0,1]$. On the other hand, the map in the
example~\ref{ex:2} satisfies the condition~(\ref{ne:uniq-rand})
if $0 \La_\rmap>\La_\rmap(\alpha)$
(by Lemma~\ref{l:convex-unique}). Thus if there is a function
$f\in\cF_\alpha$ such that $\IP_\rmap f = \La_\rmap f$,
then $\La_\rmap$ is an isolated eigenvalue.
\begin{example}\label{ex:6}
$\map_1(x) := 1/2 + {\rm sign}(x-1/2) \cdot
[1/2 - |2{\rm sign}(x-1/2)\cdot(x-1/2) - 1/2|]$,
where ${\rm sign}(x)$ is the sign of the number $x$, and
$\map_2(x):=x/2$.
\end{example}
The maps $\map_i$ are shown on Fig.~\ref{fig:ex-is-eigen}.
Note that this random map is contractive on average when $0 2$ we deduce
that the constants $a_{k}$ grow as $((1-p)/(2p))^{k}$ as $k\to\infty$.
It remains to estimate the $\na{\cdot}{\alpha}$-norm of the
generalized function $f_{\bar a}$:
$$ \na{f_{\bar a}}{\alpha}
= 2c^\alpha \sum_{k=0}^\infty a_k 2^{-k\alpha} < \infty $$
if and only if $((1-p)/(2p))2^{-k\alpha} < 1$. On the other hand,
$(1-p)/(2p)>2$ for $0 \ep, }
\beq{kernel-2}{ \int |q_\ep(x,z) - q_\ep(y,z+y-x)|~dz \le M \rho(x,y), }
We start the analysis of the operator $Q_\ep^*$ from the following simple
estimates.
\begin{lemma}\label{l:simple-est} For each $\phi\in\IC^\alpha$ we have
\beq{est-mod}{|Q_\ep^* \phi|_\infty \le |\phi|_\infty ,}
\beq{est-dif}{|Q_\ep^* \phi - \phi|_\infty \le \ep^\alpha H_\alpha(\phi) .}
\end{lemma}
\proof The proof is straightforward:%
\bea{|Q_\ep^* \phi(x)| \a= |\int q_\ep(x,z)\phi(z)\,dz|
\le \int q_\ep(x,z) |\phi(z)|\,dz \le |\phi|_\infty .\\
|Q_{\ep}^{*}\phi(x) - \phi(x)|
\a= |\int q_{\ep}(x,z)\phi(z)\,dz - \phi(x)| \\
\a\le \int q_{\ep}(x,z) |\phi(z) - \phi(x)| \,dz \\
\a\le \ep^{\alpha} H_{\alpha}(\phi) ,}%
since only the points $z\in B_\ep(x)$ should be taken into account.
\qed
Now let us estimate the norm of the operator $Q_\ep$.
\begin{lemma}\label{l:Qep-alpha} Let
$M_1(\ep):=\max\{2 \ep^{\alpha/2}, \, M\ep^{(1-\alpha)/2}\}$. Then
$\na{Q_\ep}{\alpha} \le 1 + M_1(\ep)$. \end{lemma}
\proof Our aim is to show that $Q_\ep^* \phi$ is a valid test
function and to estimate the values of $V_\alpha(Q_\ep^* \phi)$.
We already estimated the supremum norm of the function $Q_\ep^*
\phi$. To get the estimate of the H\"older constant we consider
two different situations: when the points $x,y$ are close, i.e.
$\rho(x,y)\le\sqrt{\ep}$, and the opposite case when they are far
apart. In the first case we proceed as follows:%
\bea{|Q_\ep^* \phi(x) - Q_\ep^* \phi(y)|
\a= |\int q_\ep(x,z) \phi(z)\,dz - \int q_\ep(y,z) \phi(z)\,dz | \\
\a= |\int q_\ep(x,z) \phi(z)\,dz - \int q_\ep(y,z+y-x) \phi(z+y-x)\,dz | \\
\a\le |\int q_\ep(x,z) \phi(z)\,dz - \int q_\ep(x,z) \phi(z+y-x)\,dz | \\
\a~+ |\int q_\ep(x,z) \phi(z+y-x)\,dz - \int q_\ep(y,z+y-x) \phi(z+y-x)\,dz| \\
\a\le \int q_\ep(x,z) |\phi(z) - \phi(z+y-x)|\,dz \\
\a~+ \int |q_\ep(x,z) - q_\ep(y,z+y-x)|\cdot |\phi(z+y-x)|\,dz \\
\a\le \rho^\alpha(x,y) H_\alpha(\phi) + M \rho(x,y)|\phi|_\infty \\
\a\le \left[H_\alpha(\phi)
+ M \ep^{(1-\alpha)/2}|\phi|_\infty \right] \rho^\alpha(x,y) .}%
In the opposite case, when $\rho(x,y)>\sqrt{\ep}$ we shall proceed in
a different way:%
\bea{|Q_\ep^* \phi(x) - Q_\ep^* \phi(y)|
\a\le |Q_\ep^* \phi(x) - \phi(x)| + |Q_\ep^* \phi(y) - \phi(y)|
+ |\phi(x) - \phi(y)| \\
\a\le 2|Q_\ep^* \phi - \phi|_\infty + \rho^\alpha(x,y) H_\alpha(\phi) \\
\a\le 2\ep^\alpha H_\alpha(\phi) + \rho^\alpha(x,y) H_\alpha(\phi) \\
\a\le (1 + 2\ep^{\alpha/2}) \rho^\alpha(x,y) H_\alpha(\phi) .}%
Hence we have%
\bea{V_\alpha(Q_\ep^* \phi)
\a= H_\alpha(Q_\ep^* \phi) + |Q_\ep^* \phi|_\infty \\
\a\le (1 + 2 \ep^{\alpha/2})H_\alpha(\phi)
+ M \ep^{(1-\alpha)/2}|\phi|_\infty \\
\a\le (1 + \max\{2 \ep^{\alpha/2}, \, M\ep^{(1-\alpha)/2}\})V_\alpha(\phi) .}%
Thus, setting $M_1(\ep):=\max\{2 \ep^{\alpha/2}, \, M\ep^{(1-\alpha)/2}\}$,
we get%
\bea{\na{Q_\ep f}{\alpha}
\a= \sup_{V_{\alpha}(\phi)\le} \int Q_\ep f \cdot \phi
= \sup_{V_{\alpha}(\phi)\le} \int f \cdot Q_\ep^* \phi \\
\a\le \sup_{V_{\alpha}(\phi)\le1} V_{\alpha}(Q_\ep^* \phi) \cdot
\sup_{V_{\alpha}(\psi)\le1} \int f \cdot \psi \\
\a\le (1 + M_1(\ep)) \cdot \na{f}{\alpha} .}%
Observe that in several places we used the estimates of the supremum norms
obtained in Lemma~\ref{l:simple-est}.
\qed
\begin{lemma}\label{l:3norm-0} Let $G:\cF_{\alpha}\to\cF_{\alpha}$
be a linear operator, and let $G^{*}:\IC^{1}\to\IC^{1}$ be dual
to it, i.e. $\int Gf\cdot\phi = \int f\cdot G^{*}\phi$. Then for
all $f\in\cF_{\beta}$
$$ \na{Gf}{\beta}
\le \left(\sup_{V_{\beta}(\phi)\le1} V_{\alpha}(G^{*}\phi) \right)
\cdot \na{f}{\alpha} .$$
\end{lemma}
\proof Indeed,
\bea{\na{Gf}{\beta}
\a= \sup_{V_{\beta}(\phi)\le1} \int Gf\cdot\phi
= \sup_{V_{\beta}(\phi)\le1} \int f\cdot G^{*}\phi \\
\a\le \left(\sup_{V_{\beta}(\phi)\le1} V_{\alpha}(G^{*}\phi) \right)
\cdot \sup_{V_{\alpha}(\psi)\le1} \int f\cdot\psi .}%
\qed
\begin{lemma}\label{l:3norm}
$$ |||Q_{\ep} - 1||| \equiv \na{Q_{\ep} - 1}{\beta\to\alpha} :=
\sup_{\na{f}{\alpha}\le1}\na{Q_{\ep}f - f}{\beta} \to 0
\quad {\rm as} \quad \ep\to0.$$
\end{lemma}
\proof Applying Lemma~\ref{l:3norm-0} to the operator
$G=Q_{\ep}-1$ we get that the sufficient condition of the
validity of the desired statement is the convergence of
$$ \sup_{V_{\beta}(\phi)\le1} V_{\alpha}(Q_{\ep}^{*}\phi - \phi)
\to 0 $$
as $\ep\to0$. Let us prove this convergence. Observe that since
$\beta>\alpha$ and $\phi\in\IC^\beta$ we can get a
stronger estimate compare to Lemma~\ref{l:simple-est}:%
\bea{|Q_{\ep}^{*}\phi(x) - \phi(x)|
\a= |\int q_{\ep}(x,z)\phi(z)\,dz - \phi(x)| \\
\a\le \int q_{\ep}(x,z) |\phi(z) - \phi(x)| \,dz \\
\a\le \ep^{\beta} H_{\beta}(\phi) .}%
Applying now estimates similar to ones used in the proof of
Lemma~\ref{l:Qep-alpha} and taking into account that we consider
more smooth test-functions $\phi\in\IC^{\beta}$ in the case
$\rho(x,y)\le\ep$ we get%
\bea{\a\left|\left(Q_{\ep}^{*}\phi(x) - \phi(x)\right)
- \left(Q_{\ep}^{*}\phi(y) - \phi(y)\right) \right| \\
\a~\le |Q_{\ep}^{*}\phi(x) - Q_{\ep}^{*}\phi(y)| + |\phi(x) - \phi(y)| \\
\a~\le \rho^{\beta}(x,y) H_{\beta}(\phi) + M\rho(x,y)|\phi|_{\infty}
+ \rho^{\beta}(x,y) H_{\beta}(\phi) \\
\a~\le \left[2 \ep^{\beta-\alpha}H_{\beta}(\phi)
+ M\ep^{1-\alpha}|\phi|_\infty \right] \rho^\alpha(x,y) .}%
While in the opposite case, when $\rho(x,y)>\ep$, using the same
argument as in the proof of Lemma~\ref{l:Qep-alpha} we get%
\bea{|\left(Q_{\ep}^{*}\phi(x) - \phi(x)\right)
- \left(Q_{\ep}^{*}\phi(y) - \phi(y)\right)|
\a\le 2 |Q_{\ep}^{*}\phi - \phi|_\infty
\le 2 \ep^{\beta} H_{\beta}(\phi) \\
\a\le 2 \ep^{\beta-\alpha}H_{\beta}(\phi) \rho^\alpha(x,y) .}%
Hence for $\phi\in\IC^{\beta}$
$$ H_{\alpha}(Q_{\ep}^{*}\phi - \phi)
\le 2 \ep^{\beta-\alpha}H_{\beta}(\phi)
+ M \ep^{1-\alpha} |\phi|_{\infty} ,$$
which yields the following estimate%
\bea{V_{\alpha}(Q_{\ep}^{*}\phi - \phi)
\a\le 2 \ep^{\beta-\alpha}H_{\beta}(\phi)
+ M \ep^{1-\alpha} |\phi|_{\infty} + \ep^{\beta} H_{\beta}(\phi) \\
\a\le 3 \ep^{\beta-\alpha}H_{\beta}(\phi)
+ M \ep^{1-\alpha} |\phi|_{\infty}
\le (3 + M\ep^{1-\beta})\ep^{\beta-\alpha} V_{\alpha}(\phi) \to 0 }%
as $\ep\to0$. \qed
The properties of the transition operator obtained above together
with Theorem~\ref{th-LY-rand-contr} under the additional
assumption that $\La_\rmap(\alpha)<1/2$ make it possible to use
results about the spectral stability of transfer operators
satisfying Lasota-Yorke type inequalities \cite{KeLi} and to
obtain the following stability result.
\begin{theorem}\label{t:stoch-stab} Let the conditions
(\ref{kernel-1}, \ref{kernel-2}) be satisfied and let
$\La_\rmap(\alpha)<1/2$ for some $\alpha\in(0,1)$. Then all
elements of the spectrum $\sp_{\cF_{\alpha}}(\IP_{\rmap})$
outside of the disk of radius $\La_\rmap(\alpha)$ are
stochastically stable and the corresponding eigenprojectors of
the perturbed system converge to the genuine ones.
\end{theorem}
\proof First let us show that the transfer operator for the
stochastically perturbed system satisfies a Lasota-Yorke type
inequality. A straightforward calculation shows that this
operator is equal to $Q_\ep \IP_\rmap$. Combining the results of
Lemma~\ref{l:Qep-alpha} and Theorem~\ref{th-LY-rand-contr} we
get for any $h\in\cF_\alpha$ that%
\bea{\na{Q_\ep \IP_\rmap h}{\alpha}
\a\le (1 + M_1(\ep))\na{\IP_\rmap h}{\alpha} \\
\a\le (1 + M_1(\ep)) \kappa \La_\rmap(\alpha) \na{h}{\alpha}
+ \const\cdot(\kappa-2)^{-1/\alpha}\na{h}{\beta} .}%
Therefore, if $\La_\rmap(\alpha)<2$ for some $0<\alpha<1$, then the
number $\gamma:=(1 + M_1(\ep)) \kappa \La_\rmap(\alpha) <1$ for
the value of $\kappa>2$ guaranteed by Theorem~\ref{th-LY-rand-contr}.
Since all other assumptions of the abstract spectral stability
result in \cite{KeLi} were alredy checked during the analysis of
our Banach spaces of generalized functions, we come to the desired
statement. \qed
To proceed further we need to generalize the notion of the periodic
turning point, well known in the one-dimensional dynamics. Namely,
a point $x\in X$ is called the {\em periodic turning point} for the
map $\map:X\to X$ if $\map^nx=x$ for some $n\in\IZ_+$ and the
derivative of the map $\map$ is not well defined at the point $x$.
\begin{definition} A point $x\in X$ is called the {\em periodic turning
point} for the {\em random} map $\rmap:X\to X$ if there is a finite
collection of indices $i_1,i_2,\dots,i_k$ such that the point $x$ is
the periodic turning point for the deterministic map
$\map_{i_1}\circ\map_{i_2}\circ\dots\map_{i_k}$.
\end{definition}
For example, the point $x=1/2$ is the periodic turning point for
the random map in the example 2 for any nontrivial distribution ($0 0$ be a number
such that for each point $x\in X$ the ball (v the metrics $\rho$)
of radius $\nu$ centered at this point belongs to the domain of
values of the exponential map $\Psi_x$. Note that we already have
introduced the restriction on the distance between the points in
the definition of the H\"older constant needing to be content
with the domain of definition of the exponential map. In fact,
the first difference appears only in the analysis of random
perturbations, in particular, the condition (\ref{kernel-2})
should be rewritten as%
$$ \int|q_\ep(x,y) - q_\ep(\Psi_x(\Psi_x^{-1}(x)+t),\Psi_y(\Psi_y^{-1}(y)+t))|
~dy \le \rho(x, \Psi_x(\Psi_x^{-1}(x)+t))M ,$$
where $t\in\IR^d$ and $|t|\le\nu$.
Assuming now that $\ep<\nu$ and replacing the expressions of type
$z+y-x$ to
$$ \Psi_z\left(\Psi_z^{-1}(z) + \Psi_z^{-1}(y) - \Psi_z^{-1}(x)\right) ,$$
we obtain the same estimates as in the flat case (when $X$ is the
unit torus). Therefore all results of this section remain valid
for the case of a general smooth manifold.
%%%%%
\subsection{Finite rank approximations}
Let us discuss now finite dimensional approximations of transfer
operators. Again due to the same reason as in the previous
section we shall restrict the analysis to the case of contracting
on average random maps.
Let $\{\Delta_{i}\}_{i}$ be a finite partitions of the phase
space $X$ into domains (cells) $\Delta_{i}$ of diameter not
larger than $\delta>0$. For a point $x\in X$ by $\Delta_{x}$ we
denote the element of the partition containing it. Under these
notation the so called Ulam approximation can be described as an
operator
$$ \tilde Q_{\delta}f(x) := \frac1{|\Delta|}\int_{\Delta_{x}}f .$$
Note that this operator is selfdual, i.e. $\tilde Q_{\delta} =
\tilde Q_{\delta}^*$. One can easily check also that the
dimension of the space $\tilde Q_{\delta}\cF_{\alpha}$ coincides
with the number of elements in the Ulam partition.
\begin{lemma} $\na{Q_{\delta}}{\alpha}=\infty$. \end{lemma}
\proof Let a point $y_0\in X$ belongs to the boundary between two
elements of the Ulam partition, and let the points $y(\ep)$ and
$y'(\ep)$ belong to neighboring elements of the partition both on
the distance $\ep$ from $y_0$. For the function
$$ f_\ep(x):=\1{y(\ep)}(x) + \1{y'(\ep)}(x) ,$$
where $\1{y}$ means the $\delta$-function at the point $y$, the
following inequalities hold:
$$ \na{f_\ep}{\alpha} \le \const\ep^\alpha ,\CR
\na{Q_{\delta}f_\ep}{\alpha} \ge \const > 0 .$$
The first of these inequalities follows from the definition of
the norm $\na{\cdot}{\alpha}$, while the second one is a
consequence of the fact that the function $Q_{\delta}f_\ep$ is
the characteristic function of the union of two neighboring
elements of the partition containing the points $y(\ep)$ and
$y'(\ep)$. Thus,
$\na{Q_{\delta}f_\ep}{\alpha}/\na{f_\ep}{\alpha} \to \infty$
as $\ep\to0$. \qed
This result shows that the original Ulam approximation scheme
cannot be immediately applied to the spectral analysis of random
maps.
What is still possible is that the leading eigenfunction -- \SBR
measure may be stable for the class of maps we consider (the
above example does not contradict to this -- the \SBR measure is
preserved). I believe there should be very deep reasons
explaining the stability of the leading eigenfunction, while all
others are not stable, however presently we do not have the
adequate explanation. In the literature (see, for example,
\cite{Bl-mon} and further references therein) the stability of the
\SBR measure is proven for the class of piecewise expanding maps.
Moreover numerous numerical studies confirm this stability for a
much broader class of dynamical systems. To the best of our
knowledge the following simple example of a one-dimensional
discontinuous map represent the first counterexample to the
original Ulam hypothesis.
\begin{lemma}\label{l:counter-or-ulam} The map
$$ \map x := \function{
\frac{x}4+\frac12 &\mbox{if }\; 0\le x <\frac5{12}\\
-2x +1 &\mbox{if }\; \frac5{12}\le x < \frac12\\
\frac{x}2+\frac14 &\mbox{otherwise} .} $$
from the unit interval into itself is uniquely ergodic, but the
leading eigenvector of the Ulam approximation
$\Pi_{1/n}\IP_{\map}$ does not converge weakly to the only
$\map$-invariant measure.
\end{lemma}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Counterexample with unique ergodicity
\Bfig(150,150)
{\footnotesize{
\bline(0,0)(1,0)(150) \bline(0,0)(0,1)(150)
\bline(0,150)(1,0)(150) \bline(150,0)(0,1)(150)
%\bline(0,75)(1,0)(150) \bline(75,0)(0,1)(150)
\bdline[6,8](0,75)(1,0)(150) \bdline[6,8](75,0)(0,1)(150)
\put(0,75){\vector(4,1){60}} \put(60,30){\vector(1,-2){15}}
\bline(75,75)(2,1)(75)
\bdline[6,8](60,90)(0,-1)(90)
\put(-3,-8){$0$} \put(147,-8){$1$} \put(50,-8){$5/12$} \put(72,-8){$1/2$}
}}
{Counterexample for the original Ulam construction.
\label{fig-counter-ulam}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Observe that the situation when the \SBR measure becomes unstable
with respect to Ulam scheme is indeed very exotic and the map in
the corresponding example is not only discontinuous (see
Fig.~\ref{fig-counter-ulam}), but this discontinuity occurs in a
periodic turning point (compare to instability results about
general random perturbations in \cite{BK97}).
\proof Denote by $v^{(n)}$ the normalized leading eigenvector of
the matrix $\Pi_{1/n}\IP_{\map}$. A straightforward calculation
shows that for each $n\in\IZ_{+}^{1}$ all entries of the vector
$v^{(2n+1)}$ are zeros except the first entry, which is equal to
$1/3$ and the $(n+1)$-th one, which is equal to $2/3$. Compare
this to the only invariant measure of the map $\map$ -- the unit
mass at the point $1/2$. \qed
To overcome this difficulty we consider another `smoothed'
approximation scheme. In each element of the partition $\{\Delta_i\}$
(of diametr $\le\delta$) we fix an arbitrary point (its `center')
$x_i\in\Delta_{i}$. Now for a given smooth enough kernel
$q_\ep(\cdot,\cdot)$ satisfying the assumptions from the previous
section we define the following finite dimensional operator:
$$ Q_{\ep,\delta} f(x)
:= \sum_i 1_{\Delta_i}(x) \int q_\ep(z,x_i) f(z)~dz .$$
Observe that the dual operator is equal to:
$$ Q_{\ep,\delta}^{*} \phi(x)
:= \sum_i q_\ep(x, x_i) \int_{\Delta_i} \phi(z)~dz .$$
Indeed,%
\bea{\int Q_{\ep,\delta} f(x) \cdot \phi(x)~dx
\a= \int \sum_i 1_{\Delta_i}(x) \int q_\ep(z,x_i) f(z)~dz \cdot \phi(x)~dx \\
\a= \int f(z) \sum_i q_\ep(z,x_i)
\left(\int 1_{\Delta_i}(x) \phi(x)~dx \right)~dz \\
\a= \int f(z) \sum_i q_\ep(z,x_i) \int_{\Delta_i} \phi(x)~dx~dz
= \int f(z) \cdot Q_{\ep,\delta}^{*} \phi(z)~dz .}%
\begin{lemma}\label{l:smooth-ulam-s} Let additionally to the assumptions
(\ref{kernel-1}, \ref{kernel-2}) for any points $x,y,z\in X$
the inequality%
\beq{kernel-4}{ |q_\ep(x,y) - q_\ep(x,z)| + |q_\ep(y,x) - q_\ep(z,x)|
\le M \ep^{-d-1} \rho(y,z) . }
holds. Then
$$ \na{Q_\ep f - Q_{\ep,\delta} f}{\alpha}
\le 5M \ep^{-d-1} \delta^{1-\alpha} \na{f}{\alpha} .$$
\end{lemma}
\proof
$$ \int (Q_\ep f - Q_{\ep,\delta} f)\cdot \phi
= \int f \cdot (Q_\ep^* \phi - Q_{\ep,\delta}^* \phi) .$$
Denote
$$ \Phi(x)
:= Q_\ep^* \phi(x) - Q_{\ep,\delta}^* \phi(x)
= \sum_i \int_{\Delta_i} (q_\ep(x,z) - q_\ep(x,x_i)) \phi(z)~dz .$$
Then%
\bea{|\Phi|_\infty
\a\le |\phi|_\infty \cdot
\sup_x \sum_i \int_{\Delta_i} |q_\ep(x,z) - q_\ep(x_i,x)|~dz \\
\a\le |\phi|_\infty \cdot
\sup_x \sum_i \int_{\Delta_i}
\left(|q_\ep(x,z) - q_\ep(x,x_i)|
+ |q_\ep(x,x_i) - q_\ep(x_i,x)| \right)~dz \\
\a\le 2M \ep^{-d-1} \delta |\phi|_\infty ,}%
since $x,z\in\Delta_i$ and, hence,
$\max\{\rho(z,x_i),\rho(x,x_i)\}\le\delta$.
Let us estimate $H_\alpha(\Phi)$. If $\rho(x,y) \le \delta$ then%
\bea{|\Phi(x) - \Phi(y)|
\a\le |Q_\ep^* \phi(x) - Q_\ep^* \phi(y)|
+ |Q_{\ep,\delta}^* \phi(x) - Q_{\ep,\delta}^* \phi(y)| \\
\a\le \int|q_{\ep}(x,z) - q_{\ep}(y,z)|\cdot|\phi(z)|~dz
+ \sum_i |q_\ep(x,x_i) - q_\ep(y,x_i)| \int_{\Delta_i}|\phi| \\
\a\le M\ep^{-d-1}\rho(x,y)|\phi|_{\infty}
+ M\ep^{-d-1} \rho(x,y)\cdot|\phi|_\infty
= 2M\ep^{-d-1} \delta^{1-\alpha} \rho^\alpha(x,y)\cdot|\phi|_\infty .}%
Otherwise if $\rho(x,y) > \delta$ we apply another estimate
$$ |\Phi(x) - \Phi(y)| \le 2|\Phi|_\infty
\le 4M \ep^{-d-1} \delta |\phi|_\infty
\le 4M \ep^{-d-1} \rho^\alpha(x,y)\cdot \delta^{1-\alpha}
\cdot|\phi|_\infty .$$
Thus,
$$ H_\alpha(\Phi) \le 4M \ep^{-d-1} \delta^{1-\alpha}
\cdot|\phi|_\infty ,$$
and hence
$$ V_\alpha(\Phi) \le 5M \ep^{-d-1} \delta^{1-\alpha}
\cdot V_\alpha(\phi) ,$$
which yields the desired statement. \qed
\begin{theorem}\label{smooth-ulam-s} Let the family of kernels
$\{q_\ep(\cdot,\cdot)\}$ satisfies the conditions
(\ref{kernel-1}, \ref{kernel-2},\ref{kernel-4}). Then%
\bea{\na{Q_{\ep,\delta}}{\alpha}
\a\le 1 + M_1(\ep) + 5M \ep^{-d-1} \delta^{1-\alpha}, \\
|||Q_{\ep,\delta} - 1|||
\a\le (5M + 3 + M\ep^{1-\beta})
(\ep^{-d-1} \delta^{1-\alpha}
+ \ep^{\beta-\alpha}) \to 0
\quad {\rm as} \;
\ep^{-d-1} \delta^{1-\alpha} + \ep^{\beta-\alpha}\to0 .}%
Hence for the case $\La_\rmap(\alpha)<1/2$ the isolated
eigenvalues and the corresponding eigenprojectors of the operator
$\IP_\rmap$ are stable with respect to the considered
approximation.
\end{theorem}
\proof According to Lemmas \ref{l:Qep-alpha} and \ref{l:smooth-ulam-s}
$$ \na{Q_{\ep,\delta}}{\alpha}
\le \na{Q_{\ep}}{\alpha} + \na{Q_{\ep,\delta} - Q_{\ep}}{\alpha}
\le 1 + M_1(\ep) + 5M \ep^{-d-1} \delta^{1-\alpha} ,$$
which proves the first statement.
Similarly but using Lemma~\ref{l:3norm} instead of
Lemma~\ref{l:Qep-alpha}, we get%
\bea{V_\alpha(Q_{\ep,\delta}\phi - \phi)
\a\le V_\alpha(Q_{\ep,\delta}\phi - Q_{\ep}\phi)
+ V_\alpha(Q_{\ep}\phi - \phi) \\
\a\le \left(5M \ep^{-d-1} \delta^{1-\alpha}
+ (3 + M\ep^{1-\beta})\ep^{\beta-\alpha}\right)
\cdot V_\alpha(\phi) ,}%
which finishes the proof. \qed
In fact the finite dimensional approximation defined by the
two-parameter family of operators
$\{Q_{\ep,\delta}\}_{\ep,\delta}$ one can consider as a smoothed
version of the original Ulam construction, which corresponds to
the case $\ep=0$. Observe that in our approximations the relation
between the parameters is completely different -- it is necessary
that $\ep \gg \delta$.
We consider also another (seeming more natural) finite rank
approximation scheme. Denote by $\Pi_\delta$ the pure Ulam
approximation operator corresponding to the partition into
domains $\{\Delta_i\}$ whose diameters do not exceed $\delta$:
$$ \Pi_\delta f(x) := \frac1{|\Delta_x|} \int_{\Delta_x} f(s)~ds ,$$
where $\Delta_x$ stands for the element of the partition
containing the point $x$. Note that this operator is self
adjoint. We shall approximate our transfer operator $\IP_\rmap$
by $\Pi_\delta Q_\ep \IP_\rmap$. To study the properties of this
approximation we need as usual to analyze properties of the
adjoint operator, i.e. of the operator
$$ Q_\ep^* \Pi_\delta^* \phi(x)
= \int q_\ep(x,z) \frac1{|\Delta_z|} \int_{\Delta_x} \phi(s)~ds~dz .$$
\begin{lemma}\label{l:f-r-comp}
$\na{Q_\ep - \Pi_\delta Q_\ep}{\alpha}
\le (3+2M) \ep^{-d-1} \delta^{\alpha(1-\alpha)} \to 0$
as $\ep^{-d-1} \delta^{\alpha(1-\alpha)}\to0$.
\end{lemma}
\proof Denote%
\bea{\Phi(x) \a:= Q_\ep^*\phi(x) - Q_\ep^* \Pi_\delta^* \phi(x)
= \int q_\ep(x,z)
\left( \phi(z) - \frac1{|\Delta_z|}\int_{\Delta_x} \phi(s)~ds\right) ~dz \\
\a= \int q_\ep(x,z) \frac1{|\Delta_z|}
\int_{\Delta_x} (\phi(z) - \phi(s))~ds~dz .}%
Since $\phi\in\IC^\alpha$ and the diameter of the elements of the
partition does not exceed $\delta$, we have
$$ |\Phi|_\infty \le \delta^\alpha H_\alpha(\phi) \sup_x \int q_\ep(x,z)~dz
= \delta^\alpha H_\alpha(\phi) .$$
Now we are going to estimate the H\"older constant of the function $\Phi$.
which we shall do in two steps. First, we consider the case when
$\rho(x,y)\le\delta^\alpha$:%
\bea{|\Phi(x) - \Phi(y)|
\a\le |Q_\ep^*\phi(x) - Q_\ep^*\phi(y)|
+ |Q_\ep^* \Pi_\delta^* \phi(x) - Q_\ep^* \Pi_\delta^* \phi(y)| \\
\a\le \int |q_\ep(x,z) - q_\ep(y,z)|\cdot|\phi|_\infty~dz
+ \int |q_\ep(x,z) - q_\ep(y,z)|\cdot
\frac1{|\Delta_z|}\int_{\Delta_z}|\phi(s)|~ds~dz \\
\a\le 2M\ep^{-d-1}\rho(x,y) |\phi|_\infty
\le 2M\ep^{-d-1}\delta^{\alpha(1-\alpha)} |\phi|_\infty \rho^\alpha(x,y) .}%
In the opposite case, when $r(x,y)>\delta^\alpha$ we use a
different estimate:
$$ |\Phi(x) - \Phi(y)| \le 2|\Phi|_\infty
\le 2\delta^\alpha H_\alpha(\phi)
\le 2\delta^{\alpha(1-\alpha)}H_\alpha(\phi) \rho^\alpha(x,y) .$$
Thus %
\bea{V_\alpha(\Phi)
\a\le 2\delta^{\alpha(1-\alpha)} H_\alpha(\phi)
+ 2M \ep^{-d-1}\delta^{\alpha(1-\alpha)} |\phi|_\infty
+ \delta^\alpha H_\alpha(\phi) \\
\a\le 3\delta^{\alpha(1-\alpha)} H_\alpha(\phi)
+ 2M \ep^{-d-1}\delta^{\alpha(1-\alpha)} |\phi|_\infty
\le (3+2M) \ep^{-d-1}\delta^{\alpha(1-\alpha)} V_\alpha(\phi) \to 0 }%
as $\ep^{-d-1}\delta^{\alpha(1-\alpha)} \to 0$. \qed
Observe that the rate of convergence in this approximation is lower
compare to the previous one, however the numerical application of the
2nd scheme is more straitforward.
\begin{corollary} Again as in Theorem~\ref{c:drop} and due to the
same reason the assumption $\La_\rmap(\alpha)<1/2$ can be
replaced by either the bijectivity of the maps $\map_{i}$ or
the absence of its periodic turning points.
\end{corollary}
%%%%%%%%%
%\footnotesize
\small
\begin{thebibliography}{99} %\label{bibl}
\bibitem{Bl-mon} M. Blank,
{\em Stability and localization in chaotic dynamics}, MCCME, Moscow, 2001.
\bibitem{BK95} M. Blank, G. Keller, {\em Stochastic stability versus
localization in chaotic dynamical systems}, Nonlinearity
{\bf 10}:1 (1997), 81--107.
\bibitem{BK97} M. Blank, G. Keller, {\em Random perturbations of chaotic
dynamical systems: stability of the spectrum}, Nonlinearity {\bf 11}
(1998), 81-107.
\bibitem{BKL} M. Blank, G. Keller, C. Liverani,
{\em Ruelle-Perron-Frobenius spectrum for Anosov maps},
nlin.CD/0104031, (2001), 1-58.
\bibitem{Bro} F.E. Browder, {\em On the spectral theory of elliptic
differential operators I}, Math. An. {\bf 142} (1961), 22-130.
\bibitem{Buz} J. Buzzi, {\em Exponential decay of correlations for random
Lasota-Yorke maps}, Commun. Math. Phys. {\bf 208} (1999), 25-54.
\bibitem{dellnitz} M. Dellnitz, O. Junge, {\em On the approximation of
complicated dynamical behavior}, SIAM J. on Numerical Analysis
{\bf 36}:2 (1999), 491-515.
\bibitem{DS} N. Dunford, J.T. Schwartz, {\em Linear operators, Part 1:
General Theory}, Wiley, 1957.
\bibitem{Fal} K.J. Falkoner, {\em Fractal geometry}, John Wiley
and Sons, 1990.
\bibitem{FaLa} Ai Hua Fan, Ka-Sing Lau, {\em Iterated function
system and Ruelle operator}, preprint 1999.
\bibitem{Fro} G. Froyland, {\em Ulam's method for random interval
maps}, Nonlinearity {\bf 12}:4 (1999), 1029-1052.
\bibitem{Hen} H.Hennion, {\em Sur un Th\'eoreme spectral et son
application aux noyaux Lipchitziens}, Proc. of American
Mathematical Society {\bf 118}, 2, (1993), 627--634.
\bibitem{Hut} J.E. Hutchinson, {\em Fractals and self-similarity},
Indiana Univ. Math. J. 30(1981), 713-747.
\bibitem{ITM} C.T. Ionescu-Tulcea, G. Marinescu, {\em Theorie ergodique pour
des classes d'operators non complement continues}, Ann. of Math.
(2) {\bf 52}:1 (1950), 140-147.
\bibitem{KeLi} G. Keller, C. Liverani, {\em Stability of the Spectrum
for Transfer Operators}, Annali della Scuola Normale Superiore di
Pisa, Scienze Fisiche e Matematiche (4) 28 (1999), 141-152.
\bibitem{KhKi} K. Khanin, Yu. Kifer, {\em Thermodynamic formalism for
random transformations and statistical mechanics}, Sinai's Moscow seminar
on dynamical systems, AMS Translation, Series 2, {\bf 171}, AMS, Providence,
Rhode Island, 1996.
\bibitem{Kif} Yu. Kifer, {\em Ergodic theory of random transformations},
Birkhauser, Boston, 1986.
\bibitem{Ki4} Yu. Kifer, {\em Computations in dynamical systems via random
perturbations}, Discrete Contin. Dynam. Systems {\bf 3}:4 (1997),
457--476.
\bibitem{Mo} T. Morita, {\em Random iteration of one-dimensional
transformations}, Osaka J. Math. {\bf 22}:3 (1985), 489--518.
\bibitem{Nu} R.D. Nussbaum, {\em The radius of the essential spectrum},
Duke Math. J. {\bf 37}(1970), 473-478.
\bibitem{Pe1} S. Pelikan, {\em Invariant densities for random maps of the
interval}, Trans. Amer. Math. Soc. {\bf 281}:2 (1984), 813--825.
\bibitem{Ul} S. Ulam, {\em Problems in modern mathematics}, Interscience
Publishers, New York, 1960.
\end{thebibliography}
\end{document}
\E{\xi_{i}}$ there are constants $a<1,A<\infty$
such that
$$ \cP\{\frac1n \sum_{i=1}^{n}\xi_{i} > R\} < A a^{n} $$
for each positive $n$.
\end{lemma}
\proof By the exponential Chebyshev inequality
$$ \cP\{\frac1n\sum_{i=1}^{n}\xi_{i}>R\} \le e^{-sR} \E{e^{s\xi}} $$
for each positive number $s$. For our purpose it is enough to show
that the right hand side of this inequality decreases exponentially fast.
Note that for each number $x$ the following inequality holds
$$ |e^{x} - 1 - x| \le e^{|x|} - 1 - |x| .$$
Indeed, this is trivial for $x\ge0$ (since $e^x\ge+x$ and
$e^{-x}\le e^x$), while for $x<0$ we have $e^x\le+x$. Thus the
inequality can be reduced to
$$ -e^x + 1 + x \le e^{-x} -1 + x \qquad{\rm or}\qquad
e^{-x}+e^{x}\ge2 ,$$
which is evidently correct. Therefore
$$ |e^{s\xi} - 1 - s\xi| \le e^{|s\xi|} - 1 - |s\xi| .$$
Assume first, that the values $\xi_{i}$ are bounded from below. Then
$$ \E{e^{|s\xi|}} - 1 - \E{|s\xi|} < \infty $$
for $|s|