I was trying to understand better the definition of a strong PSRG and I came across this expression which I am trying to understand better:

$$ Pr_{r \in \{0,1\}^l}[A(r) = \text{"yes"}]$$

Where r is a truly random bit string and A is a polynomial time deterministic machine. I've been having some problems understanding what this expression means conceptually (or intuitively).

So far these are some of my thoughts and I will try to point out my doubts too.

A is just a standard TM so we can image that on l steps, it will yield $2^l$ branches. Each branch has a chance of occurring depending on which r occurs. Therefore, I was wondering if the above probability expression just mean "the fraction of branches that out yes"? Is that basically the same as the chance that A will output yes on the given random bit string? The thing that was confusing me and I was not sure how to deal with it was that, A(r) always outputs the same thing ("yes" or "no") on a given r (say it always accepts or rejects if r = 1010100 or something), it didn't seem to me that it a probabilistic sense, unless we randomly choose r. So I was wondering how the community interpreted this equation and what it mean.

Also, since this is a probability, it seems to me that A(r) is just r.v. that only takes two values (yes or no), right? So this distribution only has two probability values, the one that A outputs yes or no, right? I was wondering how that related to the string r and I was not sure how to resolve this.


1 Answer 1


As the notation implies, the probability is taken over the choice of $r$. So it's the fraction of $r$s which the machine $A$ "accepts" (answer Yes). You're right that the random variable $A(r)$ has two possible values, Yes and No, and so for example the probability to get Yes and the probability to get No add up to $1$.

We usually think of $A$ as a statistical test. For example, $A$ might test the the number of $1$s in $r$ is roughly $\ell/2$, say between $\ell/2-\sqrt{\ell\log \ell}$ and $\ell/2+\sqrt{\ell\log \ell}$, and then it accepts with probability $1-2/\ell^2$ or higher (using Chernoff's inequality).

Something you are confused about is the branching. The machine $A$ can read its input bits many times. There is always one computation branch. After $\ell$ steps, there is still only one computation branch. On the other hand, at the outset there are $2^\ell$ different computations to consider.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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