I having some trouble proving Lemma 5 of http://ttic.uchicago.edu/~dmcallester/margins.ps Any help would be greatly appreciated. I want to prove the following:
Let $X \in \mathbb{R}$ be a random variable such that $Pr(X \leq x) \leq e^{-m f(x)}$, where $f(x)$ is non-negative. Then $$Pr(e^{(m-1)f(X)} \geq \nu) \leq min(1, \nu^{-m/(m-1)}).$$
The only thing I can think would be applicable here is the Markov's inequality but the result does not follow from it.