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.

  • 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