Let $A$ and $B$ be finite disjoint sets of cardinality $N$. Suppose $X_a,X_b,X_{a\to b}, X_{b\to a}$, where $(a,b)\in A\times B$, are independent Bernoulli random variables so that $X_a,X_b\sim\mathcal{B}(p)$, $X_{a\to b},X_{b\to a}\sim\mathcal{B}(q)$ for parameters $0\leq p,q\leq 1$.

Create random subsets $T_A\subset A$ and $T_B\subset B$ by setting $T_{A}=\{a\in A\mid X_a=1\}$, $T_{B}=\{b\in B\mid X_b=1\}$. Thus, $\#T_A$ and $\#T_B$ follow the binomial distribution $\mathcal{B}(N,p)$. Let $C=A\sqcup B$ and create a random subset $T_C\subset C$ like so: $$\begin{cases} \forall a\in A,~a\in T_C\iff a\in T_A\text{ and }\exists b\in T_B,X_{b\to a} = 1 \\ \\ \forall b\in B,~b\in T_C\iff b\in T_B\text{ and }\exists a\in T_A,X_{a\to b} = 1\end{cases}$$ A computation shows that the probability of $c\in C$ lying in $T_C$ is $p'=p(1-(1-pq)^N)$, but the events $[c\in T_C]$ and $[c'\in T_C]$ are not independent.

Question 1 What is the distribution of $\#T_C$? Has this problem been studied before?

We have $\#T_C=\sum_{c\in C}1_{[c\in T_C]}$ is a sum of nonindependent Bernoulli random variables, and such sums have been studied.

Question 2 What is a good reference to learn about sums of nonindependent Bernoulli random variables ?

It seems that the random variables $1_{[c\in T_C]}$ and $1_{[c'\in T_C]}$ are positively correlated.

Question 3 Can one expect to prove something like $$\forall 0\leq k\leq 2N,\quad\mathbf{P}[\#T_C\geq k]\geq\mathbf{P}[\mathcal{B}(2N,p')\geq k]?$$

Finally, if the answer to the last question is positive, consider a generalized problem: start with independent identically distributed random subsets $S_A\subset A$, $S_B\subset B$ such that $\forall 0\leq k\leq N,\mathbf{P}[\#S_A\geq k]\geq\mathbf{P}[\mathcal{B}(N,p)\geq k]$, and we again have independent Bernoulli variables $X_{a\to b},X_{b\to a}\sim\mathcal{B}(q)$. Construct a random subset $S_C\subset C$ as previously: $$\begin{cases} \forall a\in A,~a\in S_C\iff a\in S_A\text{ and }\exists b\in S_B,X_{b\to a} = 1 \\ \\ \forall b\in B,~b\in S_C\iff b\in S_B\text{ and }\exists a\in S_A,X_{a\to b} = 1\end{cases}$$

Question 4 Does $S_C$ satisfy $$\forall 0\leq k\leq 2N,\quad\mathbf{P}[\#S_C\geq k]\geq\mathbf{P}[\mathcal{B}(2N,p')\geq k]?$$


Your Answer

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

Browse other questions tagged or ask your own question.