Exponentielle Obergrenze

Angenommen, wir haben IID-Zufallsvariablen mit der Verteilung . Wir werden eine Probe des beobachten ist auf folgende Weise: lassen unabhängig Zufallsvariablen an , dass die ganze 's und ‚s sind unabhängig und definieren die Stichprobengröße . Die - geben an, welche der - in der Stichprobe enthalten sind, und wir möchten den Anteil der Erfolge in der Stichprobe untersuchen, der durch definiert ist $X_1,\dots,X_n$$\mathrm{Ber}(\theta)$$X_i$$Y_1,\dots,Y_n$$\mathrm{Ber}(1/2)$$X_i$$Y_i$$N=\sum_{i=1}^n Y_i$$Y_i$$X_i$

$$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}$$ Für wollen wir eine Obergrenze für , die mit exponentiell abfällt . Die Ungleichung von Hoeffding gilt aufgrund der Abhängigkeiten zwischen den Variablen nicht sofort.P $\epsilon>0$$\mathrm{Pr}\!\left(Z \geq \theta + \epsilon\right)$$n$

Wir können auf ziemlich direkte Weise eine Verbindung zu Höffdings Ungleichung herstellen .

Beachten , dass wir

$$\{ 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 \} \>.$$

Setze $Z_i = (X_i - \theta - \epsilon)Y_i + \epsilon/2$ so dass die $Z_i$ iid sind, $\mathbb E Z_i = 0$ und

$$\mathbb P( Z > \theta + \epsilon ) = \mathbb P\big(\sum_i Z_i > n \epsilon/2\big) \leq e^{-n \epsilon^2/2}\>,$$ Von einer einfachen Anwendung derHoeffding Ungleichung(da die$Z_i \in [-\theta-\epsilon/2,1-\theta-\epsilon/2]$ , und so nehmen Werte in einem Intervall der Größe eins).

Es gibt eine reiche und faszinierende Literatur, die sich in den letzten Jahren insbesondere zu Themen der Zufallsmatrixtheorie mit verschiedenen praktischen Anwendungen aufgebaut hat. Wenn Sie sich für so etwas interessieren, empfehle ich:

R. Vershynin, Einführung in die nicht-asymptotische Analyse von Zufallsmatrizen , Kapitel 5 von Compressed Sensing, Theory and Applications. Herausgegeben von Y. Eldar und G. Kutyniok. Cambridge University Press, 2012.

Ich denke, die Darstellung ist klar und bietet eine sehr schöne Möglichkeit, sich schnell an die Literatur zu gewöhnen.

Details, um den Fall . $N=0$

$$\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.