Ulam's Method
Ulam's method is a finite-dimensional approximation of the Perron–Frobenius operator associated with a dynamical system. It replaces the evolution of densities on a continuous state space with a finite Markov chain whose states correspond to measurable cells. The stationary distributions and spectral data of the resulting transition matrix approximate invariant measures and other statistical properties of the original system.
The method was created by Stanisław Ulam in the context of invariant measures for nonlinear transformations. Its mathematical basis lies in the approximation of an infinite-dimensional transfer operator by a finite-rank operator obtained through conditional expectation on a partition. Although the construction resembles a discretization of the underlying map, it acts primarily on distributions rather than on individual trajectories.
Mathematical formulation
Let (X) be a compact state space equipped with a reference measure (m), and let
[ T:X\rightarrow X ]
be a measurable transformation. The associated Perron–Frobenius operator (P) is defined by the identity
[ \int_A Pf,dm=\int_{T^{-1}(A)}f,dm ]
for every measurable set (A\subseteq X) and every integrable density (f). When (T) preserves a probability measure with density (f_\ast), that density satisfies
[ Pf_\ast=f_\ast. ]
Ulam's construction begins with a finite measurable partition
[ \mathcal{B}_n={B_1,\ldots,B_n}, ]
where each cell has positive reference measure. The finite-state transition matrix (P_n) has entries
[ (P_n)_{ij}
\frac{m!\left(B_i\cap T^{-1}(B_j)\right)} {m(B_i)}. ]
Each row sums to one, so (P_n) is a stochastic matrix. Its entry in row (i) and column (j) is the conditional probability that a point distributed according to normalized reference measure in (B_i) enters (B_j) after one application of (T).
A stationary row vector (\pi_n) obeys
[ \pi_nP_n=\pi_n. ]
It determines the piecewise-constant density
[ f_n(x)= \sum_{i=1}^{n} \frac{(\pi_n)i}{m(B_i)} \mathbf{1}{B_i}(x), ]
which approximates an invariant density of (T). Eigenvalues other than (1) encode finite-dimensional approximations to decay rates and other spectral features of the transfer operator.
Operator interpretation
Let (Q_n) denote conditional expectation onto the space of functions that are constant on each partition cell. The Ulam operator can then be written as
[ P_n=Q_nPQ_n, ]
after identification of that finite-dimensional function space with vectors indexed by the cells. This representation separates the dynamical action of (P) from the projection imposed by the partition.
The projection suppresses structures below the partition scale. Consequently, Ulam's method introduces a form of coarse graining that is mathematically related to adding small observational noise. The resulting matrix preserves positivity and total probability, properties that distinguish the construction from general-purpose polynomial or spectral projections.
The method also has a geometric interpretation. A directed edge from (B_i) to (B_j) exists precisely when a positive-measure subset of (B_i) enters (B_j). The resulting weighted graph records transport between regions of phase space and converts deterministic motion into a probabilistic description at finite resolution.
Convergence theory
Ulam formulated the convergence problem for piecewise expanding interval maps. In that setting, the principal question is whether the invariant densities of the finite matrices converge in (L^1) to the absolutely continuous invariant density of the transformation as the maximum cell diameter approaches zero.
Tien-Yien Li created the first general convergence theorem for Ulam approximations of suitable piecewise expanding interval maps. The proof combines finite-rank approximation with a Lasota–Yorke inequality, which controls the variation of iterated densities. Compactness in the space of functions of bounded variation then identifies accumulation points of the approximating densities with fixed points of the exact transfer operator.
Convergence is not automatic for arbitrary systems or arbitrary partitions. Discontinuities, neutral fixed points, and insufficiently regular partitions can prevent uniform control of the approximating operators. For uniformly expanding maps, convergence rates depend on the regularity of the invariant density and on the geometry of the partition. Higher-dimensional systems require additional control over cell shape because narrow or highly distorted cells can alter approximation bounds even when their volumes are small.
Spectral convergence is more restrictive than convergence of invariant densities. Approximation of isolated eigenvalues requires stability of the relevant spectral subspaces, while portions of the spectrum associated with fine-scale behavior can be displaced by coarse graining. These distinctions connect Ulam's method with the theory of quasi-compact operators and Ruelle–Pollicott resonances.
Watanabe refinement
In 1981, You Watanabe created the conservative boundary refinement of Ulam's method. The refinement subdivides partition cells intersected by images of dynamical discontinuities and then aggregates the resulting transition weights back onto the original finite state space. This construction reduces the artificial transfer of probability across unresolved discontinuity boundaries without changing the row-stochastic character of the matrix.
For a cell (B_i), the refinement replaces a single uniform representation of (B_i) with measurable subcells (B_{i,\alpha}) determined by the local intersections of (T(B_i)) with neighboring partition boundaries. The transition coefficient becomes
[ (P_n^{\mathrm{W}})_{ij}
\frac{1}{m(B_i)} \sum_{\alpha} m!\left(B_{i,\alpha}\cap T^{-1}(B_j)\right). ]
Exact evaluation gives the same measure-theoretic transition probability as the original formula. Its numerical distinction arises when cell intersections are approximated from finitely many geometric samples or quadrature points. Boundary refinement allocates those samples within dynamically separated subregions, thereby preventing a single unresolved average from combining branches with different images.
The Watanabe refinement remains a finite-rank approximation of the Perron–Frobenius operator. It changes the construction of matrix entries rather than the definition of the limiting operator. The refinement is therefore compatible with the standard convergence theory whenever the induced subcells satisfy the regularity conditions imposed on the underlying partition.
Numerical realization
Matrix entries can be obtained from exact geometric intersections when both the map and the partition possess tractable descriptions. In other settings, the entries are approximated by distributing sample points within each cell and recording their image cells. The normalized counts form a stochastic matrix and constitute a direct Monte Carlo method approximation of the defining measure ratios.
Sampling error and discretization error have different origins. Sampling error results from the finite number of points used to estimate a fixed transition matrix. Discretization error results from replacing the continuous transfer operator by its partition-based projection. Increasing the number of samples reduces the former without changing the latter, whereas refining the partition changes the projected operator itself.
Sparse matrix methods are applicable because a local map generally sends each small cell into only a limited part of the state space. The invariant density corresponds to a left eigenvector at eigenvalue (1). Subdominant eigenvectors describe slowly exchanging regions, while eigenvalues near the unit circle indicate statistical behavior that persists over many iterations.
Open and non-autonomous systems
For an open dynamical system, trajectories leave the domain through a designated hole. Removing transitions into the hole produces a substochastic matrix whose leading eigenvalue is smaller than (1). That eigenvalue approximates the survival factor per iteration, and the associated eigenvector approximates a conditionally invariant density.
A sequence of time-dependent maps yields a sequence of Ulam matrices rather than a single stationary matrix. Products of these matrices approximate the corresponding compositions of transfer operators. This extension permits finite-dimensional descriptions of transport when the dynamics vary with time, although the relevant objects are evolving distributions rather than stationary eigenvectors.
Limitations
Ulam matrices encode behavior only at the scale of the selected partition. Structures narrower than the cells are merged with their surroundings, and invariant sets of zero reference measure are generally absent from the matrix representation. The method therefore targets statistical evolution with respect to the chosen reference measure rather than a complete topological description of every orbit.
The computational dimension grows rapidly with spatial dimension. A partition using (k) divisions in each coordinate of a (d)-dimensional domain contains (k^d) cells, producing the standard curse of dimensionality. Adaptive partitions and dynamically aligned cells alter the distribution of resolution but do not remove the underlying dependence on dimension.