On exact sampling of stochastic perpetuities

José Blanchet, Karl SigmanJournal of Applied Probability 2011 · DOI

Abstract: A stochastic perpetuity takes the form $D_\infty = \sum_{n=0}^\infty \exp(Y_1 + \dots + Y_n) B_n$, where $(Y_n : n \ge 0)$ and $(B_n : n \ge 0)$ are two independent sequences of independent and identically distributed random variables (RVs). This represents the stationary distribution of the Markov chain defined recursively by $D_{n+1} = A_n D_n + B_n$, where $A_n = e^{Y_n}$. $D_\infty$ satisfies the stochastic fixed-point equation $D_\infty \stackrel{\mathcal{D}}{=} AD_\infty + B$, where $A$ and $B$ are independent copies of $A_n$ and $B_n$. In this framework, the random reward $B_n$ is assumed to be positive and unbounded with $E[B_n^p] < \infty$ for some $p > 0$, possessing a suitably regular continuous positive density. The discount rate $Y_n$ is assumed to be light-tailed. We provide an exact simulation algorithm for generating samples of $D_\infty$ using a variation of dominated coupling from the past (DCFTP) involving a sequence of dominating processes.

Introduction

Stochastic perpetuities are fundamental in various fields, including pension fund dynamics, insurance risk theory (e.g., calculating ruin probabilities), and time-series modeling like ARCH(1) models. In economic terms, a perpetuity represents the Net Present Value (NPV) of an infinite stream of random rewards ($B_n$) discounted by random rates ($Y_n$).

The primary challenge in simulating these structures is their infinite nature. Standard approaches rely on truncation, which introduces a bias. This paper, published in New Frontiers in Applied Probability, introduces a novel algorithm for the exact sampling of these perpetuities, allowing researchers to generate samples that follow the target distribution perfectly without truncation error.

Problem Formulation

The perpetuity $D_\infty$ is defined as the infinite sum: $$D_\infty = \sum_{n=0}^\infty \exp(Y_1 + \dots + Y_n)B_n$$ It satisfies the stochastic fixed-point equation: $$D_\infty \stackrel{\mathcal{D}}{=} AD_\infty + B$$ where $A$ and $B$ are independent copies of $A_n$ and $B_n$, and independent of $D_\infty$ on the right-hand side. The rewards $B_n$ are assumed to be positive and unbounded with finite moments $E[B_n^p] < \infty$ for some $p > 0$, while the discount factors $Y_n$ are light-tailed.

Methodology: Dominated Coupling From The Past (DCFTP)

The authors develop a "perfect simulation" algorithm based on DCFTP. The core concept of Coupling From The Past (CFTP) is to start simulations further back in time until all possible starting states coalesce into a single value by time zero.

Technical Innovations

  • Minorization Condition: The authors employ a "splitting" technique on the density of the reward variable $B$. This allows them to force paths to coalesce with a certain probability, a necessary condition for the algorithm to terminate in continuous state spaces.
  • Sequence of Dominating Processes: Standard DCFTP typically requires a stationary dominating Markov chain. This work relaxes that constraint, showing that a sequence of upper bounds, which can be sampled jointly, is sufficient.
  • Importance Sampling for Random Walks: To manage the "tail" of the infinite sum, the algorithm simulates the maximum of a random walk with negative drift. Importance sampling (specifically a change of measure) is used to ensure this maximum is computable in finite time.
  • Lyapunov Functions: Foster-Lyapunov criteria are used to rigorously prove that the algorithm terminates in finite time with probability 1.

Key Insights

  • Broad Applicability: Unlike previous exact sampling methods restricted to "Vervaat perpetuities" (where $B=1$), this approach works for cases where $B$ has a continuous density and potentially heavy tails (e.g., Pareto or Gamma distributions).
  • Monotonicity: The recursion $D_{n+1} = A_n D_n + B_n$ is monotone in $D$. The authors exploit this to "sandwich" the true process between zero and their constructed dominating process.
  • Coalescence Detection: By using the minorization of the reward distribution, the algorithm can detect when all possible paths have merged into one without tracking every individual path.

Results

The paper provides a step-by-step exact simulation algorithm and proves that:

  1. The samples produced are distributed exactly according to the stationary distribution of the underlying Markov chain.
  2. The expected running time of the algorithm is finite, provided the discount rates have a negative mean (ensuring convergence) and the rewards have finite moments of some order $p > 0$.

Limitations and Future Work

While the algorithm is a significant step forward, some limitations remain:

  • Tail Constraints: The method is optimized for distributions that decay at most exponentially; "super-exponential" (extremely thin) tails are not currently supported.
  • Closed-Form Requirements: The algorithm assumes the tail distribution of the rewards $B$ is available in closed form.
  • Positivity: The current framework assumes rewards $B_n$ are positive. While extensions to negative rewards are suggested, they are not fully developed in this paper.
  • Computational Efficiency: Detailed complexity analysis and wall-clock time comparisons against high-precision truncation methods are left for future empirical studies.

Summary updated

Abstract

A stochastic perpetuity takes the form D ∞=∑ n =0 ∞ exp( Y 1 +⋯+ Y n ) B n , where Y n : n ≥0) and ( B n : n ≥0) are two independent sequences of independent and identically distributed random variables (RVs). This is an expression for the stationary distribution of the Markov chain defined recursively by D n +1 = A n D n + B n , n ≥0, where A n =e Y n ; D ∞ then satisfies the stochastic fixed-point equation D ∞ D̳ AD ∞ + B , where A and B are independent copies of the A n and B n (and independent of D ∞ on the right-hand side). In our framework, the quantity B n , which represents a random reward at time n , is assumed to be positive, unbounded with E B n p &lt;∞ for some p &gt;0, and have a suitably regular continuous positive density. The quantity Y n is assumed to be light tailed and represents a discount rate from time n to n -1. The RV D ∞ then represents the net present value, in a stochastic economic environment, of an infinite stream of stochastic rewards. We provide an exact simulation algorithm for generating samples of D ∞ . Our method is a variation of dominated coupling from the past and it involves constructing a sequence of dominating processes.
BibTeX
@article{blanchet2011exact,
  author = {José Blanchet and Karl Sigman},
  title = {{On exact sampling of stochastic perpetuities}},
  journal = {Journal of Applied Probability},
  year = {2011},
  doi = {10.1239/jap/1318940463},
}
Figure