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?


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?

  • $\begingroup$ From what information are you attempting to estimate a sample size? If you don't have any data, then what will you use? $\endgroup$
    – whuber
    Commented Nov 11, 2016 at 15:39
  • $\begingroup$ I'm doing theoretical analysis, PAC style. $\endgroup$ Commented Nov 11, 2016 at 15:44
  • $\begingroup$ That unfortunately doesn't answer my question: if you have no data and no information, then you have no basis at all to do any kind of analysis. Could you please explain what information you will use or assume to estimate sample sizes? If not, this question likely will be unanswerable. $\endgroup$
    – whuber
    Commented Nov 11, 2016 at 15:47
  • $\begingroup$ @whuber I can sample $n_X$ samples from $D_X$ and $n_Y$ samples from $D_Y$. Is this what you mean? $\endgroup$ Commented Nov 11, 2016 at 15:50
  • $\begingroup$ Partly. But what would that mean in the case where $X$ and $Y$ are not independent? Are you saying you can sample from the joint distribution of $(X,Y)$? If that's the case, then the independence assumption would appear to have nothing to do with the solution, implying there really isn't any problem to solve. That's why I am trying to get some clarification about what you're trying to do. $\endgroup$
    – whuber
    Commented Nov 11, 2016 at 16:05

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

  • $\begingroup$ Thanks for the answer. when you say $U$-statistics you mean this, right? Also, since the terms in the sum are dependent, the conditions in Hoeffding inequality are not met, are they? can you formulate the expression you suggest bounding using Hoeffding ? $\endgroup$ Commented Nov 11, 2016 at 18:50
  • $\begingroup$ U-statistics are more general than Mann-Whitney (a special case). Also, Hoeffding proved its inequality for these guys originally. See for example example 2.10 here:stat.berkeley.edu/~mjwain/stat210b/… $\endgroup$
    – passerby51
    Commented Nov 11, 2016 at 19:35
  • $\begingroup$ If you feel more adventurous, concentratin inequalities for U-statistics, esp. the unbounded case is an active area of research: google.com/… $\endgroup$
    – passerby51
    Commented Nov 11, 2016 at 19:36
  • $\begingroup$ Thanks again for the interesting answer. I have one more concern though - in Example 2.10 the function $g$ is symmetric, whereas here $g$ is the indicator function and certainly not symmetric. Is there a case covering that also? $\endgroup$ Commented Nov 11, 2016 at 21:01
  • 1
    $\begingroup$ @omerbp, you should be able to symmetrize it. Take out the diagonal elements and write the rest as $\sum_{i < j} 1\{X_j < Y_i\} + 1\{X_i < X_j\}$ which has a symmetric kernel. You can deal with diagonal sum separately. $\endgroup$
    – passerby51
    Commented Nov 12, 2016 at 4:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.