On the iterations of some random functions with Lipschitz number one

Yingdong Lu, Tomasz NowickiarXiv 2024 · DOI · arXiv

Abstract

For the iterations of $x \mapsto |x - \theta|$ random functions with Lipschitz number one, we represent the dynamics as a Markov chain and prove its convergence under mild conditions. We demonstrate that the Wasserstein metric of any two measures does not increase after the corresponding induced iterations and identify conditions for polynomial convergence. Furthermore, we analyze an associated nonlinear operator on the space of probability measures, identifying its fixed points through a detailed analysis of their characteristic functions.

Introduction

In the field of Iterated Function Systems (IFS), the behavior of systems under repeated application of random functions is a central topic. While systems composed of contractions—functions that reduce the distance between points—typically converge to a unique stable distribution, the map $f(x) = |x - \theta|$ presents a unique challenge. As a "Lipschitz one" function, it preserves or reflects distances rather than contracting them. This paper addresses the long-standing questions regarding the conditions for convergence and the rate at which this system reaches a steady state.

Methodology

The study employs a rigorous mathematical framework combining several disciplines:

  • Markov Chain Theory: The iterative process is modeled as a Markov chain. By applying the Foster-Lyapunov Theorem and Harris recurrence, the authors establish that the system eventually reaches a unique invariant probability distribution, independent of the starting state.
  • Dynamical Systems and Ergodic Theory: The iterations are linked to rotations on a circle. Using Kronecker’s Theorem, the research determines the topological properties of the system's trajectory, specifically whether it is dense within an interval or confined to a discrete lattice.
  • Optimal Transport: The analysis utilizes the Wasserstein metric ($W_p$) to measure the distance between probability distributions. The authors prove that the random map acts as a non-expansive operator in this metric space.
  • Complex Analysis: To solve the nonlinear problem of identifying "self-serving" distributions (where the distribution of $\theta$ matches the invariant distribution it induces), the authors utilize probability generating functions and identify them as linear transformations of finite Blaschke products.

Key Insights

The Rotation Connection

A fundamental insight is the interpretation of the map $|x - \theta|$ as a rescaled rotation. The nature of the system's support—whether it fills an interval or remains on a grid—depends on the rationality of the ratios between different values of $\theta$.

Wasserstein Contraction and Convergence Rates

While the individual map is not a contraction, the operator it induces on the space of probability measures exhibits contractive properties in the Wasserstein sense. The authors introduce the $(A, B, C)$-condition, a regularity requirement on the reference measure. When satisfied, this condition guarantees a polynomial convergence rate of $n^{-\alpha}$, providing a quantitative measure of how quickly the system stabilizes.

Key Results

The paper establishes several landmark results regarding the stability and convergence of these random iterations:

  1. Existence and Uniqueness: Under mild regularity assumptions, the Markov chain possesses a unique invariant probability measure.
  2. Strict Metric Contraction: If the support of $\theta$ is the entire positive real line, the Wasserstein distance between any two measures strictly decreases with each iteration.
  3. Fixed Point Identification: The authors successfully identified specific fixed points for the nonlinear operator. In the continuous case, the exponential distribution is a fixed point, while geometric-like distributions serve as fixed points in the discrete case.
Numerical illustration of the fixed point analysis for the nonlinear operator across different parameter regimes.

The figure above illustrates the behavior of functions related to the fixed point analysis. The intersections of the curves and lines represent the equilibrium states of the system under different parameter settings, confirming the theoretical predictions regarding invariant measures.

Conclusion and Future Work

This research provides a comprehensive understanding of the dynamics of random absolute difference maps. However, several avenues for future work remain. It is yet to be determined if the identified Blaschke-product-based solutions are exhaustive. Additionally, the basins of attraction for the nonlinear operator and the potential existence of higher-order Blaschke products as valid probability distributions remain open questions for the mathematical community.

Summary updated

Abstract

For the iterations of $x\mapsto |x-θ|$ random functions with Lipschitz number one, we represent the dynamics as a Markov chain and prove its convergence under mild conditions. We also demonstrate that the Wasserstein metric of any two measures will not increase after the corresponding induced iterations for measures and identify conditions under which a polynomial convergence rate can be achieved in this metric. We also consider an associated nonlinear operator on the space of probability measures and identify its fixed points through an detailed analysis of their characteristic functions.
BibTeX
@misc{lu2024iterations,
  author = {Yingdong Lu and Tomasz Nowicki},
  title = {{On the iterations of some random functions with Lipschitz number one}},
  year = {2024},
  eprint = {2409.06003},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2409.06003},
}
Figure