1
$\begingroup$

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]$?

$\endgroup$
1
$\begingroup$

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)$$

$\endgroup$
  • $\begingroup$ Thank you for your comment! The transformation involved was very nice. The underlying conditions of my problem can also be stated as a bound on successive terms |X_t - X_{t-1}|, for which I discovered the Azuma-Hoeffding inequality. $\endgroup$ – Alex Jones May 27 '18 at 17:32
  • $\begingroup$ 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... $\endgroup$ – user52227 May 28 '18 at 7:15
  • $\begingroup$ 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. $\endgroup$ – forgottenarrow May 28 '18 at 18:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.