I've been looking over this proposition and proof in the book "Introduction to modern cryptography" and am a little confused. Picture is attached at the bottom).
Why is it that we do not multiply the $2^{-n}$ by $\varepsilon$.
It is true that the probability of being in the generator range is $2^{-n}$ but even once we're there the chances of A giving the correct inverse are not $1$.
Should the equation not be $\leq \varepsilon ~ 2^{-n}$ instead?
It's analyzed in this way because it is tricky to correctly conclude much more than what's written here. The issue is that a uniformly random string $w$ in the image of $G$ is not necessarily distributed like $G(x)$ for a uniformly random $x$. We know that $\mathcal{A}(y)$ succeeds with $\varepsilon$ probability for a random input $y=G(x)$ of the latter form, but that doesn't tell us much about how it behaves in the former case.
More precisely, conditioned on $w$ being in the image of $G$, it is uniformly random in that image. This does not necessarily imply that $\mathcal{A}(w)$ ouputs an element of the preimage set $G^{-1}(w) = \{x : G(x)=w\}$ with probability $\varepsilon$. For example, $G$ could be highly "irregular," meaning that some preimage sets are much larger than others. But $\mathcal{A}$ might only successfully invert on, say, those $y$ that have very large preimage sets. This would give it good inverting probability on $y=G(x)$ for uniformly random $x$, but its probability of inverting on a uniform $w$ in the image of $G$ would be much less than $\varepsilon$.
It seems to me that the case here is simply that they chose to not give a very tight bound. What they say is that at most the probability is ${2^{-n}}$. That is that even for a perfect A, one that is right all the time, the probability cannot go above that value. that's why the do not multiply by ${\epsilon}$.
I assume this choice is made for the sake of some other proof further down the line, or maybe just some convention.
