No label defined (Q4704792)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1369837
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 1369837 |
Statements
5 October 2000
0 references
Potts model
0 references
Markov chain Monte Carlo methods
0 references
mixing time
0 references
0.9058651328086852
0 references
0.868842363357544
0 references
0.8430801630020142
0 references
Let \(G=V,E)\) be an arbitrary graph, \(|V|= n\). The \(Q\)-state Potts model is defined as follows: Let \((V_1,\ldots, V_{Q})\) be an ordered partition of the set \(V\) of vertices into (possibly empty) disjoint subsets. The partition defines a configuration \(\sigma\), the vertex \(v\in V_{j}\) being assigned a colour \(j\). Let \(D(\sigma)\) be the set of edges between colour classes; the measure of the configuration \(\sigma\) is given by \(\mu(\sigma) = \exp(-\beta |D(\sigma)|)\), where the coupling constant \(\beta\) is assumed to be positive (the ferromagnetic case). Hence, the probability that the system is in the state \(\sigma\) is defined as \(Z(G)^{-1}\exp(-\beta|D(\sigma)|)\), where \(Z(G) = \sum_\sigma\exp(-\beta |D(\sigma)|)\) is the partition function, the sum being taken over all configurations. The Swendsen-Wang process [\textit{R. Swendsen} and \textit{J.-S. Wang}, Phys. Rev. Lett. 58, 86-88 (1987)]\ was proposed as a Markov chain Monte Carlo method for estimating the partition function \(Z(G)\). Let \(P_{t,\sigma}\) be the law of the process at time \(t\) under the condition that the initial state is \(\sigma\), and let \(\pi\) be the stationary distribution. Set \(d(t) = \max_\sigma \|P_{t,\sigma} -\pi\|\), where we use \(\|\cdot\|\) to denote the variation distance. The Swendsen-Wang process is called rapidly mixing if the mixing time \(\min\{t; d(t)\leq 1/e\}\) is bounded by a polynomial in \(n\). This property (or the lack thereof) is studied for various classes of graphs. For example, it is shown that for trees the mixing time is \(O(n)\) for any \(\beta\).
0 references