Probability of random variable being lesser than the other

Question

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?

Answer 1

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