## Abstract

Let X be a finite space and let π be an underlying probability on X. For any real-valued function f defined on X, we are interested in calculating the expectation of f under π. Let X _{0},X _{1}, . . .,X _{n}, . . . be a Markov chain generated by some transition matrix P with invariant distribution p. The time average, 1/n σ ^{n-1} _{k=0} f(X _{k}), is a reasonable approximation to the expectation, Eπ[f(X)]. Which matrix P minimizes the asymptotic variance of 1/n σ ^{n-1} _{k=0} f(X _{k})? The answer depends on f. Rather than a worst-case analysis, we will identify the set of P's that minimize the average asymptotic variance, averaged with respect to a uniform distribution on f.

Original language | English (US) |
---|---|

Pages (from-to) | 2743-2762 |

Number of pages | 20 |

Journal | SIAM Journal on Control and Optimization |

Volume | 50 |

Issue number | 5 |

DOIs | |

State | Published - 2012 |

## Keywords

- Asymptotic variance
- Average-case analysis
- Markov chain
- Markov chain Monte Carlo
- Nonreversibility
- Rate of convergence
- Reversibility
- Worst-case analysis