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 '16 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 '16 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 '16 at 18:12
• Have you tried looking at higher moments? – Alex R. Aug 4 '16 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 '16 at 18:42

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)$$