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 permutations in a revealed switching environment

For n=2dn = 2^d and any deterministic starting deck, after J(s0+1)J(s_0 + 1) sweeps with s0=400s_0 = 400 and J=40000J = 40000, the conditional free-slot law satisfies sup⁡initial layoutsEE∥νE−Un/2∥TV→0\sup_{\text{initial layouts}} \mathbb{E}_{\mathcal{E}} \|\nu_{\mathcal{E}} - U_{n/2}\|_{\mathrm{TV}} \to 0 as d→∞d \to \infty. Consequently, the full-deck law approaches uniform uniformly in the starting deck after 16 040 400d16\,040\,400d physical shuffles, while for every integer t≥0t \ge 0 the full-deck distance from uniform after tt physical shuffles is at least 1−2tn/2/n!1 - 2^{tn/2}/n!, establishing that the full-deck mixing time is of order dd.

For any feasible specification ee of the outside label paths through a finite interval, conditional on ee all switch values on edges incident to an outside card are fixed and all other switch values are independent fair bits. Every completion induces a permutation ge=ιT−1Teι0∈Smg_e = \iota_T^{-1} T_e \iota_0 \in S_m whose conditional law depends on the outside paths and positions but not on the incoming assignment of free labels, and on consecutive intervals the corresponding permutations multiply with later intervals on the left.

For all sufficiently large dd, every ordered list of k≤n/2k \le n/2 distinct labels, from every deterministic starting layout, has endpoint law within n−3n^{-3} in total variation of uniform ordered distinct positions after 400400 sweeps.

For n=2dn = 2^d, the full-deck law from any deterministic start has total-variation distance tending to zero from uniform after 171 798 691 968d171\,798\,691\,968d physical shuffles.

For n=2dn = 2^d, the full-deck law from any deterministic start has total-variation distance tending to zero from uniform after 33 030 144d33\,030\,144d physical shuffles.

Setting L=223L = 2^{23}, p=1−1/(2L)p = 1 - 1/(2L), and bb by (7.1), for n=2dn = 2^d the full-deck law from any deterministic start approaches uniform in total variation after 400bd400bd physical shuffles.

Methods

Conditional slot-bijection and path-cylinder construction that conditions on revealed outside-card trajectories to leave unexposed switches independent and fair, inducing a random permutation on SmS_m via increasing slot indices that composes by convolution on consecutive intervals.

Source excerpts

“For any feasible specification e of their paths through a finite interval, conditional on e all switch values on edges incident to an outside card are fixed, and all other switch values are independent fair bits.” · Show in paper

Two-sweep coarse-block L2L^2 contraction and negative-dependence preservation under partial symmetrization for preparing ordered half-decks and bounding partial mixing.

Source excerpts

“We use a two-sweep mechanism. From a balanced blocked set, one sweep contracts fluctuations within large subcubes. It may leave averages that differ between subcubes, but the same sweep makes the expected energy of those output averages small. Combining the two estimates in the next sweep will contract the whole vector.” · Show in paper

Preparation-interval truncation and active-sweep truncation combined with fixed-point character bounds (Larsen-Shalev), reciprocal-square degree sums, and Schur-conjugation operator-norm contraction over chunks.

Source excerpts

“Partition the time here into chunks, each a preparation interval of s0 sweeps and then an active interval of one sweep. ... After averaging over the actual preparation paths, we need joint domination by a uniform endpoint free set and an independent uniform slot permutation; this will permit a Schur conjugation average.” · Show in paper

Reset minorization via Nummelin splitting on forward/reverse partial mixing kernels to generate central relative-permutation increments between two copies sharing a switch environment.

Source excerpts

“Here we instead extract an exact uniform component from a long reset block. Uniformly placing the free labels makes the relative increment of two copies central, so a return probability can be computed by characters.” · Show in paper

Trajectory-overlay construction that XORs predictable independent extra switches onto a base shuffle, combined with a randomized linear change of frame and a three-round row-column-row shuffle on transverse partitions analyzed via a contingency-table local limit theorem.

Source excerpts

“In our overlay construction we supply these switches from fresh arrays of independent fair coins independent of the base arrays. Form the actual layer coins on the location pairs by xoring the corresponding extra bits (0 where absent) with the base bits.” · Show in paper

Two-half occupancy-history conditioning that reveals only two-color slot occupancy to obtain independent internal half-permutations, combined with inverse-image and buffer-complement truncations and a conditional-product Fourier transfer.

Source excerpts

“For the second block, reveal only which slots contain each of two colors at every layer. That observation leaves independent internal permutations of the two colors. We will trim their large tuple marginals and combine them with inverse-image information from the first block.” · Show in paper