Polynomial time relatively computable triangular arrays for almost sure convergence
From MaRDI portal
Central limit and other weak theorems (60F05) Analysis of algorithms and problem complexity (68Q25) Sums of independent random variables; random walks (60G50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Strong limit theorems (60F15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Abstract: For 0 < x < 1, take the binary expansion with infinitely many 0's, replace each 0 with -1, this gives the polarized binary expansion of x. Let R_i(x) be the ith "polarized bit" and let S_n(x) be the sum of the first n R_i(x). {S_n} is the Z-valued random walk on (0,1). Normalize, by dividing each S_n by the square root of n: the resulting sequence converges weakly to the standard normal distribution on (0,1). The quantiles of S_n are random variables on (0,1), denoted S*_n, which are equal in distribution to the S_n, Skorokhod showed that the sequence of normalized quantiles converges almost surely to the standard normal distribution on (0,1). For n > 2, S*_n cannot be represented as the sum of the first n terms of a fixed sequence, R*_i, of random variables with the properties of the R_i. We introduce a method of constructing, for each n, an i.i.d family, R*_(n,1), ... R*_(n,n) which sums to S*_n, pointwise, as a function, not just in distribution. Each R*_(n,i) is a mean 0, variance 1 Rademacher random variable depending only on the first n bits. For each n, we get a bijection between the set of all such i.i.d. families, R*_(n,1), ... R*_(n,n), and the set of all admissible permutations of {0, ..., (2^n)-1}. Varying n, any doubly indexed such family, gives a triangular array representation of the sequence {S*_n} which is strong (because for each n, S*_n is the pointwise sum of the R*_(n,i)). Such representations are classified by sequences of admissible permutations. We show that the complexity of any sequence of admissible permutations is bounded below by that of 2^n. We explicitly construct three such polynomial time computable sequences whose complexity is bounded above by that of the function SBC (sum of binomial coefficients). We also initiate the study of some additional fine properties of admissible permutations.
Recommendations
- On the convergence of moments in the CLT for triangular arrays with an application to random polynomials
- Sharp orders of convergence in the random central limit theorem
- A central limit theorem for numbers satisfying a class of triangular arrays
- A nearly independent, but non-strong mixing, triangular array
- Limit Theorems for the Maximal Random Sums
Cites work
- scientific article; zbMATH DE number 610968 (Why is no real title available?)
- scientific article; zbMATH DE number 2024859 (Why is no real title available?)
- scientific article; zbMATH DE number 953683 (Why is no real title available?)
- A Skorohod representation theorem for uniform distance
- A new direct proof of the central limit theorem
- Effective dimension of points visited by Brownian motion
- Kolmogorov complexity and strong approximation of Brownian motion
- Kolmogorov complexity and the geometry of Brownian motion
- Log Depth Circuits for Division and Related Problems
- Polynomial time relatively computable triangular arrays for almost sure convergence
- Skorohod representation theorem via disintegrations
- The Borel-Cantelli lemmas, probability laws and Kolmogorov complexity
- The descriptive complexity of Brownian motion
- Uniform constant-depth threshold circuits for division and iterated multiplication.
Cited in
(3)
This page was built for publication: Polynomial time relatively computable triangular arrays for almost sure convergence
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2315247)
