3
$\begingroup$

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

1 Answers 1

5

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.

  • 0
    @Yuval Is there some paper discuss this? Thks.2011-02-15
  • 0
    @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.2011-02-15
  • 0
    @Didier Yes, actually this is the most important difference between the two probabilities.2011-02-15
  • 0
    A good place to look at would be a book on Order Statistics.2011-02-15
  • 0
    @Yuval Is this one? http://en.wikipedia.org/wiki/Stirling's_approximation But Stirling's approximation may need n->inf.2011-02-15
  • 1
    @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).2011-02-15