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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.