The statistics defined on symmetric permutation groups, particularly descent and inversion, have been extensively investigated due to their wide-ranging applications in areas such as card shuffling and sorting algorithms. Descent and inversion were shown to satisfy the central limit theorem by Tanny (1973) and Bender (1973), respectively. Since then, many mathematicians studied the error bounds associated with these approximations. Uniform bounds were first established by Fulman in 2004, while Chuntee and Neammanee (2013) and Sumritnorrapong et al. (2018) derived the non-uniform bounds. The latest work of non-uniform bounds from Sumritnorrapong et al. (2018) was not practical since their main theorems are valid for large $ n $ and $ z $ ($ n\ge7.07\times10^6 $ and $ |z|\ge 8\sqrt{3} $ for descent and $ n \ge 1.9 \times 10^8 $ and $ |z|\ge 24 $ for inversion). In this paper, we extended the theorem to hold for arbitrary $ n\in \mathbb{N} $ and $ z \in \mathbb{R} $. Moreover, our constants were sharper than previously seen. The approach in this work was done by combining Stein's method with the exchangeable pair technique.
Citation: Natthapol Dejtrakulwongse, Kritsana Neammanee, Suporn Jongpreechaharn. Non-uniform bounds in normal approximation for descent and inversion[J]. AIMS Mathematics, 2026, 11(2): 3903-3919. doi: 10.3934/math.2026157
The statistics defined on symmetric permutation groups, particularly descent and inversion, have been extensively investigated due to their wide-ranging applications in areas such as card shuffling and sorting algorithms. Descent and inversion were shown to satisfy the central limit theorem by Tanny (1973) and Bender (1973), respectively. Since then, many mathematicians studied the error bounds associated with these approximations. Uniform bounds were first established by Fulman in 2004, while Chuntee and Neammanee (2013) and Sumritnorrapong et al. (2018) derived the non-uniform bounds. The latest work of non-uniform bounds from Sumritnorrapong et al. (2018) was not practical since their main theorems are valid for large $ n $ and $ z $ ($ n\ge7.07\times10^6 $ and $ |z|\ge 8\sqrt{3} $ for descent and $ n \ge 1.9 \times 10^8 $ and $ |z|\ge 24 $ for inversion). In this paper, we extended the theorem to hold for arbitrary $ n\in \mathbb{N} $ and $ z \in \mathbb{R} $. Moreover, our constants were sharper than previously seen. The approach in this work was done by combining Stein's method with the exchangeable pair technique.
| [1] | J. Fulman, Stein's method and non-reversible Markov chains, Lecture Notes-Monograph Series, 46 (2004), 69–77. |
| [2] |
M. Sun, A central limit theorem on two-sided descents of Mallows distributed elements of finite Coxeter groups, Adv. Appl. Math., 174 (2026), 103025. https://doi.org/10.1016/j.aam.2025.103025 doi: 10.1016/j.aam.2025.103025
|
| [3] |
S.-M. Ma, J.-Y. Liu, J. Yeh, Y.-N. Yeh, Eulerian-type polynomials over Stirling permutations and box sorting algorithm, J. Comb. Theory A, 220 (2026), 106132. https://doi.org/10.1016/j.jcta.2025.106132 doi: 10.1016/j.jcta.2025.106132
|
| [4] |
R. R. X. Du, Y. Li, $ d $-Separated permutations and $ q $-Stirling numbers of the first kind, Adv. Appl. Math., 173 (2026), 102976. https://doi.org/10.1016/j.aam.2025.102976 doi: 10.1016/j.aam.2025.102976
|
| [5] |
M. Ahmia, J. L. Ramírez, D. Villamizar, Inversions in colored permutations, derangements, and involutions, Adv. Appl. Math., 173 (2026), 102999. https://doi.org/10.1016/j.aam.2025.102999 doi: 10.1016/j.aam.2025.102999
|
| [6] |
S. Elizalde, A bijection for descent sets of permutations with only even and only odd cycles, Eur. J. Combin., 132 (2026), 104280. https://doi.org/10.1016/j.ejc.2025.104280 doi: 10.1016/j.ejc.2025.104280
|
| [7] |
S. Tanny, A probabilistic interpretation of Eulerian numbers, Duke Math. J., 40 (1973), 717–722. https://doi.org/10.1215/S0012-7094-73-04065-9 doi: 10.1215/S0012-7094-73-04065-9
|
| [8] |
E. A. Bender, Central and local limit theorems applied to asymptotic enumeration, J. Comb. Theory A, 15 (1973), 91–111. https://doi.org/10.1016/0097-3165(73)90038-1 doi: 10.1016/0097-3165(73)90038-1
|
| [9] |
Y. Rinott, V. Rotar, On coupling constructions and rates in the CLT for dependent summands with applications to the antivoter model and weighted $U$-statistics, Ann. Appl. Probab., 7 (1997), 1080–1105. https://doi.org/10.1214/aoap/1043862425 doi: 10.1214/aoap/1043862425
|
| [10] |
W. Chuntee, K. Neammanee, Bounds on normal approximations for the number of descents and inversions, Commun. Stat.-Theor. M., 44 (2015), 2310–2329. https://doi.org/10.1080/03610926.2013.781642 doi: 10.1080/03610926.2013.781642
|
| [11] | K. Neammanee, P. Rattanawong, A uniform bound on the generalization of a combinatorial central limit theorem, Int. Math. Forum, 3 (2008), 11–27. |
| [12] |
W. Chuntee, K. Neammanee, Exponential bounds for normal approximation of the number of descents and inversions, Commun. Stat.-Theor. M., 46 (2017), 1218–1229. https://doi.org/10.1080/03610926.2015.1014109 doi: 10.1080/03610926.2015.1014109
|
| [13] |
P. Sumritnorrapong, K. Neammanee, J. Suntornchost, Exponential bounds via Stein's method and exchangeable pairs, ScienceAsia, 44 (2018), 277–287. https://doi.org/10.2306/scienceasia1513-1874.2018.44.277 doi: 10.2306/scienceasia1513-1874.2018.44.277
|
| [14] | C. Stein, A bound for the error in the normal approximation to the distribution of a sum of dependent random variables, Proc. Sixth Berkeley Symp. Math. Stat. Probab., 2 (1972), 583–602. |
| [15] |
T. Siripraparat, K. Neammanee, An improvement of convergence rate in the local limit theorem for integral-valued random variables, J. Inequal. Appl., 2021 (2021), 57. https://doi.org/10.1186/s13660-021-02590-2 doi: 10.1186/s13660-021-02590-2
|
| [16] |
L. H. Y. Chen, Poisson approximation for dependent trials, Ann. Probab., 3 (1975), 534–545. https://doi.org/10.1214/aop/1176996359 doi: 10.1214/aop/1176996359
|
| [17] | H. Luk, Stein's method for the Gamma distribution and related statistical applications, PhD Thesis, University of Southern California, 1994. |
| [18] |
L. Goldstein, G. Reinert, Stein's method for the beta distribution and the Pólya-Eggenberger urn, J. Appl. Probab., 50 (2013), 1187–1205. https://doi.org/10.1239/jap/1389370107 doi: 10.1239/jap/1389370107
|
| [19] |
R. E. Gaunt, New error bounds for Laplace approximation via Stein's method, ESAIM: PS, 25 (2021), 325–345. https://doi.org/10.1051/ps/2021012 doi: 10.1051/ps/2021012
|
| [20] | L. H. Y. Chen, L. Goldstein, Q.-M. Shao, Normal approximation by Stein's method, Berlin: Springer, 2011. https://doi.org/10.1007/978-3-642-15007-4 |
| [21] |
P. Sumritnorrapong, J. Suntornchost, An improvement of a non–uniform bound for unbounded exchangeable pairs, J. Inequal. Appl., 2023 (2023), 9. https://doi.org/10.1186/s13660-023-02915-3 doi: 10.1186/s13660-023-02915-3
|
| [22] |
L. H. Y. Chen, Q.-M. Shao, A non-uniform Berry–Esseen bound via Stein's method, Probab. Theory Relat. Fields, 120 (2001), 236–254. https://doi.org/10.1007/PL00008782 doi: 10.1007/PL00008782
|
| [23] | D. E. Knuth, The art of computer programming, volume 3: sorting and searching, 2 Eds., Massachusetts: Addison-Wesley, 1998. |
Figures(1) / Tables(2)
Natthapol Dejtrakulwongse, Kritsana Neammanee, Suporn Jongpreechaharn. Non-uniform bounds in normal approximation for descent and inversion[J]. AIMS Mathematics, 2026, 11(2): 3903-3919. doi: 10.3934/math.2026157
DownLoad: