Exact Mixing in an Unknown Markov Chain

No abstract is available for this paper.

• Publication year

  1995

• Venue

  Electronic Journal of Combinatorics

• Publication date

  1995-05-27

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.37236/1209
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• 6.856 — Randomized Algorithms

  2002cited by this paper
• On Simulating a Markov Chain Stationary Distribution when Transition Probabilities are Unknown

  1995influential reference
• Random Walks in a Convex Body and an Improved Volume Algorithm

  1993cited by this paper
• Collisions among Random Walks on a Graph

  1993cited by this paper
• Stationarity detection in the initial transient problem

  1992cited by this paper
• Sampling and integration of near log-concave functions

  1991cited by this paper
• On the conductance of order Markov chains

  1991cited by this paper
• Random walks and the effective resistance of networks

  1991cited by this paper
• The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees

  1990influential reference
• The electrical resistance of a graph captures its commute and cover times

  1989cited by this paper
• Conductance and the Rapid Mixing Property for Markov Chains: the Approximation of the Permanent Resolved (Preliminary Version)

  1988cited by this paper
• Random Walks and Electric Networks: REFERENCES

  1987cited by this paper
• How hard is it to marry at random? (On the approximation of the permanent)

  1986cited by this paper
• Random Perturbations of Dynamical Systems

  1984cited by this paper
• Graphs and Hypergraphs

  year unknowncited by this paper

• Composing Reinforcement Learning Policies, with Formal Guarantees

  2024cites this paper
• Synthesis of Hierarchical Controllers Based on Deep Reinforcement Learning Policies

  2024cites this paper
• Perfect Sampling for Hard Spheres from Strong Spatial Mixing

  2023cites this paper
• Almost Uniform Sampling of Independent Sets in Polynomial Time - Implying NP=RP

  2023cites this paper
• Perfect simulation from unbiased simulation

  2023cites this paper
• Design of Hamiltonian Monte Carlo for perfect simulation of general continuous distributions

  2022influential citation
• Finite-Memory Near-Optimal Learning for Markov Decision Processes with Long-Run Average Reward

  2020cites this paper
• The Amazing Power of Randomness: NP=RP

  2020cites this paper
• Supplementary Material for “Finite-Memory Near-Optimal Learning for Markov Decision Processes with Long-Run Average Reward”

  2020cites this paper
• Learning-Based Mean-Payoff Optimization in an Unknown MDP under Omega-Regular Constraints

  2018cites this paper
• Perfect sampling for quantum Gibbs states

  2017cites this paper
• Markov Chains and Mixing Times: Second Edition

  2017cites this paper
• Combinatorics of acyclic orientations of graphs : algebra, geometry and probability

  2015cites this paper
• Acyclic Orientations and Spanning Trees

  2014cites this paper
• Markov Chains and Mixing Times

  2008cites this paper
• Exact sampling from anti‐monotone systems

  2008cites this paper
• Codes and Noncommutative Stochastic Matrices

  2008cites this paper
• Fast Mixing in a Markov Chain

  2007cites this paper
• The birthday problem and Markov chain Monte Carlo

  2007cites this paper
• Random Trees in Electrical Networks

  2006cites this paper
• ul 2 00 6 Random Trees in Electrical networks

  2006cites this paper
• Distribution, Approximation and Probabilistic Model Checking

  2006cites this paper
• Probabilistic Model Checking of the CSMA/CD Protocol Using PRISM and APMC

  2005cites this paper
• The eigenvalues of the empirical transition matrix of a Markov chain

  2004cites this paper
• Approximate Probabilistic Model Checking

  2004cites this paper
• Learning Near-Pareto-Optimal Conventions in Polynomial Time

  2003cites this paper
• Interruptible Exact Sampling in the Passive Case

  2002influential citation
• Perfect sampling: a review and applications to signal processing

  2002cites this paper
• Exact sampling of TCP window states

  2002cites this paper
• A Guide to Exact Simulation

  2001cites this paper
• Random Walks on Graphs: A Survey

  2001cites this paper
• Exact Sampling in Machine Scheduling Problems

  2001cites this paper
• Surveys in Combinatorics, 1999: Random Walks on Combinatorial Objects

  1999cites this paper
• Layered Multishift Coupling for use in Perfect Sampling Algorithms (with a primer on CFTP)

  1999cites this paper
• How to couple from the past using a read-once source of randomness

  1999cites this paper
• How to Get a Perfectly Random Sample from a Generic Markov Chain and Generate a Random Spanning Tree of a Directed Graph

  1998cites this paper
• Coupling from the past: A user's guide

  1997cites this paper
• An interruptible algorithm for perfect sampling via Markov chains

  1997cites this paper
• Mixing times

  1997cites this paper
• How to get an exact sample from a generic Markov chain and sample a random spanning tree from a directed graph, both within the cover time

  1996cites this paper
• Exact sampling with Markov chains

  1996cites this paper
• Exact sampling with coupled Markov chains and applications to statistical mechanics

  1996cites this paper
• Generating random spanning trees more quickly than the cover time

  1996influential citation
• Exact Sampling with Markov Chains by

  1996cites this paper
• Eecient Stopping Rules for Markov Chains

  1995cites this paper
• Mixing of random walks and other diffusions on a graph

  1995cites this paper
• Efficient stopping rules for Markov chains

  1995cites this paper
• Random Walks on Graphs: A Survey

  1993cites this paper
• Controller Synthesis from Deep Reinforcement Learning Policies

  year unknowncites this paper