<p>Only one-sided deciders are robust to bad coins, under your definition; no other decider can be robust to bad coins.  Let <span class="math-container">$D$</span> be a decider that is not one-sided.  For <span class="math-container">$x \in \mathcal{Y}$</span>, let <span class="math-container">$\mathcal{W}_x = \{r \in \{0,1\}^m : D(x,r)=\textsf{no}\}$</span> be the set of random strings <span class="math-container">$r$</span> such that <span class="math-container">$D$</span> outputs the wrong answer.  Consider a distribution <span class="math-container">$R$</span> that, with probability <span class="math-container">$1/3+\epsilon$</span>, picks <span class="math-container">$r$</span> uniformly at random from <span class="math-container">$\mathcal{W}_x$</span>, and with probability <span class="math-container">$2/3-\epsilon$</span>, picks <span class="math-container">$r$</span> uniformly at random from its complement.  Then the decider is correct on <span class="math-container">$x$</span> with probability <span class="math-container">$2/3 - \epsilon$</span> when <span class="math-container">$r$</span> is chosen from <span class="math-container">$R$</span>; yet <span class="math-container">$d_{TV}(R,U) = \epsilon$</span>.  So, there is no <span class="math-container">$c \in [0,1)$</span> with the desired property; you'd need to take <span class="math-container">$c=1$</span>.</p>

<p>If you relax your definition to allow <span class="math-container">$c \in [0,1]$</span>, so that (non-one-sided) deciders robust to bad coins exist, then the answer to your question is yes, it is a strict subset.  It is not hard to come up with trivial examples.  For instance, suppose that <span class="math-container">$D$</span> is correct for all choices of <span class="math-container">$r$</span> except for a single bad value <span class="math-container">$r_\text{bad}$</span>; if <span class="math-container">$r=r_\text{bad}$</span>, then <span class="math-container">$D$</span> is incorrect.  This decider is robust to bad coins but is not a one-sided decider.</p>

<p>Moreover: with such an adjusted definition, every decider is robust to bad coins. By the definition of total variation distance and the definition of a decider,</p>

<p><span class="math-container">$$\Pr_{r \in R}[\mathcal{W}_x] \le \Pr_{r \in U}[\mathcal{W}_x] + d_{TV}(R,U) \le 1/3 + d_{TV}(R,U),$$</span></p>

<p>so the probability that (1) holds is at least <span class="math-container">$2/3 - d_{TV}(R,U)$</span>.  Thus, <span class="math-container">$D$</span> is robust to bad coins with <span class="math-container">$c = 1$</span>.</p>

<p>So, I think you need to re-consider your definition of "robust to bad coins".  With your original formulation (<span class="math-container">$c \in [0,1)$</span>), only one-sided deciders can ever meet it; with an adjusted formulation (<span class="math-container">$c \in [0,1]$</span>), every decider meets it.  In both cases, it collapses to be equivalent to some other existing notion.  This suggests that we need a different definition.</p>

CC BY-SA 4.0
2019-04-04T19:51:44.333Z
Reading your answer in detail as soon as possible, but in the first line, you mean "no (non-one-sided) decider is robust", right?
Clement C.
CC BY-SA 4.0
2019-04-04T20:11:21.567Z
For one-sided testers, the set $\mathcal{W}_x$ is empty, so the distribution is not well-defined. Is it?
Clement C.
CC BY-SA 4.0
2019-04-04T20:14:45.173Z
@ClementC., oops, you are absolutely right, I misunderstood what you were writing.  My fault.  I've edited my answer accordingly.  Sorry about that.
D.W.
CC BY-SA 4.0
2019-04-04T20:18:04.523Z
No worries. Also, after reading your answer (I had excluded $c=1$ indeed because of the very fact it makes everything robust), indeed it looks like it's not too interesting a concept per se -- though it gives a further motivation for one-sided testers. Thank you!
Clement C.
CC BY-SA 4.0
2019-04-04T22:37:14.963Z
Is it allowed for a decider to output yes on $x\in\mathcal{Y}$ with probability strictly between $2/3$ and $1$? If so, it seems that $d_{TV}(R, U) > \varepsilon$ in such case.
Sasha Kozachinskiy
CC BY-SA 4.0
2019-04-05T00:15:51.710Z
@SashaKozachinskiy, by the definitions in the question, yes, that is possible.  If you are referring to the distribution $R$ defined in the first paragraph of my answer, how did you conclude $d_{TV}(R,U) > \epsilon$?  It seems to me that $d_{TV}(R,U)=\epsilon$ regardless of the success probability.  The total variation distance is $$\frac{1}{2} \sum_r |\Pr_R(r) - \Pr_U(r)| = \frac12 |\mathcal{W}_x| \sum_{r \in \mathcal{W}_x} |\Pr_R(r) - \Pr_U(r)| + \frac12 |\overline{\mathcal{W}_x}| \sum_{r \notin \mathcal{W}_x} |\Pr_R(r) - \Pr_U(r)| = \frac12 \epsilon + \frac12 \epsilon.$$
D.W.
CC BY-SA 4.0
2019-04-05T02:22:56.953Z
D.W. It's not a problem for the answer (can easily be fixed), but @SashaKozachinskiy is right. As defined, the TV distance between $R$ and $U$ is $$\mathrm{d}_{\rm TV}(R,U) = (R(\mathcal{W}_x)-U(\mathcal{W}_x)) = \frac{1}{3}+\epsilon - \frac{|\mathcal{W}_x|}{2^n}$$ which is exactly $\epsilon$ only if $|\mathcal{W}_x| = 2^n/3$ (and could be more otherwise, since our promise is  $|\mathcal{W}_x| \leq 2^n/3$). But replacing the weight $1/3+\epsilon$ by ${|\mathcal{W}_x|}/{2^n}+\epsilon$ fixes that issue.
Clement C.
CC BY-SA 4.0
2019-04-04T19:04:19.503Z
2019-04-04T20:15:33.840Z
2019-04-04T20:15:33.840Z
D.W.
<p>Consider any problem where, fixing two (disjoint) subsets <span class="math-container">$\mathcal{Y},\mathcal{N}\subseteq \{0,1\}^n$</span> of the input space, the goal is to obtain a randomized algorithm <span class="math-container">$D$</span> which, given a uniformly random bit string <span class="math-container">$r$</span>, and on input <span class="math-container">$x\in \{0,1\}^n$</span>, with probability at least <span class="math-container">$2/3$</span> over <span class="math-container">$r$</span>,</p>

<ol>
<li>outputs <span class="math-container">$\mathsf{yes}$</span> if <span class="math-container">$x\in\mathcal{Y}$</span>;</li>
<li>outputs <span class="math-container">$\mathsf{no}$</span> if <span class="math-container">$x\in\mathcal{N}$</span>.</li>
</ol>

<p>Call any such <span class="math-container">$D$</span> a <em>decider for <span class="math-container">$(\mathcal{Y},\mathcal{N})$</span></em>.</p>

<p>(A natural example is property testing.) If further the first item (completeness) holds with probability one, then <span class="math-container">$D$</span> is <em>one-sided</em>.</p>

<p>Clearly, if <span class="math-container">$D$</span> is one-sided, then (1) holds even if <span class="math-container">$r$</span> comes from an arbitrary distribution, possibly chosen adversarially, instead of being uniform.</p>

<p>Let us say a decider for <span class="math-container">$(\mathcal{Y},\mathcal{N})$</span> is <em>robust to bad coins</em> if completeness (first item) degrades gracefully as the distribution <span class="math-container">$R$</span> of <span class="math-container">$r$</span> gets far from uniform. For instance, the probability that completeness holds only goes down linearly, as <span class="math-container">$2/3-c\operatorname{d_{TV}}(R,U)$</span> for some <span class="math-container">$c\in[0,1)$</span> .</p>

<p>My question is then:</p>

<blockquote>
  <p>Is the class of one-sided deciders a strict subset of deciders robust to bad coins? And has this been studied in some form?</p>
</blockquote>

<p>(Also, the definition of robustness is quite open.. I went with total variation, but maybe something like min-entropy of <span class="math-container">$R$</span> makes more sense?)</p>

<randomized-algorithms><randomness><property-testing>
Robustness to non-uniform randomness vs. one-sidedness
Clement C.
# Robustness to non-uniform randomness vs. one-sidedness

(Asked by: username_0 on 2019-04-04)

Consider any problem where, fixing two (disjoint) subsets $\mathcal{Y},\mathcal{N}\subseteq \{0,1\}^n$ of the input space, the goal is to obtain a randomized algorithm $D$ which, given a uniformly random bit string $r$, and on input $x\in \{0,1\}^n$, with probability at least $2/3$ over $r$,

1. outputs $\mathsf{yes}$ if $x\in\mathcal{Y}$;
2. outputs $\mathsf{no}$ if $x\in\mathcal{N}$.

Call any such $D$ a *decider for $(\mathcal{Y},\mathcal{N})$*.

(A natural example is property testing.) If further the first item (completeness) holds with probability one, then $D$ is *one-sided*.

Clearly, if $D$ is one-sided, then (1) holds even if $r$ comes from an arbitrary distribution, possibly chosen adversarially, instead of being uniform.

Let us say a decider for $(\mathcal{Y},\mathcal{N})$ is *robust to bad coins* if completeness (first item) degrades gracefully as the distribution $R$ of $r$ gets far from uniform. For instance, the probability that completeness holds only goes down linearly, as $2/3-c\operatorname{d\_{TV}}(R,U)$ for some $c\in[0,1)$ .

My question is then:

> Is the class of one-sided deciders a strict subset of deciders robust to bad coins? And has this been studied in some form?

(Also, the definition of robustness is quite open.. I went with total variation, but maybe something like min-entropy of $R$ makes more sense?)

**Tags:** randomized-algorithms, randomness, property-testing


---

## 1 answers

### Answer by username_1 on 2019-04-04. Score: 2 | Accepted answer

Only one-sided deciders are robust to bad coins, under your definition; no other decider can be robust to bad coins. Let $D$ be a decider that is not one-sided. For $x \in \mathcal{Y}$, let $\mathcal{W}\_x = \{r \in \{0,1\}^m : D(x,r)=\textsf{no}\}$ be the set of random strings $r$ such that $D$ outputs the wrong answer. Consider a distribution $R$ that, with probability $1/3+\epsilon$, picks $r$ uniformly at random from $\mathcal{W}\_x$, and with probability $2/3-\epsilon$, picks $r$ uniformly at random from its complement. Then the decider is correct on $x$ with probability $2/3 - \epsilon$ when $r$ is chosen from $R$; yet $d\_{TV}(R,U) = \epsilon$. So, there is no $c \in [0,1)$ with the desired property; you'd need to take $c=1$.

If you relax your definition to allow $c \in [0,1]$, so that (non-one-sided) deciders robust to bad coins exist, then the answer to your question is yes, it is a strict subset. It is not hard to come up with trivial examples. For instance, suppose that $D$ is correct for all choices of $r$ except for a single bad value $r\_\text{bad}$; if $r=r\_\text{bad}$, then $D$ is incorrect. This decider is robust to bad coins but is not a one-sided decider.

Moreover: with such an adjusted definition, every decider is robust to bad coins. By the definition of total variation distance and the definition of a decider,

$$\Pr\_{r \in R}[\mathcal{W}\_x] \le \Pr\_{r \in U}[\mathcal{W}\_x] + d\_{TV}(R,U) \le 1/3 + d\_{TV}(R,U),$$

so the probability that (1) holds is at least $2/3 - d\_{TV}(R,U)$. Thus, $D$ is robust to bad coins with $c = 1$.

So, I think you need to re-consider your definition of "robust to bad coins". With your original formulation ($c \in [0,1)$), only one-sided deciders can ever meet it; with an adjusted formulation ($c \in [0,1]$), every decider meets it. In both cases, it collapses to be equivalent to some other existing notion. This suggests that we need a different definition.

> **Comments:**
> **username_0**: Reading your answer in detail as soon as possible, but in the first line, you mean "no (non-one-sided) decider is robust", right?  
> **username_0**: For one-sided testers, the set $\mathcal{W}_x$ is empty, so the distribution is not well-defined. Is it?  
> **username_1**: @ClementC., oops, you are absolutely right, I misunderstood what you were writing.  My fault.  I've edited my answer accordingly.  Sorry about that.  
> **username_0**: No worries. Also, after reading your answer (I had excluded $c=1$ indeed because of the very fact it makes everything robust), indeed it looks like it's not too interesting a concept per se -- though it gives a further motivation for one-sided testers. Thank you!  
> **username_2**: Is it allowed for a decider to output yes on $x\in\mathcal{Y}$ with probability strictly between $2/3$ and $1$? If so, it seems that $d_{TV}(R, U) > \varepsilon$ in such case.  
> **username_1**: @SashaKozachinskiy, by the definitions in the question, yes, that is possible.  If you are referring to the distribution $R$ defined in the first paragraph of my answer, how did you conclude $d_{TV}(R,U) > \epsilon$?  It seems to me that $d_{TV}(R,U)=\epsilon$ regardless of the success probability.  The total variation distance is $$\frac{1}{2} \sum_r |\Pr_R(r) - \Pr_U(r)| = \frac12 |\mathcal{W}_x| \sum_{r \in \mathcal{W}_x} |\Pr_R(r) - \Pr_U(r)| + \frac12 |\overline{\mathcal{W}_x}| \sum_{r \notin \mathcal{W}_x} |\Pr_R(r) - \Pr_U(r)| = \frac12 \epsilon + \frac12 \epsilon.$$  
> **username_0**: username_1 It's not a problem for the answer (can easily be fixed), but @SashaKozachinskiy is right. As defined, the TV distance between $R$ and $U$ is $$\mathrm{d}_{\rm TV}(R,U) = (R(\mathcal{W}_x)-U(\mathcal{W}_x)) = \frac{1}{3}+\epsilon - \frac{|\mathcal{W}_x|}{2^n}$$ which is exactly $\epsilon$ only if $|\mathcal{W}_x| = 2^n/3$ (and could be more otherwise, since our promise is  $|\mathcal{W}_x| \leq 2^n/3$). But replacing the weight $1/3+\epsilon$ by ${|\mathcal{W}_x|}/{2^n}+\epsilon$ fixes that issue.  

---

