Consider the set $[n]=\{1,2,\ldots,n\}$. Suppose for each set $A\subseteq [n]$ I have a $p_A \in [0,1]$. I now create a random collection $\mathcal{W}\subseteq\mathcal{P}([n])$ of subsets of $[n]$ by including each $A$ with probability $p_A$, independently. What is the probability that their union covers $[n]$, that is, that $$\bigcup_{W\in\mathcal{W}} W = [n]$$

This seems like a problem that absolutely has been considered before -- it's easy to state and seems natural -- and the answer should "just" be some suitably symmetric multivariate polynomial. Unfortunately, I can't figure it out on my own, and my google-fu hasn't availed me either.

  • 1
    $\begingroup$ You can easily generate some long formula (say, by inclusion-exclusion: $\sum_{B\subset[n]}(-1)^{|B|}\prod_{A\subset[n],A\cap B\ne\varnothing}(1-p_A)$) but why do you have any hope that it collapses to something nice? $\endgroup$
    – fedja
    Jun 14 '19 at 1:20

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.