Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 288 - Probability Seminar

Larry Goldstein

USC

Dickman Approximation in Quickselect sorting and Probabilistic Number Theory

Abstract:

The generalized Dickman distribution ${\cal D}_\theta$ with parameter $\theta>0$ is the unique solution to the distributional equality $W=_d W^*$, where \begin{align*} W^*=_d U^{1/\theta}(W+1), \end{align*} with $W$ non-negative with probability one, $U \sim {\cal U}[0,1]$ independent of $W$, and $=_d$ denoting equality in distribution. Members of this family appear in the study of algorithms, number theory, stochastic geometry, and perpetuities. The Wasserstein distance $d(\cdot,\cdot)$ between such a $W$ with finite mean, and $D \sim {\cal D}_\theta$ obeys \begin{align*} d(W,D) \le (1+\theta)d(W^*,W). \end{align*} The specialization of this bound to the case $\theta=1$ and coupling constructions yield for $n \ge 1$ that \begin{align*} d_1(W_n,D) \le \frac{8\log (n/2)+10}{n} \quad \mbox{where } \quad W_n=\frac{1}{n}C_n-1, \end{align*} and $C_n$ is the number of comparisons made by the Quickselect algorithm to find the smallest element of a list of $n$ distinct numbers. Joint with Bhattacharjee, using Stein's method, bounds for Wasserstein type distances can also be computed between ${\cal D}_\theta$ and weighted sums arising in probabilistic number theory of the form \begin{align*} S_n=\frac{1}{\log(p_n)} \sum_{k=1}^n X_k \log(p_k) \end{align*} where $(p_k)_{k \ge 1}$ is an enumeration of the prime numbers in increasing order and $X_k$ is, for instance, Geometric with parameter $1-1/p_k$.

Host: Todd Kemp

June 6, 2019

10:00 AM

AP&M 6402

****************************