abstract:
Let the function $f$ be given and $\pi$ be a probability measure.
The goal is to compute the integral of $f$ with respect to $\pi$, such that
\[
S(f)=\int_D f(y) \pi(dy)
\]
is the desired quantity.
A straight generation of $\pi$ is in general not possible.
Thus, it is reasonable to compute the average over a Markov chain $(X_n)_{n\in \N}$ after a burn-in $n_0$.
Hence
\begin{equation*} \label{sum}
S_{n,n_0}(f):=\frac{1}{n} \sum_{i=1}^n f(X_{i+n_0})
\end{equation*}
is the suggested approximation of $S(f)$.
Suppose that the Markov chain fulfills some convergence conditions,
for instance has an absolute $L_2$-spectral gap $1-\beta>0$.
Furthermore assume that the initial distribution $\nu$ of the Markov chain
has a density with respect to $\pi$.
Then it holds
\[
\text{err}(S_{n,n_0},f)^2 \leq
\frac{4 \norm{f}{\infty}^2}{n(1-\beta)}
\quad \text{where} \quad
n_0 = \left\lceil \frac{\log(32 \norm{\frac{d \nu}{ d \pi}-1}{2})}{1-\beta} \right\rceil.
\]
The bound is generalized to integrands which belong to $L_p$ where $p\in[2,\infty]$. |