Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

We are preparing this for an exam.

Given the division of a plane into a number of regions of different sizes. We would like to find, or guess, which is the biggest region, by doing the following.

We will shoot a number of random points at the plane, and then conclude that the region containing the most points, is also the biggest.

The question is: how do use Chernoff bounds to say how many random points we need to shoot, to know that we have found the biggest region with, say, 75% probability?

share|cite|improve this question
What parameters is the number of points allowed to depend on? Consider two regions of size $1$ and $1+\epsilon$, with $\epsilon$ small. We would need to shoot many points to distinguish which is biggest with 75% probability. – Colin McQuillan Jan 3 '13 at 21:35
There is no restriction on what parameters the points depend on. It could be arbitrarily few or many. Your problem statement is good. The question is, how do we answer/represent it using Chernoff? – andershqst Jan 4 '13 at 8:57

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.