Interpreting probabilistic time turning machines

Question

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.

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.