Combinatorics, Probability and Computing

Table of Contents - 2000 - Volume 9, Issue 04  


Random Graphs and the Strong Convergence of Bootstrap Means

SÁNDOR CSÖRGO a1a2 1 and WEI BIAO WU a1
a1 Department of Statistics, University of Michigan, 4062 Frieze Building, Ann Arbor, MI 48109–1285, USA (e-mail: scsorgo@umich.edu, wbwu@umich.edu)
a2 Bolyai Institute, University of Szeged, Aradi vértanúk tere 1, H–6720 Szeged, Hungary (e-mail: csorgo@math.u-szeged.hu)

Abstract

We consider graphs Gn generated by multisets [script I]n with n random integers as elements, such that vertices of Gn are connected by edges if the elements of [script I]n that the vertices represent are the same, and prove asymptotic results on the sparsity of edges connecting the different subgraphs Gn of the random graph generated by [cup B: union or logical sum][infty infinity]n=1[script I]n. These results are of independent interest and, for two models of the bootstrap, we also use them here to link almost sure and complete convergence of the corresponding bootstrap means and averages of related randomly chosen subsequences of a sequence of independent and identically distributed random variables with a finite mean. Complete convergence of these means and averages is then characterized in terms of a relationship between a moment condition on the bootstrapped sequence and the bootstrap sample size. While we also obtain new sufficient conditions for the almost sure convergence of bootstrap means, the approach taken here yields the first necessary conditions.

(Received October 16 1998)
(Revised May 31 1999)


Footnotes

1 Supported in part by NSF Grant DMS–9625732.