BayesSampler
This page explains the BayesSampler algorithm given in Solomonoff Induction and Singular Integrals by Will Troiani and Daniel Murfet (2026).
The input is an infinite bit-string ω = ω₁ω₂…. The algorithm reads it from left to right and writes symbols z₁, z₂, … in sequence, where each zᵢ is a length-b block, for some fixed b > 0. Here, we take b = 3.
Consider the parameter space W = [0,1]² and block size b = 3. The prior φ is uniform on W.
Each symbol s = (s₁, s₂, s₃) ∈ {0,1}³ contains three bits, independent conditional on w. Each bit is 1 with probability r(w).
Divide each square into four equal squares. In the j-th dyadic partition, each cell has side length 2−j and prior mass 4−j.
For a cell D in the j-th dyadic partition of W, the prior mass equals its area:
| Partition | Side length | Mass per cell |
|---|---|---|
| j = 1 | ½ | ¼ |
| j = 2 | ¼ | 1/16 |
| j = 3 | ⅛ | 1/64 |
Only selected cells are colored. The full j-th partition contains 4ʲ cells.
For t ≥ 1, define
Han–Hoshi interval algorithm
The interval algorithm of Han and Hoshi (1997), Interval algorithm for random number generation, samples from a finite distribution by reading an infinite input bit-string from left to right.
Partition [0,1) into consecutive outcome intervals whose lengths are the required probabilities. Start with I = [0,1). Read the next bit: 0 keeps the lower half of I; 1 keeps the upper half. Repeat until I lies wholly inside one outcome interval, then select that outcome.
| SampleChild(D) | Given an infinite input bit-string, use the Han–Hoshi algorithm to sample a dyadic child D′ of D with probability φ(D′)/φ(D). |
|---|---|
| StringSample(w) | Given an infinite input bit-string, use the Han–Hoshi algorithm to sample and write a block s ∈ {0,1}ᵇ with probability p(s ∣ w). Here b = 3. |
Successive calls read the same input bit-string, continuing from the current input head. Each call starts a new interval I = [0,1).
Choose a cell D or a parameter point w, and fix an infinite input bit-string ω, whose first 48 bits are shown below. Each example starts at ω₁.
The BayesSampler algorithm
W = [0,1]²
Outlines: sampled cells. Shading: current cell.
Points: the centers wt.
Let X₁, X₂, …, Xₙ i.i.d. ∼ q, for any distribution q on 𝔹³. Write Xⁿ = X₁X₂⋯Xₙ for their concatenation. For the uniform prior on W, the Bayesian evidence is
Write zⁿ = z₁z₂⋯zₙ for the first n output blocks. Holding the observed data fixed, the probability over fair random input bits of producing that sequence is
From this, it is easy to show the main theorem of the paper.
For every n and every observed sequence,
Fix a universal monotone Turing machine U. Its Solomonoff distribution is
Here μ is the fair-bit measure and z ⊑ U(ω) means that the output begins with the finite string z.
Main theorem
If X₁, …, Xₙ i.i.d. ∼ q and the singular learning theory hypotheses in Appendix B of the paper also hold, then