I have $m$ continues integer points on a line, randomly uniform select $n$ points from the $m$ point without replacement. Order the points ascendingly. Let the random variable $A_i$ is the position (coordination on the line) of the $i$th point. So, $$P(A_i=k)=\frac{{k-1\choose i-1} {m-k \choose n-i}}{{m \choose n}} $$

How to derive the tail inequality for this probability. The tail probability look something like this:

$$P(|A_i - E(A_i)| > t) < \sigma$$

I want the bound ($\sigma$) to be as tight as possible. The Chebyshev inequality is too loose.

Updated: Some supplement about the question: http://www.math.uah.edu/stat/urn/OrderStatistics.pdf


Edit: See Didier's comment below. The binomial coefficients are "upside down" and so what's written below is meaningless. It is worthwhile, however, to see which tools are used to obtain tail estimates on the hypergeometric distribution, to get some ideas. Perhaps all they do is use Stirling's approximation and integrate it.

Your distribution is very close to a hypergeomtric distribution (as noted in an earlier version of the question). In fact, it is related to it via a factor of $i/k$. So tail estimates for it should transfer to tail estimates for your distribution.

| cite | improve this answer | |
  • $\begingroup$ @Yuval Is there some paper discuss this? Thks. $\endgroup$ – Fan Zhang Feb 15 '11 at 6:50
  • $\begingroup$ @Yuval: There is at best an analogy between these two settings since the running argument $k$ of the distribution is at the bottom of the binomial coefficient for the hypergeometric distribution and at the top for the distribution Fan is interested in. $\endgroup$ – Did Feb 15 '11 at 9:12
  • $\begingroup$ @Didier Yes, actually this is the most important difference between the two probabilities. $\endgroup$ – Fan Zhang Feb 15 '11 at 9:44
  • $\begingroup$ A good place to look at would be a book on Order Statistics. $\endgroup$ – Yuval Filmus Feb 15 '11 at 16:35
  • 1
    $\begingroup$ @Fan Same one. There are versions of Stirling's approximation with very good bounds on the error. This is one way of estimating tails of the binomial distribution (the other way is using the "moment generating function", like they do in Chernoff's bound). $\endgroup$ – Yuval Filmus Feb 15 '11 at 20:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.