How to guarantee a random function hits all elements of image?

Question

Let's say you have a random / non-deterministic function between two countably infinite sets. How do you make sure that the random function f:x-->y 'hits' every element of y? Or make sure the probability of f hitting all of y is 1? What kind of random functions are guaranteed to do this?

Answer 1

If I understand your question correctly (and this is not guaranteed):

Let $\pi$ be any probability measure on the countable set $Y$ such that $\pi(y)>0$ for all $y\in Y$. Pick $f:X\to Y$ by picking each $f(x)$ independently from $Y$ according to $\pi$. The probability that any particular $y$ value is not hit by any $x$ is clearly $0$ (think, it is $(1-\pi(y))^\infty$), and the intersection of the events that $y$ is hit is the countable intersection of probability $1$ events.