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{4\cdot(n-1)}{n\cdot(n-1)}=\frac 4 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} 8} $$

Makes sense? how can I incorporate the diagonal indicators?

  • $\begingroup$ Mirrored from Cross Validated $\endgroup$ – omerbp Nov 12 '16 at 14:14
  • $\begingroup$ You have to be much more precise and much more careful when phrasing a question. Are $X$ and $Y$ identically distributed? What do those samples have to do with your question? $\endgroup$ – Liviu Nicolaescu Nov 13 '16 at 11:40
  • $\begingroup$ @LiviuNicolaescu As the body of the question states, we do not know anything about the distributions of $X$ and $Y$. We do know, however, that he samples are drawn from these distributions. $\endgroup$ – omerbp Nov 13 '16 at 11:48
  • $\begingroup$ What is then the info you know? You want to estimate the probability of $C$ in terms of what known quantities? $\endgroup$ – Liviu Nicolaescu Nov 13 '16 at 11:57
  • $\begingroup$ I'm trying to use Hoeffding-like concentration bounds to determine the sample size $n$ needed in order to be far no more than $\epsilon$ with probability at least $1-\delta$ $\endgroup$ – omerbp Nov 13 '16 at 17:21

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.