Metric Construction, Stopping Times and Path Coupling

Details Metric Construction, Stopping Times and Path Coupling Metric Construction, Stopping Times and Path Coupling

2005-11-08

arxiv.org/abs/math/0511202v2

Mathematics

Probability

21 pages, revised version includes statement and proof of general stopping times theorem (section 2.2), and additonal remarks

Scientific paper

In this paper we examine the importance of the choice of metric in path coupling, and the relationship of this to \emph{stopping time analysis}. We give strong evidence that stopping time analysis is no more powerful than standard path coupling. In particular, we prove a stronger theorem for path coupling with stopping times, using a metric which allows us to restrict analysis to standard one-step path coupling. This approach provides insight for the design of non-standard metrics giving improvements in the analysis of specific problems. We give illustrative applications to hypergraph independent sets and SAT instances, hypergraph colourings and colourings of bipartite graphs.

Affiliated with

Also associated with

No associations

Rating

Metric Construction, Stopping Times and Path Coupling does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Metric Construction, Stopping Times and Path Coupling, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Metric Construction, Stopping Times and Path Coupling will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-293970