Jul 2026· International Conference on Signal Processing and Communications· pp. 1-5· 0 citations· 14 references
Abstract
Mixing time bounds for Markov chains play a central role in characterizing the sample complexity of learning and inference from correlated data. While the mixing behavior of symmetric random walks on standard graph structures such as cycles, tori, and hypercubes is well understood, the impact of transition asymmetry remains less explored. In this work, we study the mixing times of lazy, asymmetric random walks on cycles, tori, and hypercubes, motivated by their relevance in practical applications. For the $n$-cycle, we develop a novel coupling construction that yields an order-wise tight upper bound $O\left(\frac{n^{2}}{p+q}\right)$, explicitly capturing the dependence on asymmetric transition probabilities $p$ and $q$. Numerical results indicate that this dependence is highly accurate. Building on this result, we derive corresponding bounds for $d$-dimensional tori. For asymmetric random walks on $n$-dimensional hypercubes, motivated by applications, we consider the problem of estimating expectations of functions that depend only on a subset $\Delta \ll n$ of coordinates. We show that the effective sample complexity improves to $O(n \log \Delta)$, compared to $O(n \log n)$ for the full chain. In all cases, our bounds recover the tightest known results for symmetric walks as special cases.
We study the mixing time of weighted Dikin walks for sampling from exponential distributions on polytopes and truncated positive-semidefinite (PSD) cones. Our first result gives a general total-variation mixing bound under strong self-concordance, $\bar{\nu}$-symmetry, and mixed-trace regularity on the local metric. The key idea is to control the Metropolis--Hastings acceptance probability on a high-probability region rather than at every point. Applying this framework to the Lee--Sidford, Lewis-weight, and John metrics yields an $\widetilde O(d^2)$ mixing bound for sampling from polytopes, while applying it to a hybrid barrier yields an $\widetilde O(d^4)$ mixing bound for sampling from truncated PSD cones. Our second result establishes stronger $\chi^2$-divergence guarantees and pointwise acceptance control using a new fourth-order bootstrap condition. For a suitably scaled Lee--Sidford metric, this yields an $\widetilde O(d^2)$ mixing bound in $\chi^2$-divergence, improving on the previous $\widetilde O(d^{9/4})$ bound.
We develop a framework for deterministic approximate counting of multi-spin systems beyond bounded-degree graphs. The algorithm recursively constructs rational polytopes containing the true marginal vectors and uses linear-fractional programming to obtain certified bounds on marginal ratios. For positive interactions on graphs of polynomial connective constant $D$, we establish strong spatial mixing and a fully polynomial-time approximation scheme (\textbf{FPTAS}) whenever $Dc<1$, where $c$ bounds the Birkhoff contraction coefficients of the interactions. We further extend the framework to proper colorings of sparse Erd\H{o}s-R\'{e}nyi random graphs using recursion on permissive blocks. For every fixed $\eta\in(0,1)$, sufficiently large fixed $d$, and fixed integer $q\ge(2+\eta)d$, we obtain an \textbf{FPTAS} for counting proper $q$-colorings of $G\sim\mathcal G(n,d/n)$ with high probability over $G$. This improves the leading constant $3$ in the earlier counting guarantee of Yin and Zhang (APPROX/RANDOM, 2016) to $2$, and asymptotically matches the spatial mixing regime established by Yin (ICALP, 2014).
Two star exponential random graph models (ERGMs) are an interesting special case of both general ERGMs and mean-field Ising models. In this paper, we study two star ERGMs conditioning on the edge density $p$. We begin with an analytic characterization of the replica symmetric region, where the conditional model is close in cut distance to the Erd\H{o}s--R\'enyi random graph $G(n,p)$. We prove that this region is twice as large as the corresponding region for the unconditional model. To study refined properties of the conditional model, we then analyze the global Kawasaki algorithm for sampling from it. Within the replica symmetric region, and under the additional condition that $4\beta p(1-p)<0.5$ when $|p-1/2|\lesssim 0.4632$, where $\beta$ is the model parameter, we prove metastable fast mixing of the Kawasaki algorithm. As corollaries, we obtain a weak Poincar\'e inequality and use it to deduce concentration inequalities of optimal order for conditional subgraph counts. The additional condition $4\beta p(1-p)<1/2$ if $|p-1/2|\lesssim 0.4632$ comes from our proof technique of contractive coupling. This bottleneck did not appear in previous studies applying the contractive coupling technique to unconditional ERGMs.
We design randomized approximation schemes for the partition function of antiferromagnetic Ising models with uniform external field on random regular bipartite graphs. Our algorithm generalizes the approach of Kocurek, Oveis Gharan and Tjowasi (arXiv, 2026) for hard-core models on the same random graph model beyond the uniqueness threshold. We show that, as long as $\lambda$ is upper bounded by a constant and $\lambda(1 - \beta) \lesssim \Delta^{-1/2}$, an efficient randomized algorithm approximates the partition function with high probability. The algorithm first truncates configurations that are large on either side of the bipartition and then samples from Gibbs distributions conditioned on fixed sizes on one or both sides. To choose an optimal truncation bound, we establish concentration properties of the Gibbs distribution on random regular bipartite graphs. Then we apply high-dimensional expansion and prove trickle-down theorems to obtain fast samplers for the conditioned distributions.
This paper analyzes mixing time lower bounds for random walks on sparse, heavy-tailed Random Intersection Graphs. In sparse feature regimes, heavy-tailed feature distributions lead to the formation of peripheral trap -- chains of overlapping low-weight feature cliques attached to high-weight hub nodes within the graph's giant component. By modeling escape trajectories from these traps as continuous limit hitting times for reflected Brownian motion, the analysis demonstrates that random walks experience logarithmic squared delays. Consequently, the mixing time is bounded below by $\Omega(\log^2 n)$, and the local total variation distance exhibits non-concentrated decay, formally preventing a sharp cutoff phenomenon.
The Watts-Strogatz random graph model on $n$ vertices with parameters $K$ (a positive even integer) and $p \in [0, 1]$ is constructed in two steps. First, one starts with a ring lattice on $n$ vertices, where each vertex is connected to its $K/2$ nearest neighbors on each side. Each edge in turn is then independently rewired with probability $p$ by replacing one endpoint with a uniformly chosen vertex not already adjacent to it. We study the empirical eigenvalue distribution of the adjacency matrix for this model, whose entries are highly dependent due to the rewiring construction. In the regime where both $K$ and $pK$ grow to infinity with the vertex size $n$, we show that, after appropriate scaling, the empirical eigenvalue distribution converges to the semicircle law. The proof is based on a novel coupling argument that approximates the adjacency matrix by a sum of two independent random matrices, one a sparse Wigner matrix and the other a random band matrix. In the case where $K$ and $p$ remain fixed, we propose conjectural formulas for the first five moments of the limiting eigenvalue distribution. These conjectures are supported by a convergence result relating the Watts-Strogatz model to another random graph model, together with numerical simulations.
Grégoire Meunier, Sean O’Rourke· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
