Can true randomness (provably) be replaced with Kolmogorov randomness for RP?

Question

Have there been any attempts to show that Kolmogorov randomness would be sufficient for RP? Would the probability used in the statement "If the correct answer is YES, then it (the probabilistic Turing machine) returns YES with probability ..." be always well defined in that case? Or would there only be upper and lower bounds for that probability? Or would there only always be some probabilistic Turing machine, for which the probabilities would be well defined (or at least the lower bound which should be bigger than 1/2)?

The class RP here is relatively arbitrary, and one could also ask this question for weaker notions of (pseudo-)randomness than Kolmogorov randomness. But Kolmogorov randomness seems to be a good starting point.

---

Making sense of the word "probability" would be part of an attempt to show that Kolmogorov randomness works for RP. However, let me try to describe one possible approach, to clarify what it could mean, and why I talked about upper and lower bounds:

Let $s$ be a (Kolmogorov random) string. Let $A$ be a the given probabilistic Turing machine corresponding to a language from RP. Run $A$ with $s$ as source for random bits $n$ times, continuing to consume previously unconsumed bits from $s$ one after the other.

For $p_n^s:=\frac{\text{#YES result in first $n$ runs of $A$ on $s$}}{n}$, let $p_+^s:=\limsup_{n\to\infty}p_n^s$ and $p_-^s:=\liminf_{n\to\infty}p_n^s$. Observe that $p_+^s$ and $p_-^s$ are well defined for a given string $s$, even if it would not be random. But one may wonder whether $p_+^s=p_-^s$ in case $s$ is Kolmogorov random, or whether $p_-^{s_1}=p_-^{s_2}$ for two arbitrary Kolmogorov random strings $s_1$ and $s_2$. Or whether there exists a $p\geq 1/2$ such that $p\leq p_-^s$ for any Kolmogorov random string $s$.

Answer 1

I think the question being asked here is roughly "is there a sense in which we can replace the sequence of random bits in an algorithm with bits drawn deterministically from an appropriately long Kolmogorov random string?" This is at least the question I will attempt to answer! (The short answer is "Yes, but only if you amplify the error probability first")

---

Yes...

We can certainly say something here. Let $L$ be some language and let $A$ be an algorithm which takes as input $x$ and a random string $r\in U_{f(|x|)}$ (the uniform distribution over $\{0,1\}^{f(|x|)}$) s.t. $\Pr[A(x,r)=L(x)]>1-\epsilon(x)$. In other words, $A$ is an algorithm which errs with probability at most $\epsilon(\cdot)$.

Notice now that if $A$ gives the wrong answer on $(x,r)$ ie, $A(x,r)\not=L(x)$, this gives us some means of describing $r$, in particular, we can describe it as the $i$-th string which causes $A$ to err on $x.$ To do this, we simply make the machine which has hard-coded $x$, $A$, $i$, and a bit $b=1\iff x\in L$, and simply enumerates choices of $r'$ from $\{0,1\}^{f(|x|)}$ until it finds the $i$-th choice of $r'$ such that $A(x,r')\not= b$.

So now that we know we can leverage being a bad choice of random string into a description, let's observe some conditions which are sufficient for turning our description of $r$ into a compression. To describe $r$, we require enough bits to describe $x$, $i$, $b$, and then the code for our procedure (the code for $A$ and the routine we described), giving as a description of length $$|x|+|i|+O(1)=|x|+\log_2(2^{f(|x|)}\epsilon(x))+O(1)=|x|+f(|x|)-\log(1/\epsilon(x))+O(1).$$

Recall that $r$ is length $f(|x|)$, so this is a compression of $r$ if $$\log(1/\epsilon(x)) = |x|+\omega(1),$$ for example, when $\epsilon(x)=1/2^{2|x|}$.

Finally, observe that if $r$ were a Kolmogorov random string, then we could have no such compression, so as long as the error probability of $A$ is sufficiently small, a Kolmogorov random string in place of the sequence of random bits will cause $A$ to answer correctly!

Notice that the only thing we leverage about $A$ is that its error probability is small. We don't care if $A$ has an extremely long run time or if $A$ has one or two sided error.

Bringing this back to the question of $RP$ (or $coRP$ or $BPP$), this says that as long as we amplify the error probability of our algorithms, we can use Kolmogorov random strings in place of their random bits.

---

...But only if we amplify first.

A followup question may be "can I do this without amplifying the error probability?" Consider the following algorithm $A$ which decides $\{0,1\}^*$ and has error probability $1/2^n$.

On input $x$:

• Generate a string $r\in\{0,1\}^n$
• If $r=x$, reject.
• Accept.

Notice that for every choice of $r$, there is some choice of $x$ such that $A$ errs on $x$, namely the choice of $r$ that is $x$, so we can not replace the random sequence of bits used by $A$ with a Kolmogorov random string without amplifying it's error probability!

---

A note about the source: I'm not sure if any of this is novel, but I included the first argument in my writeup for my qualifying exam which will eventually be available online after I finish revising it.