Wir beweisen explizite, d.h., nicht-asymptotische Fehlerabschätzungen für Markov-Ketten-Monte-Carlo-Methoden. Ziel ist es, den Erwartungswert einer Funktion f bzgl. eines Maßes π zu berechnen. Verschiedene Konvergenzeigenschaften von Markov-Ketten implizieren verschiedene Fehlerabschätzungen. Für gleichmäßig ergodische und reversible Markov-Ketten beweisen wir eine untere und eine obere Fehlerschranke bzgl. der L2-Norm von f. Wenn eine L2-Spektrallücke existiert, die eine schwächere Konvergenzeigenschaft als die gleichmäßige Ergodizität darstellt, dann zeigen wir eine obere Fehlerschranke bzgl. der Lp-Norm für p>2. Das so genannte Aufwärmen ist ein gebräuchliches Mittel um den Algorithmus abzustimmen. Wir schlagen ein Rezept für die Wahl der Aufärmzeit vor und begründen dieses ausführlich. Die Fehlerabschätzungen werden anschließend auf das Problem der Integration bzgl. einer nicht normierten Dichte angewendet. Genauer gesagt betrachten wir die Integration bzgl. log-konkaver Dichtefunktionen und die Integration über konvexe Körper. Durch die Verwendung des Metropolis-Algorithmus und des Hit-and-run-Algorithmus zeigen wir, dass diese beiden Probleme "polynomial tractable" sind.
We prove explicit, i.e. non-asymptotic, error bounds for Markov chain Monte Carlo methods. The problem is to compute the expectation of a function f with respect to a measure π. Different convergence properties of Markov chains imply different error bounds. For uniformly ergodic and reversible Markov chains we prove a lower and an upper error bound with respect to the L2-norm of f. If there exists an L2-spectral gap, which is a weaker convergence property than uniform ergodicity, then we show an upper error bound with respect to the Lp-norm of f for p > 2. Usually a burn-in period is an efficient way to tune the algorithm. We provide and justify a recipe how to choose the burn-in period. The error bounds are applied to the problem of the integration with respect to a possibly unnormalized density. More precise, we consider the integration with respect to log-concave densities and the integration over convex bodies. By the use of the Metropolis algorithm based on a ball walk and the hit-and-run algorithm it is shown that both problems are polynomial tractable.