Exponential upper bound

Suppose we have IID random variables $X_1,\dots,X_n$ with distribution $\mathrm{Ber}(\theta)$. We are going to observe a sample of the $X_i$'s in the following way: let $Y_1,\dots,Y_n$ be independent $\mathrm{Ber}(1/2)$ random variables, suppose that all the $X_i$'s and $Y_i$'s are independent, and define the sample size $N=\sum_{i=1}^n Y_i$. The $Y_i$'s indicate which of the $X_i$'s are in the sample, and we want to study the fraction of successes in the sample defined by $$Z = \begin{cases} \frac{1}{N}\sum_{i=1}^n X_i Y_i & \text{if}\quad N > 0\, , \\ 0 & \text{if} \quad N = 0 \, . \end{cases}$$ For $\epsilon>0$, we want to find an upper bound for $\mathrm{Pr}\!\left(Z \geq \theta + \epsilon\right)$ that decays exponentially with $n$. Hoeffding's inequality doesn't apply immediately because of the dependencies among the variables.

• Let $Z_i = \frac{_1}{^N} X_iY_i$. (i) Isn't $Z_i$ independent of $Z_{j\neq i}$? (ii) isn't $Z=\sum Z_i$? ... As a result, it's not clear to me that $Z$ isn't 'a sum of independent random variables' – Glen_b Jun 15 '14 at 14:51
• Ah, good point. I was thinking about $n$, rather than $N$. But can't you instead write $Z_i = \frac{1}{n}X_iY_i$, and let $Z=\sum_{i=1}^n Z_i$? That is, sum over all cases, whether or not $Y$ is 1 or 0. ... no that doesn't work. The numerator is the same but the denominator is different. – Glen_b Jun 15 '14 at 14:56
• That gives less than the fraction of successes in the sample, which is the quantity of interest in the problem, because $(1/n)\sum_{i=1}^n X_i Y_i\leq (1/N)\sum_{i=1}^n X_i Y_i$, since $N\leq n$. – Zen Jun 15 '14 at 15:03
• Yes, that's why I ended with "no that doesn't work". There are inequalities that apply to the non-independent case, such as some of Bernstein's inequalities (see the fourth item), and there are a number of inequalities that apply to martingales (though I don't know that those will apply here). – Glen_b Jun 15 '14 at 15:10
• I'll take a look, and also try to find a connection with the martingales results. The bound for $U=(1/n)\sum_{i=1}^nX_i Y _i$ is so easy ($\mathrm{Pr}(U\geq \theta/2+\epsilon)\leq \exp(-2n\epsilon^2)$) that it's tempting to connect this with $Z$ using some kind of conditioning. – Zen Jun 15 '14 at 15:16

We can draw a connection to Hoeffding's inequality in a fairly direct way.

Note that we have $$\{ Z > \theta + \epsilon\} = \big\{\sum_i X_i Y_i > (\theta + \epsilon)\sum_i Y_i \big\} = \big\{ \sum_i (X_i - \theta - \epsilon) Y_i > 0 \} \>.$$

Set $Z_i = (X_i - \theta - \epsilon)Y_i + \epsilon/2$ so that the $Z_i$ are iid, $\mathbb E Z_i = 0$ and $$\mathbb P( Z > \theta + \epsilon ) = \mathbb P\big(\sum_i Z_i > n \epsilon/2\big) \leq e^{-n \epsilon^2/2}\>,$$ by a straightforward application of Hoeffding's inequality (since the $Z_i \in [-\theta-\epsilon/2,1-\theta-\epsilon/2]$ and so take values in an interval of size one).

There is a rich and fascinating related literature that has built up over the last several years, in particular, on topics related to random matrix theory with various practical applications. If you are interested in this sort of thing, I highly recommend:

R. Vershynin, Introduction to the non-asymptotic analysis of random matrices, Chapter 5 of Compressed Sensing, Theory and Applications. Edited by Y. Eldar and G. Kutyniok. Cambridge University Press, 2012.

I think the exposition is clear and provides a very nice way to get quickly acclimated to the literature.

• Since the $Z_i$ include $\epsilon/2$ in their definition, I have the impression that $Z_i \in [-\theta-\epsilon/2,1-\theta-\epsilon/2]$ (the bound doesn't change). – Alecos Papadopoulos Jun 16 '14 at 1:53
• Dear @Zen: Note that a careful accounting of the $N=0$ case will allow you to replace the strict inequality $>$ by $\geq$ everywhere without changing the final bound. – cardinal Jun 16 '14 at 2:58
• Dear @cardinal: I've reworded the question because actually $Z$ is a (slightly) biased estimator of $\theta$, since $\mathrm{E}[Z]=\mathrm{E}[I_{\{N=0\}}Z]+\mathrm{E}[I_{\{N>0\}}Z] = (1-1/2^n)\,\theta$. – Zen Jun 18 '14 at 0:24

Details to take care of the $N=0$ case. \begin{align} \{Z\geq\theta+\epsilon\} &= \left(\{Z\geq\theta+\epsilon\} \cap \{N=0\}\right) \cup \left(\{Z\geq\theta+\epsilon\} \cap \{N>0\}\right) \\ &= \left(\{0\geq\theta+\epsilon\} \cap \{N=0\}\right) \cup \left(\{Z\geq\theta+\epsilon\} \cap \{N>0\}\right) \\ &= \left(\emptyset \cap \{N=0\}\right) \cup \left(\{Z\geq\theta+\epsilon\} \cap \{N>0\}\right) \\ &= \left\{\sum_{i=1}^n X_iY_i\geq(\theta+\epsilon)\sum_{i=1}^n Y_i\right\} \cap \{N>0\} \\ &\subset \left\{\sum_{i=1}^n X_iY_i\geq(\theta+\epsilon)\sum_{i=1}^n Y_i\right\} \\ &= \left\{\sum_{i=1}^n (X_i-\theta-\epsilon)Y_i\geq 0\right\} \\ &= \left\{\sum_{i=1}^n \left((X_i-\theta-\epsilon)Y_i+\epsilon/2\right)\geq n\epsilon/2\right\} \, . \end{align}

For Alecos. \begin{align} \mathrm{E}\!\left[\sum_{i=1} ^n W_i\right]&=\mathrm{E}\!\left[I_{\{\sum_{i=1}^n Y_i=0\}}\sum_{i=1} ^n W_i\right] + \mathrm{E}\!\left[I_{\{\sum_{i=1}^n Y_i>0\}}\sum_{i=1} ^n W_i\right] \\ &=\mathrm{E}\!\left[I_{\{\sum_{i=1}^n Y_i>0\}}\frac{\sum_{i=1} ^n Y_i}{\sum_{i=1}^n Y_i}\right]=\mathrm{E}\!\left[I_{\{\sum_{i=1}^n Y_i>0\}}\right]=1-1/2^n \, . \end{align}

This answer keeps mutating. The current version does not relate to the discussion I had with @cardinal in the comments (although it was through this discussion that I thankfully realized that the conditioning approach did not appear to lead anywhere).

For this attempt, I will use another part of Hoeffding's original 1963 paper, namely section 5 "Sums of Dependent Random Variables".

Set $$W_i \equiv \frac {Y_i}{\sum_{i=1}^nY_i}, \qquad \sum_{i=1}^nY_i \neq 0, \qquad \sum_{i=1}^nW_i=1, \qquad n\geq 2$$

while we set $W_i =0$ if $\sum_{i=1}^nY_i = 0$.

Then we have the variable

$$Z_n= \sum_{i=1}^nW_iX_i, \qquad E(Z_n) \equiv \mu_n$$

We are interested in the probability

$$\mathrm{Pr}(Z_n\geq \mu_n +\epsilon), \qquad \epsilon < 1-\mu_n$$

As for many other inequalities, Hoeffding starts his reasoning by noting that $$\mathrm{Pr}(Z_n\geq \mu_n +\epsilon) = E\left[\mathbf 1_{\{Z_n-\mu_n -\epsilon \geq 0\}}\right]$$ and that

$$\mathbf 1_{\{Z_n-\mu_n -\epsilon\geq 0\}} \leq \exp\Big\{h(Z_n-\mu_n -\epsilon)\Big\}, \qquad h>0$$

For the dependent-variables case, as Hoeffding we use the fact that $\sum_{i=1}^nW_i=1$ and invoke Jensen's inequality for the (convex) exponential function, to write

$$e^{hZ_n} = \exp\left\{h\left(\sum_{i=1}^nW_iX_i\right)\right\} \leq \sum_{i=1}^nW_ie^{hX_i}$$

and linking results to arrive at

$$\mathrm{Pr}(Z_n\geq \mu_n +\epsilon) \leq e^{-h(\mu_n+\epsilon)}E\left[\sum_{i=1}^nW_ie^{hX_i}\right]$$

Focusing on our case, since $W_i$ and $X_i$ are independent, expected values can be separated,

$$\mathrm{Pr}(Z_n\geq \mu_n +\epsilon) \leq e^{-h(\mu_n+\epsilon)}\sum_{i=1}^nE(W_i)E\left(e^{hX_i}\right)$$

In our case, the $X_i$ are i.i.d Bernoullis with parameter $\theta$, and $E[e^{hX_i}]$ is their common moment generating function in $h$, $E[e^{hX_i}] = 1-\theta +\theta e^h$. So

$$\mathrm{Pr}(Z_n\geq \mu_n +\epsilon) \leq e^{-h(\mu_n+\epsilon)}(1-\theta +\theta e^h)\sum_{i=1}^nE(W_i)$$

Minimizing the RHS with respect to $h$, we get

$$e^{h^*} = \frac {(1-\theta)(\mu_n+\epsilon)}{\theta(1-\mu_n-\epsilon)}$$

Plugging it into the inequality and manipulating we obtain

$$\mathrm{Pr}(Z_n\geq \mu_n +\epsilon) \leq \left(\frac {\theta}{\mu_n+\epsilon}\right)^{\mu_n+\epsilon}\cdot \left(\frac {1-\theta}{1-\mu_n-\epsilon}\right)^{1-\mu_n-\epsilon}\sum_{i=1}^nE(W_i)$$

while

$$\mathrm{Pr}(Z_n\geq \theta +\epsilon) \leq \left(\frac {\theta}{\theta+\epsilon}\right)^{\theta+\epsilon}\cdot \left(\frac {1-\theta}{1-\theta-\epsilon}\right)^{1-\theta-\epsilon}\sum_{i=1}^nE(W_i)$$

Hoeffding shows that

$$\left(\frac {\theta}{\theta+\epsilon}\right)^{\theta+\epsilon}\cdot \left(\frac {1-\theta}{1-\theta-\epsilon}\right)^{1-\theta-\epsilon} \leq e^{-2\epsilon^2}$$

Courtesy of the OP (thanks, I was getting a bit exhausted...) $$\sum_{i=1}^n E(W_i) =1-1/2^n$$

So, finally, the "dependent variables approach" gives us $$\mathrm{Pr}(Z_n\geq \theta +\epsilon) \leq (1-\frac 1{2^n})e^{-2\epsilon^2} \equiv B_D$$

Let's compare this to Cardinal's bound, that is based on an "independence" transformation, $B_I$. For our bound to be tighter, we need

$$B_D=(1-\frac 1{2^n})e^{-2\epsilon^2} \leq e^{-n\epsilon^2/2}=B_I$$

$$\Rightarrow \frac {2^n-1}{2^n} \leq \exp\left\{\left(\frac {4-n}{2}\right)\epsilon^2\right\}$$

So for $n\leq 4$ we have $B_D \leq B_I$. For $n \geq 5$, pretty quickly $B_I$ becomes tighter than $B_D$ but for very small $\epsilon$, while even this small "window" quickly converges to zero. For example, for $n=12$, if $\epsilon \geq 0.008$, then $B_I$ is tighter. So in all, Cardinal's bound is more useful.

COMMENT
To avoid misleading impressions regarding Hoeffding's original paper, I have to mention that Hoeffding examines the case of a deterministic convex combination of dependent random variables. Specificaly, his $W_i$'s are numbers, not random variables, while each $X_i$ is a sum of independent random variables, while the dependency may exist between the $X_i$'s. He then considers various "U-statistics" that can be represented in this way.

• Alecos: $\mathrm{E}[W_1]=(1-1/2^n)/n$ (take a look at the derivation at the end of my answer). Your bound doesn't decay exponentially with $n$ as cardinal's does. – Zen Jun 18 '14 at 13:41
• @Zen Indeed (in fact it increases with sample size, although boundedly), that's why Cardinal's bound is more useful for most sample sizes. – Alecos Papadopoulos Jun 18 '14 at 18:38