A Mathematical Proofs & Theoretical Bounds

In this appendix, we detail the rigorous mathematical proofs for several key limit theorems and algorithm convergence properties used throughout the notes.

A.1 Glivenko-Cantelli Theorem

Let \(X_1, X_2, \dots\) be independent and identically distributed random variables with cumulative distribution function \(F(x)\). Let \(\hat{F}_n(x)\) be the empirical distribution function defined as: \[\hat{F}_n(x) = \frac{1}{n} \sum_{i=1}^n I(X_i \le x)\] Theorem: The empirical distribution function \(\hat{F}_n(x)\) converges uniformly to \(F(x)\) almost surely: \[\sup_{x \in \mathbb{R}} |\hat{F}_n(x) - F(x)| \xrightarrow{a.s.} 0 \quad \text{as } n \to \infty\]

Proof:
1. For a fixed \(x\), the indicator variables \(I(X_i \le x)\) are independent Bernoulli random variables with success probability \(p = F(x)\). By the Strong Law of Large Numbers (SLLN), the sample mean \(\hat{F}_n(x)\) converges almost surely to its expectation \(F(x)\): \[\hat{F}_n(x) \xrightarrow{a.s.} F(x)\]
2. To prove uniform convergence, we partition the real line. For any partition points \(-\infty = x_0 < x_1 < \dots < x_k = \infty\) such that \(F(x_j) - F(x_{j-1}) < \epsilon\), we can bound the difference on each subinterval.
3. Since \(\hat{F}_n\) and \(F\) are monotonically non-decreasing, for any \(x \in [x_{j-1}, x_j]\): \[\hat{F}_n(x) - F(x) \le \hat{F}_n(x_j) - F(x_{j-1}) = \hat{F}_n(x_j) - F(x_j) + F(x_j) - F(x_{j-1}) < \hat{F}_n(x_j) - F(x_j) + \epsilon\] Similarly: \[\hat{F}_n(x) - F(x) \ge \hat{F}_n(x_{j-1}) - F(x_{j-1}) - \epsilon\]
4. Taking the supremum over all subintervals, we establish that: \[\sup_{x} |\hat{F}_n(x) - F(x)| \le \max_{j} |\hat{F}_n(x_j) - F(x_j)| + \epsilon\]
5. Since the maximum is taken over a finite number of points \(k\), by the SLLN the first term on the right-hand side converges to 0 almost surely. Thus: \[\limsup_{n \to \infty} \sup_x |\hat{F}_n(x) - F(x)| \le \epsilon \quad \text{a.s.}\] Since \(\epsilon > 0\) is arbitrary, the uniform convergence follows. \(\blacksquare\)

A.2 Strong Law of Large Numbers (SLLN) for MC Integration

Let \(X_1, X_2, \dots\) be independent and identically distributed random variables with \(E[|X_i|] < \infty\). Let \(\mu = E[X_i]\). Theorem: The sample mean \(\bar{X}_n = \frac{1}{n} \sum_{i=1}^n X_i\) converges almost surely to \(\mu\): \[P\left(\lim_{n \to \infty} \bar{X}_n = \mu\right) = 1\]

Proof (under finite fourth moment \(E[X^4] < \infty\)):
1. Without loss of generality, assume \(\mu = 0\). Consider the fourth moment of the sum \(S_n = \sum_{i=1}^n X_i\): \[E[S_n^4] = E\left[\left(\sum_{i=1}^n X_i\right)^4\right]\]
2. Expanding the sum, terms like \(E[X_i^3 X_j]\), \(E[X_i^2 X_j X_k]\), and \(E[X_i X_j X_k X_l]\) vanish because the variables are independent and have mean 0. The only non-zero terms are: \[E[S_n^4] = n E[X_i^4] + 3n(n-1) E[X_i^2]^2 \le C n^2\] for some positive constant \(C\).
3. Therefore, the expectation of the fourth power of the sample mean is: \[E\left[\bar{X}_n^4\right] = \frac{E[S_n^4]}{n^4} \le \frac{C n^2}{n^4} = \frac{C}{n^2}\]
4. For any \(\epsilon > 0\), by Markov’s inequality: \[P(|\bar{X}_n| \ge \epsilon) = P(\bar{X}_n^4 \ge \epsilon^4) \le \frac{E[\bar{X}_n^4]}{\epsilon^4} \le \frac{C}{\epsilon^4 n^2}\]
5. Summing the probabilities over all \(n\): \[\sum_{n=1}^\infty P(|\bar{X}_n| \ge \epsilon) \le \frac{C}{\epsilon^4} \sum_{n=1}^\infty \frac{1}{n^2} < \infty\]
6. By the Borel-Cantelli Lemma, the event \(\{|\bar{X}_n| \ge \epsilon\}\) occurs infinitely often with probability 0. Thus, \(\bar{X}_n \xrightarrow{a.s.} 0\). \(\blacksquare\)

A.3 Monotonicity & Coupling in Propp-Wilson CFTP

In the Propp-Wilson Coupling from the Past (CFTP) algorithm:

Coupling Bound: Let \(\mathcal{S}\) be a state space with a partial ordering \(\le\) having a unique maximum state \(\hat{1}\) and a unique minimum state \(\hat{0}\).
Theorem: If the transition map \(\phi(x, u)\) is monotonic (i.e., \(x \le y \implies \phi(x, u) \le \phi(y, u)\) for all \(u\)), then for any state \(z \in \mathcal{S}\): \[\phi(\hat{0}, \mathbf{u}_{-T:0}) \le \phi(z, \mathbf{u}_{-T:0}) \le \phi(\hat{1}, \mathbf{u}_{-T:0})\]
Proof: By the induction on the chain transitions: Since \(\hat{0} \le z \le \hat{1}\) by definition of the extreme elements: \[\phi(\hat{0}, u_{-T}) \le \phi(z, u_{-T}) \le \phi(\hat{1}, u_{-T})\] Applying the transition map recursively for subsequent steps \(t = -T+1, \dots, 0\): \[\phi(\hat{0}, \mathbf{u}_{-T:0}) \le \phi(z, \mathbf{u}_{-T:0}) \le \phi(\hat{1}, \mathbf{u}_{-T:0})\] When the maximum and minimum chains coalesce: \[\phi(\hat{0}, \mathbf{u}_{-T:0}) = \phi(\hat{1}, \mathbf{u}_{-T:0}) = X^*\] it forces the intermediate chain state \(\phi(z, \mathbf{u}_{-T:0})\) to equal \(X^*\). Thus, all chains starting from any state at time \(-T\) converge to the exact same state at time 0. \(\blacksquare\)

A.4 Expected Score Function is Zero

In sensitivity analysis and maximum likelihood estimation, the score function is defined as \(S(X; \theta) = \nabla_\theta \log f(X; \theta)\).

Theorem: Under regular differentiability conditions that allow exchanging the derivative and integral, the expected value of the score function is always zero: \[E_\theta\left[ \nabla_\theta \log f(X; \theta) \right] = 0\]

Proof:
1. Write as Integral: \[E_\theta\left[ \nabla_\theta \log f(X; \theta) \right] = \int \left( \nabla_\theta \log f(x; \theta) \right) f(x; \theta) \, dx\]
2. Expand Logarithmic Derivative: Using the identity \(\nabla_\theta \log f(x; \theta) = \frac{\nabla_\theta f(x; \theta)}{f(x; \theta)}\), we substitute: \[\int \left( \frac{\nabla_\theta f(x; \theta)}{f(x; \theta)} \right) f(x; \theta) \, dx = \int \nabla_\theta f(x; \theta) \, dx\]
3. Exchange Derivative and Integral: Assuming the regulatory conditions hold: \[\int \nabla_\theta f(x; \theta) \, dx = \nabla_\theta \int f(x; \theta) \, dx\]
4. Evaluate Total Probability Integral: Since \(f(x; \theta)\) is a valid probability density function, its integral over all space is exactly 1: \[\int f(x; \theta) \, dx = 1 \implies \nabla_\theta \int f(x; \theta) \, dx = \nabla_\theta (1) = 0\] This completes the proof. \(\blacksquare\)

A.5 Optimal Proposal in Importance Sampling

To estimate \(\ell = E[h(X)] = \int h(x)f(x)\,dx\), the Importance Sampling estimator is \(\hat{\ell}_{\text{IS}} = \frac{1}{N}\sum_{i=1}^N \frac{h(X_i)f(X_i)}{g(X_i)}\) where \(X_i \sim g(x)\).

Theorem: The proposal density \(g^*(x)\) that minimizes the variance of the estimator \(\hat{\ell}_{\text{IS}}\) is: \[g^*(x) = \frac{|h(x)|f(x)}{\int |h(y)|f(y)\,dy}\]

Proof:
1. Express Variance: \[\text{Var}_g(\hat{\ell}_{\text{IS}}) = \frac{1}{N}\left( E_g\left[\frac{h(X)^2 f(X)^2}{g(X)^2}\right] - \ell^2 \right)\] To minimize this variance, we only need to minimize the second moment: \[E_g\left[\frac{h(X)^2 f(X)^2}{g(X)^2}\right] = \int \frac{h(x)^2 f(x)^2}{g(x)^2} g(x) \, dx = \int \frac{h(x)^2 f(x)^2}{g(x)} \, dx\]
2. Apply Cauchy-Schwarz: Let \(u(x) = \frac{|h(x)|f(x)}{\sqrt{g(x)}}\) and \(v(x) = \sqrt{g(x)}\). Then: \[\left( \int u(x)v(x) \, dx \right)^2 \le \left( \int u(x)^2 \, dx \right) \left( \int v(x)^2 \, dx \right)\] \[\left( \int |h(x)|f(x) \, dx \right)^2 \le \left( \int \frac{h(x)^2 f(x)^2}{g(x)} \, dx \right) \left( \int g(x) \, dx \right)\] Since \(\int g(x) \, dx = 1\): \[\int \frac{h(x)^2 f(x)^2}{g(x)} \, dx \ge \left( \int |h(x)|f(x) \, dx \right)^2\]
3. Find Equality Condition: Equality holds if and only if \(u(x) / v(x) = C\) (some constant): \[\frac{|h(x)|f(x)}{g(x)} = C \implies g^*(x) \propto |h(x)|f(x)\] Integrating to find the normalizing constant yields the theorem. \(\blacksquare\)

A.6 Metropolis-Hastings Detailed Balance (Continuous Case)

Theorem: The Metropolis-Hastings kernel satisfies detailed balance for continuous densities.

Proof: Let the target distribution have continuous density \(\pi(x)\) and proposal transition density be \(q(x, y)\). The transition probability density from \(x\) to \(y\) (for \(x \ne y\)) is: \[P(x, y) = q(x, y) \alpha(x, y)\] where \(\alpha(x, y) = \min\left(1, \frac{\pi(y)q(y,x)}{\pi(x)q(x,y)}\right)\). We want to show: \[\pi(x) P(x, y) = \pi(y) P(y, x)\] Without loss of generality, assume \(\pi(x)q(x,y) \le \pi(y)q(y,x)\).
- Left Hand Side: Since the ratio is \(\ge 1\), we have \(\alpha(x, y) = 1\). Thus: \[\pi(x) P(x, y) = \pi(x) q(x, y) \times 1 = \pi(x)q(x,y)\]
- Right Hand Side: Since the inverse ratio is \(\le 1\), we have \(\alpha(y, x) = \frac{\pi(x)q(x,y)}{\pi(y)q(y,x)}\). Thus: \[\pi(y) P(y, x) = \pi(y) q(y, x) \times \frac{\pi(x)q(x,y)}{\pi(y)q(y,x)} = \pi(x)q(x,y)\] Since both sides are exactly equal, detailed balance is satisfied. \(\blacksquare\)