mixle.enumeration.density_rank module

Rank and cumulative probability of an observation under the descending-probability order.

For an observation x, two natural “where does x sit” queries are:

  • rank: how many observations are strictly more probable than x (its 0-based position in the descending-probability enumeration), and

  • cumulative probability: the total probability mass of all observations at least as probable as x – G(x) = P_{Y~p}(p(Y) >= p(x)) = sum_{y: p(y) >= p(x)} p(y).

Both are exact and cheap for the head of the distribution (the most-probable values) via the existing best-first enumerator(): walk descending until the score drops below p(x), summing mass and counting. But for an x deep in the tail the head is astronomically large, so exact enumeration is infeasible – and there a single Monte-Carlo pass is reliable, because G(x) is then large (low relative error). Conversely sampling fails for the head (G(x) tiny -> almost no samples exceed it). The two regimes are exactly complementary, so this module’s estimator is a hybrid: exact enumeration up to a budget, then a sampling fallback. The sampling fallback works for any samplable, density-evaluable model – mixtures, HMMs, and other non-decomposable families whose exact count-DP is intractable.

class DensityRankResult(cumulative_probability, rank, exact, stderr, log_prob, method, rank_stderr=0.0)[source]

Bases: object

Outcome of a rank / cumulative-probability query.

Parameters:
cumulative_probability

G(x) = sum_{y: p(y) >= p(x)} p(y) (the descending-order CDF at x).

Type:

float

rank

number of observations strictly more probable than x (0-based position). Exact when the head enumeration resolved it; in "sampling" mode it is the rounded unbiased Monte-Carlo estimate (see rank_stderr); None only when log p(x) = -inf or an exact-analytic CDF (no count) was used.

Type:

int | None

exact

True when the head enumeration resolved the query exactly; False for a sampling estimate.

Type:

bool

stderr

standard error of cumulative_probability (0.0 when exact).

Type:

float

log_prob

log p(x).

Type:

float

method

"exact-head", "exact-exhausted", "exact-analytic", or "sampling".

Type:

str

rank_stderr

standard error of the Monte-Carlo rank estimate (0.0 when exact). Large relative to rank exactly in the deep-tail / high-entropy band where exact marginal rank is provably hard – treat the estimate as unreliable there.

Type:

float

cumulative_probability: float
rank: int | None
exact: bool
stderr: float
log_prob: float
method: str
rank_stderr: float = 0.0
density_rank(dist, value, max_exact=100_000, n_samples=20_000, seed=0, tol=1.0e-9)[source]

Rank and cumulative probability of value under dist’s descending-probability order.

Strategy:

  1. If dist supports enumeration, walk the exact descending stream, accumulating the mass of every item at least as probable as value and counting those strictly more probable. If the stream drops below p(value) (or is exhausted) within max_exact items, the rank and cumulative probability are returned EXACTLY.

  2. Otherwise (value is deeper than max_exact, or enumeration is unsupported), estimate the cumulative probability by Monte Carlo: G_hat = mean_i 1[log p(Y_i) >= log p(value)] with Y_i ~ dist. Reliable here precisely because G is large in the tail.

Parameters:

  • dist (Any) – A distribution exposing log_density and sampler; optionally enumerator.

  • value (Any) – The observation to locate.

  • max_exact (int) – Cap on items pulled from the exact enumerator before falling back to sampling.

  • n_samples (int) – Monte-Carlo sample count for the fallback.

  • seed (int) – Sampler seed for the fallback (reproducible).

  • tol (float) – Log-probability tolerance for the >= comparison (ties).

Returns:

DensityRankResult.

Return type:

DensityRankResult

class TruncatedSumBound(num_enumerated, enumerated_mass, last_log_prob, support_size, exhausted, tail_upper_bound, total_upper_bound)[source]

Bases: object

Bounds on a descending-probability sum truncated after the top num_enumerated items.

Parameters:

  • num_enumerated (int)

  • enumerated_mass (float)

  • last_log_prob (float)

  • support_size (int | None)

  • exhausted (bool)

  • tail_upper_bound (float | None)

  • total_upper_bound (float | None)

num_enumerated

how many top items were enumerated (< k means the support was exhausted).

Type:

int

enumerated_mass

exact summed probability of the enumerated items (a lower bound on the total).

Type:

float

last_log_prob

log p of the smallest enumerated item; every un-enumerated item is ``<= `` this.

Type:

float

support_size

the distribution’s support cardinality (None if infinite/unknown), or the number enumerated when the support was exhausted.

Type:

int | None

exhausted

the enumerator ran dry within k – the enumerated items ARE the whole support, so the tail is exactly zero and the bounds are exact.

Type:

bool

tail_upper_bound

provable upper bound on the un-enumerated mass: (support_size - num_enumerated) * exp(last_log_prob) (0 when exhausted; None when the support size is unknown).

Type:

float | None

total_upper_bound

enumerated_mass + tail_upper_bound – an upper bound on the full sum (<= 1 for a normalized model; bounds the partition function for an unnormalized one).

Type:

float | None

num_enumerated: int
enumerated_mass: float
last_log_prob: float
support_size: int | None
exhausted: bool
tail_upper_bound: float | None
total_upper_bound: float | None
truncated_sum_bound(dist, k)[source]

Bound a distribution’s descending-probability sum by truncating after the top k items.

Enumerates the k most probable outcomes (descending), so any un-enumerated outcome has probability <= p_k (the smallest enumerated). With the support cardinality N = dist.support_size() the un-enumerated mass is then bounded by (N - k) * p_k – a finite, cheap upper bound on the truncated tail that uses only k evaluations and the support size. If the enumerator is exhausted within k the bounds are exact (the tail is zero). Requires an enumerable family; raises EnumerationError otherwise.

This is the truncation-based distribution upper bound: e.g. it certifies how much mass a top-k summary misses, or upper-bounds an unnormalized model’s partition function.

Parameters:
Return type:

TruncatedSumBound

class CountDPRankResult(rank, window_lower, window_upper, log_prob, oversample)[source]

Bases: object

Approximate rank of an observation from the count DP, for decomposable families.

Parameters:
rank

estimated number of observations strictly more probable than the query.

Type:

int

window_lower

count in buckets safely below the query’s smear window (a conservative-ish floor; see note on quantization smear below).

Type:

int

window_upper

window_lower plus the count inside the smear window.

Type:

int

log_prob

log p(x).

Type:

float

oversample

the quantizer oversample used (higher -> finer bucket -> smaller error).

Type:

int

The estimate is quantization-approximate, not exact: the count DP bins each item by a sum of floored per-factor buckets, so an item near the query’s probability can land one or two buckets to either side of the boundary. The error shrinks as oversample grows (empirically mean well under 1 rank at oversample 64 on small products) and the smear window is resolved exactly when small, but a guaranteed integer rank is not promised.

rank: int
window_lower: int
window_upper: int
log_prob: float
oversample: int
count_dp_rank(dist, value, oversample=64, bin_width_bits=1.0, smear=None, resolve_max=8192, tol=1.0e-12)[source]

Approximate rank of value via the structural count DP – for decomposable families.

The count DP convolves the per-factor log-probability histograms, so its histogram is the distribution of the total log-probability over the whole (astronomically large) support. The rank of value is then the cumulative count of more-probable buckets – a prefix sum, no enumeration – so it works for arbitrarily deep ranks that head enumeration and sampling cannot reach. Items within a few buckets of the query may straddle the boundary (quantization smear from the floored per-factor buckets), so a smear window around the query’s bucket is resolved exactly (unranked and compared) when it holds at most resolve_max items; the result is an estimate whose error shrinks with oversample.

For the NON-decomposable marginal families (mixture, HMM) the count DP bins by the tropical (dominant-path) cost and over-counts, so this returns a tropical rank, not the true-marginal rank – use density_rank() (head enumeration + sampling) for those.

Parameters:
Return type:

CountDPRankResult

class CountDPSeekResult(value, log_prob, index, rank_lower, rank_upper, exact, oversample)[source]

Bases: object

The observation at an arbitrary descending-probability index – the inverse of a rank query.

Parameters:
value

the observation at (approximately) descending-probability index.

Type:

Any

log_prob

log p(value).

Type:

float

index

the requested 0-based index.

Type:

int

rank_lower, rank_upper

the TRUE rank of value is bracketed in [rank_lower, rank_upper] by the smear window. A tight bracket means the model is in the separated / near-exact regime here, so the seek is trustworthy; a wide one means many near-ties around value.

exact

the smear window was resolved exactly (then rank_lower == rank_upper is the true rank). For decomposable families (composite/sequence/markov) the count index is exact, so seek is exact up to quantization. For mixtures/HMMs the index is the TROPICAL projection (dominant component/path), so the bracket is the tropical error envelope – a guaranteed bound only when smear covers the <= log2(K)-bit tropical displacement; otherwise it is the approximate tropical bracket (raise smear for rigor; see count_dp_rank()).

Type:

bool

oversample

the quantizer oversample used (higher -> finer buckets -> tighter bracket).

Type:

int

value: Any
log_prob: float
index: int
rank_lower: int
rank_upper: int
exact: bool
oversample: int
class CountDPTopPResult(size_lower, size_upper, covered_mass, log_prob_threshold, target, truncated, oversample)[source]

Bases: object

How many of the most-probable outcomes cover probability mass target – the nucleus SIZE.

The structural / at-depth counterpart of DistributionEnumerator.top_p: where that materializes the nucleus (fine when it is small), this reports its size for decomposable families WITHOUT enumerating it, so it scales to huge supports where the nucleus itself is too large to list.

Parameters:
size_lower, size_upper

provable bracket on the nucleus size – the number of most-probable outcomes whose summed mass first reaches target. Both bounds hold regardless of the within-bucket ordering: size_upper includes whole probability buckets until the mass covers target (a valid covering set, so the true nucleus is no larger), and size_lower caps every item in bucket b at its maximum possible probability 2**(-b * bits_per_bucket) (an over-estimate of coverage, so fewer items provably cannot reach target).

covered_mass

exact mass of the size_upper whole-bucket cover (>= target unless truncated).

Type:

float

log_prob_threshold

approximate log-prob at the cover boundary.

Type:

float

target

the requested cumulative-probability target p.

Type:

float

truncated

the depth bound was hit before the mass reached target (then size_upper is a floor on the true size, not a cover).

Type:

bool

oversample

the quantizer oversample used (higher -> finer buckets -> tighter bracket).

Type:

int

size_lower: int
size_upper: int
covered_mass: float
log_prob_threshold: float
target: float
truncated: bool
oversample: int
count_dp_seek(dist, index, oversample=64, bin_width_bits=1.0, smear=None, resolve_max=8192, tol=1.0e-12, max_fine_bucket_cap=1 << 30)[source]

Seek the observation at descending-probability index – the inverse of count_dp_rank().

Walks the structural count histogram in ascending-bucket (= descending-probability) order until the cumulative count passes index, then unranks within that bucket. No prefix enumeration, so arbitrary deep indices are reachable directly. The depth bound is grown geometrically until the index (plus a smear margin) is covered or the support is exhausted.

Returns the value together with a provable bracket [rank_lower, rank_upper] on its true rank (the smear window): a tight bracket certifies the seek is in the separated / near-exact regime. For decomposable families this is exact up to quantization; for mixtures/HMMs it seeks into the tropical (dominant-component/path) projection and the bracket is that projection’s error envelope.

Parameters:
Return type:

CountDPSeekResult

class MarginalSeekResult(value, log_prob, index, true_rank_lower, true_rank_upper, exact, oversample)[source]

Bases: object

The value at a descending index, with a guaranteed bracket on its TRUE marginal rank.

count_dp_seek() brackets only the tropical rank for a marginal family (mixture): its count index bins by the dominant-component cost M(x) and over-counts values shared by several components, so neither the cost gap nor the multiplicity is accounted for. This result closes both gaps soundly:

  • cost gap – the window is widened by the family’s tropical_displacement_bits (log2(K) for a K-component mixture, since M(x) <= log p(x) <= M(x) + log K), so every value below the window is provably more probable than value and every value above it provably less.

  • multiplicity gap – a shared value is counted at most K times, so the count strictly below the window over-states the distinct rank by at most K; dividing by K restores a sound lower bound.

Hence [true_rank_lower, true_rank_upper] provably contains #{u : log p(u) > log p(value)}. Two regimes pin it exactly (exact): a decomposable / provably-disjoint family (no displacement, no over-count -> the structural count IS the distinct rank), or a shallow index whose whole prefix fits the resolve budget (unranked and de-duplicated against the true log_density). Otherwise the bracket is the honest, provable envelope – the #P-hard core (de-duplicating an arbitrarily deep overlapping prefix) is exactly what cannot be done cheaply.

Parameters:
value

the observation at tropical descending index.

Type:

Any

log_prob

exact log p(value) (the true marginal, re-evaluated – not the tropical cost).

Type:

float

index

the requested 0-based (tropical) index.

Type:

int

true_rank_lower, true_rank_upper

guaranteed bracket on value’s TRUE marginal rank.

exact

the bracket collapsed to the exact true rank (then the two bounds are equal).

Type:

bool

oversample

the quantizer oversample used (higher -> finer buckets -> tighter bracket).

Type:

int

value: Any
log_prob: float
index: int
true_rank_lower: int
true_rank_upper: int
exact: bool
oversample: int
property semantics

DensitySemantics.EXACT when the rank is pinned, else ESTIMATE (a provable bracket).

marginal_seek(dist, index, oversample=64, bin_width_bits=1.0, resolve_max=8192, tol=1.0e-12, max_fine_bucket_cap=1 << 30)[source]

Seek descending index with a GUARANTEED bracket on the value’s true marginal rank.

For a decomposable family this matches count_dp_seek() (zero displacement, exact count). For a marginal family (mixture) the structural count index is the tropical projection; this widens the rank window by the family’s tropical_displacement_bits() so the bracket provably bounds the TRUE marginal rank, divides the below-window count by the component multiplicity to stay sound against over-counting, and – when the whole prefix is small or the family is decomposable/disjoint – resolves the window against the true log_density to pin the exact rank in O(window) rather than O(index).

Raises EnumerationError when no structural count index exists (e.g. a continuous-component mixture), and IndexError when index is beyond the reachable structural count – both exactly like count_dp_seek(), whose depth-deepening loop this shares. A large probability gap (a value separated from the rest by many bits, e.g. an outcome that only a ~1e-6-weight component can emit) can make that loop conclude the support is exhausted early, so such deep-gap indices are unreachable; this never affects reachable indices, since every unreached value is strictly less probable than everything reached. The returned value sits at the tropical index; for the value at a true descending index use mixle.enumeration.best_first.sound_top_k().

Parameters:
Return type:

MarginalSeekResult

cumulative_probability(dist, value, oversample=64, bin_width_bits=1.0, smear=None)[source]

Exact cumulative probability G(x) = sum_{y: p(y) >= p(x)} p(y) for decomposable families.

Structural and at arbitrary depth (no enumeration, no sampling): the bulk mass of all buckets strictly below the query’s smear band comes from the exact _mass_histogram() prefix, and the band itself is resolved item-by-item (true log_density) via the count index. Because each bucket’s mass is the EXACT sum of its items’ probabilities and the band absorbs the floored-bucket smear (within #factors buckets), the result is exact up to floating-point roundoff – verified to 1e-16 on a 12-factor product, where the count-times-representative-probability shortcut returns G > 1. Deterministic, so it complements density_rank() (whose deep path is Monte-Carlo).

Parameters:

  • oversample (int)

  • bin_width_bits (float)

  • smear (int | None)

count_dp_top_p(dist, p, oversample=64, bin_width_bits=1.0, tol=1.0e-9, max_fine_bucket_cap=1 << 30)[source]

Nucleus SIZE: how many most-probable outcomes cover mass p, for decomposable families.

The structural counterpart of dist.enumerator().top_p(p) – it returns the size of the minimal high-probability set (and its boundary), computed from the exact per-bucket mass (_mass_histogram()) and per-bucket counts (the count index) WITHOUT enumerating the nucleus, so it works when the nucleus is far too large to list. The size is returned as a provable bracket [size_lower, size_upper] (see CountDPTopPResult); the bracket is tight when the mass is concentrated and widens with quantization smear (raise oversample to tighten).

For mixtures/HMMs the mass histogram has no exact decomposition – use the enumerator’s top_p (exact for a small nucleus) there instead.

Parameters:
Return type:

CountDPTopPResult

mixture_cross_rank(mixture, value, oversample=64, bin_width_bits=1.0, depth_bits=64.0)[source]

True-marginal rank of value under a homogeneous mixture, at arbitrary depth.

count_dp_rank on a mixture gives only the TROPICAL (dominant-component) rank – it bins by the best single component, so a value built from several components is badly mis-ranked. This computes the true rank against the actual marginal p = sum_k w_k p_k by building the JOINT K-dimensional count histogram of the per-component log-prob buckets (structurally, no enumeration of the joint support – see _joint_bucket_histogram()) and counting joint bins whose representative marginal probability exceeds p(value).

Quantization-approximate: a joint bin’s marginal probability is evaluated at the bucket midpoints, so bins straddling the threshold may be mis-counted; the error shrinks as oversample grows. Cost is EXPONENTIAL in the number of components K (the histogram is K-dimensional), so this is for SMALL-K mixtures (a few components) of same-structured decomposable components; it needs no enumeration, so it scales to deep ranks. For non-mixtures use count_dp_rank(); for the head of any model use density_rank().

Parameters: