Estimating the minimum of a finite probability mass function Suppose we are given a discrete r.v. $X$, distributed according to some unknown, finite probability mass function $p(x)$. We can assume that $p(x)>0$ for every $x$ in its domain. We can sample $X$ i.i.d. and obtain a sample
$S= (X_1,...,X_m)$.
Problem: how can we formally lower-bound $p_*=\min_x p(x)$, within a certain confidence?
To be more specific, I'd like an estimator $\hat p_*(S)$ for which it is possible to prove something like this, for any $1\geq \lambda\geq 0$:
$\Pr(|p_*- \hat p_*(S)|>\lambda)\leq f(\lambda,m)$   
for some rapidly decreasing function $f$ of $\lambda$ and $m$. For example, $f(\lambda,m)=\exp(-c\lambda^2m)$, for some constant $c>0$.
Any reference to the relevant literature would be greatly appreciated.
 A: What you are looking for are called concentration bounds in statistical learning theory. Here is a good primer by Gabor Lugosi.
You can find more relevant literature from course websites for learning theory.
A: This is a common schema. The exact form you have mentioned is used in most standard methods to prove bounds in randomized algorithms. The logic is as follows: Suppose my task is X. I develop a randomized scheme and show using the bounds you have mentioned that P(X not happens) approaches zero. 
The key steps in these proofs involves using the Markov or Chebyshev inequality which has the form you want. Some ingenuity goes in figuring out how to chose the correct p* and how to reduce the right hand side to the form you require
A: Here are some easy calculations that you might have considered, but still seem worth jotting down.  (Disclaimer: I am not an expert and think there are better solutions).
For convenience, suppose the state space is $\{0,1,\ldots,N\}$, and $p_0 < p_1 \le p_x$ for $x = 1, \ldots, N$.  So $0$ is the (strictly) least likely outcome and $p_* = p_0$ in this case.  (For now assume that $N$ is known.)
Take the i.i.d. sample $X_1, \ldots, X_m \sim (p_x)$.
Let $L$ denote the outcome that occurs least often, i.e. $L$ is such that $\#\{i:X_i = L\}$ is minimal (with ties broken arbitrarily).  A first step is to show $L = 0$ has a good probability.
Define $c = (p_1 - p_0)/2 > 0$ by assumption.  Note that $p_0 + c = p_1 - c = (p_0 + p_1)/2$.  
If $\#\{i:X_i = 0\} < m(p_0 + c)$ and $\#\{i:X_i = x\} > m(p_1 -c)$ for all $x$ then $L = 0$.  Hence $L \neq 0$ implies one of these inequalities does not hold.  Observe that $\#\{i:X_i = x\}$ has Binomial$(m,p_x)$ distribution, for every $x$.  Thus, Hoeffding's inequality gives
$$
P( \#\{i:X_i = 0\} \ge n(p_0 + c) ) \le e^{-2m c^2},
$$
and 
$$
P( \#\{i:X_i = x\} \le n(p_1 + c) ) \le P( \#\{i:X_i = x\} \le n(p_x + c) )
\le e^{-2m c^2}.
$$
Union bounding thus gives
$$
P(L \neq 0) \le (N+1)e^{-2m c^2}.
$$
The obvious estimator to use now is $\hat p_* = \#\{i:X_i = L\}/m$, the smallest observed fraction.
We get
\begin{align}
P(|\hat p_* - p_*| \ge a) 
& = P(|\hat p_* - p_*| \ge a, L=0) +  
P(|\hat p_* - p_*| \ge a, L=0) + P(|\hat p_* - p_*| \ge a, L\ne 0) \\
& \le P(|\hat p_* - p_*| \ge a, L=0) + (N+1)e^{-2m c^2} \\
& \le P(|\#\{i:X_i = 0\}/m - p_*| \ge a)  +(N+1)e^{-2m c^2} \\
& \le 2 e^{-2m a^2} + (N+1)e^{-2m c^2}.
\end{align}
So, if you have some idea of the state space size $N$, and also the difference $p_1 - p_0$ for how less likely the least likely outcome is, then you're in business.
I will expand this post later with some thoughts about estimating $N$ and $p_1 - p_0$, which actually seems to be the tough part of the problem!
