# Finding a bound on the probability of one variable being greater than the other

Say we have two random variables, $X$ and $Y$, and we care about the event $C = \mathbb{1}_{X>Y}$. The distribution functions are not given, but we can use a black box for drawing pairs $(x_i,y_i)$. Given $\epsilon$ and $\delta$, I wish to determined the required sample size $n$ such that if $\hat C = \frac{1}{n}\cdot\sum_{i=1}^{n}{c_i}$ then

$$\mathbb{P}\bigg(\hat C\in(\mathbb{E}(C)-\epsilon,\mathbb{E}(C)+\epsilon)\bigg) \geq 1-\delta$$

If $X$ and $Y$ are dependent, we can define $c_i=\mathbb{1}_{x_i>y_i}$ and use Chernoff bound in the standard fashion to extract $n$.

Intuitively, if $X$ and $Y$ are independent, the sample size (for the same $\epsilon , \delta$) should be smaller. Unfortunately it is seem too tricky for me. Any ideas?

Thanks!

Edit: Obviously $\mathbb{E}(X)>\mathbb{E}(Y)$ doen not mean that $\mathbb{P}(X>Y)>\frac{1}{2}$.

• Yes, but for the case that $X$ and $Y$ are independent, which means we can ignore the indices $1....n$ and treat the sample set as if it was two sets: $\{x_1,x_2,\dots x_n\}$ and $\{y_1,y_2,\dots,y_n\}$ Nov 3, 2016 at 11:36