Skip to main content
3 of 3
Attempted to clarify

Conditional prob of value given input is drawn from subset = conditioning over subset?

Hey guys, I have a pretty basic question that I want to be sure of. I'm taking a probability over an input selected uniformly at random from binary strings of length $l(n)$. I would like to compare the conditional probability of a function taking a value given that its input is in a subset of this set to the probability of the function taking this value over input selected uniformly at random from the subset.

That is, I want to see if the given equality is valid: $\Pr_{w \leftarrow U_{l(n)}} \left[g\left(A(w)\right) = w \mid w \in g(U_n)\right] = Pr_{w \leftarrow_R \;g(U_n)} \left[g\left(A(w)\right) = w\right]$

Is this true?

EDIT: Above, the g is a pseudorandom generator, essentially it's just a function. The subscripts on the probabilities indicate that the probabilities are taken over a $w$ chosen uniformly at random from the distribution of binary strings of length $n$ (represented by choosing from the distribution $U_n$). A is a function that is supposed to invert the output of $g$. $l(n)$ is a function that is always greater than $n$, which represents the length of the output of $g$.

I believe I have resolved my conflict, and that the two are indeed the same. For those who commented, sorry for the lack of clarity, and thanks for the help!