Perron-Frobenius Operator

Consider a map $f$ which possibly has a finite (or countable) number of discontinuities or points where possibly the derivative does not exist. We assume that there are points

$\displaystyle q_{0}<q_{1}<\cdot\cdot\cdot <q_{k}$ or $q_{0}<q_{1}<\cdot\cdot\cdot<q_{\infty}<\infty$

such that $f$ restricted to each open interval $A_{j}=(q_{j-1},q_{j})$ is $C^{2}$ , with a bound on the first and the second derivatives. Assume that the interval $[q_{0},q_{k}]$ ( or $[q_{0},q_{\infty}]$ ) is positive invariant, so $f(x)\in [q_{0},q_{k}]$ for all $x\in [q_{0}, q_{k}]$ ( or $f(x)\in [q_{0},q_{\infty}]$ for all $x\in[q_{0},q_{\infty}]$ ).

For such a map, we want a construction of a sequence of density functions that converge to a density function of an invariant measure. Starting with $\rho_{0}(x)\equiv(q_{k}-q_{0})^{-1}$ ( or $\rho_{0}(x)\equiv(q_{\infty}-q_{0})^{-1}$ ),assume that we have defined densities up to $\rho_{n}(x)$ , then define define $\rho_{n+1}(x)$ as follows

$\displaystyle \rho_{n+1}(x)=P(\rho_{n})(x)=\sum_{y\in f^{-1}(x)}\frac{\rho_{n}(y)}{|Df(y)|}.$

This operator $P$ , which takes one density function to another function, is called the Perron-Frobenius operator. The limit of the first $n$ density functions converges to a density function $\rho^{*}(x)$ ,

$\displaystyle \rho^{*}(x)=\lim_{k\rightarrow \infty}\frac{1}{k}\sum_{n=0}^{k-1}\rho_{n}(x).$

The construction guarantees that $\rho^{*}(x)$ is the density function for an invariant measure $\mu_{\rho^{*}}$ .

Example 1. Let

$\displaystyle f(x)= \begin{cases} x &\mbox{if } x\in(0,\frac{1}{2}), \\ 2x &\mbox{if } x\in(\frac{1}{2},1). \end{cases}$

We construct the first few density functions by applying the Perron-Frobenius operator, which indicates the form of the invariant density function.
Take $\rho_{0}(x)\equiv1$ on $[0,1]$ . From the definition of $f(x)$ , the slope on $(0,\frac{1}{2})$ and $(\frac{1}{2},1)$ are 1 and 2, respectively. If $x\in (\frac{1}{2},1)$ , then it has only one pre-image on $(\frac{1}{2},1)$ ; else if $x\in(0,\frac{1}{2})$ , then it has two pre-images, one is $x^{'}$ in $(0,\frac{1}{2})$ , the other one is $x^{''}$ in $(\frac{1}{2},1)$ . Therefore,

$\rho_{1}(x)= \begin{cases} \frac{1}{1}+\frac{1}{2} &\mbox{if } x\in(0,\frac{1}{2}), \\ \frac{1}{2} &\mbox{if } x\in(\frac{1}{2},1). \end{cases}$

By similar considerations,

$\displaystyle \rho_{2}(x)=\begin{cases}1+\frac{1}{2}+\frac{1}{2^{2}} &\mbox{if } x\in(0,\frac{1}{2}), \\ \frac{1}{2^{2}} &\mbox{if } x\in(\frac{1}{2},1).\end{cases}$

By induction, we get

$\displaystyle \rho_{n}(x)=\begin{cases}1+\frac{1}{2}+\cdot\cdot\cdot+\frac{1}{2^{n}} &\mbox{if } x\in(0,\frac{1}{2}), \\ \frac{1}{2^{n}} &\mbox{if } x\in(\frac{1}{2},1).\end{cases}$

Now, we begin to calculate the density function $\rho^{*}(x)$ . If $x\in(0,\frac{1}{2})$ , then
$\displaystyle \rho^{*}(x)=\lim_{k\rightarrow \infty}\frac{1}{k}\sum_{n=0}^{k-1}\rho_{n}(x) =\lim_{k\rightarrow \infty}\frac{1}{k}\sum_{n=0}^{k-1} \sum_{m=0}^{n}\frac{1}{2^{m}} =\lim_{k\rightarrow \infty}\frac{1}{k}\sum_{n=0}^{k-1}\left(2-\frac{1}{2^{n}}\right)=2.$
If $x\in(\frac{1}{2},1)$ , then
$\displaystyle \rho^{*}(x)=\lim_{k\rightarrow \infty}\frac{1}{k}\sum_{n=0}^{k-1}\rho_{n}(x) =\lim_{k\rightarrow \infty}\frac{1}{k}\sum_{n=0}^{k-1}\frac{1}{2^{n}} =\lim_{k\rightarrow \infty}\frac{1}{k}\left(2-\frac{1}{2^{k}}\right)=0.$
i.e.

$\displaystyle \rho^{*}(x)= \begin{cases} 2 &\mbox{if } x\in(0,\frac{1}{2}), \\ 0 &\mbox{if } x\in(\frac{1}{2},1). \end{cases}$

Example 2. Let

$\displaystyle f(x)=\begin{cases} 2x &\mbox{if } x\in(0,\frac{1}{2}), \\ 2x-1 &\mbox{if } x\in(\frac{1}{2},1). \end{cases}$

Take $\rho_{0}(x)\equiv1$ on $(0,1)$ . By induction, $\rho_{n}(x)\equiv1$ on $(0,1)$ for all $n\geq 0$ . Therefore, $\rho^{*}(x)\equiv1$ on $(0,1)$ .

Example 3. Let

$\displaystyle f(x)=\begin{cases} x &\mbox{if } x\in(0,\frac{1}{2}), \\ 2^{n+1}\cdot\left(x-\left(1-\frac{1}{2^{n}}\right)\right) &\mbox{if } x\in\left(1-\frac{1}{2^{n}},1-\frac{1}{2^{n+1}}\right) \text{ for all } n\geq 1.\end{cases}$

Take $\rho_{0}(x)\equiv1$ on $(0,1)$ . Assume

$\displaystyle \rho_{n}(x)= \begin{cases} a_{n} &\mbox{if } x\in(0,\frac{1}{2}), \\ b_{n} &\mbox{if } x\in(\frac{1}{2},1). \end{cases}$

for all $n\geq 0$ . It is obviously that $a_{0}=b_{0}=1$ . By similar considerations,
$\displaystyle \rho_{n+1}(x)= \begin{cases} \frac{a_{n}}{1}+\frac{b_{n}}{4}+\frac{b_{n}}{8}+\frac{b_{n}}{16}+\cdot\cdot\cdot= a_{n}+\frac{b_{n}}{2} &\mbox{if } x\in(0,\frac{1}{2}), \\ \frac{b_{n}}{4}+\frac{b_{n}}{8}+\frac{b_{n}}{16}+\cdot\cdot\cdot = \frac{b_{n}}{2} &\mbox{if } x\in(\frac{1}{2},1). \end{cases}$
That means

$\displaystyle \left( \begin{array}{ccc} a_{n+1} \\ b_{n+1} \end{array} \right) =\left( \begin{array}{ccc} a_{n}+\frac{1}{2}b_{n} \\ \frac{1}{2}b_{n} \end{array} \right) = \left( \begin{array}{ccc} 1 & \frac{1}{2} \\ 0 & 1 \end{array} \right) \left( \begin{array}{ccc} a_{n} \\ b_{n} \end{array} \right)$

for all $n\geq 0$ . From direct calculation, $\displaystyle a_{n}=2-\frac{1}{2^{n}}$ and $\displaystyle b_{n}=\frac{1}{2^{n}}$ for all $n\geq 0$ . Therefore,

$\displaystyle \rho^{*}(x)=\lim_{k\rightarrow \infty}\frac{1}{k}\sum_{n=0}^{k-1}\rho_{n}(x)=\begin{cases} 2 &\mbox{if } x\in (0,\frac{1}{2}), \\ 0 &\mbox{if } x\in (\frac{1}{2},1). \end{cases}$

Example 4. Let

$\displaystyle f(x)=\begin{cases} 1.5 x &\mbox{if } x\in(0,\frac{1}{2}), \\ 2^{n+1}\cdot\left(x-\left(1-\frac{1}{2^{n}}\right)\right) &\mbox{if } x\in\left(1-\frac{1}{2^{n}},1-\frac{1}{2^{n+1}}\right) \text{ for all } n\geq 1.\end{cases}$

Take $\rho_{0}(x)\equiv1$ on $(0,1)$ . Assume

$\displaystyle \rho_{n}(x)= \begin{cases} a_{n} &\mbox{if } x\in(0,\frac{3}{4}), \\ b_{n} &\mbox{if } x\in(\frac{3}{4},1). \end{cases}$

for all $n\geq 0$ . It is obviously that $a_{0}=b_{0}=1$ . By similar considerations,

$\displaystyle \left( \begin{array}{ccc} a_{n+1} \\ b_{n+1} \end{array} \right) =\left( \begin{array}{ccc} \frac{11}{12}a_{n}+\frac{1}{4}b_{n} \\ \frac{1}{4}a_{n}+\frac{1}{4}b_{n} \end{array} \right) = \left( \begin{array}{ccc} \frac{11}{12} & \frac{1}{4} \\ \frac{1}{4} & \frac{1}{4} \end{array} \right) \left( \begin{array}{ccc} a_{n} \\ b_{n} \end{array} \right)$

for all $n\geq 0$ . From matrix diagonalization , $\displaystyle a_{n}=\frac{6}{5}-\frac{1}{5}\cdot\frac{1}{6^{n}}$ and $\displaystyle b_{n}=\frac{2}{5}+\frac{3}{5}\cdot\frac{1}{6^{n}}$ for all $n\geq 0$ .

Therefore,

$\displaystyle \rho^{*}(x)=\lim_{k\rightarrow \infty}\frac{1}{k}\sum_{n=0}^{k-1}\rho_{n}(x)=\begin{cases} \frac{6}{5} &\mbox{if } x\in (0,\frac{3}{4}), \\ \frac{2}{5} &\mbox{if } x\in (\frac{3}{4},1). \end{cases}$

Perron-Frobenius Theory

Definition. Let $A=[a_{ij}]$ be a $k\times k$ matrix. We say $A$ is non-negative if $a_{ij}\geq 0$ for all $i,j$ . Such a matrix is called irreducible if for any pair $i,j$ there exists some $n>0$ such that $a_{ij}^{(n)}>0$ where $a_{ij}^{(n)}$ is the $(i,j)-$ th element of $A^{n}$ . The matrix $A$ is irreducible and aperiodic if there exists $n>0$ such that $a_{ij}^{(n)}>0$ for all $i,j$ .

Perron-Frobenius Theorem Let $A=[a_{ij}]$ be a non-negative $k\times k$ matrix.

(i) There is a non-negative eigenvalue $\lambda$ such that no eigenvalue of $A$ has absolute value greater than $\lambda$ .

(ii) We have $\min_{i}(\sum_{j=1}^{k}a_{ij})\leq \lambda\leq \max_{i}(\sum_{j=1}^{k}a_{ij})$ .

(iii) Corresponding to the eigenvalue $\lambda$ there is a non-negative left (row) eigenvector $u=(u_{1},\cdot\cdot\cdot, u_{k})$ and a non-negative right (column) eigenvector $v=(v_{1},\cdot\cdot\cdot, v_{k})^{T}$ .

(iv) If $A$ is irreducible then $\lambda$ is a simple eigenvalue and the corresponding eigenvectors are strictly positive (i.e. $u_{i}>0$ , $v_{i}>0$ all $i$ ).

(v) If $A$ is irreducible then $\lambda$ is the only eigenvalue of $A$ with a non-negative eigenvector.

Theorem.
Let $A$ be an irreducible and aperiodic non-negative matrix. Let $u=(u_{1},\cdot\cdot\cdot, u_{k})$ and $v=(v_{1},\cdot\cdot\cdot, v_{k})^{T}$ be the strictly positive eigenvectors corresponding to the largest eigenvalue $\lambda$ as in the previous theorem. Then for each pair $i,j$ , $\lim_{n\rightarrow \infty} \lambda^{-n}a_{ij}^{(n)}=u_{j}v_{i}$ .

Now, let us see previous examples, again. The matrix $A$ is irreducible and aperiodic non-negative matrix, and $\lambda=1$ has the largest absolute value in the set of all eigenvalues of $A$ . From Perron-Frobenius Theorem, $u_{i}, v_{j}>0$ for all pairs $i,j$ . Then for each pari $i,j$ ,
$\lim_{n\rightarrow \infty}a_{ij}^{(n)}=u_{j}v_{i}$ . That means $\lim_{n\rightarrow \infty}A^{(n)}$ is a strictly positive $k\times k$ matrix.

Markov Maps

Definition of Markov Maps. Let $N$ be a compact interval. A $C^{1}$ map $f:N\rightarrow N$ is called Markov if there exists a finite or countable family $I_{i}$ of disjoint open intervals in $N$ such that

(a) $N\setminus \cup_{i}I_{i}$ has Lebesgue measure zero and there exist $C>0$ and $\gamma>0$ such that for each $n\in \mathbb{N}$ and each interval $I$ such that $f^{j}(I)$ is contained in one of the intervals $I_{i}$ for each $j=0,1,...,n$ one has

$\displaystyle \left| \frac{Df^{n}(x)}{Df^{n}(y)}-1 \right| \leq C\cdot |f^{n}(x)-f^{n}(y)|^{\gamma} \text{ for all } x,y\in I;$

(b) if $f(I_{k})\cap I_{j}\neq \emptyset$ , then $f(I_{k})\supseteq I_{j}$ ;

As usual, let $\lambda$ be the Lebesgue measure on $N$ . We may assume that $\lambda$ is a probability measure, i.e., $\lambda(N)=1$ . Usually, we will denote the Lebesgue measure of a Borel set $A$ by $|A|$ .

Theorem. Let $f:N\rightarrow N$ be a Markov map and let $\cup_{i}I_{i}$ be corresponding partition. Then there exists a $f-$ invariant probability measure $\mu$ on the Borel sets of $N$ which is absolutely continuous with respect to the Lebesgue measure $\lambda$ . This measure satisfies the following properties:

(a) its density $\frac{d\mu}{d\lambda}$ is uniformly bounded and Holder continuous. Moreover, for each $i$ the density is either zero on $I_{i}$ or uniformly bounded away from zero.