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 Nov 11 '16 at 15:39
  • $\begingroup$ I'm doing theoretical analysis, PAC style. $\endgroup$ – omerbp Nov 11 '16 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 Nov 11 '16 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$ – omerbp Nov 11 '16 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 Nov 11 '16 at 16:05

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$ – omerbp Nov 11 '16 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 Nov 11 '16 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 Nov 11 '16 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$ – omerbp Nov 11 '16 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 Nov 12 '16 at 4:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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