Polynomial time relatively computable triangular arrays for almost sure convergence

We start from a discrete random variable, O, defined on (0,1) and taking on 2M+1 values with equal probability—any member of a certain family whose simplest member is the Rademacher random variable (with domain (0,1)), whose constant value on (0,1/2) is −1. We create (via left-shifts) independent copies, Xi, of O and let Sn:=∑i=1nXi. We let Sn∗ be the quantile of Sn. If O is Rademacher, the sequence {Sn} is the equiprobable random walk on Z with domain (0,1). In the general case, Sn follows a multinomial distribution and as O varies over the family, the resulting family of multinomial distributions is sufficiently rich to capture the full generality of situations where the Central Limit Theorem applies. The X1,…,Xn provide a representation of Sn that is strong in that their sum is equal to Sn pointwise. They represent Sn∗ only in distribution. Are there strong representations of Sn∗? We establish the affirmative answer, and our proof gives a canonical bijection between, on the one hand, the set of all strong representations with the additional property of being trim and, on the other hand, the set of permutations, πn, of {0,…,2n(M+1)−1}, with the property that we call admissibility. Passing to sequences, {πn}, of admissible permutations, these provide a complete classification of trim, strong triangular array representations of the sequence {Sn∗}. We explicitly construct two sequences of admissible permutations which are polynomial time computable, relative to a function τ1O which embodies the complexity of O itself. The trim, strong triangular array representation corresponding to the second of these is as close as possible to the representation of {Sn} provided by the Xi.