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 efficient 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 when log p(x) = -inf, an exact-analytic CDF (no count) was used, or the sampling estimate itself overflowed (see rank_stderr, which is still finite – or inf – even when rank is None).

Type:

int | None

exact

True when the head enumeration resolved the query exactly WITH RESPECT TO the tol- equivalence relation ties are defined by (see density_rank’s tol parameter); 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

density_rank(dist, value, max_exact=100_000, n_samples=20_000, seed=0, tol=_EXACT_TIE_TOL)[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; must be a positive integer (validated eagerly, even on a call that never reaches the sampling path – a bad n_samples is a caller bug regardless of whether this particular query happens to exercise it).

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

  • tol (float) – Log-probability tolerance for the >=/> comparisons (ties). Defaults to this module’s 1e-12 “true rank” convention (also used by count_dp_rank/count_dp_seek/ marginal_seek). exact=True is exact WITH RESPECT TO this tolerance’s equivalence relation: two scores within tol of each other are treated as tied. Widening tol trades a stricter mathematical comparison for robustness against floating-point jitter in log_density – know that a wide tol can change which values compare as tied.

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

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, low-overhead 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.

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, truncated=False)[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

truncated

True when the search hit max_fine_bucket_cap before value’s smear window could be fully built AND before the distribution’s own exhaustion certificate could rule out more (deeper, possibly gapped) support – then exact is always False, and only rank_lower remains a PROVEN bound; rank_upper is a best-effort figure from a partially-built window, not a guarantee (buckets beyond the built depth are simply absent from the histogram, not confirmed empty). False (the normal case) means rank_lower/ rank_upper are both certified, whether or not they collapsed to an exact point.

Type:

bool

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

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 distribution’s own exhaustion certificate proves no more support exists – see quantized_count_index()’s truncated return value, which is False exactly when its histogram holds the ENTIRE support. A plain “the cumulative count stopped growing between two depths” plateau is deliberately NOT used to conclude exhaustion: a discrete model can have zero support across a wide run of probability buckets and resume having support below it (e.g. disjoint support clusters, or a component reachable only through a tiny-weight path), and a plateau there is indistinguishable from genuine exhaustion by count alone.

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. If the search reaches max_fine_bucket_cap before the window is fully built and before exhaustion is certified, the result is returned with truncated=True (exact=False, and only rank_lower remains a proven bound) rather than silently passed off as a certified bracket. If index itself is never located within the cap and exhaustion is not certified either, raises EnumerationError – NOT IndexError, since IndexError would falsely claim the index is proven out of range, when in fact the search simply ran out of budget; a genuine out-of-range index (proven via the exhaustion certificate) still raises IndexError, unchanged.

Parameters:
Return type:

CountDPSeekResult

class MarginalSeekResult(value, log_prob, index, true_rank_lower, true_rank_upper, exact, oversample, truncated=False)[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 certified, provable envelope – the #P-hard core (de-duplicating an arbitrarily deep overlapping prefix) is exactly what cannot be done efficiently.

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

truncated

True when the search hit max_fine_bucket_cap before value’s (displacement- widened) rank window could be fully built AND before the distribution’s own exhaustion certificate ruled out more support – then exact is always False, and only true_rank_lower remains a PROVEN bound; true_rank_upper is a best-effort figure from a partially-built window, not a guarantee. False (the normal case) means both bounds are certified, whether or not they collapsed to an exact point.

Type:

bool

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) – both exactly like count_dp_seek(), whose depth-deepening loop this shares, INCLUDING its exhaustion certificate: deepening is driven by quantized_count_index’s own truncated flag (False exactly when the histogram already holds the ENTIRE support), never by a plateau in the total count. 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) no longer causes a false-exhaustion conclusion: the loop deepens straight through the gap, since a plateau in that region is not by itself proof that nothing lies beyond it. IndexError is raised only once exhaustion is actually certified and index is still unreached – a proof, not a guess. If the search instead gives up at max_fine_bucket_cap with index still unreached and exhaustion uncertified, it raises EnumerationError (budget exhausted, existence unproven) rather than a falsely-certain IndexError; if index WAS reached but its rank window could not be fully verified within the cap, it returns a result with truncated=True instead of a certified bracket. 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

class CumulativeProbabilityResult(probability, exact, dropped_upper, index_truncated, sum_defect)[source]

Bases: object

Outcome of cumulative_probability(): G(x) plus what is, and isn’t, certified about it.

Parameters:
probability

G(x) = sum_{y: p(y) >= p(x)} p(y), from the exact bulk mass-histogram prefix plus the item-resolved tie band (see cumulative_probability()’s docstring). Clamped into [0, 1] only when the raw bulk+band sum landed outside that range by no more than this module’s _ROUNDOFF_TOL roundoff budget – see sum_defect; a larger excursion raises instead of being silently clamped (a real defect, not roundoff).

Type:

float

exact

True when nothing this function can detect compromises probability: the count index behind the tie band carries no approximation-search drop (dropped_upper == 0.0, true for every exact-count family – Composite/Sequence/Record/MarkovChain/leaf/Mixture/HMM – and false only for an approximate-search index, e.g. an autoregressive branch_cap build). False means probability is a best-effort figure that may UNDERSTATE the truth – see dropped_upper.

Type:

bool

dropped_upper

a proven upper bound on the COUNT of in-band items an approximate-search family’s count index may have pruned before ever reaching this function – 0.0 for every exact-count family. Nonzero means probability may understate the true G(x) by up to that many items’ worth of (each individually small) probability.

Type:

float

index_truncated

the count index build’s own truncated flag (True when the distribution’s support extends beyond the query’s tie band – the common case for any non-trivial query). Exposed for transparency, but on its own it does NOT compromise probability: the tie band only touches buckets within the requested depth, which the count-DP contract guarantees are correctly represented regardless of what lies beyond it. exact/ dropped_upper are the actual soundness signals; this one is diagnostic only.

Type:

bool

sum_defect

how far the raw bulk+band sum landed outside [0, 1] before any clamping – 0.0 when the sum was already a valid probability, otherwise a value <= _ROUNDOFF_TOL (anything larger raises instead of reaching this result).

Type:

float

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

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 for every exact-count family – 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).

Returns a CumulativeProbabilityResult, not a bare float: an approximate-search family’s count index (e.g. an autoregressive branch_cap build) can silently prune in-band items WITHOUT tripping the index’s own truncated flag (that flag means something different and, for this function, largely benign – see the result’s index_truncated doc), so the honest completeness signal is the index’s dropped_upper, surfaced via result.exact/result.dropped_upper rather than folded into a single number the caller has no way to audit.

Parameters:

  • tol (float) – Log-probability tie tolerance for the band’s >= comparison. Defaults to this module’s 1e-12 “true rank” convention (see density_rank()’s tol) – NOT the previous hardcoded 1e-9, which is 1000x looser and can pull in values that are genuinely, if only slightly, less probable than value.

  • oversample (int)

  • bin_width_bits (float)

  • smear (int | None)

Return type:

CumulativeProbabilityResult

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

class MixtureCrossRankResult(rank, rank_lower, rank_upper, exact, truncated, oversample, bin_width_bits, depth_bits)[source]

Bases: object

Quantized mixture cross-rank estimate with an honest support-count bracket.

rank_lower counts only bins whose least-probable corner is still strictly above the query. rank_upper also includes every threshold-straddling bin and every support item omitted by depth_bits. The estimate uses bucket midpoints and is never presented as an exact scalar unless the bracket collapses without truncation.

Parameters:
mixture_cross_rank(mixture, value, oversample=64, bin_width_bits=1.0, depth_bits=64.0, max_leaf_support=100_000)[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, with no enumeration of the JOINT/cross-component support – see _joint_bucket_histogram()) and counting joint bins whose representative marginal probability exceeds p(value).

Returns a MixtureCrossRankResult, not an uncertified scalar. A joint bin’s mixture probability is bounded using both probability corners implied by its component buckets. Bins certainly above the query contribute to rank_lower; threshold-straddling bins contribute only to rank_upper. Support omitted by depth_bits is also included conservatively in the upper bound and sets truncated=True. The midpoint-based rank is an estimate within that bracket; exact=True only when the bracket collapses without truncation.

Cost is EXPONENTIAL in the number of components K (the histogram is K-dimensional), so this is for SMALL-K mixtures (a few components); it needs no enumeration of the joint support, so it scales to deep ranks along that axis. It is NOT free along every axis, though: each LEAF component’s OWN support (e.g. one field of a composite, or an atomic leaf) IS enumerated once (the union of what every component assigns positive probability to), so every leaf must have a finite support of at most max_leaf_support – an infinite-support leaf (Poisson, geometric, an unbounded sequence, …) or a merely huge finite one raises EnumerationError rather than hanging or silently defeating the advertised scaling. For non-mixtures use count_dp_rank(); for the head of any model use density_rank().

Parameters:

  • oversample (int)

  • bin_width_bits (float)

  • depth_bits (float)

  • max_leaf_support (int)