<p>Let $M$ be a probabilistic Turing machine with a unary input $n$ whose 
space is bounded by a polynomial in $n$ and 
its output is a distribution $D$ over binary strings.
Note that the number of random bits that $M$ can use can be exponential in $n$. </p>

<p>Can $D$ be "approximated" by 
a probabilistic polynomial space-bounded Turing machine 
<em>which uses only a polynomial number of random bits</em>? </p>

<p>More formally,</p>

<blockquote>
  <p>Let $M$ be a TM with space bound $s$. 
  Is there a probabilistic Turing machine $N$ using poly(s) space and random bits with the following property: 
  $$\forall k&lt;s \ \left(Pr[M = x] &gt; 2^{-k} \implies 
Pr[N = x] &gt; 2^{-k - O(\log s)} \right)$$</p>
</blockquote>

CC BY-SA 3.0
2016-06-04T11:34:51.703Z
A polynomial-space machine using polynomially many random bits can simulate itself for all possible random choices and take appropriate measures. That is, it can be made deterministic polynomial space.
Emil Jeřábek
CC BY-SA 3.0
2016-06-04T16:36:56.620Z
Is $M$ assumed to have bounded error? If so, I believe Nisan's generator can be adapted to do what you want. If $M$'s error is one-sided (and possibly very small), then the desired result follows from Savitch's theorem.
Andrew Morgan
CC BY-SA 3.0
2016-06-04T19:33:24.837Z
@AndrewMorgan Could you explain what is "assumed to have bounded error"?
Alexey Milovanov
CC BY-SA 3.0
2016-06-05T02:58:03.673Z
I'm referring to the difference, for instance, between $\mathsf{PP}$ and $\mathsf{BPP}$, where in the first case the Turing machine just has to be right "most" ($\ge 1/2$) of the time, whereas in the latter case the Turing machine has to be right "significantly more than most" ($\ge 2/3$) of the time. What guarantees do you have regarding $M$?

I just noticed the "without enter" in your problem description- do you mean "without error"? In this case, both Nisan's PRG and Savitch's theorem appear to work.
Andrew Morgan
CC BY-SA 3.0
2016-06-05T06:54:02.940Z
@AndrewMorgan I mean that $M$ just set a distribution. There are no "right" or "wrong" outputs. And I want to approximate this distribution by another one, such that a corresponding Turing machine uses smaller number of random bits.
Alexey Milovanov
CC BY-SA 3.0
2016-06-05T07:10:28.810Z
@Alexey: Okay, I understand what you're asking for now. Formally I think you want $M$ to still take in a unary input (otherwise asymptotics don't make sense), but that's a minor point.

Also, presumably we are charging the length of the output $x$ to the space complexity of $M$. The answer to your question is "no" if we do not, because $M$ can just pass $2^n$ random bits to its output.
Andrew Morgan
CC BY-SA 3.0
2016-06-05T07:33:04.133Z
@AndrewMorgan In such case $Pr[M = x] = 2^{-2^n}$, isn't it? I allow $poly(n,k)$ space-bounded for $M'$ and so this is not a counter-example.
Alexey Milovanov
CC BY-SA 3.0
2016-06-07T11:39:35.040Z
@AndrewMorgan I think you know the answer on the simpler question: Does BPP-PSPACE equal to PSPACE (if we allow exponential number of random bits)? I do not understand how it is directly follows from Savitch's theorem
Alexey Milovanov
CC BY-SA 3.0
2016-06-07T12:42:16.543Z
@AndrewMorgan I think, I get it: it is result of Nisan(1994) "$RL \subseteq SC$" (Theorem 1.2)
Alexey Milovanov
<cc.complexity-theory><randomized-algorithms><space-bounded>
Can every distribution producible by a probabilistic PSpace machine be produced by a PSpace machine with only polynomially many random bits?
Alexey Milovanov
# Can every distribution producible by a probabilistic PSpace machine be produced by a PSpace machine with only polynomially many random bits?

(Asked by: username_0 on 2016-06-04)

Let $M$ be a probabilistic Turing machine with a unary input $n$ whose
space is bounded by a polynomial in $n$ and
its output is a distribution $D$ over binary strings.
Note that the number of random bits that $M$ can use can be exponential in $n$.

Can $D$ be "approximated" by
a probabilistic polynomial space-bounded Turing machine
*which uses only a polynomial number of random bits*?

More formally,

> Let $M$ be a TM with space bound $s$.
> Is there a probabilistic Turing machine $N$ using poly(s) space and random bits with the following property:
> $$\forall k ~~2^{-k} \implies
> Pr[N = x] > 2^{-k - O(\log s)} \right)$$~~

**Tags:** cc.complexity-theory, randomized-algorithms, space-bounded

> **Comments:**
> **username_1**: A polynomial-space machine using polynomially many random bits can simulate itself for all possible random choices and take appropriate measures. That is, it can be made deterministic polynomial space.  
> **username_2**: Is $M$ assumed to have bounded error? If so, I believe Nisan's generator can be adapted to do what you want. If $M$'s error is one-sided (and possibly very small), then the desired result follows from Savitch's theorem.  
> **username_0**: @AndrewMorgan Could you explain what is "assumed to have bounded error"?  
> **username_2**: I'm referring to the difference, for instance, between $\mathsf{PP}$ and $\mathsf{BPP}$, where in the first case the Turing machine just has to be right "most" ($\ge 1/2$) of the time, whereas in the latter case the Turing machine has to be right "significantly more than most" ($\ge 2/3$) of the time. What guarantees do you have regarding $M$?  I just noticed the "without enter" in your problem description- do you mean "without error"? In this case, both Nisan's PRG and Savitch's theorem appear to work.  
> **username_0**: @AndrewMorgan I mean that $M$ just set a distribution. There are no "right" or "wrong" outputs. And I want to approximate this distribution by another one, such that a corresponding Turing machine uses smaller number of random bits.  
> **username_2**: @Alexey: Okay, I understand what you're asking for now. Formally I think you want $M$ to still take in a unary input (otherwise asymptotics don't make sense), but that's a minor point.  Also, presumably we are charging the length of the output $x$ to the space complexity of $M$. The answer to your question is "no" if we do not, because $M$ can just pass $2^n$ random bits to its output.  
> **username_0**: @AndrewMorgan In such case $Pr[M = x] = 2^{-2^n}$, isn't it? I allow $poly(n,k)$ space-bounded for $M'$ and so this is not a counter-example.  
> **username_0**: @AndrewMorgan I think you know the answer on the simpler question: Does BPP-PSPACE equal to PSPACE (if we allow exponential number of random bits)? I do not understand how it is directly follows from Savitch's theorem  
> **username_0**: @AndrewMorgan I think, I get it: it is result of Nisan(1994) "$RL \subseteq SC$" (Theorem 1.2)  

---

## 0 answers

