About: Markov chain mixing time

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Markov chain mixing time Goto Sponge NotDistinct Permalink

An Entity of Type : yago:YagoPermanentlyLocatedEntity, within Data Space : dbpedia.demo.openlinksw.com associated with source document(s)
QRcode icon

http://dbpedia.demo.openlinksw.com/c/789Mt6b8SP

In probability theory, the mixing time of a Markov chain is the time until the Markov chain is "close" to its steady state distribution. More precisely, a fundamental result about Markov chains is that a finite state irreducible aperiodic chain has a unique stationary distribution π and, regardless of the initial state, the time-t distribution of the chain converges to π as t tends to infinity. Mixing time refers to any of several variant formalizations of the idea: how large must t be until the time-t distribution is approximately π ? One variant, variation distance mixing time, is defined as the smallest t such that the total variation distance of probability measures is small:

Attributes	Values
rdf:type	yago:WikicatMarkovProcesses yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity
rdfs:label	Markov chain mixing time (en)
rdfs:comment	In probability theory, the mixing time of a Markov chain is the time until the Markov chain is "close" to its steady state distribution. More precisely, a fundamental result about Markov chains is that a finite state irreducible aperiodic chain has a unique stationary distribution π and, regardless of the initial state, the time-t distribution of the chain converges to π as t tends to infinity. Mixing time refers to any of several variant formalizations of the idea: how large must t be until the time-t distribution is approximately π ? One variant, variation distance mixing time, is defined as the smallest t such that the total variation distance of probability measures is small: (en)
dct:subject	Markov processes
Wikipage page ID	6101938 (xsd:integer)
Wikipage revision ID	1021873383 (xsd:integer)
Link from a Wikipage to another Wikipage	Probability distribution Mixing (mathematics) Conductance (probability) Graph coloring Monte Carlo method Steady state Probability theory Coupling (probability) Markov processes Markov chains Randomized algorithms Markov chain Markov chain Monte Carlo Sharp-P-complete Total variation distance of probability measures Shuffle
Link from a Wikipage to an external page	http://stat-www.berkeley.edu/users/aldous/RWG/book.html http://statweb.stanford.edu/%7Ecgates/PERSI/papers/bayer92.pdf https://web.archive.org/web/20040921020230/http:/stat-www.berkeley.edu/users/aldous/RWG/book.html
sameAs	Markov chain mixing time Markov chain mixing time Markov chain mixing time Markov chain mixing time
dbp:wikiPageUsesTemplate	dbt:Citation dbt:Harv dbt:Mvar dbt:Harvs
first	Dave (en) Persi (en)
last	Bayer (en) Diaconis (en)
year	1992 (xsd:integer)
has abstract	In probability theory, the mixing time of a Markov chain is the time until the Markov chain is "close" to its steady state distribution. More precisely, a fundamental result about Markov chains is that a finite state irreducible aperiodic chain has a unique stationary distribution π and, regardless of the initial state, the time-t distribution of the chain converges to π as t tends to infinity. Mixing time refers to any of several variant formalizations of the idea: how large must t be until the time-t distribution is approximately π ? One variant, variation distance mixing time, is defined as the smallest t such that the total variation distance of probability measures is small: for all subsets of states and all initial states. This is the sense in which Dave Bayer and Persi Diaconis proved that the number of riffle shuffles needed to mix an ordinary 52 card deck is 7. Mathematical theory focuses on how mixing times change as a function of the size of the structure underlying the chain. For an -card deck, the number of riffle shuffles needed grows as . The most developed theory concerns randomized algorithms for #P-Complete algorithmic counting problems such as the number of graph colorings of a given vertex graph. Such problems can, for sufficiently large number of colors, be answered using the Markov chain Monte Carlo method and showing that the mixing time grows only as. This example and the shuffling example possess the rapid mixing property, that the mixing time grows at most polynomially fast in (number of states of the chain). Tools for proving rapid mixing include arguments based on conductance and the method of coupling. In broader uses of the Markov chain Monte Carlo method, rigorous justification of simulation results would require a theoretical bound on mixing time, and many interesting practical cases have resisted such theoretical analysis. (en)
author1-link	Dave Bayer (en)
author2-link	Persi Diaconis (en)
prov:wasDerivedFrom	wikipedia-en:Markov_chain_mixing_time?oldid=1021873383&ns=0
page length (characters) of wiki page	4435 (xsd:nonNegativeInteger)
foaf:isPrimaryTopicOf	wikipedia-en:Markov_chain_mixing_time
is Link from a Wikipage to another Wikipage of	Ronald Graham Mixing time David Aldous List of probability topics Computing the permanent Conductance (graph) Elizabeth Wilmer Convex volume approximation Combinatorics Yuval Peres Markov Chains and Mixing Times Jason P. Miller Alan M. Frieze Reconfiguration Catalog of articles in probability theory Ramanujan graph Cereceda's conjecture Markov chain Markov chain Monte Carlo List of statistics articles List of things named after Andrey Markov Shuffling
is Wikipage disambiguates of	Mixing time
is foaf:primaryTopic of	wikipedia-en:Markov_chain_mixing_time

Faceted Search & Find service v1.17_git147 as of Sep 06 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3331 as of Sep 2 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (378 GB total memory, 52 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software