<p>1) Yes, but only because of your definition. Take a unary language $L\in EXP\setminus BPP$ (yeah, I know this might be empty, in that case just take something even bigger than $EXP$), that is very sparse in the sense that $n\notin L$ if $n$ is not a tower of $2's$, i.e., of the form $2^{2^{2^\ldots}}$. Define $p=\sum_{n\in L} 1/n$. This $p$ is not $BPP$-computable, but $p$ can be approximated in $P$ up to a small enough additive error that allows the simulation of a $BPP_p$ machine.</p>

<p>Had you defined $BPP$-computable such that you want to approximate $p$ up to an additive error of $1/n$ (instead of $1/2^n$) in polynomial time, things would be different.</p>

<p><strong>Update.</strong> The below answer is for the case when the additive error we allow is $2^{-n}$ instead of $2^{-n-1}$.</p>

<p>2) Yes, because here you can forget about the polynomial restriction on the classes and by sampling $2^n$ times you can get the $n$-th bit of $p$ in $BPP_p$.</p>

CC BY-SA 3.0
2016-08-08T06:08:24.977Z
2) I think that central limit theorem suggests that one should sample $2^{2n}$, not $2^n$, times to acquire $2^{-n}$ precision. But the main problem is that sometimes we need much greater precision. Say, if $|p-\frac12|<\epsilon$ then one needs $\frac1{\epsilon^2}$ samples to compute even the first digit. And the number of samples needed may be arbitrarily, even uncomputably, large. The point is a bit clarified in the edit.
Daniil Musatov
CC BY-SA 3.0
2016-08-08T07:00:42.193Z
@Daniil: As I've commented on the question as well, you did not ask for the computation of the digits in your definition of $BPP$-computable. So, if $p$ equals, say, $0.01111111111$, then one should guess $1$ for the first digit after the comma according to your def.
domotorp
CC BY-SA 3.0
2016-08-08T11:53:25.110Z
We are now talking about uncomputable $p$, aren't we? If I understand you right, you suggest not to compute by sampling digits of $p$, but instead to compute whether the $i$'th digit of $2^{-i-1}$ binary rational approximation of $p$ is 1. But here we face the same problem: to compute the first digit we need to distinguish 0.010000000001 and 0.001111111110.
Daniil Musatov
CC BY-SA 3.0
2016-08-08T20:11:26.370Z
@Daniil: OK, my bad, I thought you wanted a binary rational whose distance is at most $2^{-n}$ from $p$. I have updated my answer accordingly. Are you happy with my solution to 1)?
domotorp
CC BY-SA 3.0
2016-08-08T05:23:57.647Z
2016-08-08T20:10:28.167Z
2016-08-08T20:10:28.167Z
domotorp
<p>Let a probabilistic Turing machine have access to an unfair coin that comes up heads with probability $p$ (flips are independent). Define $BPP_p$ as the class of languages recognizable by such a machine in polynomial time. It is a standard exercise to prove that:</p>

<p>A) If $p$ is rational or even $BPP$-computable then $BPP_p=BPP$. (By $BPP$-computable I mean: there is a randomized polynomial algorithm that being fed $n$ in unary returns w.h.p. the binary rational with denominator $2^n$ that lies within $2^{-n-1}$ of $p$.)</p>

<p>B) For some uncomputable $p$ the class $BPP_p$ contains an undecidable language and hence is larger than $BPP$. Such values of $p$ form a dense set in $(0,1)$.</p>

<p>My question is the following: what happens in between? Is there a criterion for $BPP_p=BPP$? In particular:</p>

<p>1) Do uncomputable in $BPP$ probabilities $p$ exist such that $BPP_p=BPP$? (They may be computable in some higher classes).</p>

<p>2) Is $BPP_p$ wider than $BPP$ for all uncomputable $p$? (The parameters in question are those whose binary expansion contains very long sequences of zeros and/or ones. In this case computing bits by random sampling may take very long, even uncomputable time, and the problem cannot be rescaled to polynomial time. Sometimes the difficulty can be overcome by another base of expansion, but certain $p$ may fool all bases).</p>

CC BY-SA 3.0
2016-08-07T19:48:50.940Z
What exactly do you mean by p being (un)computable?
daniello
CC BY-SA 3.0
2016-08-08T01:42:23.370Z
I added the definition of $BPP$-computable. For computable in general one may just drop the words "randomized polynomial" or simply say that binary expansion is computable. (With bounded resources this is not the same.)
Daniil Musatov
CC BY-SA 3.0
2016-08-08T02:45:56.573Z
I think $BPP_p \neq BPP$ for every uncomputable $p$ because given a $p$-biased coin one can compute the $n$'th bit of $p$ by sampling. Suppose we can compute the $n$'th bit in time $f(n)$, then the language that contains $1^x$ for all $x$ such that the $f^{-1}(x)$'th bit of $p$ is $1$ is in $BPP_p$, but clearly it is uncomputable.
daniello
CC BY-SA 3.0
2016-08-08T04:16:52.020Z
This is definitely true for vast majority of uncomputable $p$. But there is a caveat: if $p$ contains very long sequences of zeros and ones then it may need very long sampling to determine the $n$'th bit. This sampling may be so long that $f(n)$ would be uncomputable (like the Busy Beavers function). I also doubt it can be precisely computed from sampling itself. And it seems that without computing $f(n)$ one cannot recognize the language mentioned.
Daniil Musatov
<cc.complexity-theory><randomized-algorithms><probabilistic-complexity>
When does BPP with a biased coin equal standard BPP?
Daniil Musatov
# When does BPP with a biased coin equal standard BPP?

(Asked by: username_0 on 2016-08-07)

Let a probabilistic Turing machine have access to an unfair coin that comes up heads with probability $p$ (flips are independent). Define $BPP\_p$ as the class of languages recognizable by such a machine in polynomial time. It is a standard exercise to prove that:

A) If $p$ is rational or even $BPP$-computable then $BPP\_p=BPP$. (By $BPP$-computable I mean: there is a randomized polynomial algorithm that being fed $n$ in unary returns w.h.p. the binary rational with denominator $2^n$ that lies within $2^{-n-1}$ of $p$.)

B) For some uncomputable $p$ the class $BPP\_p$ contains an undecidable language and hence is larger than $BPP$. Such values of $p$ form a dense set in $(0,1)$.

My question is the following: what happens in between? Is there a criterion for $BPP\_p=BPP$? In particular:

1) Do uncomputable in $BPP$ probabilities $p$ exist such that $BPP\_p=BPP$? (They may be computable in some higher classes).

2) Is $BPP\_p$ wider than $BPP$ for all uncomputable $p$? (The parameters in question are those whose binary expansion contains very long sequences of zeros and/or ones. In this case computing bits by random sampling may take very long, even uncomputable time, and the problem cannot be rescaled to polynomial time. Sometimes the difficulty can be overcome by another base of expansion, but certain $p$ may fool all bases).

**Tags:** cc.complexity-theory, randomized-algorithms, probabilistic-complexity
> **Comments:**
> **username_1**: What exactly do you mean by p being (un)computable?  
> **username_0**: I added the definition of $BPP$-computable. For computable in general one may just drop the words "randomized polynomial" or simply say that binary expansion is computable. (With bounded resources this is not the same.)  
> **username_1**: I think $BPP_p \neq BPP$ for every uncomputable $p$ because given a $p$-biased coin one can compute the $n$'th bit of $p$ by sampling. Suppose we can compute the $n$'th bit in time $f(n)$, then the language that contains $1^x$ for all $x$ such that the $f^{-1}(x)$'th bit of $p$ is $1$ is in $BPP_p$, but clearly it is uncomputable.  
> **username_0**: This is definitely true for vast majority of uncomputable $p$. But there is a caveat: if $p$ contains very long sequences of zeros and ones then it may need very long sampling to determine the $n$'th bit. This sampling may be so long that $f(n)$ would be uncomputable (like the Busy Beavers function). I also doubt it can be precisely computed from sampling itself. And it seems that without computing $f(n)$ one cannot recognize the language mentioned.  

---

## 1 answers

### Answer by username_2 on 2016-08-08. Score: 1

1) Yes, but only because of your definition. Take a unary language $L\in EXP\setminus BPP$ (yeah, I know this might be empty, in that case just take something even bigger than $EXP$), that is very sparse in the sense that $n\notin L$ if $n$ is not a tower of $2's$, i.e., of the form $2^{2^{2^\ldots}}$. Define $p=\sum\_{n\in L} 1/n$. This $p$ is not $BPP$-computable, but $p$ can be approximated in $P$ up to a small enough additive error that allows the simulation of a $BPP\_p$ machine.

Had you defined $BPP$-computable such that you want to approximate $p$ up to an additive error of $1/n$ (instead of $1/2^n$) in polynomial time, things would be different.

**Update.** The below answer is for the case when the additive error we allow is $2^{-n}$ instead of $2^{-n-1}$.

2) Yes, because here you can forget about the polynomial restriction on the classes and by sampling $2^n$ times you can get the $n$-th bit of $p$ in $BPP\_p$.

> **Comments:**
> **username_0**: 2) I think that central limit theorem suggests that one should sample $2^{2n}$, not $2^n$, times to acquire $2^{-n}$ precision. But the main problem is that sometimes we need much greater precision. Say, if $|p-\frac12|<\epsilon$ then one needs $\frac1{\epsilon^2}$ samples to compute even the first digit. And the number of samples needed may be arbitrarily, even uncomputably, large. The point is a bit clarified in the edit.  
> **username_2**: @Daniil: As I've commented on the question as well, you did not ask for the computation of the digits in your definition of $BPP$-computable. So, if $p$ equals, say, $0.01111111111$, then one should guess $1$ for the first digit after the comma according to your def.  
> **username_0**: We are now talking about uncomputable $p$, aren't we? If I understand you right, you suggest not to compute by sampling digits of $p$, but instead to compute whether the $i$'th digit of $2^{-i-1}$ binary rational approximation of $p$ is 1. But here we face the same problem: to compute the first digit we need to distinguish 0.010000000001 and 0.001111111110.  
> **username_2**: @Daniil: OK, my bad, I thought you wanted a binary rational whose distance is at most $2^{-n}$ from $p$. I have updated my answer accordingly. Are you happy with my solution to 1)?  

---

