比利时vs摩洛哥足彩
,
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
****************************