SpecializedSource checked

No-U-Turn Sampler

No-U-Turn Sampler draws samples while controlling distribution, coverage, or variance.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Randomness & Sampling
Difficulty: Intermediate
Family: Randomness and Sampling
Tier: Specialized
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 2
Code example: Ready
Visualization: Ready
Aliases: NUTS

Overview

No-U-Turn Sampler is a randomness and sampling method that generates samples, estimates, or pseudorandom values while controlling distribution and variance. It is most useful when repeatable sample behavior matters as much as raw randomness.

Core Concepts

probability distributionrandom variatevariance controlrandom drawdistributionestimate

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n)

Average

O(n)

Worst

O(n^2)

Space

O(n)

When to Use

Use No-U-Turn Sampler when sample quality, reproducibility, or distribution shape affects the result.
Use it when deterministic seeds and distribution checks can be part of testing.

When Not to Use

Avoid when the target distribution is poorly defined.
Avoid when independence, burn-in, or seeding assumptions cannot be tested.

What It Does

Draws or transforms random values
Controls bias, variance, or coverage
Returns samples for simulation or estimation

Use Cases

Monte Carlo estimation
Simulation
Randomized testing

Inputs

Target distribution or population
Random seed or random source
Sample count

Outputs

Random samples
Estimated statistic
Generated sequence

Key Formulas (1)

No-U-turn test

(q_plus − q_minus) dot p_minus < 0 or (q_plus − q_minus) dot p_plus < 0

(q_plus - q_minus) dot p_minus < 0 or (q_plus - q_minus) dot p_plus < 0

Stops trajectory expansion when simulated motion starts turning back.

Pseudocode

1.Initialize the random source and sampling parameters
2.Draw or transform candidate values
3.Accept, weight, or store samples according to the method
4.Repeat until the requested sample count is reached
5.Return the sample set or estimate

Canonical Example

Input: target = small distribution, samples = 5, seed = 7
Output: five repeatable samples or an estimate
Explanation: No-U-Turn Sampler uses the seed and sampling rule to produce values with the intended distribution or coverage.

Implementation Notes

Expose the seed and record enough parameters to reproduce samples.
Test distribution behavior with small deterministic checks before large simulations.

Common Pitfalls

Using an untracked seed makes results hard to reproduce.
Confusing distribution quality with visual randomness can hide bias.

Interactive Mechanism Walkthrough

Iterative Convergence & State Trajectory

Show samples accumulating over the target distribution or sample space.

Step 1 of 5: Initialize the random source and sampling parameters

sampling

Notes

No-U-Turn Sampler operates in O(n) time and O(n) space within the Randomness and Sampling family. Key governing relation: (q_plus - q_minus) dot p_minus < 0 or (q_plus - q_minus) dot p_plus < 0. Often compared with Rejection Sampling and Importance Sampling.