Tropical Sampler

Tropical Sampler is a Monte Carlo integrator for integrals, over positive variables, of products of polynomials with positive coefficients raised to powers. It takes the monomial exponent vectors and the powers and returns an unbiased estimate with a statistical error bar, and the exact rational value of the simplified ("tropical") integral it samples from. It is a Python implementation by BootLoops of the tropical sampling algorithm of Michael Borinsky, Anna-Laura Sattelberger, Bernd Sturmfels and Simon Telen (Algorithm 1 of arXiv:2204.06414), whose own Julia program is on MathRepo.

What it does

The integrals have the form

$$ Z \;=\; C\int_{\mathbb{R}_+^E} \prod_k Q_k(t)^{u_k}\,\prod_{e=1}^{E}(1+t_e)^{-c}\,dt , $$

where every $Q_k$ has positive coefficients (no cancellation between terms, or "subtraction-free"), the $u_k$ are real powers, and $c$ is large enough for convergence. Such integrals appear as marginal likelihoods in Bayesian statistics, as generalized hypergeometric integrals, and as Feynman and string integrals in parametric form.

In logarithmic variables $y=\log t$, replacing each polynomial by its largest monomial makes the log of the integrand piecewise linear. This is the tropical approximation. The linear pieces live on cones fixed by the Newton polytopesthe Newton polytope of a polynomial is the convex hull of the exponent vectors of its monomials of the $Q_k$. Together the cones form the normal fanthe division of direction space into cones according to which vertex of a polytope is the extreme one in that direction of the polytopes' Minkowski sum (the set of all sums of one point from each polytope), with a unit segment per variable added for the decay factors.

On a cone spanned by integer rays $r_i$, the columns of a matrix $R$, the approximate integral is elementary, $c_\sigma=|\det R|/\prod_i\beta_i$, with $\beta_i\gt0$ the decay rate along $r_i$. The sampler works in three steps.

Two variants cut the variance and stay unbiased. The stratified one allocates samples per cone from a pilot run (Neyman allocation). The tilted one also fits the slope of the log-weight along each ray and lowers the exponential rates to match (never raises them, so the weights stay bounded). When the powers are large, as when they count data, only the tilted variant converges usefully.

The pilot-based allocation and the tilting are BootLoops additions to Algorithm 1. The authors' program already allocates samples cone by cone, in proportion to the cone integrals.

The sampler has these limits:

The cegm_gj scripts. A companion set of scripts sits in the same package directory, under cegm_gj/. It uses the same cone decomposition, with deterministic high-precision quadrature in place of sampling, for the Grassmannian string integral on $X(3,6)$ (the space of six points in the plane) of Arkani-Hamed, He and Lam (arXiv:1912.08707). Splitting an integral over the cones of the normal fan and mapping each cone to the unit cube is the sector decomposition of the paper of Borinsky, Sattelberger, Sturmfels and Telen.

The integrand has four positive variables and twenty $3\times3$ minors raised to kinematic powers, in the positive coordinates of Giménez Umbert and Sturmfels (arXiv:2501.10805). Log space splits into 48 maximal cones, refined to 52 simplicial ones.

Mapped to the unit cube, each cone's integrand is smooth, so tensor-product Gauss–Jacobi quadrature in arbitrary precision converges geometrically in the nodes per axis $n$, which quadrature over the undivided domain does not. A value counts as correct to $D$ digits only when two runs at different $n$ and working precision agree to $D$ digits, rounded down. Kinematic points, fan and certificates are specific to $X(3,6)$.

On its 52-cone decomposition cegm_gj computed the $X(3,6)$ integral to 60 digits at one kinematic point and 32 at a second. The sampler gave Monte Carlo values of five-taxon (five-species) marginal-likelihood integrals, checked against exactly known ones. The integrals themselves are described on the Grassmannian string integral and Phylogenetics pages.

Examples

Build a fan and check it. The fan has two variables and one polynomial with power 2 whose Newton polytope is the unit square. The decay $c=7$ per variable is entered as a segment from the origin to each unit vector with weight $-7$. With NumPy and SciPy installed (see Requirements), run this from the package directory tools/tropical-sampler/:

import numpy as np
from fractions import Fraction
from tropical_sampler import build_fan, tiling_probe

E = 2
pat  = np.array([[0, 0], [1, 0], [0, 1], [1, 1]], dtype=np.int64)
seg1 = np.array([[0, 0], [1, 0]], dtype=np.int64)
seg2 = np.array([[0, 0], [0, 1]], dtype=np.int64)
groups = [(2, pat), (-7, seg1), (-7, seg2)]

rng = np.random.default_rng(0)
fan = build_fan(groups, E, rng)
ok, cmin, cmax = tiling_probe(fan, rng, nprobe=500)

extra = np.array([[0, 0], [2, 1], [1, 2]], dtype=np.int64)
fan2 = build_fan(groups, E, rng, refine_extra=extra)

fan['cones'] holds 4 cones, the four quadrants, each a dict with the ray matrix R, gradient g, rates beta and exact csigma ($1$, $\tfrac14$, $\tfrac14$, $\tfrac1{16}$). fan['Itr'] is Fraction(25, 16), and tiling_probe returns (True, 1, 1): each of 500 random directions lies in exactly one cone. With the triangle extra added at weight zero, fan2 has 7 cones and the same Fraction(25, 16).

Estimate the integral. On the same fan the polynomial is $Q(t)=\sum_{D\subseteq\{1,2\}}\prod_{e\in D}(1+4t_e)=(2+4t_1)(2+4t_2)$ with $u=2$, and $N=5$ so that $c=7$ matches the segment weights:

from tropical_sampler import make_eval_data, estimate_logZ, estimate_logZ_tilt

N, u = 5, 2
Dsets = [frozenset(), frozenset({0}), frozenset({1}), frozenset({0, 1})]
evdata = make_eval_data([(u, Dsets)], E)

logZ, se_rel, mean_w, se_w, wmin, wmax = estimate_logZ(
    fan, evdata, N, E, 200_000, rng, 0.0)
logZ_t, se_rel_t, Zint, n_used, wmin_t, wmax_t = estimate_logZ_tilt(
    fan, evdata, N, E, 20_000, 200_000, rng, 0.0)

The last argument is $\log C$, and 0.0 returns the bare integral. estimate_logZ draws 200,000 points, and its relative standard error here is a few parts in a thousand. estimate_logZ_tilt takes a pilot size and a main size. This small integral factorizes into two Beta-function integrals and equals $(22/15)^2\approx2.151$, so exp(logZ) should sit within a few error bars of it.

Routines

tropical_sampler.py has one command-line mode, the self-test. The other commands are scripts under cegm_gj/.

CommandWhat it does
tropical_sampler.py --selftestBuilds the two-variable fan of the first example and runs its checks
t3_prod.py sanity [--procs P] [--engine E]Evaluates the integral at the first built-in kinematic point over all 52 cones and compares with the stored reference value
t3_prod.py cert --point {1,2}Writes point{N}_certificate.json: kinematics, exact momentum conservation, convergence conditions, minimum decay rate over the 52 cones, fan checksum
t3_prod.py run --point {1,2} --n N --prec BITS [--procs P] [--cpp C] [--engine E]Re-derives the certificate, computes one high-precision value and writes it with its settings to run_p{point}_n{N}_b{BITS}.json
gates.py A B [--bar D] [--relmax R]Counts the agreeing digits of two run JSONs or decimal strings, rounded down; exits 0 at D or more (default 30)
bank.pyReassembles the recorded $X(3,6)$ values from the run JSONs in the directory named in the environment variable CEGM_GJ_RUNDIR, recomputing every two-run comparison
tropical_cones.pyBuilds the 48-cone, 52-subcone fan with its coverage check and writes fan_x36.json to the current directory

Notes on the cegm_gj commands:

The functions are imported from tropical_sampler.py.

FunctionWhat it returns
build_fan(groups, E, rng)The exact normal fan as dict(cones, Itr, E); refine_extra adds a weight-zero polytope
tiling_probe(fan, rng, nprobe)(ok, min_cover, max_cover) from the check that random directions each lie in exactly one cone
make_eval_data(patterns, E)The arrays that log_weight uses
log_weight(Y, evdata, N, E)Log of true integrand over tropical integrand at a block of points in log coordinates, one per row
sample_tropical(fan, nsamples, rng)A generator of blocks of points drawn from the tropical density
estimate_logZ(fan, evdata, N, E, nsamples, rng, ln_prefac)Plain estimator: (logZ, relative_stderr, mean_w, se_w, wmin, wmax)
estimate_logZ_strat(fan, evdata, N, E, n_pilot, n_main, rng, ln_prefac)Stratified by cone with pilot-based allocation: (logZ, relative_stderr, Z_int, n_used, wmin, wmax)
estimate_logZ_tilt(fan, evdata, N, E, n_pilot, n_main, rng, ln_prefac)Stratified with tilting, same tuple; the variant for large powers

groups is a list of (weight, integer point set) pairs: a polynomial with weight $u_k$, or a variable's segment with weight $-c$. patterns is a list of (u_k, Dsets), with Dsets a list of frozensets of variable indices, where repeats count as multiplicity.

The lower-level routines (idet, primitive_normal, hull_vertices, minkowski_vertices, ln_fraction) are defined in tropical_sampler.py. GUIDE.md in the package lists the modules of cegm_gj/.

Requirements

Source and references

The code is tools/tropical-sampler/ in the BootLoops repository.

ReferenceWhat it supplies
M. Borinsky, A.-L. Sattelberger, B. Sturmfels and S. Telen, "Bayesian integrals on toric varieties", arXiv:2204.06414; code: BayesianIntegralsThe sampling algorithm (Algorithm 1) and the sector decomposition over the cones of the normal fan
M. Borinsky, arXiv:2008.12310The tropical Monte Carlo method on which the sampling algorithm is built
N. Arkani-Hamed, S. He and T. Lam, "Stringy canonical forms", arXiv:1912.08707The Grassmannian string integral and its convergence conditions
B. Giménez Umbert and B. Sturmfels, "Splitting CEGM amplitudes", arXiv:2501.10805The positive coordinates and the split-kinematics reference value

← back to the tools index