I am studying the DNF counting problem from the book Randomized Algorithm by Rajeev Motwani.
Then, by Theorem 11.1(Estimator Theorem), in order to have an $\epsilon$-approximation to $\mid G\mid$ with high probability, the sampling size $\begin{equation}N \geq \displaystyle\frac{4}{\epsilon^{2}\rho}\ln\frac{2}{\delta}\end{equation}$, where $\rho = \displaystyle\frac{\mid G\mid}{\mid U\mid}$.
My question is, our goal is to estimate the size of $\mid G\mid$, we need to repeat the sampling process more than $N$ times, so the value of $\rho$ should be probably known. But in that case, we know $\mid G \mid$, exactly. That is what I am confused.
UPDATE
- Here is a lecture note from CMU, DNF counting. And above, $G$ denotes the set of satisfying assignments, while denoting by $S$ in CMU note.