Source-linked AI summary
Exact Estimation for Markov Chain Equilibrium Expectations
Peter W. Glynn, Chang-han Rhee
TL;DR
Exact simulation methods typically require substantial structure, and a universal practical sampler is not available for Harris recurrent chains. This paper introduces exact estimation algorithms that construct unbiased equilibrium-expectation estimators. It presents algorithms for positive recurrent Harris chains and suitable contracting chains, arguing that this relaxes exact simulation’s requirements.
Problem
Exact simulation typically requires substantial Markov-chain structure, and no universal, practically implementable sampler is described for Harris recurrent chains.
Source: §1 · p. 1Method
Exact estimation couples successive chain approximations so their functional differences converge to zero, enabling unbiased equilibrium-expectation estimation.
Source: §2 · p. 3Results
The paper provides exact estimation algorithms for positive recurrent Harris chains and suitable non-φ-irreducible contracting chains, a significant relaxation relative to exact simulation.
Source: §1 · p. 2Takeaways & Limitations
For the Harris-chain construction, coupling makes the expected computation effort finite when Eτ<∞, regardless of the randomization distribution.
Source: §3 · p. 9The estimator may lack a square-root convergence rate if Z has infinite variance, though the Harris-chain construction has finite expected computation when Eτ<∞.
Source: §3 · p. 9
Abstract
from arXiv · showhide
We introduce a new class of Monte Carlo methods, which we call exact estimation algorithms. Such algorithms provide unbiased estimators for equilibrium expectations associated with real- valued functionals defined on a Markov chain. We provide easily implemented algorithms for the class of positive Harris recurrent Markov chains, and for chains that are contracting on average. We further argue that exact estimation in the Markov chain setting provides a significant theoretical relaxation relative to exact simulation methods.
1 Introduction
Perfect simulation produces exact equilibrium samples, but available methods require substantial structure and no universal, practically implementable sampler is described for Harris recurrent chains. The paper instead introduces exact estimation, targeting unbiased equilibrium-expectation estimators across broader chain classes.
1 Introduction
- Perfect simulation draws exact equilibrium samples from Markov-chain paths, but its construction typically requires substantial chain structure.The introduction notes no universal, practically implementable perfect sampler for Harris recurrent or countable-state positive recurrent chains.Source: §1 · pp. 1–2
- Exact estimation requires an unbiased equilibrium-expectation estimator rather than an exact sample from the equilibrium distribution.This relaxes the output demanded by exact simulation.Source: §1 · p. 2
- Exact estimation builds on Rhee and Glynn’s construction of unbiased estimators from sequences of biased approximations.The introduction also cites McLeish (2011) and Rhee and Glynn (2012) for related work.Source: §1 · p. 2
- The proposed algorithms cover positive recurrent Harris chains and non-φ-irreducible chains that are contractive in a suitable sense with suitably Lipschitz equilibrium functionals.The paper presents this scope as a significant relaxation of exact simulation.Source: §1 · p. 2
- Unlike most existing exact-simulation methods, these procedures need neither multiple initial conditions nor monotonicity and require little sample-path storage.The authors describe them as relatively straightforward to implement.Source: §1 · p. 2
2 Exact Estimation for Contracting Markov Chains
The section develops unbiased estimators of equilibrium expectations by randomizing coupled differences between successive approximations to a Markov-chain expectation. For chains contractive on average and Lipschitz functionals, suitable randomization yields finite-variance estimators and square-root convergence.
2 Exact Estimation for Contracting Markov Chains
- A coupling that makes successive differences converge to zero is key: the direct difference f(X_k) − f(X_{k−1}) need not converge to zero.The estimator randomizes over an approximation sequence whose increments have means equal to successive expectation differences.Source: §2 · p. 3
- For an average-contractive chain and Lipschitz f, the equilibrium distribution is unique and the estimator is unbiased when the approximation expectations converge geometrically.The assumptions include a complete separable metric state space and an iid random-function representation of the chain.Source: §2 · pp. 3–4
- Under the stated tail conditions, iid estimator averages converge at rate n^−1/2; the section also gives square-root convergence as computation time grows when estimator variance and expected randomization cost are finite.The randomization cost is measured by N, the number of random functions generated for an estimator.Source: §2 · pp. 4–5
- A second coupling yields another unbiased estimator, Z*, with the same square-root convergence guarantee under conditions (2.4)–(2.10).It is more complicated to implement and has a different variance from Z.Source: §2 · p. 6
- Exact estimation relaxes exact simulation's requirements: its algorithms need not explicitly simulate paths from multiple initial states, and can apply even to certain non-φ-irreducible chains.For exact simulation, the discussion identifies a priori knowledge of a qualifying state set as a requirement; without additional structure, φ-irreducibility is needed to guarantee it.Source: §2 · p. 7
3 Exact Estimation for Harris Recurrent Markov Chains
For positive recurrent Harris chains and bounded functionals, the section constructs an unbiased estimator of the equilibrium expectation using regeneration-based coupling. Under stronger moment conditions, it also establishes square-root convergence in computational effort.
3 Exact Estimation for Harris Recurrent Markov Chains
- The construction uses regeneration times for two chains and couples them when their regeneration schedules align, making later estimator increments zero.The two renewal processes are independent before their coupling time.Source: §3 · pp. 8–9
- For a positive recurrent Harris chain and bounded f, the estimator Z is unbiased for Ef(X∞).The periodic case is handled by applying the construction to the chain sampled every p steps.Source: §3 · p. 9
- Finite expected computation is automatic because Eτ is finite, but Z may lack finite variance and fail to achieve a square-root convergence rate.The number of simulated steps is bounded by 2 min(τ, N), regardless of N’s distribution.Source: §3 · p. 9
- Square-root convergence in computational effort is established when f is bounded and the inter-regeneration time has a finite rth moment for r > 2.The theorem’s conclusion concerns convergence in computational effort.Source: §3 · p. 10
- An alternative coupling preserves the chains’ marginal distributions and has a coupling time no later than the independent coupling, making it computationally preferable.Its coupling-time moments are no larger, so it can replace the original coupling in the square-root result.Source: §3 · p. 10
4 A Glivenko-Cantelli Result
The section extends the estimator to the equilibrium distribution function, whose indicator functional is not Lipschitz. It proves a Glivenko-Cantelli-type result for the resulting estimator in the positive recurrent Harris-chain setting.
4 A Glivenko-Cantelli Result
- Because the indicator functional is not Lipschitz, the section’s result focuses on positive recurrent Harris chains rather than applying Section 2’s theory.Source: §4 · p. 10
- The section proves a Glivenko-Cantelli-type theorem for the estimator of the equilibrium distribution function.The proof uses monotonicity of the sample functions in x.Source: §4 · pp. 11, 13
- For a positive recurrent Harris chain, Fn(x) is unbiased for F∞(x) at each x when P(N ≥ k) ∼ ck^-α for α > 0.Here F∞(x) is the equilibrium probability P(f(X∞) ≤ x).Source: §4 · pp. 10, 13
5 Numerical Results
The numerical examples report computational behavior for a contracting chain and confidence-interval behavior for a Harris-chain algorithm.
5 Numerical Results
- The contracting-chain example is non-φ-irreducible and has a uniform equilibrium distribution on [0, 2].For its listed functionals, the equilibrium expectations are 1 for f1, 3/4 for f2, and 4/3 for f3.Source: §5 · p. 13
- With heavier-tailed N, Z becomes more attractive: its computational effort grows linearly in N, versus quadratically for Z*.The comparison reflects the non-recursive computation of the Δi for Z*.Source: §5 · p. 13
- The Harris-chain implementation uses the waiting-time sequence of an M/M/1 queue with arrival rate 1/2 and unit service rate.Its equilibrium distribution is an equal-probability mixture of a point mass at 0 and an exponential distribution with rate 1/2.Source: §5 · p. 13
- With P(N ≥ k) = 1/k, λ = 1, and A = {0}, the Harris-chain results show the expected square-root decrease in confidence-interval width.The authors report these computations in Table 3.Source: §5 · p. 14