OctoInformBeta

OpenAI preprint, September 2026 · §2. Words and strict drift · §2

Proposition 2.4 [Strict drift]: Almost-sure finiteness of the first survivor time and expected orders at most 1/(2p)<11/(2p) < 1 with finite-horizon covariance and variance bounds

Strict backward drift of inventory streams for p∈(1/2,1)p \in (1/2, 1)..

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

In the inventory-stream encoding of Fortuin-Kasteleyn (FK) random planar maps with Potts parameter q>4q > 4, setting t=qt = \sqrt{q} gives an order-type probability p=t/(t+2)∈(1/2,1)p = t/(t+2) \in (1/2, 1). Letters are drawn from a five-symbol alphabet of two burger types and three order types (two fixed orders, one for each burger type, and one flexible order). As a finite word is read, unmatched burgers accumulate on a stack stored freshest-first, and each order consumes the freshest eligible burger.

For p∈(1/2,1)p \in (1/2, 1) and an infinite sequence of random letters drawn from this alphabet, prefixes may be reduced backwards in time from the origin. The problem is whether a surviving burger appears after finitely many backward steps almost surely, and how the expected number of unmatched orders at that stopping time is bounded in terms of pp alongside finite-horizon covariance and variance bounds for letter signs.

The Inventory Alphabet and Stream Law

An FK model parameter pp is a real number satisfying 1/2<p<11/2 < p < 1.✦ The set 𝔹\mathbb{B} of boolean burger types is the two-element set {true,false}\{\mathrm{true}, \mathrm{false}\}. An inventory order oo is an element of the three-element set 𝒪\mathcal{O} consisting of the flexible order *\ast and one fixed order for each boolean type b∈𝔹b \in \mathbb{B}.✦ A letter aa of the burger-order alphabet 𝒜\mathcal{A} is either a burger token of boolean type b∈𝔹b \in \mathbb{B} or an order token carrying an inventory order o∈𝒪o \in \mathcal{O}.✦

An inventory stack evaluation state ξ=(O(ξ),B(ξ))\xi = (O(\xi), B(\xi)) is a pair consisting of a list O(ξ)O(\xi) of pending orders in 𝒪\mathcal{O} and a list B(ξ)B(\xi) of boolean burger types in 𝔹\mathbb{B} stored freshest-first.✦ Given a finite word ww of letters in 𝒜\mathcal{A} and an evaluation state ξ\xi, the word evaluation ℰ(w,ξ)\mathcal{E}(w, \xi) is the evaluation state equal to ξ\xi when ww is empty, and equal on a nonempty word with leading letter a∈𝒜a \in \mathcal{A} and suffix w′w' to the word evaluation of w′w' from the state obtained by updating ξ\xi with the single-step stack transition on aa.✦ The word reduction R(w)R(w) of a finite word ww of letters in 𝒜\mathcal{A} is the evaluation state ℰ(w,ξ0)\mathcal{E}(w, \xi_0) starting from the state ξ0\xi_0 whose pending-order and burger lists are both empty.✦

The letter mass function mp:𝒜→ℝm_p : \mathcal{A} \to \mathbb{R} of an FK model parameter p∈(1/2,1)p \in (1/2, 1) is the real-valued function given by mp(a)={1/4if a is a burger,p/2if a is the flexible order,(1−p)/4if a is a fixed order.m_p(a) = \begin{cases} 1/4 & \text{if } a \text{ is a burger}, \\ p/2 & \text{if } a \text{ is the flexible order}, \\ (1-p)/4 & \text{if } a \text{ is a fixed order}. \end{cases}(1) The letter distribution νp\nu_p on 𝒜\mathcal{A} for p∈(1/2,1)p \in (1/2, 1) is the probability distribution assigning mass mp(a)m_p(a) to each letter a∈𝒜a \in \mathcal{A}.✦ Given an index set ι\iota and p∈(1/2,1)p \in (1/2, 1), the independent and identically distributed (i.i.d.) inventory stream measure ℙpι\mathbb{P}_p^{\iota} on 𝒜ι\mathcal{A}^{\iota} is the product probability measure whose coordinate marginals equal νp\nu_p; for ι=ℕ\iota = \mathbb{N} we write Ω=𝒜ℕ\Omega = \mathcal{A}^{\mathbb{N}}, ℙp=ℙpℕ\mathbb{P}_p = \mathbb{P}_p^{\mathbb{N}}, and 𝔼p\mathbb{E}_p for expectation under ℙp\mathbb{P}_p.✦

Backward Stopping Time and Terminal Statistics

Given a set EE and an integer-valued process Z=(Zn)n∈ℕZ = (Z_n)_{n \in \mathbb{N}} on EE, the first hitting time of zero τ0(Z)(ω)∈ℕ∪{∞}\tau_0(Z)(\omega) \in \mathbb{N} \cup \{\infty\} at ω∈E\omega \in E is the extended natural number in ℕ∪{∞}\mathbb{N} \cup \{\infty\} given by the least n∈ℕn \in \mathbb{N} such that Zn(ω)=0Z_n(\omega) = 0, or ∞\infty if Zn(ω)≠0Z_n(\omega) \ne 0 for every n∈ℕn \in \mathbb{N}.✦ For a sequence x=(xk)k∈ℕ∈Ωx = (x_k)_{k \in \mathbb{N}} \in \Omega and a length n∈ℕn \in \mathbb{N}, the revealed word wn(x)w_n(x) is the finite word (xn−1,xn−2,…,x0)(x_{n-1}, x_{n-2}, \dots, x_0) obtained by reversing the prefix (xi)0≤i<n(x_i)_{0 \le i < n} (the empty word when n=0n = 0).✦ At step n∈ℕn \in \mathbb{N} of a sequence x∈Ωx \in \Omega, the survivor indicator In(x)∈ℤI_n(x) \in \mathbb{Z} is the integer equal to 11 if the burger list B(R(wn+1(x)))B(R(w_{n+1}(x))) is empty, and equal to 00 otherwise.✦ The first backward survivor time J(x)∈ℕ∪{∞}J(x) \in \mathbb{N} \cup \{\infty\} of a sequence x∈Ωx \in \Omega is the extended natural number τ0(I)(x)\tau_0(I)(x), the first hitting time of zero of the survivor indicator process (In)n∈ℕ(I_n)_{n \in \mathbb{N}}.✦

The unmatched order count K(x)∈ℕK(x) \in \mathbb{N} of a sequence x∈Ωx \in \Omega is the natural number given by K(x)={|O(R(wJ(x)+1(x)))|if J(x)<∞,0if J(x)=∞,K(x) = \begin{cases} \bigl|O\bigl(R(w_{J(x)+1}(x))\bigr)\bigr| & \text{if } J(x) < \infty, \\ 0 & \text{if } J(x) = \infty, \end{cases}(2)✦ where |L||L| denotes the length of a list LL. At horizon m∈ℕm \in \mathbb{N}, the truncated order count Km(x)∈ℝK_m(x) \in \mathbb{R} of a sequence x∈Ωx \in \Omega is the real-valued quantity given by Km(x)={K(x)if J(x)<m,0otherwise.K_m(x) = \begin{cases} K(x) & \text{if } J(x) < m, \\ 0 & \text{otherwise.} \end{cases}(3)✦

Setting j(x)=J(x)j(x) = J(x) when J(x)<∞J(x) < \infty and j(x)=0j(x) = 0 when J(x)=∞J(x) = \infty, the first survivor type α(x)∈𝔹\alpha(x) \in \mathbb{B} of a sequence x∈Ωx \in \Omega is the boolean type of the first (freshest) entry in B(R(wj(x)+1(x)))B(R(w_{j(x)+1}(x))), defaulting to false\mathrm{false} if that burger list is empty.✦ The boolean type sign σ(b)∈ℤ\sigma(b) \in \mathbb{Z} of b∈𝔹b \in \mathbb{B} is the integer equal to 11 if b=trueb = \mathrm{true} and −1-1 if b=falseb = \mathrm{false}.✦ The first survivor sign T(x)∈ℝT(x) \in \mathbb{R} of a sequence x∈Ωx \in \Omega is the real number σ(α(x))\sigma(\alpha(x)).✦

Assigned Increments, Covariance, and Sum Variance

Given an inventory order o∈𝒪o \in \mathcal{O} and a reference boolean r∈𝔹r \in \mathbb{B}, the assigned order type γ(o,r)∈𝔹\gamma(o, r) \in \mathbb{B} is the boolean equal to bb if oo is a fixed order of type bb, and equal to rr if oo is the flexible order *\ast.✦ The assigned letter sign s(a,r)∈ℤs(a, r) \in \mathbb{Z} of a letter a∈𝒜a \in \mathcal{A} relative to a reference boolean r∈𝔹r \in \mathbb{B} is the integer defined by s(a,r)={σ(b)if a is a burger of type b∈𝔹,−σ(γ(o,r))if a is an order o∈𝒪.s(a, r) = \begin{cases} \sigma(b) & \text{if } a \text{ is a burger of type } b \in \mathbb{B}, \\ -\sigma(\gamma(o, r)) & \text{if } a \text{ is an order } o \in \mathcal{O}. \end{cases}(4)✦

Given n∈ℕn \in \mathbb{N} and a sequence x∈Ωx \in \Omega, the shifted letter stream θnx∈Ω\theta^n x \in \Omega is the sequence defined by (θnx)k=xn+k(\theta^n x)_k = x_{n+k} for every k∈ℕk \in \mathbb{N}.✦ At index n∈ℕn \in \mathbb{N} of a sequence x∈Ωx \in \Omega, the assigned increment Dn(x)∈ℤD_n(x) \in \mathbb{Z} is the integer given by Dn(x)=s(xn,α(θn+1x)).D_n(x) = s\bigl(x_n,\, \alpha(\theta^{n+1} x)\bigr).(5)✦ The partial sum of assigned increments Sm(x)∈ℤS_m(x) \in \mathbb{Z} of a sequence x∈Ωx \in \Omega over m∈ℕm \in \mathbb{N} steps is the integer Sm(x)=∑i=0m−1Di(x),S_m(x) = \sum_{i=0}^{m-1} D_i(x),(6)✦ with S0(x)=0S_0(x) = 0.

Under parameter p∈(1/2,1)p \in (1/2, 1) at horizon m∈ℕm \in \mathbb{N}, the inventory covariance Cp(m)C_p(m) with TT is the real number defined by Cp(m)=∫ΩT(x)Sm(x)dℙp(x).C_p(m) = \int_{\Omega} T(x)\, S_m(x)\, d\mathbb{P}_p(x).(7) At horizon m∈ℕm \in \mathbb{N} under parameter p∈(1/2,1)p \in (1/2, 1), the inventory sum variance Vp(m)∈ℝV_p(m) \in \mathbb{R} is the real number given by Vp(m)=∫ΩSm(x)2dℙp(x).V_p(m) = \int_{\Omega} S_m(x)^2\, d\mathbb{P}_p(x).(8)✦

The Claim

Theorem 1. Let p∈(1/2,1)p \in (1/2, 1). Under the inventory stream measure ℙp\mathbb{P}_p, the first backward survivor time JJ and the unmatched order count KK satisfy ℙp(J<∞)=1,\mathbb{P}_p(J < \infty) = 1,(9)✦ 𝔼p[K]≤12p,\mathbb{E}_p[K] \le \frac{1}{2p},(10)✦ and 𝔼p[K]<1,\mathbb{E}_p[K] < 1,(11)✦ while the extended nonnegative Lebesgue integral of KK in [0,∞][0, \infty] satisfies ∫ΩK(x)dℙp(x)≤1.\int_{\Omega} K(x)\, d\mathbb{P}_p(x) \le 1.(12)✦ For every m∈ℕm \in \mathbb{N}, the covariance Cp(m)C_p(m) and sum variance Vp(m)V_p(m) obey 2𝔼p[Km]≤Cp(m)2\,\mathbb{E}_p[K_m] \le C_p(m)(13)✦ and Vp(m+1)−Vp(m)≤1−2p𝔼p[Km].V_p(m+1) - V_p(m) \le 1 - 2p\,\mathbb{E}_p[K_m].(14)✦

In the paper, the result reads: the stopping time JJ is almost surely finite, and 𝔼p[K]≤1/(2p)<1\mathbb{E}_p[K] \le 1/(2p) < 1, where 𝔼p\mathbb{E}_p stands for the paper’s expectation 𝔼\mathbb{E}. Here p∈(1/2,1)p \in (1/2, 1) acts on the backward-revealed stream ℙp\mathbb{P}_p, separating the stopping claim (9) and the drift pair (10) and (11) while adding the extended-integral bound (12) and the finite-horizon inequalities (13) and (14).

What Is Checked

The claim is stated for any parameter p∈(1/2,1)p \in (1/2, 1) over the i.i.d. product measure ℙp\mathbb{P}_p on burger-order letter sequences, for the backward word-reduction stopping time JJ and terminal order count KK, and at any horizon m∈ℕm \in \mathbb{N} for the truncated count KmK_m alongside the covariance Cp(m)C_p(m) and sum variance Vp(m)V_p(m) of partial sums of shifted assigned increments.