Limit Distributions and Random Trees Derived from the Birthday Problem with Unequal Probabilities
Limit Distributions and Random Trees Derived from the Birthday Problem with Unequal Probabilities
复制标题
DOI：
10.1214/ejp.v5-58
复制
发表时间：
2000
影响因子：
1.4
通讯作者：
Michael Camarri;J. Pitman
中科院分区：
文献类型：
--
作者：
Michael Camarri;J. Pitman
给定可计数集合上的任意分布，考虑直到看到第一个重复值为止所需的独立样本的数量。精确和渐近公式推导出这个时间的分布和时间，直到随后的重复。通过嵌入泊松过程，得到了重复次数的渐近性质。特别地，给出了收敛的充分必要条件，并明确描述了可能的限制。在相同的条件下，有限维分布的重复时间收敛到适当修改的泊松过程的到达时间，和随机树从序列的独立试验收敛到一个非齐次连续随机树的分布。
Given an arbitrary distribution on a countable set, consider the number of independent samples required until the first repeated value is seen. Exact and asymptotic formulae are derived for the distribution of this time and of the times until subsequent repeats. Asymptotic properties of the repeat times are derived by embedding in a Poisson process. In particular, necessary and sufficient conditions for convergence are given and the possible limits explicitly described. Under the same conditions the finite dimensional distributions of the repeat times converge to the arrival times of suitably modified Poisson processes, and random trees derived from the sequence of independent trials converge in distribution to an inhomogeneous continuum random tree.