Mixing
What is the probability that a random function from $mathbb{N} to mathbb{N}$ is surjective?
$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.
probability combinatorics elementary-set-theory
asked Jan 13 at 18:19
Geoffrey CritzerGeoffrey Critzer
1,5391328
$endgroup$
|
show 1 more comment
$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.
probability combinatorics elementary-set-theory
asked Jan 13 at 18:19
Geoffrey CritzerGeoffrey Critzer
1,5391328
$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}tomathbb{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
|
show 1 more comment
$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.
probability combinatorics elementary-set-theory
asked Jan 13 at 18:19
Geoffrey CritzerGeoffrey Critzer
1,5391328
$endgroup$
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.
probability combinatorics elementary-set-theory
probability combinatorics elementary-set-theory
asked Jan 13 at 18:19
Geoffrey CritzerGeoffrey Critzer
1,5391328
asked Jan 13 at 18:19
Geoffrey CritzerGeoffrey Critzer
1,5391328
edited Jan 13 at 18:46
Geoffrey Critzer
asked Jan 13 at 18:19
Geoffrey CritzerGeoffrey Critzer
1,5391328
asked Jan 13 at 18:19
Geoffrey CritzerGeoffrey Critzer
1,5391328
asked Jan 13 at 18:19
Geoffrey CritzerGeoffrey Critzer
1,5391328
1,5391328
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}tomathbb{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
|
show 1 more comment
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}tomathbb{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
2
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
$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
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$
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$
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$
@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}tomathbb{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
$begingroup$
@NateEldredge Sure, but there doesn't seem to be a nice way to pass that to a distribution on the functions $mathbb{N}tomathbb{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
|
show 1 more comment
2 Answers
2
active
oldest
votes
$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 $mtoinfty$. 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$.
answered Jan 13 at 18:32
jmerryjmerry
8,6931123
$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
add a comment |
$begingroup$
Consider the problem of looking for the value of $0^0$. If you were to argue that $0^0$ should be $limlimits_{yto 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 $limlimits_{xto 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 $limlimits_{(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 $limlimits_{ntoinfty}frac{n!}{n^2}$ or $limlimits_{ntoinfty}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.
answered Jan 13 at 18:39
JMoravitzJMoravitz
47.6k33886
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3072350%2fwhat-is-the-probability-that-a-random-function-from-mathbbn-to-mathbbn%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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 $mtoinfty$. 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$.
answered Jan 13 at 18:32
jmerryjmerry
8,6931123
$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
add a comment |
$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 $mtoinfty$. 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$.
answered Jan 13 at 18:32
jmerryjmerry
8,6931123
$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
add a comment |
$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 $mtoinfty$. 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$.
answered Jan 13 at 18:32
jmerryjmerry
8,6931123
$endgroup$
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 $mtoinfty$. 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$.
answered Jan 13 at 18:32
jmerryjmerry
8,6931123
edited Jan 13 at 18:42
answered Jan 13 at 18:32
jmerryjmerry
8,6931123
answered Jan 13 at 18:32
jmerryjmerry
8,6931123
answered Jan 13 at 18:32
jmerryjmerry
8,6931123
8,6931123
$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
add a comment |
$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
$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
$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
1
$begingroup$
With probability 1, yes. Countable additivity can be nonintuitive sometimes.
$endgroup$
– jmerry
Jan 13 at 19:19
$begingroup$
With probability 1, yes. Countable additivity can be nonintuitive sometimes.
$endgroup$
– jmerry
Jan 13 at 19:19
add a comment |
$begingroup$
Consider the problem of looking for the value of $0^0$. If you were to argue that $0^0$ should be $limlimits_{yto 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 $limlimits_{xto 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 $limlimits_{(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 $limlimits_{ntoinfty}frac{n!}{n^2}$ or $limlimits_{ntoinfty}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.
answered Jan 13 at 18:39
JMoravitzJMoravitz
47.6k33886
$endgroup$
add a comment |
$begingroup$
Consider the problem of looking for the value of $0^0$. If you were to argue that $0^0$ should be $limlimits_{yto 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 $limlimits_{xto 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 $limlimits_{(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 $limlimits_{ntoinfty}frac{n!}{n^2}$ or $limlimits_{ntoinfty}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.
answered Jan 13 at 18:39
JMoravitzJMoravitz
47.6k33886
$endgroup$
add a comment |
$begingroup$
Consider the problem of looking for the value of $0^0$. If you were to argue that $0^0$ should be $limlimits_{yto 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 $limlimits_{xto 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 $limlimits_{(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 $limlimits_{ntoinfty}frac{n!}{n^2}$ or $limlimits_{ntoinfty}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.
answered Jan 13 at 18:39
JMoravitzJMoravitz
47.6k33886
$endgroup$
Consider the problem of looking for the value of $0^0$. If you were to argue that $0^0$ should be $limlimits_{yto 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 $limlimits_{xto 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 $limlimits_{(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 $limlimits_{ntoinfty}frac{n!}{n^2}$ or $limlimits_{ntoinfty}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.
answered Jan 13 at 18:39
JMoravitzJMoravitz
47.6k33886
answered Jan 13 at 18:39
JMoravitzJMoravitz
47.6k33886
answered Jan 13 at 18:39
JMoravitzJMoravitz
47.6k33886
answered Jan 13 at 18:39
JMoravitzJMoravitz
47.6k33886
47.6k33886
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3072350%2fwhat-is-the-probability-that-a-random-function-from-mathbbn-to-mathbbn%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
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}tomathbb{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