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.

Run
Input
ω₁ ω₂ ω₃ ω₄ ω₅ ω₆ ω₇ ω₈ ω₉ …
Output
z₁ z₂ z₃ …
3 tape squares

Consider the parameter space W = [0,1]² and block size b = 3. The prior φ is uniform on W.

r(w) = (4 + w₁ + w₂) / 16
p(s ∣ w) = ∏ᵢ₌₁³ r(w)sᵢ(1 − r(w))1−sᵢ

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.

2⁻¹ 2⁻² 2⁻³ W = [0,1]² 4⁻¹ 4⁻² 4⁻² 4⁻³ 4⁻³ 4⁻³ 4⁻³

For a cell D in the j-th dyadic partition of W, the prior mass equals its area:

φ(D) = area(D) = (2⁻ʲ)² = 4⁻ʲ
PartitionSide lengthMass 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

j(t) := min{j ∈ ℕ | 2j ≥ (27/2)t²}

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 ω₁.

0 bits read in this call
Input ω
W = [0,1]²
011 w₁ w₂
Outcome · probability
Outcomes
01

The BayesSampler algorithm

D ← W; j ← 0
Loop over t = 1, 2, 3, …:
While j < j(t):
D ← SampleChild(D); j ← j + 1
wt ← center of D
StringSample(wt)
Step 0
Input ω
0 bits read
Output z
0 symbols
SampleChildStringSampleinput head

W = [0,1]²

Outlines: sampled cells. Shading: current cell.
Points: the centers wt.

1
0
0
D ← W; j ← 0
Loop over t = 1, 2, 3, …:
While j < j(t):
D ← SampleChild(D); j ← j + 1
wt ← center of D
StringSample(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

Zₙ(Xⁿ) = ∫W ∏ₜ₌₁ⁿ p(Xₜ ∣ w) dw.

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

ℙ(zⁿ = Xⁿ) := ℙ(z₁ = X₁, …, zₙ = Xₙ)
|ℙ(zⁿ = Xⁿ) − Zₙ(Xⁿ)| → 0 as n → ∞.

From this, it is easy to show the main theorem of the paper.

For every n and every observed sequence,

e⁻ᶜ Zₙ(Xⁿ) ≤ ℙ(zⁿ = Xⁿ) ≤ eᶜ Zₙ(Xⁿ), C = π²/6.

Fix a universal monotone Turing machine U. Its Solomonoff distribution is

M(z) := μ{ω ∈ 𝔹ᴺ | z ⊑ U(ω)}.

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

−log M(Xⁿ) ≤ nLₙ(w₀) + λ log n − (m − 1) log log n + Oℙ(1).