Iterated Piecewise-Stationary Random Functions

Ramen Ghosh, Jakub Marecek, Robert ShortenarXiv 2019 · OpenReview

TL;DR

This paper introduces "iterated piecewise-stationary random functions," a new framework for modeling dynamical systems where the underlying probabilistic rules change over time. This work extends existing models by allowing the distribution used to sample functions to vary, providing a more realistic approach for systems with evolving agent behavior and offering theoretical guarantees on tracking error and convergence.

What Problem Does This Paper Address?

Many real-world systems, from smart cities to economic models, involve ensembles of agents whose behavior is probabilistic and can change over time. Traditional "iterated random functions" (IRFs) model these systems by sampling functions from a fixed probability distribution. However, this assumption is often unrealistic, as factors like changing prices, agent preferences, or system dynamics can cause the underlying probability distribution to shift. The challenge is to develop a theoretical framework that can handle these time-varying probabilistic behaviors and still provide guarantees about the system's long-term behavior and its ability to track desired states.

Methods

The core contribution is the introduction of iterated piecewise-stationary random functions (IPSRFs). This framework extends standard IRFs by allowing the probability distribution used to sample functions from a finite family of Lipschitz maps to change over time. The authors define this new class of systems and then develop the mathematical tools to analyze them. Key techniques include:

  • Generalizing to Polish Spaces: The framework is developed for Polish spaces (complete, separable metric spaces), which are more general than the compact metric spaces often assumed in prior work.
  • Piecewise-Invariant Measures: They define and establish criteria for the existence and uniqueness of "piecewise-invariant measures," which are the time-varying equivalent of invariant measures in stationary systems.
  • Markov Operators and Contraction: The analysis relies on defining Markov operators associated with the time-varying probability distributions and proving contraction properties in Wasserstein-type metrics. This is crucial for establishing convergence.
  • Tracking Error and Regret Bounds: The paper derives theoretical bounds for the "tracking error" (how closely the system's state measure follows a target measure) and "regret" (the difference between the system's performance and the best possible performance).

Datasets

Not discussed in the paper. The paper focuses on theoretical development and uses a computational illustration with a generated dataset based on fractal transformations.

Key Insights and Ideas

  • Modeling Evolving Probabilities is Crucial: The paper highlights that many real-world systems exhibit time-varying probabilistic dynamics, and existing models often fall short by assuming stationarity. IPSRFs offer a more flexible and realistic modeling approach.
  • Piecewise-Invariant Measures as the New Ergodic Property: Just as invariant measures characterize the long-term behavior of stationary systems, piecewise-invariant measures are introduced to capture the ergodic properties of these time-varying systems.
  • Contraction is Key for Convergence: The authors leverage the concept of contraction in Wasserstein-type metrics to prove that the system's state measure converges to an invariant measure, even when the underlying sampling probabilities change.
  • Quantifying Performance: The derivation of tracking error and regret bounds provides concrete theoretical guarantees on how well the system can adapt to changing dynamics and how efficiently it can achieve desired outcomes.

Key Results

  • Existence and Uniqueness of Piecewise-Invariant Measures: The paper establishes conditions for the existence and uniqueness of piecewise-invariant measures for IPSRFs in Polish spaces.
  • Bounds on Distance Between Invariant Measures: A theoretical bound is derived for the distance between invariant measures corresponding to consecutive probability distributions, showing how the system adapts to changes.
  • Tracking Error Bound: A bound is provided for the tracking error, quantifying how well the system's state measure can follow a target measure under time-varying dynamics.
  • Regret Bound: A (rudimentary) bound on the regret is established, indicating the difference between the system's performance and the optimal performance.
  • Computational Illustration: The paper includes simulations using a fractal example, visually demonstrating the existence of piecewise-invariant measures and the decay of distances between measures, supporting the theoretical findings.

Limitations and Future Work

  • Rudimentary Regret Bound: The authors acknowledge that the derived regret bound is "only rudimentary and can be improved upon."
  • Future Work: The paper suggests several avenues for future research, including:
  • Improving the regret bound.
  • Investigating the effect of interconnecting multiple ergodic populations.
  • Dealing with more complex time-varying resource-allocation problems.
  • Exploring the preservation of ergodicity under feedback mechanisms.

Summary updated

Abstract

Within the study of uncertain dynamical systems, iterated random functions are a key tool. There, one samples a family of functions according to a stationary distribution. Here, we introduce an extension, where one sample functions according to a time-varying distribution over the family of functions. For such iterated piecewise-stationary random functions on Polish spaces, we prove a number of results, including a bound on the tracking error.
BibTeX
@misc{ghosh2019iterated,
  author = {Ramen Ghosh and Jakub Marecek and Robert Shorten},
  title = {{Iterated Piecewise-Stationary Random Functions}},
  year = {2019},
  eprint = {1909.10093},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1909.10093},
}
Figure