Acceptance probabilities and logarithmic-space derandomization

Source and verification

This article explains family 103 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Space-bounded computation and randomness

For an input of length $n$, a logarithmic-space machine has $O(\log (n+2))$ writable bits. It may reread its input on a read-only tape. An address or a counter up to a fixed polynomial in $n$ fits in this space, but an entire polynomial-length random tape does not.

The class $\mathsf{L}$ consists of problems decided by halting deterministic machines with this workspace. With the input heads confined between endmarkers, such a machine has only polynomially many complete configurations. A halting deterministic execution cannot revisit one, so its time is automatically polynomial.

The randomized classes here also require polynomial running time on every random tape, with fresh independent fair bits:

• $\mathsf{RL}$ has acceptance probability zero on NO inputs and at least $1/2$ on YES inputs.
• $\mathsf{BPL}$ has acceptance probability at most $1/3$ on NO inputs and at least $2/3$ on YES inputs.

All simultaneously live counters, saved calls, and numerical registers count toward the space bound. A recursion using logarithmic space at each of logarithmically many active levels can use squared-logarithmic space in total.

🏷️ The acceptance-probability claim

Manuscript statement

For every fixed polynomial-time randomized logarithmic-space machine $\mathcal{M}$, there is one uniform deterministic algorithm which, on input $(x,1^q)$ with $q\ge 1$, outputs an integer $a$ such that

$$\begin{array}{c}0\le a\le 2^{q+2},\\ \left|a{2}^{-(q+2)}-p_{\mathcal{M}}(x)\right|\le 2^{-q}.\end{array}$$

Its space is $O(\log (n+2)+q)$ and its time is $(n+2{)}^{O(1)}{2}^{O(q)}$. Constants may depend on the fixed machine. The precision request is unary. (OpenAI, 2026)

For fixed $q=3$, the returned estimate is at most $11/24$ on a BPL NO input and at least $13/24$ on a YES input. Comparing with $1/2$ gives a deterministic logarithmic-space decision procedure. Together with the elementary containments, the manuscript concludes

$$\mathsf{L}=\mathsf{RL}=\mathsf{BPL}.$$

For $q=O(\log n)$, the same quantitative statement gives inverse-polynomial accuracy in polynomial time and logarithmic space. For general $q$, the time is exponential in precision. “Exact derandomization” in the title refers to the deterministic decision of the language, not exact output of an arbitrary acceptance probability.

🏷️ A finite matrix representation

Add a time coordinate to the machine configuration, up to its polynomial worst-case bound, and pad halted runs to the final time. Let $V_0$ be the resulting polynomial-size set. The matrix $S$ records one-step transition probabilities to the next time layer; lost mass may represent rejection. Thus $S$ is nonnegative, has row sums at most one, and is strictly forward in time.

For an indicator $e$ of accepting terminal configurations, acceptance probabilities satisfy

$$\begin{array}{rl}{p}_0& =e+S{p}_0,\\ p_0& =(I-S{)}^{-1}e=\sum _{j=0}^T{S}^{j}e.\end{array}$$

The inverse is a finite sum because $S^{T+1}=0$. This is a representation of the target; it does not by itself give a small-space algorithm for evaluating it.

For example, a computation accepting only after two consecutive successful fair-bit tests has a path with two transitions of probability $1/2$. The relevant entry of $S^{2}e$ is $1/4$. A general machine has many merging paths, and enumerating paths directly may take exponential time even when their endpoints have short addresses.

🏷️ Corrections, copies, and a fixed target

Write $B=\Theta (\log (n+2))$. The manuscript constructs successive transition systems on copies of configurations, with accumulated reward vectors $W_l$. A designated primary-copy chain $z_l$ satisfies

$$0\le p_0(x_0)-W_l(z_l)\le |V_0|2^{-(H-1)l},$$

where $H\ge 4$ is fixed. Consequently $O(B)$ stages suffice for any fixed inverse-polynomial target error, while the number of vertices at each stage remains $2^{O(B)}$.

One elementary identity explains how a correction can change transitions while preserving the target equation. Given a transition matrix $C$ and a correction $E$, put

$$D=C-E+EC.$$

Then $I-D=(I+E)(I-C)$. If $(I-C)p=W$, it follows that $(I-D)p=(I+E)W$. The removed transition contribution is transferred into the reward. The actual construction must additionally preserve positivity and control support; the identity alone gives neither property.

Detectors suppress corrections in columns receiving too many substantial entries. Copying distributes large entries, while an ordered-support estimate bounds the truncation error. The exact matrices and conditional expectations define mathematical targets, rather than arrays stored by the algorithm.

🏷️ From an averaged moment to one starting state

The estimator uses one shared finite environment $\sigma$ described by $O(B)$ bits. A retention test selects vertices at rate comparable to $f=2^{-HL}$. Let $X_f(v)$ be its indicator and ${\pi }_f=\mathrm{Pr}[X_f(v)=1]$. Write ${\Delta }_v={\overline{W}}_L(v)-W_L(v)$ for the error of the actual recursively implemented estimator. The source proves the eighth-moment estimate

$$\frac{1}{N}{\mathbb{E}}_{\sigma }\sum _{v\in V_L}\frac{X_f(v)}{f}|{\Delta }_v{|}^8\le C^8{2}^{-8p},$$

where $N$ bounds the stage size and $p$ is a statistical accuracy parameter. This is an average over vertices. Keeping only the nonnegative summand for the required start $z_L$ gives

$$\begin{array}{rl}& \mathbb{E}\left[|{\Delta }_{z_L}{|}^8\mid X_f(z_L)=1\right]\\ & \le N\frac{f}{{\pi }_f}{C}^8{2}^{-8p}.\end{array}$$

The factor $N$ cannot be dropped. Markov’s inequality bounds the conditional probability of error greater than $\eta$ by this quantity divided by ${\eta }^8$. Because $\log N=O(B)$ and ${\pi }_f$ is comparable to $f$, choosing $p$ as a sufficiently large multiple of $B$ leaves more than three quarters of the conditional environments accurate. Hierarchy truncation and numerical error must be paid separately.

The estimator’s factors share randomness and depend on earlier estimates. The proof therefore tracks conditional means, retained endpoints, and error from releasing old source addresses; it does not multiply error bounds as though the factors were independent. A mixing theorem supplies the conditional averaging interface. Its group-theoretic derivation lies beyond these computational preliminaries.

🏷️ Median enumeration without storing the estimates

Once each environment can be evaluated in $O(B)$ space, enumerate all encodings satisfying $X_f(z_L)=1$ and take a median. Enumeration must retain the original encoding multiplicities, because those multiplicities define the conditional distribution for which the moment estimate was proved.

The median need not be stored as a sorted list. With a fixed dyadic output grid of $2^{O(B)}$ possible values, repeated scans can count how many estimates lie below a candidate threshold. The current encoding, threshold, and counts require only $O(B)$ bits. Polynomially many evaluations remain polynomial time, provided every evaluation terminates in logarithmic space.

This last proviso includes inaccurate environments. An estimator that halts only on statistically good choices cannot be exhaustively enumerated in this way. The source’s controller proves termination and a total space bound for every environment, independently of accuracy.

🏷️ Paying for the entire recursion stack

The difficult implementation uses short fingerprint keys instead of a full vertex address at every level. Since candidate endpoints depend on earlier comparisons, a collision bound for one fixed pair is insufficient. The analysis first constructs candidate sets independent of the current block’s fingerprint bits, then charges departures from those sets to lower-level errors.

Each numerical query requests one bounded binary digit of the same fixed estimator value. Increasing precision does not change the sampled lists defining that value. A shared cursor and reversible local access rules allow old addresses to be recovered rather than kept on the stack.

For a parent call with recursion allowance $w$ and digit place $t$, and a child with allowance $w^{\prime }$ and digit place $j$, the controller bounds retained local data by

$$A(w-w^{\prime })+D(t-j).$$

The allowance decreases, and any increase in the digit place is limited by that decrease. Summing these differences along the active call chain telescopes. The environment, cursor, scratch space, and shared auxiliary bit vector are counted once. This is the mechanism behind a total $O(B)$ bound; a separate $O(B)$ bound for each frame would not suffice.

The manuscript also describes a compiler taking a source program and supplied resource bounds. Those bounds are hypotheses on the source, not properties the compiler decides. The present review covers the acceptance theorem and its stated proof architecture; it does not independently establish this implementation or the statistical estimates.

🏷️ Key steps and proof outlines

Separating three errors before taking a median

The final argument in “A dyadic approximation at the specified start” has three numerical objects: the true acceptance probability $p$, the deterministic hierarchy reward $W_L(z)$ at the designated copied start $z$, and the implemented estimate ${\overline{W}}_L(z)$. A finite digit expansion introduces a raw truncated value ${\tilde{v}}_{\sigma }$, indexed by the master environment $\sigma$, followed by $v_{\sigma }=\min \{1,\max \{0,{\tilde{v}}_{\sigma }\}\}$. For a target scale $\Delta$, the construction arranges

$$\begin{array}{rl}|p-W_L(z)|& \le \Delta /8,\\ |W_L(z)-{\overline{W}}_L(z)|& \le \Delta /8,\\ |{\overline{W}}_L(z)-{\tilde{v}}_{\sigma }|& <\Delta /8.\end{array}$$

The first bound is deterministic, the second holds on most retained environments, and the third follows from truncation. Because $W_L(z)\in [0,1]$, clipping satisfies $|v_{\sigma }-W_L(z)|\le |{\tilde{v}}_{\sigma }-W_L(z)|$. These bounds therefore imply $|p-v_{\sigma }|<3\Delta /8$ on a majority of the correct conditional environment law. This division is useful because increasing digit precision improves only the third error; it does not repair the estimator’s statistical error. (OpenAI, 2026)

Paying for a specified coordinate

From an integrated moment to one start

If the averaged retained eighth moment is at most $C^8{2}^{-8p_0}$, then the conditional eighth moment at a specified vertex is at most $N(f/{\pi }_f)C^8{2}^{-8p_0}$, where $N$ is the domain bound, $f$ the nominal retention rate, and ${\pi }_f$ the actual retention probability.

The proof keeps only the nonnegative summand corresponding to $z$ in the integrated estimate. Since

$$\mathbb{E}\left[\frac{X_f(z)}{f}|{\Delta }_z{|}^8\right]=\frac{{\pi }_f}{f}\mathbb{E}[|{\Delta }_z{|}^8\mid X_f(z)=1],$$

division gives the asserted conditional moment. Markov’s inequality at threshold $\Delta /8$ then contributes the factor $(8/\Delta {)}^8$. Choosing the precision parameter $p_0$ larger by roughly $({\log }_{2}N)/8$ pays for the loss of selecting one vertex. Without this payment an average estimate could conceal a large error precisely at the start configuration.

The hierarchy depth pays a different bill. If $|V_0|\le 2^{C_{0}B}$ and its residual is bounded by $|V_0|2^{-(H-1)L}$, choose

$$L\ge \frac{C_{0}B+{\log }_2(1/\Delta )+3}{H-1}.$$

This makes the deterministic residual at most $\Delta /8$. Both depth and statistical precision remain proportional to $B$ when the requested accuracy is inverse-polynomial.

Recomputing order statistics without storing a sample list

The final estimator becomes deterministic by enumerating every admissible master environment, retaining those with $X_f(z)=1$. The source enumerates original random-bit encodings, including repeated encodings that happen to produce the same fingerprint. Those multiplicities matter: enumerating distinct fingerprints instead would generally change the probability law and invalidate the majority bound.

For each candidate dyadic numerator $a$, a pass counts environments with numerator at most $a$. Binary search finds the upper median. Only the search endpoints, a counter, the current environment and one numerator accumulator remain live. Each count recomputes values instead of storing the entire multiset. A majority of values in an interval forces its median into that interval, so this operation preserves the error guarantee.

The controller theorem supplies termination on every environment, including inaccurate ones. This is necessary for enumeration: a single nonterminating bad environment would prevent a median from being computed. A terminating deterministic computation using $O(B)$ work bits has only $2^{O(B)}$ complete configurations on a fixed input; repeating one would force an infinite loop. Consequently each digit query takes at most $2^{O(B)}$ time. Multiplying by the number of environments and polynomially many passes preserves that bound.

The arbitrary-precision result uses virtual padding to make $B=O(\log n+q)$. The padded input is accessed by addresses and never materialized. This last step simultaneously explains the linear dependence of space on $q$ and the exponential dependence of time on $q$.

See Also

• Mean-payoff algorithms likewise separates exact targets, numerical encoding length, and the resources used by recursive evaluation.
• Unique Games and approximation gaps uses randomness to describe deterministic reductions; that is a different role from simulating an arbitrary randomized machine.

🏷️ Manuscripts and verification scope

• Exact Derandomization of Logarithmic Space: L = RL = BPL — pinned manuscript and companion source.

No family scope page was present at lean/docs/103.md in the pinned snapshot. This does not establish that all related formalization code is absent. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. Exact Derandomization of Logarithmic Space: L = RL = BPL.