论文标题
迪克曼在kolmogorov距离的加权随机总和的近似
Dickman Approximation of weighted random sums in the Kolmogorov distance
论文作者
论文摘要
我们考虑通过广义迪克曼分布的分布近似，这些分布出现在数字理论，永久性，对数组合结构和许多其他领域。我们证明了该家族成员的伯诺利（Bernoulli）和泊松随机变量的某些加权总和的近似值。虽然以前在Bhattacharjee和Goldstein（2019）中显示了基于平滑的测试函数的距离以及本文考虑的随机变量的特殊情况，但结果是Kolmogorov距离是新的。我们还通过得出下限来确立收敛速率的最佳性。结果，根据基础参数的选择，一些有趣的相变出来。我们结果的证明主要依赖于Stein方法的使用。特别是，我们研究了与Kolmogorov距离相关的测试函数对应的Stein方程的溶液，并确定其平滑度。作为应用程序，我们研究了QuickSelect算法的运行时间和随机生长的简单增加树木中的加权深度。
We consider distributional approximation by generalized Dickman distributions, which appear in number theory, perpetuities, logarithmic combinatorial structures and many other areas. We prove bounds in the Kolmogorov distance for the approximation of certain weighted sums of Bernoulli and Poisson random variables by members of this family. While such results have previously been shown in Bhattacharjee and Goldstein (2019) for distances based on smoother test functions and for a special case of the random variables considered in this paper, results in the Kolmogorov distance are new. We also establish optimality of our rates of convergence by deriving lower bounds. As a result, some interesting phase transitions emerge depending on the choice of the underlying parameters. The proofs of our results mainly rely on the use of Stein's method. In particular, we study the solutions of the Stein equation corresponding to the test functions associated to the Kolmogorov distance, and establish their smoothness properties. As applications, we study the runtime of the Quickselect algorithm and the weighted depth in randomly grown simple increasing trees.
