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

Optimal-order mixing of the Thorp shuffle

The Thorp shuffle on n=2dn = 2^d cards mixes in Θ(d)\Theta(d) complete shuffles: as d→∞d \to \infty, ∥qd∗(1600d)−Un∥TV→0\|q_d^{*(1600d)} - U_n\|_{\mathrm{TV}} \to 0, while for every integer t≥0t \ge 0, ∥qd∗t−Un∥TV≥1−2tn/2n!\|q_d^{*t} - U_n\|_{\mathrm{TV}} \ge 1 - \frac{2^{tn/2}}{n!}, yielding tmix(d)≥⌈2nlog⁡23n!4⌉=2d−O(1)t_{\mathrm{mix}}(d) \ge \lceil \frac{2}{n} \log_2 \frac{3n!}{4} \rceil = 2d - O(1) and tmix(d)=Θ(d)t_{\mathrm{mix}}(d) = \Theta(d).

For every t≥dt \ge d, the expected squared norm Et=E∥wt∥22E_t = \mathbb{E}\|w_t\|_2^2 of the centered conditional flow satisfies the one-sweep energy identity Et=∑j=1d2−jbt−jE_t = \sum_{j=1}^d 2^{-j} b_{t-j}, where bs=ELsb_s = \mathbb{E} L_s is the expected noise contribution.

For n=2dn = 2^d, T=200dT = 200d, 1≤k≤7n/81 \le k \le 7n/8, and an ordered list C=(c1,…,ck)C = (c_1, \dots, c_k) chosen uniformly among all lists of distinct labels independently of the shuffle, EC∥L((ΠT(c1),…,ΠT(ck))∣C)−Uinj∥TV≤εn:=n3/22(31/32)198d+32e−n/256=O(n−5/2)\mathbb{E}_C \|\mathcal{L}((\Pi_T(c_1), \dots, \Pi_T(c_k)) \mid C) - U_{\mathrm{inj}}\|_{\mathrm{TV}} \le \varepsilon_n := \frac{n^{3/2}}{2} \sqrt{(31/32)^{198d} + 32 e^{-n/256}} = O(n^{-5/2}).

The reciprocal-degree sums of irreducible representations of SsS_s satisfy C1:=sup⁡s≥1∑λ⊢s(fλ)−1<∞C_1 := \sup_{s \ge 1} \sum_{\lambda \vdash s} (f^\lambda)^{-1} < \infty and ∑λ⊢s,λ∉{(s),(1s)}(fλ)−1→0\sum_{\lambda \vdash s, \lambda \notin \{(s), (1^s)\}} (f^\lambda)^{-1} \to 0 as s→∞s \to \infty.

For nn a positive multiple of 88, if a probability measure ν\nu on G=SnG = S_n satisfies ν(gHa)≤4∣Ha∣/∣G∣\nu(g H_a) \le 4 |H_a|/|G| for all g∈Gg \in G and 1≤a≤81 \le a \le 8 (where HaH_a fixes every label outside block MaM_a of size n/8n/8), then every irreducible unitary representation ρ\rho of GG of degree DD satisfies ∥ν^(ρ)∥op≤AD−5/16\|\widehat{\nu}(\rho)\|_{\mathrm{op}} \le A D^{-5/16} with A=32C1A = \sqrt{32 C_1}.

Methods

Cyclic-coordinate frame change Xt=R−tYtX_t = R^{-t} Y_t converting physical Thorp shuffles into independent matching switches along successive coordinate directions.

Source excerpts

“If Yt = RStYt−1 is the physical permutation, started from Y0 = id, and Xt = R−tYt , then Xt+1 = QtXt , Qt = R −tSt+1R t . The Qt are independent matching switches in the directions it = 1+(t mod d), since R−t e1 = eit .” · Show in paper

Conditional flow with one sweep of memory, exposing the trajectories of ℓ\ell cards and tracking the centered conditional distribution wsw_s of a tagged card on the remaining positions.

Source excerpts

“For 0 ≤ ℓ < k ≤ n, expose the trajectories of its first ℓ cards, and call the next card the tagged card. Let Fs be the sigma-field generated by the list and the exposed paths through time s. Let Bs be the positions not occupied by those ℓ cards, so m = |Bs| = n − ℓ is constant. Define ps(x) = P{Πs(cℓ+1) = x | Fs}, ws(x) = ps(x) − 1 m 1Bs (x).” · Show in paper

Eight-block coset trimming and orbit-span Fourier bound, partitioning labels into eight equal blocks, removing heavy cosets to form a conditioned law ν\nu, and bounding ∥ν^(ρ)∥op\|\widehat{\nu}(\rho)\|_{\mathrm{op}} via restriction to H1×⋯×H8H_1 \times \dots \times H_8.

Source excerpts

“For each a, remove every coset C ∈ G/Ha with µ(C) > 2|Ha|/|G|, and let E be what remains after all eight removals.” · Show in paper

Finite-group Fourier method of Diaconis and Shahshahani applied to eight convolution factors of the trimmed law, with a separate coin-flipping argument for the sign representation.

Source excerpts

“The final comparison uses the finite-group Fourier method of Diaconis and Shahshahani [3, Section 3]. The shuffle law is not constant on conjugacy classes, so we retain matrix norms throughout.” · Show in paper