Upper bound for dependent variables

Question

If i have a set of $n$ dependent variables $\{n_1,...n_n\}$

The probability of success for every one of those variables is equal to $k$ but if there is one variable that succeeded the probability that another variable will succeed is $k'<k$.

Is there any problem if i assume that the variables are indenpendent and follow a binomial distribution to derive an upper bound on the probability of $x$ variables succeed?

Answer 1

So the idea is (roughly) to use stochastic domination. Consider the sequence $(X_1,\dots,X_n)$ of random variables that you are considering. Consider also a sequence $(Y_1,\dots,Y_n)$ of random variables of parameter $(m,k)$ ($m$ tries, $k$ probability of success for each try). You have $$ \mathbb{P}(\sum_{i=1}^n X_i \ge x) \le \mathbb{P}(\sum_{i=1}^n Y_i \ge x) = \mathbb{P}(Z_n \ge x), $$ where $Z_n = \sum_{i=1}^n Y_i$.

The last quantity in the RHS can be computed explicitely: $Z_n$ is a binomial r.v. of parameter (mn, k). Now my inequality above is not fully obvious, see below if you need the details.

Bonus track : to justify this with a coupling, let $U$ be a uniform random variable on $(0,1)$ and $k' < k$. Consider $$ X = \mathbf{1}_{U \le k'}, \qquad Y = \mathbf{1}_{U \le k}. $$ With this construction, $X \sim \mathcal{B}(k')$, $Y \sim \mathcal{B}(k)$ and $X \le Y$ for all $\omega$ in your probability space (i.e. for all realization of $U$). Now you can build

• First of whole sequence $A^1, \dots, A^m$ and $C^1,\dots, C^m$ that you sum to get your binomial $X_1 \sim \mathcal{Bin}(m,k')$ and $Y_1 \sim \mathcal{Bin}(m,k)$. As $A^i \le C^i$ for all $i$, $X_1 \le Y_1$.
• Once this is clear, you get your whole sequence of $(X_i)_{i \ge 1}$ and $(Y_i)_{i \ge 1}$ using this and obtain exactly the sequence $(X_1,\dots,X_n)$ and $(Y_1,\dots,Y_n)$ desired, with $X_j \le Y_j$ for all $j \ge 1$, which fully justifies my computation.