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:
- The samples produced are distributed exactly according to the stationary distribution of the underlying Markov chain.
- 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