Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR05-075 | 21st July 2006 00:00

Dobrushin conditions and Systematic Scan Revision of: TR05-075

RSS-Feed




Revision #1
Authors: Martin Dyer, Leslie Ann Goldberg, Mark Jerrum
Accepted on: 21st July 2006 00:00
Downloads: 1147
Keywords: 


Abstract:

We consider Glauber dynamics on finite spin systems.
The mixing time of Glauber dynamics can be bounded
in terms of the influences of sites on each other.
We consider three parameters bounding these influences ---
$\alpha$, the total influence on a site, as studied by Dobrushin;
$\alpha'$, the total influence of a site, as studied by Dobrushin and Shlosman;
and $\alpha''$, the total influence on a site in any given context,
which is related to the path-coupling method of Bubley and Dyer.
It is known that if any of these parameters is less than~$1$ then
random-update Glauber dynamics (in which a randomly-chosen site is updated
at each step) is rapidly mixing. It is also known that
the Dobrushin condition $\alpha<1$ implies that
systematic-scan Glauber dynamics (in which sites are updated in a deterministic
order) is rapidly mixing.
This paper studies two related issues, primarily in the context of
systematic scan:
(1) the relationship between the parameters~$\alpha$, $\alpha'$ and
$\alpha''$, and
(2) the relationship between proofs of rapid mixing using Dobrushin
uniqueness (which
typically use analysis techniques) and proofs of rapid mixing using path
coupling.
We use matrix-balancing to show that the Dobrushin-Shlosman condition
$\alpha'<1$ implies rapid mixing of systematic scan.
An interesting question is whether the rapid mixing results for scan can be
extended to the $\alpha=1$ or $\alpha'=1$ case.
We give positive results for the rapid mixing of systematic scan for
certain $\alpha=1$
cases.
As an application,
we show rapid mixing of systematic scan (for any scan order) for
heat-bath Glauber dynamics for proper $q$-colourings of a
degree-$\Delta$ graph~$G$
when $q\geq 2\Delta$.


Paper:

TR05-075 | 4th July 2005 00:00

Dobrushin conditions and Systematic Scan





TR05-075
Authors: Martin Dyer, Leslie Ann Goldberg, Mark Jerrum
Publication: 15th July 2005 17:15
Downloads: 1337
Keywords: 


Abstract:

We consider Glauber dynamics on finite spin systems.
The mixing time of Glauber dynamics can be bounded
in terms of the influences of sites on each other.
We consider three parameters bounding these influences ---
$\alpha$, the total influence on a site, as studied by Dobrushin;
$\alpha'$, the total influence of a site, as studied by Dobrushin and Shlosman;
and $\alpha''$, the total influence on a site in any given context,
which is related to the path-coupling method of Bubley and Dyer.
It is known that if any of these parameters is less than~$1$ then
random-update Glauber dynamics (in which a randomly-chosen site is updated
at each step) is rapidly mixing. It is also known that
the Dobrushin condition $\alpha<1$ implies that
systematic-scan Glauber dynamics (in which sites are updated in a deterministic
order) is rapidly mixing.
This paper studies two related issues, primarily in the context of systematic scan:
(1) the relationship between the parameters~$\alpha$, $\alpha'$ and $\alpha''$, and
(2) the relationship between proofs of rapid mixing using Dobrushin uniqueness (which
typically use analysis techniques) and proofs of rapid mixing using path
coupling.
We use matrix-balancing to show that the Dobrushin-Shlosman condition
$\alpha'<1$ implies rapid mixing of systematic scan.
An interesting question is whether the rapid mixing results for scan can be
extended to the $\alpha=1$ or $\alpha'=1$ case.
We give positive results for the rapid mixing of systematic scan for certain $\alpha=1$
cases.
As an application,
we show rapid mixing of systematic scan (for any scan order) for
heat-bath Glauber dynamics for proper $q$-colourings of a degree-$\Delta$ graph~$G$
when $q\geq 2\Delta$.



ISSN 1433-8092 | Imprint