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

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:

share|cite|improve this question
up vote 5 down vote accepted

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.

share|cite|improve this answer
@Yuval Is there some paper discuss this? Thks. – Fan Zhang Feb 15 '11 at 6:50
@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. – Did Feb 15 '11 at 9:12
@Didier Yes, actually this is the most important difference between the two probabilities. – Fan Zhang Feb 15 '11 at 9:44
A good place to look at would be a book on Order Statistics. – Yuval Filmus Feb 15 '11 at 16:35
@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). – Yuval Filmus Feb 15 '11 at 20:20

Your Answer


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

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