How to find correlations between multiple low-frequency variables? Let's say we have multiple ($k > 2$) binary variables (e.g., genetic mutations and/or disease states), which appear at a given frequency of $f(1)$ to $f(k)$ in a sample.  We would like to test whether there is a correlation between these variables, such that the combined frequency $F$ at which all $k$ variables occur together (in each test individual) is greater than the product of individual frequencies $f(1)$ to $f(k)$, so that:
$H_0: F \leq \prod_{i=1}^k f(i)$
$H_1: F > \prod_{i=1}^k f(i)$
Now, how to determine the minimum sample size $n$ for such a test, given that the individual frequencies $f(1)$ to $f(k)$ may be very low (e.g., <0.0001), and so the combined frequency $F$ may be extremely low?
In particular, is there a formula to define $n$ in terms of $\alpha$, $\beta$, and the individual frequencies $f(1)$ to $f(k)$?
In case it helps, we can simplify the problem by assuming that all individual frequencies are equal, so that:
$f = { f(1) = f(2) = \ldots = f(k) }$
$H_0: F \leq f^k$
$H_1: F > f^k$
So what would be the minimum sample size in this case?
 A: Still no direct answer to my question, but with a bit of digging and putting the pieces together myself, I have managed to get to the bottom of this puzzle…
So, in order to identify at least one “significant” correlation (if there actually is one) between any 2 out of $k$ binary variables, you would need a total sample size of at least:
$$n = \Huge[\small{\frac{z(1-2\alpha/(k^2-k))\sqrt{f^2(1-f^2)}+z(1-\beta)\sqrt{(1+d)f^2(1-(1+d)f^2)}}{df^2}}\Huge]^{\large2}$$
where:
$z(p)$ = critical value of the standard normal distribution at $p$
$k$ = total number of variables tested in all possible 2-variable combinations
$f$ = frequency of each variable in the sample (assumed constant)
$d$ = minimum effect size (% increase in observed vs expected random correlations)
$\alpha$ = significance level (target p value) = type I error rate
$\beta$ = 1 - power = type II error rate
Note this formula takes into account the issue of multiple hypothesis testing, where the significance level $\alpha$ must be divided by the total number of tests (all possible 2-variable combinations) in order to keep the false discovery rate below the nominal $\alpha$.
So for example, with $k$ = 1,000, $f$ = 0.01, $d$ = 20%, $\alpha$ = 0.05 and $\beta$ = 0.2, you would need to sample (i.e., fully sequence and characterize) at least 5.79 million people in order to identify at least one significant correlation.
And if the variables appear at 10 times lower frequency in the sample ($f$ = 0.001), then you would need to sample at least 579 million people to identify any correlations...
Anyway, you get the idea, it's very easy to see how we quickly run out of people on the planet before we can ensure that any results are meaningful!
