Probability of random variable being lesser than the other Say there are two independent random variables, $X$ and $Y$, and we have samples $\{x_1,\dots x_n\},\{y_1,\dots y_n\}$. I am interested in bounding the probability of the event $C = \mathbb{1}_{X<Y}$, namely bounding  $\mathbb{P}(C)=\mathbb{E}(C) $.
I know that I can define $c_i=\mathbb{1}_{x_i<y_i}$,  and use Chernoff bound in the standard fashion to estimate 
$$\mathbb{P}\bigg(\hat C\in(\mathbb{E}(C)-\epsilon,\mathbb{E}(C)+\epsilon)\bigg) \geq 1-\delta $$
However, doing so means completely ignoring the fact that $X$ and $Y$ are independent, hence seems wrong.
Any ideas?
Thanks!

This is what I have done so far, based a partial answer by @passerby51's:
First, we define the U-statistic:
$$
U := \frac1{n^2} \sum_{i=1}^n \sum_{j=1}^n 1\{X_j < Y_i\}
$$
Now, we would really like to follow Example 2.10 from here, with $g(X_i,Y_j)=1_{X_i<Y_j}$. Unfortunately, $1_{X_i<Y_j}$ is not symmetric (as needed from the proof of the cited example). One lead as hinted by @passerby51, is to decompose $U$ into two terms, i.e.
$$
U := \frac1{n^2}\underbrace{\sum_{k=1}^n 1\{X_k < Y_k\}}_{U_1}+\frac1{n^2}\underbrace{ \sum_{i<j} 1\{X_i < Y_j\}+1\{X_j < Y_i\}}_{U_2}
$$
Obviously, each term in $U_2$ is symmetric in $i,j$. I'm not sure what to do with $U_1$, so I'll ignore it for now. Redefine:
$$
U' := \frac1{n^2-n} \sum_{i<j} \big[1\{X_j < Y_i\}+1\{X_i < Y_j\}\big]=\frac1{n^2-n} \sum_{i<j} g(i,j)
$$
and again $\mathbb{E}(U')=\mathbb{E}(C)$. Next, if look at $U'$ as a function of $(X_1,\dots, X_n,Y_1,\dots,Y_n)$  it holds that:
$$|f(x_1,\dots,x_k,\dots,y_1,\dots,y_n)-f(x_1,\dots,x'_k,\dots,y_1,\dots,y_n)|\leq \frac{2\cdot(n-1)}{n\cdot(n-1)}=\frac 2 n$$
So using bounded differences inequality (see Corollary 2.2 here ) we finally get
$$\mathbb{P}(|U'-\mathbb E(U')| \geq \epsilon) \leq 2\cdot e^{\frac{-n \epsilon^2} 2} $$ 
Make sense? how can I incorporate the diagonal indicators?
 A: Let $ F(y) := \mathbb P(X < y)$. We have $\mathbb P(X < Y | Y = y) = \mathbb P(X < y) =  F(y)$ by independence. Hence $p^* := \mathbb P (X < Y) = \mathbb E  F (Y)$.
Now, a good general estimate for $p^* = \mathbb E  F (Y)$ is the empirical mean $\hat p = \frac1n \sum_{i=1}^n  F(Y_i)$, and a good general estimate for $F$ is again the empirical mean, $\hat {F}(y) = \frac1n \sum_{j=1}^n  1(X_j < y)$.
Thus, in the absence of any information besides independence of $X$ and $Y$, the following is I believe the best estimate you can hope for
$$
\hat p = \frac1{n^2} \sum_{i=1}^n \sum_{j=1}^n 1\{X_j < Y_i\}.
$$
With obvious modifications, this works for uneven number of samples from $X$ and $Y$.
EDIT: You can use Hoeffding bound for U-statistics for this. (The terms of the sum are not independent as I originally mistakenly wrote. The variance of this estimate however is a lot smaller than what you had in your question: $\frac1n \sum_{i=1}^n 1\{X_i < Y_i\}$. (Perhaps by a factor of $n^{-2}$, but not sure.)
