How many maxima can there be? |
| |
Authors: | Mordecai J Golin |
| |
Institution: | INRIA Rocquencourt, 78153 Le Chesnay, France |
| |
Abstract: | Let C be a planar region. Choose n points p1,,pnI.I.D. from the uniform distribution over C. Let MCn be the number of these points that are maximal. If C is convex it is known that either E(MCn)=Θ(√n)> or E(MCn)=O(log n). In this paper we will show that, for general C, there is very little that can be said, a-priori, about E(MCn). More specifically we will show that if g is a member of a large class of functions then there is always a region C such that E(MCn)=Θ(g(n)). This class contains, for example, all monotically increasing functions of the form g(n)= nlnβn, where 0<<1 and β0. This class also contains nondecreasing functions like g(n)=ln*n. The results in this paper remain valid in higher dimensions. |
| |
Keywords: | Maxima probabilistic analysis |
本文献已被 ScienceDirect 等数据库收录! |
|