Does a sample version of the one-sided Chebyshev inequality exist? I am interested in the following one-sided Cantelli's version of the Chebyshev inequality:
$$
\mathbb P(X - \mathbb E (X) \geq t) \leq \frac{\mathrm{Var}(X)}{\mathrm{Var}(X) + t^2} \,.
$$
Basically, if you know the population mean and variance, you can calculate the upper bound on the probability of observing a certain value. (That was my understanding at least.)
However, I would like to use the sample mean and sample variance instead of the actual population mean and variance.
I am guessing that since this would introduce more uncertainty, the upper bound would increase.
Is there an inequality analogous to the above, but that uses the sample mean and variance?
Edit: The "sample" analog of the Chebyshev Inequality (not one sided), has been worked out. The Wikipedia page has some details. However, I am not sure how it would translate to the one sided case I have above.
 A: Yes, we can get an analogous result using the sample mean and variance, with perhaps, a couple slight surprises emerging in the process.
First, we need to refine the question statement just a little bit and set out a few assumptions. Importantly, it should be clear that we cannot hope to replace the population variance with the sample variance on the right hand side since the latter is random! So, we refocus our attention on the equivalent inequality
$$
\mathbb P\left( X - \mathbb E X \geq t \sigma \right) \leq \frac{1}{1+t^2} \>.
$$
In case it is not clear that these are equivalent, note that we've simply replaced $t$ with $t \sigma$ in the original inequality without any loss in generality.
Second, we assume that we have a random sample $X_1,\ldots,X_n$ and we are interested in an upper bound for the analogous quantity
$
\mathbb P(X_1 - \bar X \geq t S)
$,
where $\bar X$ is the sample mean and $S$ is the sample standard deviation. 
A half-step forward 
Note that already by applying the original one-sided Chebyshev inequality to $X_1 - \bar X$, we get that
$$
\mathbb P( X_1 - \bar X \geq t\sigma ) \leq \frac{1}{1 + \frac{n}{n-1}t^2}
$$
where $\sigma^2 = \mathrm{Var}(X_1)$, which is smaller than the right-hand side of the original version. This makes sense! Any particular realization of a random variable from a sample will tend to be (slightly) closer to the sample mean to which it contributes than to the population mean. As we shall see below, we'll get to replace $\sigma$ by $S$ under even more general assumptions.
A sample version of one-sided Chebyshev

Claim: Let $X_1,\ldots,X_n$ be a random sample such that $\mathbb P(S = 0) = 0$. Then, $$ \mathbb P(X_1 - \bar X \geq t S) \leq \frac{1}{1 + \frac{n}{n-1} t^2}\>. $$ In particular, the
  sample version of the bound is tighter than the original population
  version.

Note: We do not assume that the $X_i$ have either finite mean or variance!
Proof. The idea is to adapt the proof of the original one-sided Chebyshev inequality and employ symmetry in the process. First, set $Y_i = X_i - \bar X$ for notational convenience. Then, observe that
$$
\mathbb P( Y_1 \geq t S ) = \frac{1}{n} \sum_{i=1}^n \mathbb P( Y_i \geq t S ) = \mathbb E \frac{1}{n} \sum_{i=1}^n \mathbf 1_{(Y_i \geq t S)} \>.
$$
Now, for any $c > 0$, on $\{S > 0\}$,
$$\newcommand{I}[1]{\mathbf{1}_{(#1)}}
\I{Y_i \geq t S} = \I{Y_i + t c S \geq t S (1+c)} \leq \I{(Y_i + t c S)^2 \geq t^2 (1+c)^2 S^2} \leq \frac{(Y_i + t c S)^2}{t^2(1+c)^2 S^2}\>.
$$
Then,
$$
\frac{1}{n} \sum_i \I{Y_i \geq t S} \leq \frac{1}{n} \sum_i \frac{(Y_i + t c S)^2}{t^2(1+c)^2 S^2} = \frac{(n-1)S^2 + n t^2 c^2 S^2}{n t^2 (1+c)^2 S^2} = \frac{(n-1) + n t^2 c^2}{n t^2 (1+c)^2} \>,
$$
since $\bar Y = 0$ and $\sum_i Y_i^2 = (n-1)S^2$.
The right-hand side is a constant (!), so taking expectations on both sides yields,
$$
\mathbb P(X_1 - \bar X \geq t S) \leq \frac{(n-1) + n t^2 c^2}{n t^2 (1+c)^2} \>.
$$
Finally, minimizing over $c$, yields $c = \frac{n-1}{n t^2}$, which after a little algebra establishes the result.
That pesky technical condition
Note that we had to assume $\mathbb P(S = 0) = 0$ in order to be able to divide by $S^2$ in the analysis. This is no problem for absolutely continuous distributions, but poses an inconvenience for discrete ones. For a discrete distribution, there is some probability that all observations are equal, in which case $0 = Y_i = t S = 0$ for all $i$ and $t > 0$.
We can wiggle our way out by setting $q = \mathbb P(S = 0)$. Then, a careful accounting of the argument shows that everything goes through virtually unchanged and we get

Corollary 1. For the case $q = \mathbb P(S = 0) > 0$, we have $$ \mathbb P(X_1 - \bar X \geq t S) \leq (1-q) \frac{1}{1 + \frac{n}{n-1} t^2} + q \>. $$

Proof. Split on the events $\{S > 0\}$ and $\{S = 0\}$. The previous proof goes through for $\{S > 0\}$ and the case $\{S = 0\}$ is trivial.
A slightly cleaner inequality results if we replace the nonstrict inequality in the probability statement with a strict version.

Corollary 2. Let $q = \mathbb P(S = 0)$ (possibly zero). Then, $$ \mathbb P(X_1 - \bar X > t S) \leq (1-q) \frac{1}{1 + \frac{n}{n-1} t^2} \>. $$

Final remark: The sample version of the inequality required no assumptions on $X$ (other than that it not be almost-surely constant in the nonstrict inequality case, which the original version also tacitly assumes), in essence, because the sample mean and sample variance always exist whether or not their population analogs do.
A: This is just a complement to @cardinal 's ingenious answer. Samuelson Inequality, states that, for a sample of size $n$, when we have at least three distinct values of the realized $x_i$'s, it holds that
$$x_i-\bar x < s\sqrt{n-1},\;\; i=1,...n$$
where $s$ is calculated without the bias correction, $s= \left (\frac 1n\sum_{i=1}^n(x_i-\bar x)^2\right)^{1/2}$.
Then, using the notation of Cardinal's answer we can state that
$$\mathbb P\left(X_1-\bar X \ge S\sqrt{n-1}\right) =0 \;\;a.s. \qquad [1]$$
Since we require, three distinct values, we will have $S\neq 0$ by assumption. So setting $t=\sqrt{n-1}$ in Cardinal's Inequality (the initial version) we obtain
$$\mathbb P\left (X_1 - \bar X \geq  S\sqrt{n-1}\right) \leq \frac{1}{1 + n}, \;\; \qquad [2]$$
Eq. $[2]$ is of course compatible with eq. $[1]$. The combination of the two tells us that Cardinal's Inequality is useful as a probabilistic statement for $0< t < \sqrt{n-1}$.  
If Cardinal's Inequality requires $S$ to be calculated bias-corrected (call this $\tilde S$) then the equations become
$$\mathbb P\left(X_1-\bar X \ge \tilde S\frac{n-1}{\sqrt{n}}\right) =0 \;\;a.s. \qquad [1a]$$
and we choose $ t= \frac{n-1}{\sqrt{n}}$ to obtain through Cardinal's Inequality
$$\mathbb P\left (X_1 - \bar X \geq  \tilde S\frac{n-1}{\sqrt{n}}\right) \leq \frac{1}{ n}, \;\; \qquad [2a]$$
and the probabilistically meaningful interval for $t$ is $0< t < \frac{n-1}{\sqrt{n}}.$
A: I have attempted to apply @cardinal's equation to my permutation test to determine an upper-bound for its p-value. I have 1 unpermuted dataset $y$ and and $n$ permuted datasets $x_i$. I define some testing function $F$ and apply it to my datasets as follows: $F^{orig} = F(y)$ and $F^{perm}_i = F(x_i)$. Then I apply the above inequality to the set of values $\{F^{orig}\}\cup \{ F^{perm}_i \}$ s.t. $X_1 = F^{orig}$. I also compute the z-score of permuted vs original data for comparison $z = \frac{F^{orig} - \bar{F}^{perm}}{s^{perm}}$.

The numbers in the legend correspond to different quantities of sample points.
Rule of thumb: If you wish to use above inequality to prove the $X_1$ is an outlier with p-value of 1% or lower, you need at least 1000 samples, and the outlier must be at least $10\sigma$ away from the mean of the rest of the points. This is kind of brutal compared to slightly less than $3\sigma$ for gaussian distribution, but, I guess, that's the price of having no assumptions
Self-check: For large $n$ and small $p$, we have $t^{min} \approx p^{-0.5} \approx 10$ for $p=0.01$, which matches with z-score being $10\sigma$
If you are wondering, p-value improves with the number of samples because when there are more points, the outlier has less effect on the sample mean and variance
