# Improving Chebyshev-type bound for discrete uniform distribution

I take $N$ samples from a fully specified, discrete, finite uniform random variable $X$ with mean $\mu$ and variance $\sigma_X^2$. I want to find the probability that the absolute error of the empirical mean $\bar{\mu}$ of the $N$ samples is larger than a supplied $\varepsilon>0$. I can use Chebyshev's inequality to bound this probability: $$P(|\mu - \bar{\mu}|>\varepsilon)\leq\frac{\sigma_X^2}{N\varepsilon^2}.$$ However, Monte Carlo simulation shows this bound to be very loose. Is there a tighter bound for this specific distribution?

• What does the support of your random variable look like? For instance, we might conceive of a variable that assigns probability $1/3$ to each of the numbers $1, 10,$ and $100$ to be "uniform" because all probabilities are the same.
– whuber
Aug 4, 2016 at 17:53
• Both the support and the number of possible values are small. As a typical example of the kind of RV I'm studying, let's assume the variable takes one of 16 possible values in the range [-1,1]. I don't want to assume that $\mu$ is zero, so the distribution can be slightly biased towards -1 or 1.
– MBaz
Aug 4, 2016 at 18:04
• Unless $N$ is large, "small" might not be a sufficient description. Of greater concern is the possible variation in spacing among the values in the support: are they equally spaced or not? BTW, I presume your "$\hat\mu$" is the same thing as "$\bar\mu$". If not, please clarify the distinction.
– whuber
Aug 4, 2016 at 18:12
• Have you tried looking at higher moments? Aug 4, 2016 at 18:22
• @whuber I'll try to be more precise. Assume that $X$ takes values in an ordered set $\lbrace x_1, x_2, \ldots, x_{16} \rbrace$, where $x_i<x_{i+1}$, the difference between neighboring elements is constant, and $x_{16}-x_1<2$. Informally, the RVs I'm looking at are very "regular" and "compact". BTW, I fixed the typo with $\hat{\mu}$; indeed I meant $\bar{\mu}$.
– MBaz
Aug 4, 2016 at 18:42

If you know that the the random variable is bounded then you know a lot about the random variable and the Chebyshev and Markov inequality will not be tight in general.

A better inequality is the Hoeffding's inequality (consider the general case and not the binomial version). This takes into account implicitly that you have all higher moments (since the RV is finite with finite support) but is nice because it doesn't need any support information and says that you go to your mean exponentially fast.

For example if your RV is bounded on $[-1,1]$ (Note that it doesn't have to discrete) then you can say the following for $\epsilon>0$

$$\mathbb{P}(|\mu - \bar{\mu}| \geq \epsilon) \leq 2 \exp\bigg(-\frac{n\epsilon^2}{2}\bigg)$$

I don't believe you could get much better by trying to figure in the discrete knowledge because all the values could be at the endpoints causing higher variance (in other words the worst case scenarios are probably the discrete cases).

• Specifically in OP's case the distribution is bounded, so Hoeffding's Lemma would possibly suffice: en.wikipedia.org/wiki/Hoeffding%27s_lemma Aug 4, 2016 at 18:33
• This looks very promising, thanks -- I'm taking a closer look.
– MBaz
Aug 4, 2016 at 18:49