Displaying similar documents to “Explicit error bounds for Markov chain Monte Carlo”

Directed forests with application to algorithms related to Markov chains

Piotr Pokarowski (1999)

Applicationes Mathematicae

Similarity:

This paper is devoted to computational problems related to Markov chains (MC) on a finite state space. We present formulas and bounds for characteristics of MCs using directed forest expansions given by the Matrix Tree Theorem. These results are applied to analysis of direct methods for solving systems of linear equations, aggregation algorithms for nearly completely decomposable MCs and the Markov chain Monte Carlo procedures.

Two algorithms based on Markov chains and their application to recognition of protein coding genes in prokaryotic genomes

Małgorzata Grabińska, Paweł Błażej, Paweł Mackiewicz (2013)

Applicationes Mathematicae

Similarity:

Methods based on the theory of Markov chains are most commonly used in the recognition of protein coding sequences. However, they require big learning sets to fill up all elements in transition probability matrices describing dependence between nucleotides in the analyzed sequences. Moreover, gene prediction is strongly influenced by the nucleotide bias measured by e.g. G+C content. In this paper we compare two methods: (i) the classical GeneMark algorithm, which uses a three-periodic...

Computing upper bounds on Friedrichs’ constant

Vejchodský, Tomáš

Similarity:

This contribution shows how to compute upper bounds of the optimal constant in Friedrichs’ and similar inequalities. The approach is based on the method of a p r i o r i - a p o s t e r i o r i i n e q u a l i t i e s [9]. However, this method requires trial and test functions with continuous second derivatives. We show how to avoid this requirement and how to compute the bounds on Friedrichs’ constant using standard finite element methods. This approach is quite general and allows variable coefficients and mixed boundary conditions. We use the...

On the spectral analysis of second-order Markov chains

Persi Diaconis, Laurent Miclo (2013)

Annales de la faculté des sciences de Toulouse Mathématiques

Similarity:

Second order Markov chains which are trajectorially reversible are considered. Contrary to the reversibility notion for usual Markov chains, no symmetry property can be deduced for the corresponding transition operators. Nevertheless and even if they are not diagonalizable in general, we study some features of their spectral decompositions and in particular the behavior of the spectral gap under appropriate perturbations is investigated. Our quantitative and qualitative results confirm...

Why the Kemeny Time is a constant

Karl Gustafson, Jeffrey J. Hunter (2016)

Special Matrices

Similarity:

We present a new fundamental intuition forwhy the Kemeny feature of a Markov chain is a constant. This new perspective has interesting further implications.

The Kendall theorem and its application to the geometric ergodicity of Markov chains

Witold Bednorz (2013)

Applicationes Mathematicae

Similarity:

We give an improved quantitative version of the Kendall theorem. The Kendall theorem states that under mild conditions imposed on a probability distribution on the positive integers (i.e. a probability sequence) one can prove convergence of its renewal sequence. Due to the well-known property (the first entrance last exit decomposition) such results are of interest in the stability theory of time-homogeneous Markov chains. In particular this approach may be used to measure rates of convergence...