Cole Campton

Projects Interests About
  • Iterative Graph Alignment
    Discussion of an interesting factorization and iterative algorithm for (relaxed) sub-graph isomorphism.

  • Image Deconvolution
    Discussion of the math behind denoising by directly inverting a regularized convolution objective.

  • The Perron-Frobenius Operator
    A project which demonstrates the power of numerical methods in approximating the long-term behavior of Ergodic mappings.

  • The Probabilistic Method
    A discussion and example of Paul Erdoős' Probabilistic Method.

  • Chronic Kidney Disease
    An overview of work at Emory University's Summer Institute in Biostatistics to predict development of Chronic Kidney Disease.

  • Coffee
    A compilation of some useful resouces and background information in coffee and brewing equiptment.

  • The Elektra Factory
    Photos from my tour of the Eletra factory in Treviso, Italy.

  • Climbing
    Photos from various climbing trips, including some with the Reed Mountaineering Club.

  • Budapest Semesters in Mathematics
    My experiences at the Budapest Semesters in Mathematics program.


    Hello my name is Cole Campton. I was born and raised in Mill Valley, California. I graduated from Reed College with a B.A. in mathematics. While at Reed I wrote a thesis on the homological equivalence of discrete configure space models used in motion planning.

    I currently work at Gilead Science's Clinical Bioinformatics and Exploratory Analytics group in Foster City, California.

    I am interested in computer science, mathematics, rock climbing, coffee and lever espresso machines.

    Feel free to contact me. Let’s talk computer science and coffee.

The Perron-Frobenius Operator


In the investigation of chaotic systems it is clear that hopes of predicting long term behavior is futile. However, from the investigation of chaotic systems Ergodic Theory has arisen in order to predict the average long term behavior of dynamic systems. It is our intent to investigate the theoretical results of a main result of Ergodic Theory, namely that of Birkhoff’s Ergodic Theorem.


An Ergodic Endomorphism or measure preserving map is a map \(T: X\rightarrow X\) where for measure \(\mu\) it is the case that \(T\) satisfies

  1. \(T\) is surjective
  2. \(T\) is measureable
  3. \(\mu(T^{-1}A)=\mu(A)\) for all \(A\) in the sigma algebra on \(X\), for preimage \(T^{-1}(A)\).

Birhoff’s Ergodic Theorem

Let \(T\) be an ergodic endomorphism of the probability space \(X\) with measure \(\mu\) and let \(f:X\rightarrow \mathbb{R}\) be a real-valued measurable function. Then for almost every \(x \in X\), we have \(\lim_{n\rightarrow \infty} \frac{1}{n}\sum_{j=0}^{n}{f\circ T^j(x)} = \int_{X} f d\mu\)

A simple measureable function is the characteristic function \(f\) of some subset \(A\subset X\).

\[f(x)=\begin{cases} 1 & \text{ if }x\in A \\ 0 & \text{ if }x\not\in A \end{cases}\]

The statement of Birkhoff’s Theorem is that for almost all initial points, the time-wise average converges to the space-wise average. More precisely that is for all but a set of measure zero initial points \(x_0\), the average value over the ‘time evolution’ orbit of the point \(x_0\), given by \(\{T^j(x_0)\}\), is given by the invariant distribution \(\mu\).

Logistic Maps

The family of logistic maps are maps, for some value \(r\in [0,4]\) are given by

\[T:[0,1] \rightarrow [0,1]\] \[T(x) = r\cdot x (1-x)\]

These functions simulate the effects of reproduction for small populations and starvation at a population’s carrying capacity. The logistic map for \(r=4\) is a well know ergodic endomorphism.

We define time evolutions of an initial point \(x_0\) at time \(t\) by \(X_{t+1} = T(X_t)\) A graph of the evolution of the logistic map for \(r=4\) can be seen below.

We may observer the chaotic behavior of the logistic map by selecting a random initial point \(X_0\) in the domain, and a second random point initial point \(X_0^{'}\) within some \(\epsilon=10^{-8}\) of \(X_0\).

We see that within 100 time iterations, the values of the two points have dispersed.

The residues of the points shows the dispersion of the points.

In the long term iterations of the map orbit the co-domain fast enough to fill the plot.

Calculating Invariant Distribution

The value of first investigating the logistic map is that it has an invariant distribution with may be calculated analytically, which leads into general methods for finding such a distribution.

Consider \(\mathbb{P}(X_{t+1}\le x)\), the cumulative distribution of the logistic map. \(\begin{align*} \mathbb{P}(X_{t+1}\le x) &= \mathbb{P}(X_{t+1}\in[0,x])= \mathbb{P}(X_{t}\in F^{-1}([0,x]))\\ &=\mathbb{P}(X_{t}\in [0,\frac{1}{2}(1-\sqrt{1-x})]\cup\frac{1}{2}([1+\sqrt{1-x},1])))\\ &=\int_0^{\frac{1}{2}(1-\sqrt{1-x})}\rho_t(y) dy+\int_{\frac{1}{2}(1+\sqrt{1-x})}^1\rho_t(y) dy \end{align*}\)

Where \(\rho_t\) is the distribution of \(X_t\), this yields that \(\int_0^x \rho_{t+1}(y)dy =\int_0^{\frac{1}{2}(1-\sqrt{1-x})} \rho_t(y) dy+ \int_{\frac{1}{2}(1+\sqrt{1-x})}^1 \rho_t (y) dy\)

In general this sort expression may be difficult or impossible to solve. The logistic map however, yields to the following method by differentiating both sides of the previous expression. \(\begin{align*} \rho_{t+1} &= \frac{d}{dx} \int_0^{\frac{1}{2}(1-\sqrt{1-x})} \rho_t(y) dy+ \frac{d}{dx}\int_{\frac{1}{2}(1+\sqrt{1-x})}^1 \rho_t (y) dy \\ &= \rho_t (\frac{1}{2}(1-\sqrt{1-x})) \frac{d}{dx}( \frac{1}{2}(1-\sqrt{1-x}))-\rho_t (\frac{1}{2}(1+\sqrt{1-x})) \frac{d}{dx}( \frac{1}{2}(1+\sqrt{1-x}))\\ &= \frac{1}{4\sqrt{1-x}} (\rho_t(\frac{1}{2}(1-\sqrt{1-x}))+ \rho_t(\frac{1}{2}(1+\sqrt{1-x}))) \end{align*}\) First note that the previous display is an expression between distributions under iterations of the map. This expression is solvable and we may verify that \(\rho(x)=\frac{1}{\pi\sqrt{x(1-x)}}\) is the unique solution. We see that

\(\begin{align*} \rho(\frac{1}{2}(1-\sqrt{1-x})) &= \frac{1}{pi}( \frac{1}{2}(1+\sqrt{1-x})(1-\frac{1}{2}(1+\sqrt{1-x})))^{-1/2}\\ &= \frac{1}{\pi}( \frac{1}{2}(1-\sqrt{1-x})\frac{1}{2}(1+\sqrt{1-x}))^{-1/2} = \frac{2}{\pi\sqrt{x}} \end{align*}\) Then by noting that \(\rho(x)=\rho(1-x)\) it follows that

\[\rho_{t+1} = \frac{1}{4\sqrt{1-x}} (\rho_t(\frac{1}{2}(1-\sqrt{1-x}))+ \rho_t(\frac{1}{2}(1+\sqrt{1-x}))) = \frac{1}{\pi\sqrt{x(1-x)}}=\rho_t\]

Comparing Time and Invariant Distribution

We may then plot the histogram produced by selecting a random initial position and evaluating the function over a period of several steps. Below we sample a random point in \([0,1]\) for 1 million steps then by breaking the domain into one thousand intervals we may approximate a histogram giving the distribution of the logistic function with respect to time. For comparison we plot our analytic invariant space solution.

The Perron-Frobenius Operator

The recurrent expression obtained in evaluating the invariant distribution of the Logistic map is a type of linear operator called a Perron-Frobenius Operator. These operators describe the time evolution of mappings in phase space defined such that for Perron-Frobenius operator \(P\), where the invariant distribtution satisfies

\[\rho_{t+1} = P\rho_{t} \quad \rho = P \rho\]

A description of the Perron-Frobenius operator is given explicitly as

\[P \rho(y) = \sum_{x\in T^{-1}(y)} \frac{\rho(x)}{|T^{'}(x)|}\]

We note that this is exactly the form of the expression we obtained in evaluating the invariant distribution of the Logistic map.

In their paper Klaus, Koltai, Sch{"u}tte \cite{PFO} give a numerical method adapted from Ulam’s Monte Carlo method. Ulam’s method is a projection from the Perron-Frobenius operator’s Banach space to a subspace spanned by indicator functions, of the type given as example in the introduction of the Birkhoff Ergodic Theorem. For simplicity we may simply split the codomain into \(N\) small intervals \(\mathbb{B}_i = [\frac{i}{N},\frac{i+1}{N}]\)

\[\mathbb{I}_{\mathbb{B}_i}(x)=\begin{cases} 1 & x\in \mathbb{B}_i \\ 0 & x\not\in \mathbb{B}_i \end{cases}\]

Then the Perron-Frobenius operator is given by

\[P=(p_{ij})\in \mathbb{R}^{k \times k}\] \[p_{ij} = \frac{\mu(T^{-1}(\mathbb{B}_j)\cap \mathbb{B}_i)}{\mu(\mathbb{B}_i)}\]

For example

\[P_{\text{SOM}}=\small{\begin{pmatrix} 0 & 0.572 & 0.428 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0.394 & 0.606 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0.306 & 0.694 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0.697 & 0.303 \\ 0 & 0 & 0 & 0 & 0 & 0.189 & 0.213 & 0.598 \\ 0.202 & 0.204 & 0.195 & 0.2 & 0.199 & 0 & 0 & 0\end{pmatrix}}\]

The normalization of this discrete operator makes it the row-stochastic operator for a finite Markov chain.

This view of the operator allows us to approximate the matrix \((p_{ij})\) by sampling points in some interval \(\mathbb{B}_i\) and approximating the probability that a point will move into each interval \(\mathbb{B}_j\). So for \(L\) test points, and \(x_i^l\in \mathbb{B}_i\) \(p_{ij}\approx \frac{1}{L} \sum^L_{l=1}\mathbb{I}_{\mathbb{B}_j}(T(x_i^l))\)

Then since \(\mu(T^{-1}(\mathbb{B}_j)\cap \mathbb{B}_i)= \int \mathbb{I}_{\mathbb{B}_j}\cdot P \mathbb{I}_{\mathbb{B}_i} d\mu\) is evaluated by the previous integral, this evaluation of each \(p_{ij}\) is a Monte-Carlo approximation.

Then finally for the matrix \(P=(p_{ij})\), we may evaluate the invariant distribution \(P\rho = \rho\) as the eigenvector giving the discrete distribution, for eigenvalue \(\lambda=1\).

The Shobu-Ose-Mori Map

The Shobu-Ose-Mori map allows for a demonstration of the power of the discretization of the Perron-Frobenius operator. These maps are defined as There is no analytic solution to the invariant distribution of these maps.

We see a fantastic display of the Birkhoff Ergodic Theorem as the time orbit of a point, whose histogram is shown below in blue, approximates the Perron-Frobenius numerical approximation of the invariant distribution, shown below in red.

Let \(\alpha =0.7\), \(\beta =0.2\), \(\gamma=0.8/(1+\alpha)\).

\[f(x)=\begin{cases} \alpha x +0.2 & 0\le x\le \gamma \\ \alpha^{-1}(x-0.8)+1 & \gamma\le x \le 0.8 \\ -\beta^{-1} (x-1) & 0.8 \le x\le 1 \end{cases}\]