On the variance of the number of maxima in random vectors and its applications

• 成果类型: Article
• 署名作者: Bai, ZD; Chao, CC; Hwang, HK; Liang, WQ
• 署名单位: National University of Singapore; Academia Sinica - Taiwan; National Sun Yat Sen University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• 发表日期: 1998
• 页码: 886-895
• 关键词: linear expected-time; AVERAGE NUMBER; convex hulls; set

摘要

We derive a general asymptotic formula for the variance of the number of maxima in a set of independent and identically distributed random vectors in R-d, where the components of each vector are independently and continuously distributed. Applications of the results to algorithmic analysis are also indicated.