SYNTOLOGY HomeExplorerAtlasCodeMethodologyAboutDevelopersFeedPricing
Paper · 2001.04555 · 2020

Optimal Approximate Sampling from Discrete Probability Distributions

arXiv · PDF · Open in the Atlas

Code that ran

11 of 22 samples (functions and classes) lifted from this paper's linked repositories executed on a synthesized input in Syntology's jail (0 of them constructed an object rather than computing a result; 0 honoured the contract we drafted, 0 violated it and 11 have no contract verdict; 0 failures of our instrument; 11 no recorded run), measured 2026-11-21; repository links from the Papers with Code archive attributed under CC BY-SA, no affiliation; bodies inline only under a permissive licence as GitHub detects it. Not a reproduction of the paper's results.

"Ran" means the function executed on a synthesized input and returned a value. It is not a reproduction of the paper's results. This record, dated, as JSON: /api/ran/2001.04555.json · badge: /api/ran/2001.04555.svg

Each repository's role is a label: a classifier's output recorded on the link, or, where no role is recorded, what the Papers with Code archive marked. The line under it names its basis. Neither says who wrote the code.

RepositoryRoleRan
probcomp/optimal-approximate-sampling canonical (classifier label)
classifier basis: census
11 ran · 11 no recorded run
FunctionStatusWhere it lives
get_common_denominator Ran
ran on a synthesized input
probcomp/optimal-approximate-sampling/src/utils.py
code served (permissive licence) · get_code("4cf28f8c3eba0421")
How it ran

Ran in Syntology's sandbox on this synthesized input (drafted by a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API) and returned int, ndim 0, dtype family int, shape () as a later run recorded it. The image it ran in was not recorded. If your copy returns the same type, ndim and shape on these inputs, it matched what we observed; nothing here checks that. It does NOT mean the output is correct: nothing has compared it to the paper.

from fractions import Fraction

# Create a list of Fraction objects to pass to get_common_denominator
# The function expects objects with a .denominator attribute
probabilities = [
    Fraction(1, 2),
    Fraction(1, 3),
    Fraction(1, 4)
]

ARGS = {
    "probabilities": probabilities
}
Setup block drafted by
a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API
Imports
none outside the standard library — import names as written, not package names to install; a name the repository itself provides is not a package
Returned
type int, ndim 0, dtype family int, shape () — shape () as a later run recorded it
dtype family
int means an integer dtype; float means any other dtype the instrument saw, bool and complex included (fixture_check.py records only these two families)
Environment
image not recorded; re-verify against syntology-harvest-sandbox:v5-deps; not recorded for this sample: the harness installs a cuda-to-cpu shim (cuda_shim.py) before every sample and no run records whether a sample needed it; seed: none by the harness; any seed is in the setup block
get_common_numerators Ran
ran on a synthesized input
probcomp/optimal-approximate-sampling/src/utils.py
code served (permissive licence) · get_code("388e095eeeca2661")
How it ran

Ran in Syntology's sandbox on this synthesized input (drafted by a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API) and returned list, ndim 1, dtype family int; no output shape is stated. The image it ran in was not recorded. If your copy returns the same type and ndim on these inputs, it matched what we observed; nothing here checks that. It does NOT mean the output is correct: nothing has compared it to the paper.

import torch
import numpy as np

torch.manual_seed(0)

# Analyzing the function:
# - Z: a numeric value (int or float) used for multiplication
# - probabilities: an iterable of numeric values that get multiplied by Z

Z = 10
probabilities = [0.1, 0.2, 0.3, 0.4]

ARGS = {
    "Z": Z,
    "probabilities": probabilities,
}
Setup block drafted by
a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API
Imports
numpy, torch — import names as written, not package names to install; a name the repository itself provides is not a package
Returned
type list, ndim 1, dtype family int — a list output has no array shape of its own; none is stated
dtype family
int means an integer dtype; float means any other dtype the instrument saw, bool and complex included (fixture_check.py records only these two families)
Environment
image not recorded; re-verify against syntology-harvest-sandbox:v5-deps; not recorded for this sample: the harness installs a cuda-to-cpu shim (cuda_shim.py) before every sample and no run records whether a sample needed it; seed: none by the harness; any seed is in the setup block
get_delta_error Ran
ran on a synthesized input
probcomp/optimal-approximate-sampling/src/opt.py
code served (permissive licence) · get_code("e716cfd09ac434c7")
How it ran

Ran in Syntology's sandbox on this synthesized input (drafted by a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API) and returned float, ndim 0, dtype family float, shape () as a later run recorded it. The image it ran in was not recorded. If your copy returns the same type, ndim and shape on these inputs, it matched what we observed; nothing here checks that. It does NOT mean the output is correct: nothing has compared it to the paper.

import torch
import numpy as np

torch.manual_seed(0)

# The function calls kernel(p, ...) twice with scalar arguments
# kernel should be a callable that takes two arguments and returns a numeric value
def kernel(p, ratio):
    """Simple kernel function that takes a parameter p and a ratio, returns a value"""
    return float(p) * float(ratio)

# Z: appears to be a divisor, used as Z in M/Z and (M+delta)/Z
Z = 10

# p: passed to kernel function
p = 0.5

# M: an integer used in comparisons and arithmetic with delta
M = 5

# delta: must be -1 or 1 (checked by assert)
delta = 1

ARGS = {
    "Z": Z,
    "p": p,
    "M": M,
    "delta": delta,
    "kernel": kernel
}
Setup block drafted by
a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API
Imports
numpy, torch — import names as written, not package names to install; a name the repository itself provides is not a package
Returned
type float, ndim 0, dtype family float, shape () — shape () as a later run recorded it
dtype family
int means an integer dtype; float means any other dtype the instrument saw, bool and complex included (fixture_check.py records only these two families)
Environment
image not recorded; re-verify against syntology-harvest-sandbox:v5-deps; not recorded for this sample: the harness installs a cuda-to-cpu shim (cuda_shim.py) before every sample and no run records whether a sample needed it; seed: none by the harness; any seed is in the setup block
get_initial_Ms Ran
ran on a synthesized input
probcomp/optimal-approximate-sampling/src/opt.py
code served (permissive licence) · get_code("4fa6c82bf596ac2b")
How it ran

Ran in Syntology's sandbox on this synthesized input (drafted by a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API) and returned tuple, ndim 1, dtype family int; no output shape is stated. The image it ran in was not recorded. If your copy returns the same type and ndim on these inputs, it matched what we observed; nothing here checks that. It does NOT mean the output is correct: nothing has compared it to the paper.

import torch
import numpy as np

torch.manual_seed(0)

def kernel_fn(p, x):
    """Simple kernel function that takes two scalars and returns a scalar."""
    return float(p * x + (1 - p) * (1 - x))

Z = 10
p_target = [0.3, 0.5, 0.7]
kernel = kernel_fn

ARGS = {
    "Z": Z,
    "p_target": p_target,
    "kernel": kernel
}
Setup block drafted by
a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API
Imports
numpy, torch — import names as written, not package names to install; a name the repository itself provides is not a package
Returned
type tuple, ndim 1, dtype family int — a tuple output has no array shape of its own; none is stated
dtype family
int means an integer dtype; float means any other dtype the instrument saw, bool and complex included (fixture_check.py records only these two families)
Environment
image not recorded; re-verify against syntology-harvest-sandbox:v5-deps; not recorded for this sample: the harness installs a cuda-to-cpu shim (cuda_shim.py) before every sample and no run records whether a sample needed it; seed: none by the harness; any seed is in the setup block
kernel_hellinger Ran
ran on a synthesized input
probcomp/optimal-approximate-sampling/src/divergences.py
code served (permissive licence) · get_code("8e3254232604c04a")
How it ran

Ran in Syntology's sandbox on this synthesized input (drafted by a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API) and returned float, ndim 0, dtype family float, shape () as a later run recorded it. The image it ran in was not recorded. If your copy returns the same type, ndim and shape on these inputs, it matched what we observed; nothing here checks that. It does NOT mean the output is correct: nothing has compared it to the paper.

import torch
import numpy as np
from math import sqrt

torch.manual_seed(0)

# The function kernel_hellinger takes two scalar arguments a and b
# and computes (sqrt(a) - sqrt(b)) ** 2
# We need to provide valid numeric values for both parameters

a = 4.0
b = 1.0

ARGS = {
    "a": a,
    "b": b,
}
Setup block drafted by
a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API
Imports
numpy, torch — import names as written, not package names to install; a name the repository itself provides is not a package
Returned
type float, ndim 0, dtype family float, shape () — shape () as a later run recorded it
dtype family
int means an integer dtype; float means any other dtype the instrument saw, bool and complex included (fixture_check.py records only these two families)
Environment
image not recorded; re-verify against syntology-harvest-sandbox:v5-deps; not recorded for this sample: the harness installs a cuda-to-cpu shim (cuda_shim.py) before every sample and no run records whether a sample needed it; seed: none by the harness; any seed is in the setup block
kernel_tv Ran
ran on a synthesized input
probcomp/optimal-approximate-sampling/src/divergences.py
code served (permissive licence) · get_code("7f88bdd1e0d18ad7")
How it ran

Ran in Syntology's sandbox on this synthesized input (drafted by a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API) and returned Tensor, ndim 2, dtype family float, shape (2, 4) as a later run recorded it. The image it ran in was not recorded. If your copy returns the same type, ndim and shape on these inputs, it matched what we observed; nothing here checks that. It does NOT mean the output is correct: nothing has compared it to the paper.

import torch
import numpy as np

torch.manual_seed(0)

# The function kernel_tv takes two arguments (a, b) and computes
# 1/2 * abs(a - b). Both a and b appear to be numeric values or tensors.
# We'll use small tensors for both parameters.

a = torch.randn(2, 4)
b = torch.randn(2, 4)

ARGS = {
    'a': a,
    'b': b
}
Setup block drafted by
a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API
Imports
numpy, torch — import names as written, not package names to install; a name the repository itself provides is not a package
Returned
type Tensor, ndim 2, dtype family float, shape (2, 4) — shape (2, 4) as a later run recorded it
dtype family
int means an integer dtype; float means any other dtype the instrument saw, bool and complex included (fixture_check.py records only these two families)
Environment
image not recorded; re-verify against syntology-harvest-sandbox:v5-deps; not recorded for this sample: the harness installs a cuda-to-cpu shim (cuda_shim.py) before every sample and no run records whether a sample needed it; seed: none by the harness; any seed is in the setup block
lcm Ran
ran on a synthesized input
probcomp/optimal-approximate-sampling/src/utils.py
code served (permissive licence) · get_code("9a61b5ea009c49ab")
How it ran

Ran in Syntology's sandbox on this synthesized input (drafted by a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API) and returned int, ndim 0, dtype family int, shape () as a later run recorded it. The image it ran in was not recorded. If your copy returns the same type, ndim and shape on these inputs, it matched what we observed; nothing here checks that. It does NOT mean the output is correct: nothing has compared it to the paper.

from math import gcd

def lcm(a, b):
    return abs(a * b) // gcd(a, b)

ARGS = {
    "a": 12,
    "b": 8
}
Setup block drafted by
a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API
Imports
none outside the standard library — import names as written, not package names to install; a name the repository itself provides is not a package
Returned
type int, ndim 0, dtype family int, shape () — shape () as a later run recorded it
dtype family
int means an integer dtype; float means any other dtype the instrument saw, bool and complex included (fixture_check.py records only these two families)
Environment
image not recorded; re-verify against syntology-harvest-sandbox:v5-deps; not recorded for this sample: the harness installs a cuda-to-cpu shim (cuda_shim.py) before every sample and no run records whether a sample needed it; seed: none by the harness; any seed is in the setup block
make_ddg_tree Ran
ran on a synthesized input
probcomp/optimal-approximate-sampling/src/tree.py
code served (permissive licence) · get_code("9473b3dc91b4a9e3")
How it ran

Ran in Syntology's sandbox on this synthesized input (drafted by a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API) and returned Node. The image it ran in was not recorded. If your copy returns the same type on these inputs, it matched what we observed; nothing here checks that. It does NOT mean the output is correct: nothing has compared it to the paper.

from math import log2

def make_leaf_table(P):
    N = len(P)
    k = len(P[0])
    table = {}
    current = 2
    for level in range(k):
        for row in range(N):
            if P[row][level] == 1:
                table[current] = row + 1
                current -= 1
        current = 2 * current + 2
    return table

class Node(object):

    def __init__(self, index):
        self.index = index
        self.label = None
        self.left = None
        self.right = None
        self.loc = None

def make_tree(index, k, l, ancestors, L):
    node = Node(index)
    if index in L:
        node.label = L[index]
    else:
        level = int(log2(index + 1))
        index_lc = 2 * index + 1
        index_rc = 2 * index + 2
        if level == l:
            ancestors.append(node)
        if level == k - 1 and index_rc not in L:
            assert node not in ancestors
            node.right = ancestors.pop(0)
        else:
            node.right = make_tree(index_rc, k, l, ancestors, L)
        if level == k - 1 and index_lc not in L:
            assert node not in ancestors
            node.left = ancestors.pop(0)
        else:
            node.left = make_tree(index_lc, k, l, ancestors, L)
    return node

def make_ddg_tree(P, k, l):
    assert 0 < k and 0 <= l <= k
    if k == 1 and l == 0:
        root = Node(1)
        root.label = 1
        return root
    L = make_leaf_table(P)
    root = make_tree(0, k, l, [], L)
    return root


P = [
    [1, 0, 1],
    [0, 1, 0],
    [1, 1, 0],
    [0, 0, 1]
]
k = 3
l = 1

ARGS = {
    "P": P,
    "k": k,
    "l": l
}
Setup block drafted by
a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API
Imports
none outside the standard library — import names as written, not package names to install; a name the repository itself provides is not a package
Returned
type Node — a Node output has no array shape of its own; none is stated — the instrument coerces any output to an array; for a Node output the recorded ndim 0 and dtype family float describe that coercion, not the output, and are not stated
Environment
image not recorded; re-verify against syntology-harvest-sandbox:v5-deps; not recorded for this sample: the harness installs a cuda-to-cpu shim (cuda_shim.py) before every sample and no run records whether a sample needed it; seed: none by the harness; any seed is in the setup block
make_hamming_vector Ran
ran on a synthesized input
probcomp/optimal-approximate-sampling/src/matrix.py
code served (permissive licence) · get_code("3ff5069ec587d49d")
How it ran

Ran in Syntology's sandbox on this synthesized input (drafted by a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API) and returned list, ndim 1, dtype family int; no output shape is stated. The image it ran in was not recorded. If your copy returns the same type and ndim on these inputs, it matched what we observed; nothing here checks that. It does NOT mean the output is correct: nothing has compared it to the paper.

import torch
import numpy as np

torch.manual_seed(0)

# Analyze the function:
# - P is indexed as P[r][c] where r ranges over N rows and c ranges over k columns
# - P is a 2D structure (list of lists)
# - The function sums across rows for each column
# - Returns a list of k sums

# Create a simple 2D list (matrix) with distinct dimensions
# Using 3 rows (N=3) and 4 columns (k=4) for distinctness
P = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12]
]

ARGS = {
    "P": P
}
Setup block drafted by
a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API
Imports
numpy, torch — import names as written, not package names to install; a name the repository itself provides is not a package
Returned
type list, ndim 1, dtype family int — a list output has no array shape of its own; none is stated
dtype family
int means an integer dtype; float means any other dtype the instrument saw, bool and complex included (fixture_check.py records only these two families)
Environment
image not recorded; re-verify against syntology-harvest-sandbox:v5-deps; not recorded for this sample: the harness installs a cuda-to-cpu shim (cuda_shim.py) before every sample and no run records whether a sample needed it; seed: none by the harness; any seed is in the setup block
make_leaf_table Ran
ran on a synthesized input
probcomp/optimal-approximate-sampling/src/tree.py
code served (permissive licence) · get_code("599e5c702aea357f")
How it ran

Ran in Syntology's sandbox on this synthesized input (drafted by a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API) and returned dict. The image it ran in was not recorded. If your copy returns the same type on these inputs, it matched what we observed; nothing here checks that. It does NOT mean the output is correct: nothing has compared it to the paper.

import torch
import numpy as np

# Construct P: a list of lists where each inner list represents a binary pattern
# The function iterates through levels (columns) and rows
# P[row][level] should be 0 or 1
# Let's create a simple example: 3 rows, 4 levels
P = [
    [1, 0, 1, 0],
    [0, 1, 0, 1],
    [1, 1, 0, 0]
]

ARGS = {
    'P': P
}
Setup block drafted by
a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API
Imports
numpy, torch — import names as written, not package names to install; a name the repository itself provides is not a package
Returned
type dict — a dict output has no array shape of its own; none is stated — the instrument coerces any output to an array; for a dict output the recorded ndim 0 and dtype family float describe that coercion, not the output, and are not stated
Environment
image not recorded; re-verify against syntology-harvest-sandbox:v5-deps; not recorded for this sample: the harness installs a cuda-to-cpu shim (cuda_shim.py) before every sample and no run records whether a sample needed it; seed: none by the harness; any seed is in the setup block
pack_tree Ran
ran on a synthesized input
probcomp/optimal-approximate-sampling/src/packing.py
code served (permissive licence) · get_code("97a14f39df6e7aa7")
How it ran

Ran in Syntology's sandbox on this synthesized input (drafted by a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API) and returned int, ndim 0, dtype family int, shape () as a later run recorded it. The image it ran in was not recorded. If your copy returns the same type, ndim and shape on these inputs, it matched what we observed; nothing here checks that. It does NOT mean the output is correct: nothing has compared it to the paper.

import numpy as np

class TreeNode:
    def __init__(self, label=None, left=None, right=None):
        self.label = label
        self.left = left
        self.right = right
        self.loc = None

# Build a small tree structure
# Tree with internal nodes and leaf nodes
left_leaf = TreeNode(label=5)
right_leaf = TreeNode(label=3)
root = TreeNode(label=None, left=left_leaf, right=right_leaf)

# Create encoding array large enough to hold the tree
# For a binary tree with 3 nodes, we need enough space
enc = np.zeros(10, dtype=np.int64)

offset = 0

ARGS = {
    'enc': enc,
    'node': root,
    'offset': offset
}
Setup block drafted by
a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API
Imports
numpy — import names as written, not package names to install; a name the repository itself provides is not a package
Returned
type int, ndim 0, dtype family int, shape () — shape () as a later run recorded it
dtype family
int means an integer dtype; float means any other dtype the instrument saw, bool and complex included (fixture_check.py records only these two families)
Environment
image not recorded; re-verify against syntology-harvest-sandbox:v5-deps; not recorded for this sample: the harness installs a cuda-to-cpu shim (cuda_shim.py) before every sample and no run records whether a sample needed it; seed: none by the harness; any seed is in the setup block
construct_sample_ky_encoding Not yet run
unverified (harvested, no recorded run)
probcomp/optimal-approximate-sampling/src/construct.py
code served (permissive licence) · get_code("7f7a7496ddb342a9")
How it ran

no invocation recorded.

construct_sample_ky_matrix Not yet run
unverified (harvested, no recorded run)
probcomp/optimal-approximate-sampling/src/construct.py
code served (permissive licence) · get_code("6f620229d6782cd4")
How it ran

no invocation recorded.

construct_sample_ky_matrix_cached Not yet run
unverified (harvested, no recorded run)
probcomp/optimal-approximate-sampling/src/construct.py
code served (permissive licence) · get_code("8c103a34014ef59a")
How it ran

no invocation recorded.

find_optimal_indexes Not yet run
unverified (harvested, no recorded run)
probcomp/optimal-approximate-sampling/src/opt.py
code served (permissive licence) · get_code("30463725333b18bb")
How it ran

no invocation recorded.

kernel_pchi2 Not yet run
unverified (harvested, no recorded run)
probcomp/optimal-approximate-sampling/src/divergences.py
code served (permissive licence) · get_code("b542fca2f1e4b985")
How it ran

no invocation recorded.

make_ddg_matrix Not yet run
unverified (harvested, no recorded run)
probcomp/optimal-approximate-sampling/src/matrix.py
code served (permissive licence) · get_code("8d3912840cbc2ad0")
How it ran

no invocation recorded.

make_matrix Not yet run
unverified (harvested, no recorded run)
probcomp/optimal-approximate-sampling/src/matrix.py
code served (permissive licence) · get_code("18fdfd1e058d844d")
How it ran

no invocation recorded.

make_tree Not yet run
unverified (harvested, no recorded run)
probcomp/optimal-approximate-sampling/src/tree.py
code served (permissive licence) · get_code("4303f40052d64e52")
How it ran

no invocation recorded.

sample_ky_encoding Not yet run
unverified (harvested, no recorded run)
probcomp/optimal-approximate-sampling/src/sample.py
code served (permissive licence) · get_code("b8308fdb20d40153")
How it ran

no invocation recorded.

sample_ky_matrix Not yet run
unverified (harvested, no recorded run)
probcomp/optimal-approximate-sampling/src/sample.py
code served (permissive licence) · get_code("f19d056c1eb9addc")
How it ran

no invocation recorded.

sample_ky_matrix_cached Not yet run
unverified (harvested, no recorded run)
probcomp/optimal-approximate-sampling/src/sample.py
code served (permissive licence) · get_code("2ff3534a77da0bc7")
How it ran

no invocation recorded.

Also present in other papers' code

Of 22 samples lifted from this paper's linked repositories, 22 carry a function identity and 0 do not. Of the 22 distinct functions with an identity, 0 are also present in other papers whose code we hold (0 with at least one paper dated earlier, 0 the same month, 0 later) and 22 are only here among the 52,977 papers whose code Syntology holds (as of 2026-09-26).

Only here means: among the 52,977 papers whose code Syntology holds (51,887 with lifted samples, 1,090 through their assemblies only), as of 2026-09-26, no other paper's lifted samples or current assembly bricks contain an identical function body after normalisation.

Presence, not direction: an identical function body in two papers' repositories does not say who wrote it, which came from which, or that either paper's method rests on it. Matching is exact after normalisation, so a renamed or edited function is not matched. Dates are when papers appeared, not when code was written. Only .py files the harvester lifted are covered; notebooks are not read. A new-style arXiv id YYMM.NNNN dates a paper to the month 20YY-MM; otherwise Paper.year dates it to the year; otherwise it is undated. Dates are when the paper appeared, not when the code was written. Read 2026-11-21.

Repositories linked to this paper

Some links come from the archived Papers with Code dataset (CC BY-SA 4.0): attribution and licence.

Abstract

This paper addresses a fundamental problem in random variate generation: given access to a random source that emits a stream of independent fair bits, what is the most accurate and entropy-efficient algorithm for sampling from a discrete probability distribution $(p_1, \dots, p_n)$, where the probabilities of the output distribution $(\hat{p}_1, \dots, \hat{p}_n)$ of the sampling algorithm must be specified using at most $k$ bits of precision? We present a theoretical framework for formulating this problem and provide new techniques for finding sampling algorithms that are optimal both statistically (in the sense of sampling accuracy) and information-theoretically (in the sense of entropy consumption). We leverage these results to build a system that, for a broad family of measures of statistical accuracy, delivers a sampling algorithm whose expected entropy usage is minimal among those that induce the same distribution (i.e., is "entropy-optimal") and whose output distribution $(\hat{p}_1, \dots, \hat{p}_n)$ is a closest approximation to the target distribution $(p_1, \dots, p_n)$ among all entropy-optimal sampling algorithms that operate within the specified $k$-bit precision. This optimal approximate sampler is also a closer approximation than any (possibly entropy-suboptimal) sampler that consumes a bounded amount of entropy with the specified precision, a class which includes floating-point implementations of inversion sampling and related methods found in many software libraries. We evaluate the accuracy, entropy consumption, precision requirements, and wall-clock runtime of our optimal approximate sampling algorithms on a broad set of distributions, demonstrating the ways that they are superior to existing approximate samplers and establishing that they often consume significantly fewer resources than are needed by exact samplers.

For agents

The same record, over MCP at https://syntology.ai/mcp:

get_harvested_code_for_paper("2001.04555")
get_code_for_paper("2001.04555")
have("2001.04555")

The run record, dated, one paper per request, free:

curl https://syntology.ai/api/ran/2001.04555.json

A badge for a README (the split and the date, never a ratio):

[![Syntology run record](https://syntology.ai/api/ran/2001.04555.svg)](https://syntology.ai/paper/2001.04555)

Connect an agent — have() is free.