Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-17T23:28:53.219Z Has data issue: false hasContentIssue false

Analysis of a non-reversible Markov chain speedup by a single edge

Published online by Cambridge University Press:  04 January 2023

Balázs Gerencsér*
Affiliation:
Alfréd Rényi Institute of Mathematics and ELTE Eötvös Loránd University
*
*Postal address: Alfréd Rényi Institute of Mathematics, 1053 Budapest, Reáltanoda utca 13-15, Hungary. Email address: gerencser.balazs@renyi.hu
Rights & Permissions [Opens in a new window]

Abstract

We present a Markov chain example where non-reversibility and an added edge jointly improve mixing time. When a random edge is added to a cycle of n vertices and a Markov chain with a drift is introduced, we get a mixing time of $O(n^{3/2})$ with probability bounded away from 0. If only one of the two modifications were performed, the mixing time would stay $\Omega(n^2)$.

Information

Type
Original Article
Copyright
© The Author(s), 2023. Published by Cambridge University Press on behalf of Applied Probability Trust
Figure 0

Figure 1.Cycle graph with either (a) no extra edges, (b) all parallel edges between opposing vertices, or (c) a single random extra edge.

Figure 1

Figure 2.Illustration of ${\mathbb{Z}}_+^2\times H$. Points of the form $(\cdot,\cdot,A)$ are represented by gray dots while $(\cdot,\cdot,B)$ points are represented by black dots. The extension to $R_*$ by grid lines is also shown, with gray (dashed) and black (solid) lines corresponding to points having A and B as the last coordinate, respectively.

Figure 2

Figure 3.Illustration of R. An intersection of the slanted line with a grid line represents a single point in R, while passing through a grid point corresponds to two points in R.

Figure 3

Figure 4.Possible transitions depicted as $U\rightarrow U'$ while scanning through $R_1$.

Figure 4

Figure 5.Evolution of the points of $R_1^i$ with the increase of i. Two such zigzag paths are depicted.

Figure 5

Figure 6.Fluctuation of $t_{\rm mix}\big(\frac 1 4\big)$ depending on the extra edge length k by computer numerical results: (a) for a cycle of $n=2000$ vertices; (b) comparing for various values of n, both normalizing edge lengths and scaling down mixing times with an $n^{3/2}$ factor.