Perron-Frobenius Operator

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}

Screen Shot 2014-11-08 at 9.55.51 am

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}

Screen Shot 2014-11-08 at 9.56.12 am

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}

Screen Shot 2014-11-08 at 9.56.31 am

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}

Screen Shot 2014-11-08 at 9.56.38 am

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};

(c) there exists r>0 such that |f(I_{i})|\geq r for each i.

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.

If for every i and j one has f^{n}(I_{j})\supseteq I_{i} for some n\geq 1 then

(b) the measure is unique and its density \frac{d\mu}{d\lambda} is strictly positive;

(c) f is exact with respect to \mu;

(d) \lim_{n\rightarrow \infty} |f^{-n}(A)|=\mu(A) for every Borel set A\subseteq N.

If f(I_{i})=N for each interval I_{i}, then

(e) the density of \mu is also uniformly bounded from below.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s