Moment convergence in conditional limit theorems

被引:13
作者
Janson, S [1 ]
机构
[1] Uppsala Univ, Dept Math, SE-75106 Uppsala, Sweden
关键词
conditional distribution; limit theorem; moment convergence; occupancy; hashing; random forest; branching process;
D O I
10.1017/S002190020001994X
中图分类号
O21 [概率论与数理统计]; C8 [统计学];
学科分类号
020208 [统计学]; 070103 [概率论与数理统计]; 0714 [统计学];
摘要
Consider a stun Sigma (N)(1) Y(i) of random variables conditioned on a given value of the sum Sigma (N)(1) X(i) of some other variables, where Xi and Yi are dependent but the pairs (Xi, Yi) form an i.i.d. sequence. We consider here the case when each Xi is discrete. We prove, for a triangular array ((X(ni), Y(ni))) of such pairs satisfying certain conditions, both convergence of the distribution of the conditioned sum (after suitable normalization) to a normal distribution, and convergence of its moments. The results are motivated by an application to hashing with linear probing; we give also some other applications to occupancy problems, random forests, and branching processes.
引用
收藏
页码:421 / 437
页数:17
相关论文
共 23 条
[1]
[Anonymous], 1962, MAGYAR TUD AKAD MAT
[2]
[Anonymous], 1998, SORTING SEARCHING
[3]
CHIBISOV DM, 1972, 6TH P BERK S MATH ST, V1, P153
[4]
On the analysis of linear probing hashing [J].
Flajolet, P ;
Poblete, P ;
Viola, A .
ALGORITHMICA, 1998, 22 (04) :490-515
[5]
HIPP C, 1984, PROBAB MATH STAT-POL, V4, P207
[6]
2 CONDITIONAL LIMIT-THEOREMS WITH APPLICATIONS [J].
HOLST, L .
ANNALS OF STATISTICS, 1979, 7 (03) :551-557
[7]
JANSON S, 2001, IN PRESS RANDOM STRU
[8]
Kolchin V.F., 1984, RANDOM MAPPINGS
[9]
Kolchin V.P., 1976, RANDOM ALLOCATIONS
[10]
KUDLAEV EM, 1984, THEOR PROBAB APPL, V29, P776