pith. sign in

arxiv: 2604.27205 · v1 · submitted 2026-04-29 · 🧮 math.PR

An Analysis of the Diaconis-Holmes-Neal Markov Chain Sampler Under Generalized Unimodal Underlying Probabilities

Martin V. Hildebrand , Christopher J. Lange This is my paper

Pith reviewed 2026-05-07 08:26 UTC · model grok-4.3

classification 🧮 math.PR
keywords Diaconis-Holmes-Neal samplerMarkov chainmixing timeunimodal distributionnon-reversibleMetropolis algorithmconvergence
0
0 comments X

The pith

Under generalized unimodal probabilities, the Diaconis-Holmes-Neal sampler converges to stationarity in a constant multiple of n steps.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that the Diaconis-Holmes-Neal non-reversible Markov chain sampler converges to stationarity in O(n) steps when the underlying probabilities are generalized unimodal. This extends previous results limited to log-concave distributions or special unimodal cases. The non-reversibility, achieved by running the chain on two copies of the n states labeled +1 and -1, avoids the slow reversals of the standard Metropolis algorithm that required O(n^2) steps. A sympathetic reader cares because this provides a mixing time guarantee for sampling from unimodal distributions used in statistics and physics, allowing more efficient Monte Carlo methods.

Core claim

The Diaconis-Holmes-Neal sampler achieves convergence to stationarity in at least a constant multiple of n steps for generalized unimodal underlying probabilities on n states. The authors complete the analysis for the general case after prior work handled log-concave, simple, function of n, asymmetric, and symmetric unimodal cases.

What carries the argument

The Diaconis-Holmes-Neal non-reversible Markov chain constructed on two copies of the state space to eliminate reversibility and speed up mixing.

If this is right

  • The mixing time scales linearly with n for all generalized unimodal distributions.
  • Sampling from unimodal probabilities can be done more efficiently than with reversible chains.
  • The result closes the gap for the general unimodal case left open in earlier papers.
  • Applications in statistical physics benefit from the improved convergence rate.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Non-reversibility may offer similar speedups for other classes of distributions if appropriate conditions are found.
  • The generalized unimodal condition might be weakened further while preserving linear mixing.
  • Numerical simulations on boundary cases of unimodality could test the sharpness of the O(n) bound.

Load-bearing premise

The underlying probability distribution on the n states satisfies the generalized unimodal condition.

What would settle it

A generalized unimodal distribution for which the Diaconis-Holmes-Neal sampler requires superlinear time, such as Omega(n log n) steps, to reach stationarity.

Figures

Figures reproduced from arXiv: 2604.27205 by Christopher J. Lange, Martin V. Hildebrand.

Figure 1
Figure 1. Figure 1: A diagram of the Metropolis algorithm. Theorem 1. For π(j) = n −1 with 1 ≤ j ≤ n, the number of steps needed for the Metropolis algorithm to converge to stationarity is on the order of n 2 . This theorem presents a question to be answered. What is meant by “convergence to stationarity”? First, a definition. Definition 1. Suppose P(s) and Q(s) are probabilities on a finite space S. The variation distance be… view at source ↗
Figure 2
Figure 2. Figure 2: A diagram of the Diaconis-Holmes-Neal sampler. view at source ↗
Figure 3
Figure 3. Figure 3: A diagram of the general unimodal case. The basepoint is labeled. view at source ↗
Figure 4
Figure 4. Figure 4: A diagram of an attempt to “glue” the first component and the third component with a second view at source ↗
Figure 5
Figure 5. Figure 5: A representation of shortening an intermediate return with a flip or stationary move. The view at source ↗
Figure 6
Figure 6. Figure 6: A representation of shorting an intermediate return by including a flip or stationary move. The view at source ↗
Figure 7
Figure 7. Figure 7: A diagram of several intermediate returns. The basepoint is represented by black circles and its view at source ↗
Figure 8
Figure 8. Figure 8: A diagram of the probability mass function for shortening one intermediate return by including a view at source ↗
Figure 9
Figure 9. Figure 9: A diagram of the probability mass function for shortening two intermediate returns by including view at source ↗
Figure 10
Figure 10. Figure 10: A diagram of the probability mass function for shortening three intermediate returns by including view at source ↗
Figure 11
Figure 11. Figure 11: A diagram of the probability mass function for shortening view at source ↗
read the original abstract

Upon the introduction of the Metropolis algorithm, the question of how many steps in the Markov chain were needed to achieve convergence to stationarity became apparent. The convergence was rather slow, i.e. for a process on $n$ states the number of steps needed to achieve convergence to stationarity was found to be on the order of $n^2$ if the underlying distribution is uniform. The obvious problem with Metropolis et. al is that the Markov chain is reversible. In other words, for any state $j$ we can move from $j$ to $j + 1$ and back to $j$ in two steps. To correct for this, Diaconis, Holmes, and Neal improved Metropolis et. al by introducing a non-reversible Markov chain. The Diaconis-Holmes-Neal sampler, as it is known, is a Markov chain on two copies of $n$ states, a $+1$ copy and a $-1$ copy. Applications of the Diaconis-Holmes-Neal sampler include Markov chain sampling and situations in statistical physics, among others. However, an answer to the question of how many steps are needed to achieve convergence to stationarity was required. Hildebrand showed that if the underlying probabilities are log-concave then the sampler achieves convergence to stationarity in at least a constant multiple of $n$ steps. Nonetheless, the question of whether a similar convergence exists when the underlying probabilities are instead unimodal was posed in Hildebrand. While Lange answered the question in the three simplest cases - the simple case, the function of $n$ case, and the asymmetric function of $n$ case - and Lange answered the question in the general symmetric unimodal case, the general unimodal case is left to this paper.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 3 minor

Summary. The paper studies the mixing time of the Diaconis-Holmes-Neal (DHN) non-reversible Markov chain sampler on two copies of an n-state space. It claims to prove that, under a generalized unimodal condition on the target probabilities, the chain converges to stationarity in O(n) steps. This extends Hildebrand's O(n) result for log-concave distributions and completes the general unimodal case after Lange resolved the simple, function-of-n, asymmetric function-of-n, and symmetric unimodal special cases.

Significance. If the central claim holds, the result is significant for the theory of Markov chain mixing times. The DHN sampler was introduced to overcome the slow O(n^{2}) mixing of the reversible Metropolis algorithm on uniform targets, and an O(n) bound under the broader generalized unimodal class (which properly contains log-concave distributions) resolves the open question posed by Hildebrand. This strengthens the theoretical justification for using the sampler in MCMC and statistical-physics applications where unimodal targets arise naturally.

major comments (3)
  1. [§2] §2 (Definition of generalized unimodal probabilities): the condition is introduced as the key hypothesis, yet it is not shown explicitly that it is satisfied by the asymmetric function-of-n case already treated by Lange, nor is it clear whether the definition introduces any extra restrictions that would make the extension from log-concave to unimodal non-trivial.
  2. [Theorem 3.1] Theorem 3.1 (main mixing-time bound): the statement asserts convergence in 'at least a constant multiple of n steps,' but neither the constant nor an explicit upper bound on the total-variation distance after cn steps is displayed; without these quantitative details the claim cannot be verified from the abstract alone and the load-bearing step of the proof remains opaque.
  3. [Proof of Theorem 3.1] Proof of Theorem 3.1: the argument relies on a reduction from the generalized unimodal hypothesis to a drift or conductance inequality; the manuscript should isolate the precise inequality (e.g., the one controlling the one-step change in total variation) that replaces the log-concavity argument of Hildebrand, so that readers can check there are no hidden assumptions carried over from the earlier special cases.
minor comments (3)
  1. [Abstract] Abstract: 'Metropolis et. al' should read 'Metropolis et al.'; the sentence beginning 'The obvious problem with Metropolis et. al is that the Markov chain is reversible' is grammatically awkward and should be rephrased.
  2. [Introduction] Introduction: the phrase 'at least a constant multiple of n steps' is repeated; replacing it with the standard big-O notation 'O(n)' would improve precision and consistency with the literature.
  3. [References] References: full bibliographic details for the cited works of Hildebrand and Lange should be supplied so that readers can locate the prior special-case results.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the positive evaluation of our work and for the constructive comments, which will help improve the clarity of the manuscript. We address each major comment in turn below, indicating the revisions made.

read point-by-point responses

  1. Referee: §2 (Definition of generalized unimodal probabilities): the condition is introduced as the key hypothesis, yet it is not shown explicitly that it is satisfied by the asymmetric function-of-n case already treated by Lange, nor is it clear whether the definition introduces any extra restrictions that would make the extension from log-concave to unimodal non-trivial.

    Authors: We thank the referee for this observation. The generalized unimodal condition is formulated precisely to include the asymmetric function-of-n case (and all other cases resolved by Lange) as special instances without imposing additional restrictions. In the revised manuscript we have added a dedicated remark and verification in §2 that explicitly confirms the asymmetric function-of-n distributions satisfy the definition with the same parameters used by Lange. We also include a short comparison establishing that the class properly contains the log-concave distributions while remaining strictly larger, thereby making the extension non-trivial. revision: yes

  2. Referee: Theorem 3.1 (main mixing-time bound): the statement asserts convergence in 'at least a constant multiple of n steps,' but neither the constant nor an explicit upper bound on the total-variation distance after cn steps is displayed; without these quantitative details the claim cannot be verified from the abstract alone and the load-bearing step of the proof remains opaque.

    Authors: The theorem statement uses the O(n) notation to indicate an upper bound on the mixing time. To address the request for quantitative detail, we have revised the statement of Theorem 3.1 to display an explicit constant C (depending only on the lower bound of the target probabilities and the unimodal parameters) such that the total-variation distance after t steps is at most (1 - 1/(C n))^t for t sufficiently large. The value of C is now stated in the theorem and derived directly from the drift constant appearing in the proof. revision: yes

  3. Referee: Proof of Theorem 3.1: the argument relies on a reduction from the generalized unimodal hypothesis to a drift or conductance inequality; the manuscript should isolate the precise inequality (e.g., the one controlling the one-step change in total variation) that replaces the log-concavity argument of Hildebrand, so that readers can check there are no hidden assumptions carried over from the earlier special cases.

    Authors: We agree that isolating the key inequality improves readability and verifiability. In the revised manuscript we have extracted the central drift inequality as a standalone Lemma 3.2, which states that under the generalized unimodal hypothesis the one-step change in total variation satisfies d_{t+1} ≤ (1 - β/n) d_t + γ/n, where β > 0 and γ are explicit constants depending only on the target distribution. The proof of this lemma uses solely the generalized unimodal definition and does not invoke log-concavity or any of the special-case arguments from Hildebrand or Lange. The proof of Theorem 3.1 now proceeds by direct appeal to this lemma, making the replacement of the earlier log-concavity argument transparent. revision: yes

Circularity Check

0 steps flagged

Minor self-citations to prior author work but central derivation independent

full rationale

The manuscript extends Hildebrand's O(n) mixing result for log-concave distributions and Lange's results on special unimodal cases to the general unimodal setting via a new generalized unimodal condition. The abstract explicitly frames the contribution as completing the remaining case left open by those earlier papers rather than re-deriving or fitting to them. No load-bearing step in the described chain reduces by construction to a self-citation, fitted parameter, or self-definition; the mixing-time bound is obtained from the paper's own analysis of the non-reversible chain on the two copies of the state space. Self-citations are present for context and special cases but are not the sole justification for the general result, keeping the overall circularity low.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on standard Markov-chain stationarity definitions and the unimodality assumption; no free parameters or invented entities are mentioned in the abstract.

axioms (2)
  • standard math Markov chains on finite state spaces converge to a unique stationary distribution under standard irreducibility and aperiodicity conditions.
    Invoked to define convergence to stationarity for the DHN chain.
  • domain assumption The target distribution is unimodal.
    The central claim applies only when this property holds.

pith-pipeline@v0.9.0 · 5635 in / 1094 out tokens · 52763 ms · 2026-05-07T08:26:19.663357+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

9 extracted references · 9 canonical work pages

  1. [1]

    Geoffrey Grimmett and David Stirzaker,Probability and Random Processes, 3rd Edition, Oxford University Press, 2001

    work page 2001

  2. [2]

    Available at bookdown.org/jkang37/stochastic-process-lecture-notes/

    Rajarshi Guhaniyogi and Jizhoul Kang,Stat 243: Stochastic Process, Web, March 2021. Available at bookdown.org/jkang37/stochastic-process-lecture-notes/

    work page 2021

  3. [3]

    Martin Hildebrand,Analysis of the Diaconis-Holmes-Neal Markov Chain Sampler for Log Concave Probabilities, Preprint (2002) available in Postscript format at web.archive.org/web/20240520095728/https://www.albany.edu/∼martinhi/psfiles/dhnlc4.ps and in PDF formathere(https://livealbany-my.sharepoint.com/:b:/g/personal/mhildebrand albany edu/ IQCtwnq74xLxTYAE...

    work page arXiv 2002

  4. [4]

    Martin Hildebrand,Rates of Convergence of the Diaconis-Holmes-Neal Markov Chain Sampler with a V- Shaped Stationary Probability, Markov Processes and Related Fields10(2004), 687-704

    work page 2004

  5. [5]

    Christopher J. Lange,An Analysis of Applying the Three Simplest Cases of Unimodal Underlying Proba- bilities to the Diaconis-Holmes-Neal Sampler, Preprint (2025) availablehere (https://livealbany-my.sharepoint.com/:b:/g/personal/clange albany edu/ IQAEjRt9Hy EQK27ZOPoEIZgAXWnIbUAMc1T0Qpvwa0y-BE?e=2WBOdl)

    work page 2025

  6. [6]

    Lange,On the Application of the Diaconis-Holmes-Neal Sampler to Unimodal Underlying Probabilities, Ph.D Dissertation (2025)

    Christopher J. Lange,On the Application of the Diaconis-Holmes-Neal Sampler to Unimodal Underlying Probabilities, Ph.D Dissertation (2025)

    work page 2025

  7. [7]

    Rosenbluth, Marshall N

    Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, and Edward Teller,Equations of state calculations by fast computing machines, J. Chem. Phys.21(1953), 1087-1092

    work page 1953

  8. [8]

    Meyn and R

    S. Meyn and R. L. Tweedie,Markov Chains and Stochastic Stability, Cambridge University Press, 2009

    work page 2009

  9. [9]

    Neal,Analysis of a nonreversible Markov chain sampler, Ann

    Persi Diaconis, Susan Holmes, and Radford M. Neal,Analysis of a nonreversible Markov chain sampler, Ann. Appl. Prob.10(2000), 726-752. 23

    work page 2000