<p>Suppose we have a predicate <span class="math-container">$\phi:\{0,1\}^n\to \{0, 1\}$</span> corresponding to a self-reducible problem and a FPAUS that can approximately sample from a distribution <span class="math-container">$p$</span> such that <span class="math-container">$\|p-u\|_{L_1}\leq \delta$</span>, where <span class="math-container">$u$</span> is the uniform distribution of <span class="math-container">$\phi^{-1}(1)$</span>. Is it possible to get an approximation of the number of solutions <span class="math-container">$|\phi^{-1}(1)|$</span> within a relative error of <span class="math-container">$\varepsilon$</span> for an arbitrary <span class="math-container">$\varepsilon&gt;0$</span> ignoring the time complexity ? Or is the lowest <span class="math-container">$\varepsilon$</span> we can hope for bounded by (a function of) <span class="math-container">$\delta$</span> ?</p>

CC BY-SA 4.0
2020-10-27T19:53:22.947Z
Ignoring time complexity, why not just enumerate $x\in\{0,1\}^n$, compute $\phi(x)$, and count the number of $x$ such that $\phi(x)=1$?  Or is the only access to $\phi$ via the sampler?  In the latter case, surely you can have no bound independent of $\delta$, because in the case that $\delta$ is large, $p$ could, say, have all its probability on just one element $x_0$ of $\phi^{-1}(1)$, so all you can learn about $\phi^{-1}(1)$ is that it contains $x_0$.
Neal Young
CC BY-SA 4.0
2020-10-27T19:59:12.530Z
@NealYoung Thank you for the comment; indeed I forgot those two assumptions. First, we have access to $\phi$ only via the sampler and second, we should assume that the support of $p$ is $\phi^{-1}(1)$, i.e. all points in $\phi^{-1}(1)$ have non-zero mass under $p$. What can one do in such a case ? Are there any studies that deal with reducing the relative error of the approximate counter for a fixed $\delta$ that we cannot influence ? In all the texts I could find, it is assumed that we can choose a desired $\delta$ of the FPAUS (usually a function of $\varepsilon$).
Nocturne
CC BY-SA 4.0
2020-10-28T01:29:19.260Z
Consider any algorithm $A$.  Consider what $A$ on input $(n, S)$ where $S$ is the sampler that can return only one input, say, $\mathbf 0$.  Let $T_n$ be the number of samples that $A$ takes on input $(n, S)$.  Now, let $S'$ be a sampler that, for each sample, returns $\mathbf 0$ with probability $1-\epsilon$, and otherwise (with probability $\epsilon$) returns an element uniformly at random from $\{0,1\}^n$.  As long as $\epsilon^{-1} \gg T_n$, on input $(n, S')$, w.h.p. $A$ returns the same output as it does for $(n, S)$, so must be wrong w.h.p. on one of the two inputs.
Neal Young
CC BY-SA 4.0
2020-10-28T12:27:38.783Z
@NealYoung If I understand correctly, your counterexample is to construct a distribution $p$ that has almost all its mass ($1-\varepsilon$) concentrated on one element of $\phi^{-1}(1)$ and let the remaining mass of $\varepsilon$ be uniformly distributed on the remaining elements. This would yield a high $\delta$ for the $L_1$ distance between $p$ and the uniform distribution on $\phi^{-1}(1)$. My question is what can we do now that this $L_1$ distance is fixed in order to achieve an arbitrarily low relative error for the approximate counter ignoring the time complexity ?
Nocturne
CC BY-SA 4.0
2020-10-28T12:29:50.847Z
If we fix the number of samples that we can afford and let $\varepsilon \to 0$, I agree that we can make the algorithm output something completely wrong with high probability. My question is what happens when we keep the sampler distribution $p$ *fixed* (with an $\varepsilon$ of your choice in your example) and then take an arbitrarily high number of samples from this (potentially very non-uniform) sampler ?
Nocturne
CC BY-SA 4.0
2020-10-28T17:16:32.997Z
I'm not fixing the number of samples, exactly.  My point is that any algorithm that is independent of $\delta$ and works for $S$ (where $|\phi^{-1}(1)| = 1$) must terminate on that input (where the sampler always returns the same thing) in some time, say $T_n$.  Then given some $S'$ as I describe (for small enough $\epsilon$) it will (w.h.p.) execute the same way.  So it either fails for $S$ or w.h.p. fails for that $S'$.  So no $\delta$-independent algorithm works on all inputs.  Of course, for every $p$ as you describe, some algorithm works: sample enough to see all of $\phi^{-1}(1)$ w.h.p.
Neal Young
<counting-complexity>
Approximate counting with non-uniform sampler
Nocturne
# Approximate counting with non-uniform sampler

(Asked by: username_0 on 2020-10-27)

Suppose we have a predicate $\phi:\{0,1\}^n\to \{0, 1\}$ corresponding to a self-reducible problem and a FPAUS that can approximately sample from a distribution $p$ such that $\|p-u\|\_{L\_1}\leq \delta$, where $u$ is the uniform distribution of $\phi^{-1}(1)$. Is it possible to get an approximation of the number of solutions $|\phi^{-1}(1)|$ within a relative error of $\varepsilon$ for an arbitrary $\varepsilon>0$ ignoring the time complexity ? Or is the lowest $\varepsilon$ we can hope for bounded by (a function of) $\delta$ ?

**Tags:** counting-complexity

> **Comments:**
> **username_1**: Ignoring time complexity, why not just enumerate $x\in\{0,1\}^n$, compute $\phi(x)$, and count the number of $x$ such that $\phi(x)=1$?  Or is the only access to $\phi$ via the sampler?  In the latter case, surely you can have no bound independent of $\delta$, because in the case that $\delta$ is large, $p$ could, say, have all its probability on just one element $x_0$ of $\phi^{-1}(1)$, so all you can learn about $\phi^{-1}(1)$ is that it contains $x_0$.  
> **username_0**: @NealYoung Thank you for the comment; indeed I forgot those two assumptions. First, we have access to $\phi$ only via the sampler and second, we should assume that the support of $p$ is $\phi^{-1}(1)$, i.e. all points in $\phi^{-1}(1)$ have non-zero mass under $p$. What can one do in such a case ? Are there any studies that deal with reducing the relative error of the approximate counter for a fixed $\delta$ that we cannot influence ? In all the texts I could find, it is assumed that we can choose a desired $\delta$ of the FPAUS (usually a function of $\varepsilon$).  
> **username_1**: Consider any algorithm $A$.  Consider what $A$ on input $(n, S)$ where $S$ is the sampler that can return only one input, say, $\mathbf 0$.  Let $T_n$ be the number of samples that $A$ takes on input $(n, S)$.  Now, let $S'$ be a sampler that, for each sample, returns $\mathbf 0$ with probability $1-\epsilon$, and otherwise (with probability $\epsilon$) returns an element uniformly at random from $\{0,1\}^n$.  As long as $\epsilon^{-1} \gg T_n$, on input $(n, S')$, w.h.p. $A$ returns the same output as it does for $(n, S)$, so must be wrong w.h.p. on one of the two inputs.  
> **username_0**: @NealYoung If I understand correctly, your counterexample is to construct a distribution $p$ that has almost all its mass ($1-\varepsilon$) concentrated on one element of $\phi^{-1}(1)$ and let the remaining mass of $\varepsilon$ be uniformly distributed on the remaining elements. This would yield a high $\delta$ for the $L_1$ distance between $p$ and the uniform distribution on $\phi^{-1}(1)$. My question is what can we do now that this $L_1$ distance is fixed in order to achieve an arbitrarily low relative error for the approximate counter ignoring the time complexity ?  
> **username_0**: If we fix the number of samples that we can afford and let $\varepsilon \to 0$, I agree that we can make the algorithm output something completely wrong with high probability. My question is what happens when we keep the sampler distribution $p$ *fixed* (with an $\varepsilon$ of your choice in your example) and then take an arbitrarily high number of samples from this (potentially very non-uniform) sampler ?  
> **username_1**: I'm not fixing the number of samples, exactly.  My point is that any algorithm that is independent of $\delta$ and works for $S$ (where $|\phi^{-1}(1)| = 1$) must terminate on that input (where the sampler always returns the same thing) in some time, say $T_n$.  Then given some $S'$ as I describe (for small enough $\epsilon$) it will (w.h.p.) execute the same way.  So it either fails for $S$ or w.h.p. fails for that $S'$.  So no $\delta$-independent algorithm works on all inputs.  Of course, for every $p$ as you describe, some algorithm works: sample enough to see all of $\phi^{-1}(1)$ w.h.p.  

---

## 0 answers

