By OpenAISourceGitHub

Manuscripts from openai/math

Fork
Clone
git clone https://openversions.com/git/index/openai-math.git
Cite
Version link
https://openversions.com/index/openai-math/commit/dfd8c46870b48511e697cbb43a3c8c91d375fa2f
Version identifier (commit hash)
dfd8c46870b48511e697cbb43a3c8c91d375fa2f

Fork to create your own copy with credit to the source. Clone to get a Git copy on your computer.

All papers

Claims

Findings

Conditional information under deterministic coordinate sweeps

Uniformly over deterministic starting decks and specified ordered lists of distinct labels, as d→∞d \to \infty: (1) at time 256d256d, the images of any k≤7n/8k \le 7n/8 labels have total-variation distance o(1)o(1) from Unif(inj([k],V))\mathrm{Unif}(\mathrm{inj}([k], V)); (2) at time 1024d1024d, the images of any k≤15n/16k \le 15n/16 labels have total-variation distance at most n−3/2n^{-3/2} for all sufficiently large dd; and (3) the full permutation law satisfies ∥qd∗(2048d)−USn∥TV→0\|q_d^{*(2048d)} - U_{S_n}\|_{\mathrm{TV}} \to 0, giving tmix(d)≤2048dt_{\mathrm{mix}}(d) \le 2048d for all sufficiently large dd.

For any fixed 0<p<10 < p < 1, set BB of r0r_0 base labels, and disjoint ordered list (a1,…,ak)(a_1, \dots, a_k) with r0+k−1≤pnr_0 + k - 1 \le pn, after T=2b(p)dT = 2b(p)d steps (where b(p)=⌈10/cp⌉b(p) = \lceil 10/c_p \rceil, cp=−18log⁡2((3+p)/4)c_p = -\frac{1}{8}\log_2((3+p)/4)), E∥L((ΠT(aj))j=1k∣HB)−Unif(inj([k],AB))∥TV≤kn−4\mathbb{E}\|\mathcal{L}((\Pi_T(a_j))_{j=1}^k \mid \mathcal{H}_B) - \mathrm{Unif}(\mathrm{inj}([k], A_B))\|_{\mathrm{TV}} \le kn^{-4} for all sufficiently large dd depending only on pp.

For the Thorp shuffle on n=2dn = 2^d, worst-start total-variation convergence to uniform holds at: (1) 8192d8192d via the sixteen-subgroup orbit-span argument; (2) 16384d16384d via predictable coset caps; (3) 400⋅222d400 \cdot 2^{22}d via diagram peeling; and (4) 16000d16000d via the covariance and four-subgroup coefficient argument.

For the Thorp shuffle on n=2dn = 2^d positions, ∥qd∗2052d−UG∥TV→0\|q_d^{*2052d} - U_G\|_{\mathrm{TV}} \to 0 as d→∞d \to \infty, and in particular d≤tmix(d)≤2052dd \le t_{\mathrm{mix}}(d) \le 2052d for all sufficiently large dd.

Let H⊆{0,1}dH \subseteq \{0,1\}^d be deterministic with ∣H∣≥n/4|H| \ge n/4, and let ff be a deterministic real vector supported on HH with ∑xf(x)=0\sum_x f(x) = 0. Evolving (H,f)(H,f) by the conditional signed-mass rule in the same coordinate order in each sweep, the energy Eb\mathcal{E}_b after bb sweeps satisfies EEb≤n−(b−1)/64E0\mathbb{E}\mathcal{E}_b \le n^{-(b-1)/64}\mathcal{E}_0 for all sufficiently large dd and every integer b≥1b \ge 1, which yields tmix(d)≤18456dt_{\mathrm{mix}}(d) \le 18456d for sufficiently large dd.

There is an absolute positive integer CC such that for the law μ\mu after CdCd physical shuffles and a uniform (n/256)(n/256)-subset RR of input labels, ERD(μ−R∥u−R)=O(n−3)=o(1)\mathbb{E}_R D(\mu_{-R} \| u_{-R}) = O(n^{-3}) = o(1), and the full permutation law after 32Cd32Cd physical shuffles tends to uniform in total variation from every starting deck.

The worst-start full-deck total-variation distance tends to zero after 30000d30000d physical Thorp shuffles via three-group amplification.

For the physical Thorp shuffle on N=2dN = 2^d cards, ∥qd∗(1327104d)−USN∥TV→0\|q_d^{*(1327104d)} - U_{S_N}\|_{\mathrm{TV}} \to 0, and with L=256L = 256, q=N−N/Lq = N - N/L, and ww the law after 16384d16384d physical shuffles, EIKL(wI∥uq)=O(d4)\mathbb{E}_I \mathrm{KL}(w_I \| \mathbf{u}_q) = O(d^4).

For the physical Thorp shuffle on n=2dn = 2^d positions, ∥qd∗(100000d+1)−USn∥TV→0\|q_d^{*(100000d+1)} - U_{S_n}\|_{\mathrm{TV}} \to 0, and after B=5dB = 5d physical shuffles with h≥n/8h \ge n/8 hidden labels, the conditional transition matrix KK satisfies Q(i,j)=E[(KK⊤)ij]≥(1−n−1/100)/hQ(i,j) = \mathbb{E}[(KK^\top)_{ij}] \ge (1 - n^{-1/100})/h for all pairs i,ji, j of initial available positions.

Methods

Conditional path-flow and adapted-noise scalar recurrence: tracking the centered conditional law ft(x)=Pr⁡{Πt(a)=x∣Ht}−1Vt(x)/∣Vt∣f_t(x) = \Pr\{\Pi_t(a) = x \mid \mathcal{H}_t\} - \mathbf{1}_{V_t}(x)/|V_t| under the deterministic cyclic coordinate schedule via the finite-memory identity at=∑j=1d2−jwt−ja_t = \sum_{j=1}^d 2^{-j} w_{t-j} and opposite-half balance.

Source excerpts

“Lemma 3.1 (Finite memory of the centered noise). For either the conditional tagged vector or the signed-vector evolution just defined, put ξt = ft+1 − Pitft, wt = E P x∈V ft(x)21{xit∈/Vt}.” · Show in paper

Walsh-coordinate derivation of finite-memory weights: expanding fsf_s in the Boolean Walsh character basis f^s(A)\widehat{f}_s(A) and counting characters whose last active coordinate was updated at each preceding layer.

Source excerpts

“Lemma 6.1 (Walsh derivation). For A ⊆ {1, . . . , d}, define bfs(A) = P x fs(x)(−1) P i∈A xi . If is ∈/ A, then bfs+1(A) = bfs(A). If is ∈ A, then E (bfs+1(A)2 | Fs) = Ls.” · Show in paper

Bitwise autocorrelation recurrence with reversed-schedule two-sided Fourier transfer: tracking vt(z)=E∑x∈Vft(x)ft(x⊕z)v_t(z) = \mathbb{E}\sum_{x\in V} f_t(x)f_t(x\oplus z) and applying predictable subprobability caps in both forward and reversed coordinate schedules.

Source excerpts

“Lemma 8.2 (Finite-memory identity). For every t ≥ 0, vt+1 = vtLh(t) + 1 2 bt(δ0 − δeh(t)).” · Show in paper

Prefix-tree symmetry and hierarchical energy recursion: decomposing expected energy over coordinate blocks and using invariance under binary prefix-tree automorphisms Ad\mathcal{A}_d after a completed sweep to contract energy at every subsequent sweep.

Source excerpts

“Lemma 10.3 (Prefix-tree invariance). For every deterministic initial (H, f), the output law of one sweep is invariant under (H′, f′) 7→ (gH′, gf′) for every g ∈ Ad.” · Show in paper

Replica entropy coupling and isolated-path cancellation: coupling a replica path to bound EIKL(wI∥uq)\mathbb{E}_I \mathrm{KL}(w_I \| \mathbf{u}_q) via partner-repeat counts, combined with an alternating-sum cancellation kernel F∗F_* for one untruncated sweep on small-dimension representations.

Source excerpts

“We construct a replica path, starting at the same position as X, that will be on reference trajectories of unobserved labels.” · Show in paper

Reverse-probe coupling for fixed reservoirs: tracing possible partner positions backward to the initial hidden set using reverse paths coupled to independent uniform probes to lower-bound the mean collision matrix.

Source excerpts

“From each Zs, trace backward through the base process to time a; membership in As is equivalent to the trace’s endpoint lying in Aa. Compare these traces with independent ideal probes, starting at the same words and prepending independent fair bits while dropping the last bit at each reverse step.” · Show in paper