2
$\begingroup$

Here $[n]$ denotes the first $n$ positive integers $\{1,2,...,n\}$ and $\mathbb{N}$ is the set of natural numbers.

Let $f:[n] \to [n]$ be a random function chosen uniformly from all possible functions from $[n] \to [n]$. The probability that $f$ is surjective is $\frac{n!}{n^n}$ which tends to zero as $n \to \infty$. This makes me want to believe that a function from $\mathbb{N} \to \mathbb{N}$ has probability zero of being surjective.

On the other hand, let $g:\mathbb{N} \to [n]$ be a random function chosen uniformly from all possible functions from $\mathbb{N} \to [n]$ . For each $m \in [n]$, the probability that $g^{-1}(m) = \emptyset$ is equal to the limit as $k \to \infty$ of $(\frac{n-1}{n})^k$ which equals zero. This makes me think that the desired probability is 1.

$\endgroup$
  • 2
    $\begingroup$ What is the probability space under discussion here? What measure are you defining on this [rather large] space? $\endgroup$ – ncmathsadist Jan 13 at 18:21
  • 3
    $\begingroup$ What kind of probability measure do you want to put on the uncountable set of functions from $\mathbb{N}$ to itself? $\endgroup$ – Hans Engler Jan 13 at 18:22
  • $\begingroup$ I'm pretty sure that it is not possible to choose a function uniformly at random from all possible functions from $\mathbb{N}$ to $[n]$. Your first approach seems like a reasonable way to define this kind of thing: it's essentially analogous to natural density. $\endgroup$ – user3482749 Jan 13 at 18:23
  • $\begingroup$ @user3482749: The natural "uniform" measure seems to be the one where the values of $f(k)$ are iid uniform on $[n]$. $\endgroup$ – Nate Eldredge Jan 13 at 18:55
  • $\begingroup$ @NateEldredge Sure, but there doesn't seem to be a nice way to pass that to a distribution on the functions $\mathbb{N}\to\mathbb{N}$. Sure, you could instead take the same approach as for natural density, but it seems a bit odd to do that in one argument, and do something entirely different in the other. $\endgroup$ – user3482749 Jan 13 at 19:02
3
$\begingroup$

It is possible to define a uniform distribution on the functions from $\mathbb{N}$ to $[n]$ - we just choose each value $f(k)$ independently from the discrete uniform distribution.

Now, the probability we're looking for, of the function being surjective? That's $1$. Why the difference from the $[n]\to[n]$ case? Because it's really a limit of functions from $[m]$ to $[n]$ as $m\to\infty$. The likelihood of those being surjective? See the coupon collector problem. While the specific probability at any $m$ is very complicated, the time needed to get all of them has expected value $n(1+\frac12+\frac13+\cdots+\frac1n)$. The very fact that there's an expected value for the time tells us that the probability of infinite time is zero, and the probability our random function includes all values is $1$.

The title question, about functions from $\mathbb{N}$ to $\mathbb{N}$? That's something there's no canonical probability distribution for. Still, we can do something. Choose some distribution $u$ such that every natural number has positive probability under $u$, and choose each value of the function $f$ independently from $u$. The probability that a given value $k$ is absent from the image of $f$ is zero for each $k$. By countable additivity of measure, the probability that at least one $k$ is absent from the image is thus $\le \sum_{k=1}^{\infty} 0 = 0$, and $f$ is surjective with probability $1$.

$\endgroup$
  • $\begingroup$ If I choose $u$ to be a Poisson distribution (perhaps with a very small value of the parameter $\lambda$) then are you saying that a random function created as you describe above is surjective with probability 1. Moreover, the preimage of any element in the codomain is infinite? $\endgroup$ – Geoffrey Critzer Jan 13 at 19:17
  • 1
    $\begingroup$ With probability 1, yes. Countable additivity can be nonintuitive sometimes. $\endgroup$ – jmerry Jan 13 at 19:19
1
$\begingroup$

Consider the problem of looking for the value of $0^0$. If you were to argue that $0^0$ should be $\lim\limits_{y\to 0} 0^y$ then you might think that $0^0$ should be zero since $0$ to any other power is again $0$. On the other hand if you were to argue that $0^0$ should be $\lim\limits_{x\to 0} x^0$ you might say that $0^0$ should be $1$ since any other number raised to the zeroth power is $1$. In the end, we say that $\lim\limits_{(x,y)\to (0,0)} x^y$ does not exist since we arrive at different answers depending on choices made. (In the context of combinatorics and set theory we do commonly make the arbitrary decision to define $0^0$ to be equal to $1$ for a number of reasons. See elsewhere on this site for a discussion of that topic in greater detail)

In effect, it matters "how quickly" the base and the exponent each travel to zero in relation to one another. In related problems with limits you might want to talk about a limit which appears to be in the form of $\frac{\infty}{\infty}$ such as $\lim\limits_{n\to\infty}\frac{n!}{n^2}$ or $\lim\limits_{n\to\infty}\frac{\sqrt{n}}{\log(n)}$. In this problem too, the relative speed at which each of the top or bottom approaches infinity will influence the final result.

In your specific problem, since you have not adequately specified a probability distribution (uniform distributions are tricky and do not make sense in a number of exotic scenarios and cannot work in countably infinite scenarios), we are forced to try to make sense of it using limits as the probability of a function being a surjection when taken from a function from $[m]\to[n]$ and letting both $m$ and $n$ approach infinity. As in the earlier mentioned problems with limits however, it depends on the speed at which each of the terms moving toward infinity travel. Indeed, as you showed, under one choice of relative speeds you would have expected a probability of $1$. Under a difference choice of relative speeds you would have expected a probability of $0$.

That is not to say that the final answer is necessarily that there is no answer, just that given the way you have so far presented the problem it is impossible to answer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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