We study the mixing time of the single-site update Markov chain, known as the Glauber dynamics, forgenerating a random independent set of a tree. Our focus is obtaining optimal convergence results forarbitrary trees. ...
详细信息
We study the mixing time of the single-site update Markov chain, known as the Glauber dynamics, forgenerating a random independent set of a tree. Our focus is obtaining optimal convergence results forarbitrary trees. We consider the more general problem of sampling from the Gibbs distribution in the hard-core model where independent sets are weighted by a parameter lambda>0;the special case lambda=1 corresponds to the uniform distribution over all independent sets. Previous work of Martinelli, Sinclair and Weitz(2004) obtained optimal mixing time bounds for the complete Delta-regular tree for all lambda. However, Restrepo,Stefankovic, Vera, Vigoda, and Yang (2014) showed that for sufficiently large lambda there are bounded-degreetrees where optimal mixing does not hold. Recent work of Eppstein and Frishberg (2022) proved a poly-nomial mixing time bound for the Glauber dynamics for arbitrary trees, and more generally for graphs ofbounded tree-width. We establish an optimal bound on the relaxation time (i.e., inverse spectral gap) ofO(n) for the Glauber dynamics for unweighted independent sets on arbitrary trees. We stress that our results hold for arbitrarytrees and there is no dependence on the maximum degree Delta. Interestingly, our results extend (far) beyondthe uniqueness threshold which is on the order lambda=O(1/Delta). Our proof approach is inspired by recent workon spectral independence. In fact, we prove that spectral independence holds with a constant independentof the maximum degree for any tree, but this does not imply mixing for general trees as the optimal mixingresults of Chen, Liu, and Vigoda (2021) only apply for bounded-degree graphs. We instead utilize thecombinatorial nature of independent sets to directly prove approximate tensorization of variance via anon-trivial inductive proof.
Obtaining frequency information of data streams, in limited space, is a well-recognized problem in literature. A number of recent practical applications (such as those in cornputational advertising) require temporally...
详细信息
ISBN:
(纸本)9781450335317
Obtaining frequency information of data streams, in limited space, is a well-recognized problem in literature. A number of recent practical applications (such as those in cornputational advertising) require temporally-aware solutions: obtaining historical count statistics for both time-points as well as time-ranges. In these scenarios, accuracy of estimates is typically more important for recent instances than for older ones;we call this desirable property Time Adapkiwi-less. With this observation, [20] introduced the HoKuSAl technique based on count-min sketches for estimating the frequency of any given item at any given time. The proposed approach is problematic 111 practice, as its memory requirements grow linearly with time, and it produces discontimiities in the estimation accuracy. Tn this work, we describe a new method, Time-adaptive Sketches, (ADA-sKETc0), that overcomes these limitations, while extending and providing a strict generalization of several popular sketching algorithms. The core idea of our method is inspired by the well-known digital Dolby noise reduction procedure that dates back to the 1960s. The theoretical analysis presented could be of independent interest in itself, as it provides clear results for the time-adaptive nature of the errors. An experimental evaluation on real streaming datasets demonstrates the superiority of the described method over ilokusai in estimating point and range queries over time. The method is simple to implement and offers a variety of design choices for future extensions. The simplicity of the procedure and the method's generalization of classic sketching techniques give hope for wide applicability of Ada. sketchesin practice.
We develop an efficient algorithmic approach for approximatecounting and sampling in the low-temperature regime of a broad class of statistical physics models on finite subsets of the lattice Z(d) and on the torus (Z...
详细信息
ISBN:
(纸本)9781450367059
We develop an efficient algorithmic approach for approximatecounting and sampling in the low-temperature regime of a broad class of statistical physics models on finite subsets of the lattice Z(d) and on the torus (Z/nZ)(d). Our approach is based on combining contour representations from Pirogov-Sinai theory with Barvinok's approach to approximatecounting using truncated Taylor series. Some consequences of our main results include an FPTAS for approximating the partition function of the hard-core model at sufficiently high fugacity on subsets of Z(d) with appropriate boundary conditions and an efficient sampling algorithm for the ferromagnetic Potts model on the discrete torus (Z/nZ)(d) at sufficiently low temperature.
暂无评论