2
$\begingroup$

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<s \ \left(Pr[M = x] > 2^{-k} \implies Pr[N = x] > 2^{-k - O(\log s)} \right)$$

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Jun 4 '16 at 11:34
  • 3
    $\begingroup$ 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. $\endgroup$ – Andrew Morgan Jun 4 '16 at 16:36
  • $\begingroup$ @AndrewMorgan Could you explain what is "assumed to have bounded error"? $\endgroup$ – Alexey Milovanov Jun 4 '16 at 19:33
  • 1
    $\begingroup$ @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. $\endgroup$ – Alexey Milovanov Jun 5 '16 at 6:54
  • 1
    $\begingroup$ @AndrewMorgan I think, I get it: it is result of Nisan(1994) "$RL \subseteq SC$" (Theorem 1.2) $\endgroup$ – Alexey Milovanov Jun 7 '16 at 12:42
1
+50
$\begingroup$

Yes.


I took the four screenshots ​ 0,1,2,3 ​ of this answer in case is doesn't render correctly.

Alexey did not specify that the outputs are bounded-length (that was edited in by Kaveh),
so I do not assume that. ​ ​ ​ Note that ​ L $\subseteq$ NL $\subseteq$ NC2 $\subseteq$ DSPACE$\hspace{-0.02 in}\left(\hspace{-0.04 in}O\hspace{-0.05 in}\left(\hspace{-0.04 in}(\hspace{.02 in}\log(n)\hspace{-0.03 in})^2\right)\hspace{-0.03 in}\right)$ .

In this answer, "strings" without further clarification may continue infinitely to the right.

The part of this answer between here and the at-symbol applies
to all probabilistic automata with at most $C$ configurations;

even those with, for example, irrational transition probabilities.


Consider any positive integer $j$. $\;\;\;$ Since probabilities are non-negative and add to one,
there are less than $j$ $x$s such that $\: 1/j < \operatorname{Pr}[\text{Automaton outputs }x] \;$. $\;\;\;$ Consider any such $x$.
For strings $s$, say a configuration is bad for $s$ if the probability of the automaton outputting $s$
from the configuration is at most $1/j$, and good for $s$ otherwise. $\:$ Say a configuration
is good if the configuration is good for at least one suffix of $x$, and bad otherwise.

$\operatorname{Pr}[\text{Automaton outputs }x \;\; | \;\; \text{Automaton reaches a bad configuration}]$
$\leq$
$1/j \: < \: \operatorname{Pr}[\text{Automaton outputs }x] \;\;\;$,

so it's possible for the automaton to output $x$ without reaching any bad configuration.
Probabilities are non-negative and add to one, so any given configuration is good
for less than $j$ strings. $\;\;\;$ The automaton has at most $C$ configurations, so there are
less than $\: C\hspace{-0.04 in}\cdot \hspace{-0.03 in}j \:$ strings for which there exists a configuration which is good for the string.
Since it's possible for the automaton to output $x$ while remaining in
good configurations, $x$ has less than $\: C\hspace{-0.04 in}\cdot \hspace{-0.03 in}j \:$ distinct non-empty suffixes.
Thus, either $x$'s length is less than $\: C\hspace{-0.04 in}\cdot \hspace{-0.03 in}j \:$ or $\big[x$ is eventually-periodic and the length
of [the pre-periodic part concatenated with the initial period] is less than $\: C\hspace{-0.04 in}\cdot \hspace{-0.03 in}j \hspace{.02 in}\big]$.
Regard the former case as having period zero, so both of those cases are
covered by "pre-periodic part and initial period, each with length less than $\: C\hspace{-0.04 in}\cdot \hspace{-0.03 in}j \:$".

Now, choose a family $H$ of hash functions with short output and domain equal to
$\big[$the set of strings with length less than $\: C\hspace{-0.04 in}\cdot \hspace{-0.03 in}j \hspace{.02 in}\big]$, $\:$ such that for all distinct equal-length
elements $x_0$ and $y$ of their domain, if ​ $y\neq x$ ​ then $\;\;\; \operatorname{Pr}_{h\leftarrow H'}[h(\hspace{.03 in}y) = h(x_0)] \: \leq \: 1/(2\hspace{-0.05 in}\cdot \hspace{-0.04 in}j\hspace{.02 in}) \:\:\:\:$.
Let $x_0$ and $x_1$ be the pre-periodic part and initial period respectively of $x$.
For all strings $y_0$ and $y_1$ whose lengths are at most the lengths of $x_0$ and $x_1$ respectively,

$\operatorname{Pr}_{h\leftarrow H}\hspace{-0.06 in}\big[\langle \operatorname{length}(\hspace{.03 in}y_0),\operatorname{length}(\hspace{.03 in}y_1)\rangle = \langle \operatorname{length}(x_0),\operatorname{length}(x_1)\rangle$
$\text{and } \: \langle \hspace{.02 in}y_0,\hspace{-0.03 in}y_1\rangle \neq \langle x_0,\hspace{-0.03 in}x_1\rangle \: \text{ and } \: \langle h(\hspace{.03 in}y_0),h(\hspace{.03 in}y_1)\rangle = \langle h(x_0),h(x_1)\rangle\big]$
$\leq$
$\operatorname{Pr}_{h\leftarrow H}[\langle \hspace{.02 in}y_0,\hspace{-0.03 in}y_1\rangle \neq \langle x_0,\hspace{-0.03 in}x_1\rangle \: \text{ and } \: \langle h(\hspace{.03 in}y_0),h(\hspace{.03 in}y_1)\rangle = \langle h(x_0),h(x_1)\rangle]$
$\leq$
$1/(2\hspace{-0.05 in}\cdot \hspace{-0.04 in}j\hspace{.02 in})$

. ​ ​ Since doing so will correspond to taking a weighted average, that will still apply when
$y_0$ and $y_1$ are chosen from a distribution independently of $h$. ​ In particular, it will still apply when
$\langle \hspace{.03 in}y_0,\hspace{-0.03 in}y_1\rangle \:$ is chosen according to the automaton's outputs so that $y_0$ is the first up-to-length($x_0$)
bits of the output and $y_1$ is the next up-to-length($x_1$) bits of the output. ​ Since the random
choice of $h$ from $H$ also corresponds to a weighted average, there is an $h$ from $H$ such that

$\operatorname{Pr}_{\langle \hspace{.02 in}y_0,\hspace{.02 in}y_1\hspace{-0.02 in}\rangle \leftarrow \text{Automaton}}\hspace{-0.05 in}\big[\langle \operatorname{length}(\hspace{.03 in}y_0),\operatorname{length}(\hspace{.03 in}y_1)\rangle = \langle \operatorname{length}(x_0),\operatorname{length}(x_1)\rangle$
$\text{and } \: \langle \hspace{.02 in}y_0,\hspace{-0.03 in}y_1\rangle \neq \langle x_0,\hspace{-0.03 in}x_1\rangle \: \text{ and } \: \langle h(\hspace{.03 in}y_0),h(\hspace{.03 in}y_1)\rangle = \langle h(x_0),h(x_1)\rangle\big]$
$\leq$
$1/(2\hspace{-0.05 in}\cdot \hspace{-0.04 in}j\hspace{.02 in})$

. ​ ​ Let $h_0$ be such an $h$.

$1/j \: < \: \operatorname{Pr}[\text{Automaton outputs } x] \;\; \leq \;\; \operatorname{Pr}_{\langle \hspace{.02 in}y_0,\hspace{.02 in}y_1\hspace{-0.02 in}\rangle \leftarrow \text{Automaton}}[\langle \hspace{.02 in}y_0,\hspace{-0.03 in}y_1\rangle = \langle x_0,\hspace{-0.02 in}x_1\rangle]$
$=$
$\operatorname{Pr}_{\langle \hspace{.02 in}y_0,\hspace{.02 in}y_1\hspace{-0.02 in}\rangle \leftarrow \text{Automaton}}\hspace{-0.05 in}\big[\langle \operatorname{length}(\hspace{.03 in}y_0),\operatorname{length}(\hspace{.03 in}y_1)\rangle = \langle \operatorname{length}(x_0),\operatorname{length}(x_1)\rangle$
$\text{and } \: \langle \hspace{.02 in}y_0,\hspace{-0.03 in}y_1\rangle = \langle x_0,\hspace{-0.03 in}x_1\rangle \: \text{ and } \: \langle h_0(\hspace{.03 in}y_0),h_0(\hspace{.03 in}y_1)\rangle = \langle h_0(x_0),h_0(x_1)\rangle\big]$

, ​ ​ so the probability of $\: \langle \hspace{.02 in}y_0,\hspace{-0.03 in}y_1\rangle = \langle x_0,\hspace{-0.03 in}x_1\rangle \:$ conditioned on

$\langle \operatorname{length}(\hspace{.03 in}y_0),\operatorname{length}(\hspace{.03 in}y_1)\rangle = \langle \operatorname{length}(x_0),\operatorname{length}(x_1)\rangle$
$\text{and } \; \langle h_0(\hspace{.03 in}y_0),h_0(\hspace{.03 in}y_1)\rangle = \langle h_0(x_0),h_0(x_1)\rangle$

is greater than $2/3$. ​ In particular, for each element $i$ of
$\{\hspace{-0.02 in}0,\hspace{-0.05 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...\operatorname{length}(x_0)\hspace{-0.03 in}+\hspace{-0.03 in}\operatorname{length}(x_1)\hspace{-0.03 in}-\hspace{-0.04 in}1\hspace{-0.02 in}\}$, conditioned on the same event,

$2/3$
$<$
$\operatorname{Prob}[\text{Automaton gives more than } i \text{ bits of output and}$
$\text{the }i\text{-th bit of the output equals the }i\text{-th bit of } x_0$||$x_1]$

. ​ ​ ​ ​ Multiplying the number of states by ​ $4\hspace{-0.04 in}\cdot \hspace{-0.04 in}C\hspace{-0.04 in}\cdot \hspace{-0.04 in}j$ ​ lets the automata track $i$ and
for hard-coded $i_0$ from $\{0,\hspace{-0.05 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...\operatorname{length}(x_0)\hspace{-0.03 in}+\hspace{-0.03 in}\operatorname{length}(x_1)\hspace{-0.03 in}-\hspace{-0.04 in}1\hspace{-0.02 in}\}$, record the $i_0$-th output.

Now, for efficiency's sake, we must turn back to the hash family $H$. ​ Let $p$ be the
smallest prime that is not less than ​ $2\hspace{-0.04 in}\cdot \hspace{-0.04 in}C\hspace{-0.04 in}\cdot \hspace{-0.04 in}j^{\hspace{.02 in}2}$ , ​ and then use wikipedia's string hashing method.
For input length of at most one block, collisions are simply impossible. ​ ​ ​ Otherwise,

$\text{maximum_collision_probability} \leq \text{degree}\hspace{.02 in}/p \; = \; ((\text{number_of_blocks})\hspace{-0.04 in}-\hspace{-0.05 in}1)/p \; \leq \; (\lceil (\text{input_length})/(\text{block_size})\rceil\hspace{-0.04 in}-\hspace{-0.05 in}1)/p \; \leq \; (\lceil (\text{input_length})/1\rceil \hspace{-0.04 in}-\hspace{-0.04 in}1)/p \; = \;$
$(\lceil \text{input_length}\rceil \hspace{-0.04 in}-\hspace{-0.05 in}1)/p \; < \; (\text{input_length})/p < (C\hspace{-0.04 in}\cdot \hspace{-0.04 in}j)/p \leq (C\hspace{-0.04 in}\cdot \hspace{-0.04 in}j)/(2\hspace{-0.04 in}\cdot \hspace{-0.04 in}C\hspace{-0.04 in}\cdot \hspace{-0.04 in}j^{\hspace{.02 in}2}) \; = \; 1/(2\hspace{-0.04 in}\cdot \hspace{-0.04 in}j)$

. ​ ​ ​ ​ Thus wikipedia' string hashing method has small enough collision probability for this answer.
By Bertrand's postulate, $p$ will be less than ​ $4\hspace{-0.04 in}\cdot \hspace{-0.04 in}C\hspace{-0.04 in}\cdot \hspace{-0.04 in}j^{\hspace{.02 in}2}$ , ​ so for $j$ given in unary, logspace can find $p$
by trial division and do the arithmetic operations mod $p$. ​ ​ ​ In particular, NC2 can do the same. ​ Observe that wikipedia's string hashing method takes the input as a stream, so
(for $j$ given in unary) NC2 can find a deterministic finite automata for each hash in the $p$ family.
Thus, by a product construction, NC2 can get automata which will use any given
hash in the $p$ family to test both parts of the underlying automata's output -
If the underlying automaton would halt without having produced output or finish a part
not matching the target hash values, then the resulting automaton will enter a reject state;
if the underlying automaton gives enough output without either of those happening,
then the resulting automaton goes to Finalize0 or Finalize1,
determined by the value of the bit the underlying automaton was recording.

By the conditional probability I went over earlier, there is an $h_0$ is the $p$ family such that,
when that's done with $\operatorname{length}(x_0)$ and $\operatorname{length}(x_1)$ and $h_0(x_0)$ and $h_0(x_1)$, for each element $i_0$$\{0,\hspace{-0.05 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...\operatorname{length}(x_0)\hspace{-0.03 in}+\hspace{-0.03 in}\operatorname{length}(x_1)\hspace{-0.03 in}-\hspace{-0.04 in}1\hspace{-0.02 in}\}$, the probability of the resulting automaton finalizing the $i_0$-th bit of ​ $x_0$||$x_1$ ​ is more than twice its probability of finalizing the other bit. ​ ​ ​ Clearly, for each such automaton, there is at most one pair ​ $\langle \hspace{.02 in}y_0,\hspace{-0.03 in}y_1\rangle$ ​ of $\big[$strings with length less than $\: C\hspace{-0.04 in}\cdot \hspace{-0.03 in}j\big]$ satisfying the previous sentence's condition. ​ ​ ​ Furthermore, the $p$ family and its outputs
are given by integers mod $p$ and the lengths are restricted to being less than ​ $C\hspace{-0.04 in}\cdot \hspace{-0.03 in}j$ ,
so for $j$ in unary, NC2 can output a list of all such automata.


@


Now, assume that all probabilistic transitions are coin-flips, i.e.,
equal probability of going to each of 2 possible next-states:

There are only polynomially many possibilities for the workspace's contents, so the automata's sizes are polynomial. ​ ​ ​ Each transition probability is in {0,1/2,1}, so by Lemma 6.1, (for $j$ given
in unary) NC2 can determine whether there is a pair of $\big[$strings with length less than $\: C\hspace{-0.04 in}\cdot \hspace{-0.03 in}j\big]$ satisfying the condition in the paragraph just-before the at-symbol, and if so, find that pair.
There's almost certainly a simpler method, but as a brute-force for determining whether-or-not
the strings represented by such pairs are equal, NC2 can build the deterministic finite automata from those representations which give one output per step, construct their product, and check
whether-or-not that product automata reaches a state from which [exactly one halts or they
give different outputs]. ​ Thus NC2 can (for $j$ given in unary) output a list of pairs such that
[each string which the Turing machine has probability greater than $1/j$ of outputting]
is the eventually-periodic string encoded in the obvious way by exactly one of the pairs in the list.
Now it's time to show that NC2 can find the probabilities of those strings being outputted.

We start by dealing with no-further-output scenarios. ​ Non-deterministic logspace can check whether-or-not there is a sequence of random bits which will cause further output from a given configuration, so NC2 can replace entering those configurations with entering the halt state.
The remaining configurations all have some way of giving output. ​ Since loops can be removed from any such way, it must be that for each non-halt configuration, there's a way to give output with at most number_of_configurations transitions. ​ Since non-zero transition probabilities are at least 1/2, one will have that for each non-halt configuration, the probability of giving output from there in
at most most number_of_configurations transitions is at least 1/(2^(number_of_configurations)).
That remains the case as long as it stays in configurations which weren't replaced with halt,
so for all positive integers t, the probability of it doing so for t steps without giving output
is at most (1-(1/(2^(number_of_configurations))))^(floor(t/(number_of_configurations)))
That goes to zero as t goes to infinity, so for each time and configuration-at-that-time, the probability of [giving no further output but not halting] is zero. ​ By countable additivity, the previous sentence remains true when "for each time and configuration-at-that-time," is removed, so the probability of [the total output being finite without the automata ever entering its halt state] is 0.

For infinite eventually-periodic strings, apply the previous paragraph, then further modify
the automaton to have it track its output's location in ​ ​ ​ the pre-periodic part ​ / ​ the period ​ ,
as applicable, and halt if it would output something other than the eventually-periodic
string's next bit. ​ ​ ​ ​ ​ ​ ​ The only other way for it to not output the whole eventually-periodic string
is its output being finite, so by the previous paragraph, the probability of it outputting the
eventually-periodic string is one minus the probability of it reaching the halt configuration.

For finite strings, apply 2 paragraphs ago then further modify the automaton
to track [the amount of output it has given, up to the string's length, inclusive],
enter an accept state if has outputted the whole string and would halt (for a reason other than
the following part of this sentence), and halt if it [hasn't finished outputting the string and
would output something other than the next bit] or would output more than the string.
By two paragraphs ago, its probability of outputting the string without entering the accept state is zero, so its probability of outputting the string equals its probability of entering the accept state.

By Lemma 6.1, given $j$ in unary, NC2 can compute those probabilities. ​ NC2 can also
compare those probabilities to $1/j$, so can strip out the pairs with probability at most $1/j$.
In summary, given $j$ in unary and an automaton whose probabilistic transitions
are coin-flips, NC2 can output a list of triples ​ $\langle \text{prob},\hspace{-0.02 in}x_0,\hspace{-0.02 in}x_1\rangle$ ​ such that

the pairs formed by taking the right two entries from distinct triples
represent distinct eventually-periodic strings
and
for each such eventually-periodic string, the left entry of its triple
is the probability of the automaton outputting that string
and
each of those probabilities is greater than $1/j$
and
for each string x, if the probability of the automaton outputting $x$ is greater than $1/j$ then
$x$ is eventually-periodic and represented by the right two entries of one of the triples

. ​ (In light of this paper, I suspect Lemma 6.1 can be improved to put its problem in TC1.
If so, then TC1 can also do everything relevant to this answer that NC2 can do.)



Applying that to the OP's problem:


NC2 can round the probabilities down to fractions with denominator $j$ and remove the denominators. ​ Since $j$ is in unary, logspace can reduce mod $j$, and thus sample "as close to uniformly as possible" from $\{\hspace{-0.02 in}0,\hspace{-0.05 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...,j\hspace{-0.04 in}-\hspace{-0.04 in}2,j\hspace{-0.04 in}-\hspace{-0.05 in}1\}$. ​ ​ ​ ​ Note that ​ $2\hspace{-0.05 in}\cdot \hspace{-0.05 in}\lceil \log_2(\hspace{.05 in}j)\rceil$ ​ random bits are enough to make the error less than $1/(2\hspace{-0.05 in}\cdot \hspace{-0.04 in}j\hspace{.02 in})$. ​ ​ ​ For the same reason, logspace can use the list of [triples with integer left entries] and the element from $\{\hspace{-0.02 in}0,\hspace{-0.05 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...,j\hspace{-0.04 in}-\hspace{-0.04 in}2,j\hspace{-0.04 in}-\hspace{-0.05 in}1\}$ to add the integers, stopping if/when the sum exceeds the element, and then [if that happened then output the eventually-periodic string indicated by the most recent triple's other two elements, else output $\bot$].
Thus NC2 can do those things after it computes the list, so DSPACE$\hspace{-0.02 in}\left(\hspace{-0.04 in}O\hspace{-0.05 in}\left(\hspace{-0.04 in}(\hspace{.02 in}\log(n)\hspace{-0.03 in})^2\right)\hspace{-0.03 in}\right)$
can also do the same things. ​ ​ ​ That means DSPACE$\hspace{-0.02 in}\left(\hspace{-0.04 in}O\hspace{-0.05 in}\left(\hspace{-0.04 in}(\hspace{.02 in}\log(n)\hspace{-0.03 in})^2\right)\hspace{-0.03 in}\right)$ can use
at most ​ $2\hspace{-0.05 in}\cdot \hspace{-0.05 in}\lceil \log_2(\hspace{.05 in}j)\rceil$ ​ random bits to sample from a distribution such that, other than $\bot$,
the probabilities for each output are less than $3/(2\hspace{-0.05 in}\cdot \hspace{-0.04 in}j\hspace{.02 in})$ away from the original probabilities, and whenever the latter is greater than $1/j$, the resulting probability will be greater than $1/(2\hspace{-0.05 in}\cdot \hspace{-0.04 in}j\hspace{.02 in})$.

Now, plugging in ​ $j = 2^k$ ​ and [using just $k$ random bits] and $\big[$using the actual input machine's structure as a Turing machine to simulate reading from a $\left(\hspace{-0.04 in}O(S)\hspace{-0.04 in}\cdot \hspace{-0.04 in}2^S\right)$-state automata whose probabilistic transitions are all coin-flips$\big]$ gives a ​ $O\hspace{-0.04 in}\left(\hspace{-0.03 in}(S\hspace{-0.04 in}+\hspace{-0.04 in}k)^{\hspace{.02 in}2}\hspace{-0.03 in}\right)\hspace{-0.02 in}$-space algorithm that uses $2\hspace{-0.05 in}\cdot \hspace{-0.04 in}k$ random bits to sample from a distribution such that, other than $\bot$, the probabilities for each output are less than $1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.04 in}2^k\hspace{-0.04 in}\right)$ away from the original probabilities, and whenever the latter is greater than $1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.04 in}2^k\hspace{-0.04 in}\right)$, the resulting probability will be at least $1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.04 in}2^k\hspace{-0.04 in}\right)$. ​ ​ ​ (Since $2^k$ is a power of two,
$k$ random bits is enough to choose the element from $\{\hspace{-0.02 in}0,\hspace{-0.05 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...,j\hspace{-0.04 in}-\hspace{-0.04 in}2,j\hspace{-0.04 in}-\hspace{-0.05 in}1\}$ perfectly uniformly.)

That achieves what you're after.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.