# Chernoff Type Bounds for Uniformly Bounded Conditional Random Variables

I am considering a set of Bernoulli RVs $X_1,X_2,\ldots,X_n$ for which we have a uniform conditional bound $\mathbb{P}[X_i=1|X_1,\ldots,X_{i-1}] \leq p$ for fixed $p$. Can we show the sum of these random variables is no larger than a the sum of i.i.d. Bernoulli random variables $Y_1,\ldots,Y_n$ with parameter $p$?

In other words, for any $C$ can we show $\mathbb{P}[\sum X_i > C] \leq \mathbb{P}[\sum Y_i > C]$?

Yes we can. Define $p_k(X_{1,\dots,k-1}) := \mathbb{P}(X_k=1|X_1,\dots,X_{k-1}) \leq p$. Here $p_1$ is just a constant. Notice that the joint distribution of $(X_1,\dots,X_n)$ is uniquely characterized by the sequence of functions $\{p_k\}_{k=1}^n$ (This is clearly true for $n=1$. For other cases, just use induction).
Let $\{U_k\}_{k=1}^\infty$ be a sequence of i.i.d. uniform$[0,1]$ random variables. Let $\overline{X}_k = \mathbb{I}_{U_k < p_k(\overline{X}_{1,\dots,k-1})}$. Then for any $n$, $(\overline{X}_1,\dots,\overline{X}_n) \overset{(d)}{=} (X_1,\dots,X_n)$.
Let $Y_k = \mathbb{I}_{U_k < p}$. Then $\{Y_k\}$ are i.i.d. Bernoulli random variables with parameter $p$ and $Y_k \geq \overline{X}_k$ almost surely. So for any $C$, $\sum_{k=1}^n \overline{X}_k > C$ implies $\sum_{k=1}^n Y_k > C$. By monotonicity of probability measures,
$$\mathbb{P}\left(\sum_{k=1}^n X_n > C\right) = \mathbb{P}\left(\sum_{k=1}^n \overline{X}_n > C\right) \leq \mathbb{P}\left(\sum_{k=1}^n Y_k > C\right)$$
• It seems to me that the $\overline{X}_k$ are all independent. So, I don't understand why we the equality in distribution above should be true because that would imply that the $X_k$ are independent as well... – user52227 May 28 '18 at 7:15
• Use induction to prove equality in distribution. Define $Y^{k-1} := Y_{1,\dots,k-1}$ for any process $Y$. $X_1$ and $\overline{X}_1$ are Bernoulli with the same parameter. Apply induction: $$\mathbb{P}(\overline{X}_k=1,\overline{X}^{k-1} = x) = \mathbb{P}(\overline{X}_k=1|\overline{X}^{k-1} = x)\mathbb{P}(\overline{X}^{k-1} = x) = \mathbb{P}(U_k < p_k(\overline{X}^{k-1})|\overline{X}^{k-1}=x) \mathbb{P}(X^{k-1} = x) = p_k(x)\mathbb{P}(X^{k-1} = x) = \mathbb{P}(X_k=1|X^{k-1} = x)\mathbb{P}(X^{k-1} = x) = \mathbb{P}(X_k=1,X^{k-1} = x)$$ The $\overline{X}_k = 0$ case is similar. – forgottenarrow May 28 '18 at 18:47