Polynomial time relatively computable triangular arrays for almost sure convergence.

*(English)*Zbl 07088306Summary: We start from a discrete random variable, \(\mathbf{O}\), defined on \((0,1)\) and taking on \(2^{M+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, \(\mathbf{X}_i\), of \(\mathbf{O}\) and let \(\mathbf{S}_n:=\sum_{i=1}^n \mathbf{X}_i\). We let \(\mathbf{S}_n^\ast\) be the quantile of \(\mathbf{S}_n\). If \(\mathbf{O}\) is Rademacher, the sequence \(\{\mathbf{S}_n\}\) is the equiprobable random walk on \(\mathbb{Z}\) with domain \((0,1)\). In the general case, \(\mathbf{S}_n\) follows a multinomial distribution and as \(\mathbf{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 \(\mathbf{X}_1,\ldots,\mathbf{X}_n\) provide a representation of \(\mathbf{S}_n\) that is strong in that their sum is equal to \(\mathbf{S}_n\) pointwise. They represent \(\mathbf{S}_n^\ast\) only in distribution. Are there strong representations of \(\mathbf{S}_n^\ast\)? 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, \(\pi_n\), of \(\{0,\ldots,2^{n(M+1)}-1\}\), with the property that we call admissibility. Passing to sequences, \(\{\pi_n\}\), of admissible permutations, these provide a complete classification of trim, strong triangular array representations of the sequence \(\{S_n^\ast\}\). We explicitly construct two sequences of admissible permutations which are polynomial time computable, relative to a function \(\tau_1^{\mathbf{O}}\) which embodies the complexity of \(\mathbf{O}\) itself. The trim, strong triangular array representation corresponding to the second of these is as close as possible to the representation of \(\{\mathbf{S}_n\}\) provided by the \(\mathbf{X}_i\).

The \(\mathbf{X}_1,\ldots,\mathbf{X}_n\) provide a representation of \(\mathbf{S}_n\) that is strong in that their sum is equal to \(\mathbf{S}_n\) pointwise. They represent \(\mathbf{S}_n^\ast\) only in distribution. Are there strong representations of \(\mathbf{S}_n^\ast\)? 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, \(\pi_n\), of \(\{0,\ldots,2^{n(M+1)}-1\}\), with the property that we call admissibility. Passing to sequences, \(\{\pi_n\}\), of admissible permutations, these provide a complete classification of trim, strong triangular array representations of the sequence \(\{S_n^\ast\}\). We explicitly construct two sequences of admissible permutations which are polynomial time computable, relative to a function \(\tau_1^{\mathbf{O}}\) which embodies the complexity of \(\mathbf{O}\) itself. The trim, strong triangular array representation corresponding to the second of these is as close as possible to the representation of \(\{\mathbf{S}_n\}\) provided by the \(\mathbf{X}_i\).

##### MSC:

60G50 | Sums of independent random variables; random walks |

60F15 | Strong limit theorems |

60F05 | Central limit and other weak theorems |

68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |

68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |

68Q25 | Analysis of algorithms and problem complexity |

##### Software:

OEIS
PDF
BibTeX
XML
Cite

\textit{V. Dobrić} et al., Ill. J. Math. 63, No. 2, 219--257 (2019; Zbl 07088306)

**OpenURL**

##### References:

[1] | P. W. Beame, S. A. Cook, and H. J. Hoover, Log depth circuits for division and related problems, SIAM J. Comput. 15 (1986), 994-1003. · Zbl 0619.68047 |

[2] | P. Berti, L. Pratelli, and P. Rigo, Skorohod representation theorem via disintegrations, Sankhya A 72 (2010), 208-220. · Zbl 1209.60005 |

[3] | P. Berti, L. Pratelli, and P. Rigo, A Skorohod representation theorem for uniform distance, Probab. Theory Related Fields 150, nos. 1-2 (2011), 321-335. |

[4] | P. Clote and E. Kranakis, Boolean Functions and Computation Models, Springer, Berlin, Heidelberg, New York, 2002. · Zbl 1016.94046 |

[5] | G. Davie, The Borel-Cantelli lemmas, probability laws and Kolmogorov complexity, Ann. Probab. 28, no. 6 (2001), 1426-1434. · Zbl 1017.60002 |

[6] | V. Dobrić and P. Garmirian, A new direct proof of the Central Limit Theorem, Illinois J. Math. 61, nos. 3-4 (2017), 355-370. |

[7] | V. Dobrić, P. Garmirian, and L. J. Stanley, Polynomial time relatively computable triangular arrays in a multinomial setting, preprint, arXiv:1603.06006. |

[8] | V. Dobrić, M. Skyers, and L. J. Stanley, Polynomial time computable triangular arrays for almost sure convergence, preprint, arXiv:1603.04896. |

[9] | W. L. Fouché, The descriptive complexity of Brownian motion, Adv. Math. 155 (2000), 317-343. |

[10] | W. L. Fouché, Kolmogorov complexity and the geometry of Brownian motion, Math. Structures Comput. Sci. 25, no. 7 (2015), 1590-1606. · Zbl 1361.68110 |

[11] | P. M. Garmirian, The Central Limit Theorem and the estimation for the concentration of measure for fractional Brownian motion, Ph.D. dissertation, Lehigh University, 2013. |

[12] | W. Hesse, E. Allender, and D. A. M. Barrington, Uniform constant-depth threshold circuits for division and iterated multiplication. J. Comput. Syst. Sci. 65 (2002), 695-716. · Zbl 1059.68044 |

[13] | A. Khintchine, Über dyadische brüche. Math. Z. 18 (1923), 109-116. · JFM 49.0132.01 |

[14] | B. Kjos-Hanssen and A. Nerode, Effective dimension of points visited by Brownian motion, Theoret. Comput. Sci. 410, nos. 4-5, 347-354. · Zbl 1158.68017 |

[15] | B. Kjos-Hanssen, and T. Szabados, Kolmogorov complexity and strong approximation of Brownian motion, Proc. Amer. Math. Soc. 139 (2011), 3307-3316. · Zbl 1244.68043 |

[16] | A. Kolmogoroff, Über das gesetz des iterierten logarithmus, Math. Ann. 101 (1929), 126-135. · JFM 55.0298.01 |

[17] | The On-Line Encyclopedia of Integer Sequences, published electronically at http://oeis.org. · Zbl 1044.11108 |

[18] | C. H. Papadimitriou, Computational Complexity. Addison-Wesley, Reading, Massachusetts, 1994. |

[19] | A. V. Skorokhod, Limit theorems for stochastic processes, Theory Probab. Appl. 1 (1956), 261-290. |

[20] | M. Skyers, A tale of two sequences: a story of convergence, weak and almost sure, Ph.D. dissertation, Lehigh University, 2012. |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.