✦ LIBER ✦

On the conductance of order Markov chains

✍ Scribed by Alexander Karzanov; Leonid Khachiyan

Publisher: Springer Netherlands
Year: 1991
Tongue: English
Weight: 425 KB
Volume: 8
Category: Article
ISSN: 0167-8094
DOI: 10.1007/bf00385809

No coin nor oath required. For personal study only.

✦ Synopsis

Let Q be a convex solid in R", partitioned mto two volumes u and t' by an area s. We show that s > min(u, o)/diam Q, and use this inequality to obtain the lower bound n -'/' on the conductance of order Markov chains, which describe nearly uniform generators of linear extensions for posets of size n. We also discuss an applicatron of the above results to the problem of sorting of posets.

📜 SIMILAR VOLUMES

Markov approximations of chains of infin

Markov approximations of chains of infinite order

✍ R. Fernández; A. Galves 📂 Article 📅 2002 🏛 Springer 🌐 English ⚖ 86 KB

On model order estimation for partially

On model order estimation for partially observed Markov chains

✍ R.G. Whiting; E.E. Pickett 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 406 KB

On the First-Order Edgeworth Expansion f

On the First-Order Edgeworth Expansion for a Markov Chain

✍ S. Datta; W.P. Mccormick 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 474 KB

We consider the first-order Edgeworth expansion for summands related to a homogeneous Markov chain. Certain inaccuracies in some earlier results by Nagaev are corrected and the expansion is obtained under relaxed conditions. An application of our result to the distribution of the mle of a transition

On coupling of Markov chains

✍ J. W. Pitman 📂 Article 📅 1976 🏛 Springer 🌐 English ⚖ 406 KB

The choice of optimum scores in a Markov

The choice of optimum scores in a Markov chain of order one

✍ H. I. Patel 📂 Article 📅 1970 🏛 Springer Japan 🌐 English ⚖ 164 KB

On the range of recurrent Markov chains

✍ K.B Athreya 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 152 KB