Home / Curated / Algorithms / Diaconis–Holmes–Neal fiber sampler

Diaconis–Holmes–Neal fiber sampler

Algorithms AIMech:DiaconisHolmesNealFiberSampler DRAFT

A finite-state Metropolis sampler that uses partitions into ordered lines, retains a binary direction for each partition, and combines a neighbor proposal with a separate probabilistic sign update to preserve a target distribution on the augmented state.

Identity Notes & Concept Scope Whole-corpus normalized checks cover every ID, name, alias and scoped synonym in 442 pinned AIO and 703 native records; four full checkouts include ignored and hidden files. Finite ordered fibers, one retained sign per partition, fixed partition selection and the post-MH sign operation define this identity. The one-line directed sampler is explicitly covered as d=1 specialization, with no separate record or narrower-name exact alias. Shared MH or lifting does not make this equivalent to random walk MH, Neal pair-state or acceptance-uniform updates, HMC or continuous Gustafson half-normal displacement. Existing source-frontier reference is resolved in place. Related AIO:MarkovChain does not assert model identity or layer inheritance; 18 complete candidate class contexts and 19 native neighbors were assessed.

Claims & Grounded Evidence

6 Claims

Mechanism #ordered-partitions-and-augmented-target

Let pi be a strictly positive probability mass function on a finite state space X. For each of d directions, partition X into linearly ordered lines. Require connectivity through the union of these lines: any two states can be joined by successive within-line moves. Retain z in {−1,+1}^d and use augmented target pi(x)/2^d. Fix positive direction-selection probabilities w_i summing to one and parameters theta_i satisfying 0<theta_i<1.

supports Source: Analysis of a Non-Reversible Markov Chain Sampler · Locator: Section 5.2, printed p. 16 / PDF p. 17, partitions, connectedness and augmented state

Mechanism #directed-neighbor-metropolis-stage

Choose direction i using w_i and find its line containing x. Propose the successor of x on that line when z_i=+1 or the predecessor when z_i=−1, together with negation of the proposed z_i. Accept with min(1,pi(x*)/pi(x)); otherwise leave the state unchanged for this stage. A proposed step beyond a line endpoint is rejected. Other direction signs remain unchanged. This uses neighboring elements of the ordering, not an independent draw from the full line conditional.

supports Source: Analysis of a Non-Reversible Markov Chain Sampler · Locator: Section 5.2, printed p. 16 / PDF p. 17, Steps 1–2; endpoint rule in Section 5.1, printed p. 15 / PDF p. 16, Step 1; application to each line in Proposition 2 proof, printed p. 17 / PDF p. 18

Mechanism #post-metropolis-sign-update

After the Metropolis stage, negate the resulting sign z_i with probability 1−theta_i and keep it with probability theta_i, without changing x or other signs. Thus an accepted move preserves its incoming direction with probability 1−theta_i and reverses it with probability theta_i; a rejected move reverses the incoming direction with probability 1−theta_i and retains it with probability theta_i. This second sign operation follows both acceptance and rejection.

supports Source: Analysis of a Non-Reversible Markov Chain Sampler · Locator: Section 5.2, printed p. 16 / PDF p. 17, Step 3; combined-effect explanation in Section 5.1, printed p. 15 / PDF p. 16

Scope #finite-state-invariance-and-ergodicity

The Metropolis stage preserves the augmented target and the sign-update stage preserves its uniform sign factors. Each direction kernel is therefore invariant, and so is their fixed mixture. Proposition 2 establishes irreducibility and aperiodicity for the stated finite positive-target construction with connected ordered-line partitions, positive direction probabilities and 0<theta_i<1. Endpoint holding probabilities enter the aperiodicity argument. These are assumption-bound finite-state results, not an ergodicity theorem for arbitrary continuous extensions or parameter endpoints.

supports Source: Analysis of a Non-Reversible Markov Chain Sampler · Locator: Section 5.1, printed p. 15 / PDF p. 16, Proposition 1; Section 5.2, printed pp. 16–17 / PDF pp. 17–18, Proposition 2 and proof

Scope #one-line-directed-specialization

With d=1 and one ordered line X={1,...,n}, the fiber construction is the directed sampler of Section 5.1: propose x+z with sign negation, reject an out-of-range move, and apply the same second sign operation. This record includes that one-line specialization. The authors discuss continuous counterparts and Gustafson’s guided walk separately; the finite construction does not define all persistent-direction or lifted MCMC algorithms.

supports Source: Analysis of a Non-Reversible Markov Chain Sampler · Locator: Section 5.1, printed pp. 15–16 / PDF pp. 16–17; Section 5.2, printed pp. 16–17 / PDF pp. 17–18

Limitation #line-selection-and-exploration-limits

Useful ordered lines must be available, although the implementation need only find a current point’s successor or predecessor rather than explicitly enumerate each line. Lines aligned poorly with the target can retain diffusive behavior, and local moves can still encounter probability barriers. The construction does not provide a general advantage over direct conditional or other proposal methods merely by retaining direction.

supports Source: Analysis of a Non-Reversible Markov Chain Sampler · Locator: Section 5.2, printed p. 17 / PDF p. 18, line-construction discussion; Section 7, printed pp. 23–24 / PDF pp. 24–25, discussion

⚠️ Curated Limitations & Negative Results

The maintained identity is the finite ordered-fiber construction, including its one-line directed case. It does not denote every nonreversible sampler, graph non-backtracking walk, momentum method or continuous guided-walk extension.
Strict positivity, line connectivity, positive fixed direction weights and 0<theta_i<1 belong to the stated finite ergodicity result. Setting theta_i to zero or one requires separate analysis; stationarity alone does not certify convergence.
The stored sign for each partition is part of the state. Resetting signs at every transition, omitting the second sign operation or applying it only after rejection changes the specified kernel.
The primary evidence is the author-hosted 5 June 1997 Technical Report BU-1385-M. The later 2000 journal article was not obtained, and exact equivalence of versions is not asserted.
The record makes no numerical mixing-rate, variance-reduction or runtime claim. The source’s specially tuned uniform walk and illustrative target experiments do not establish such a guarantee for every fiber construction.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:MarkovChain` Markov Chain	related_match	The fiber procedure constructs a finite Markov chain on state-and-direction pairs with a specified target marginal. AIO MarkovChain describes a stochastic process/model; this is a method-to-process association without equivalence, subclass status or inheritance of Network and ProbabilisticHiddenLayer assertions.

Evidence Sources & Primary Literature

1 Source

Source ID	Publication / Document	Type / Access	Reference & Checksum
`dhn1997`	Analysis of a Non-Reversible Markov Chain Sampler Persi Diaconis, Susan Holmes, Radford M. Neal	author technical report full_text	sha256:795fc1d47425…

Curation Provenance

Curator: Codex

Method: ai_assisted

Model: GPT-6

Created: 2026-10-14T21:02:45Z

Updated: 2026-10-14T21:02:45Z

Source File: data/curated/DiaconisHolmesNealFiberSampler.yaml