Approximate independence for fixpoints of random permutations
$begingroup$
Let $F_n$ be the random variable that is the number of fixed points of a random permutation on $n$ elements. As $n to infty$, the distribution of $F_n$ approaches a Poisson distribution with mean 1. This can easily be shown via direct calculation.
I would like a more intutive proof. For large $n$ the events that any particular $k << n$ elements are fixed are approximately independent. If we are assume they are exactly independent, it is immediate that the limit is Poisson with mean 1. Is there a way to make this reasoning precise, ideally with a minimum of calculation?
permutations random-variables poisson-distribution
asked Dec 22 '18 at 6:14
Geoffrey IrvingGeoffrey Irving
469314
$endgroup$
add a comment |
$begingroup$
Let $F_n$ be the random variable that is the number of fixed points of a random permutation on $n$ elements. As $n to infty$, the distribution of $F_n$ approaches a Poisson distribution with mean 1. This can easily be shown via direct calculation.
I would like a more intutive proof. For large $n$ the events that any particular $k << n$ elements are fixed are approximately independent. If we are assume they are exactly independent, it is immediate that the limit is Poisson with mean 1. Is there a way to make this reasoning precise, ideally with a minimum of calculation?
permutations random-variables poisson-distribution
asked Dec 22 '18 at 6:14
Geoffrey IrvingGeoffrey Irving
469314
$endgroup$
1
$begingroup$
There is this method: projecteuclid.org/download/pdf_1/euclid.ss/1177012015
$endgroup$
– kimchi lover
Dec 22 '18 at 13:48
$begingroup$
It is easy to show that the mean is $1$ for any $n$, so the real issue is the Poisson distribution limit. If you know that the number of derangements (no fixed points) of $m$ values is the rounded $lceil m!/e rfloor$, then the probability of having $k$ fixed points out of $n$ is ${n choose k}lceil (n-k)!/e rfloor / n!$ which has a limit of $e^{-1}/k!$ as $n$ increases, implying convergence in distribution to a Poisson distribution with pmf $lambda^k e^{-lambda} / k!$ with $lambda=1$
$endgroup$
– Henry
Dec 24 '18 at 12:52
$begingroup$
@Henry: Yes, that's the calculation. It's an easy calculation, but I'm still interested in trying to do it via approximate independence methods (such as the Chen-Stein method from the first comment).
$endgroup$
– Geoffrey Irving
Dec 24 '18 at 19:20
$begingroup$
@GeoffreyIrving - perhaps so, but the approximate independence amounts to little more than saying $lceil m!/e rfloor approx m!/e$
$endgroup$
– Henry
Dec 25 '18 at 1:02
add a comment |
$begingroup$
Let $F_n$ be the random variable that is the number of fixed points of a random permutation on $n$ elements. As $n to infty$, the distribution of $F_n$ approaches a Poisson distribution with mean 1. This can easily be shown via direct calculation.
I would like a more intutive proof. For large $n$ the events that any particular $k << n$ elements are fixed are approximately independent. If we are assume they are exactly independent, it is immediate that the limit is Poisson with mean 1. Is there a way to make this reasoning precise, ideally with a minimum of calculation?
permutations random-variables poisson-distribution
asked Dec 22 '18 at 6:14
Geoffrey IrvingGeoffrey Irving
469314
$endgroup$
Let $F_n$ be the random variable that is the number of fixed points of a random permutation on $n$ elements. As $n to infty$, the distribution of $F_n$ approaches a Poisson distribution with mean 1. This can easily be shown via direct calculation.
I would like a more intutive proof. For large $n$ the events that any particular $k << n$ elements are fixed are approximately independent. If we are assume they are exactly independent, it is immediate that the limit is Poisson with mean 1. Is there a way to make this reasoning precise, ideally with a minimum of calculation?
permutations random-variables poisson-distribution
permutations random-variables poisson-distribution
asked Dec 22 '18 at 6:14
Geoffrey IrvingGeoffrey Irving
469314
asked Dec 22 '18 at 6:14
Geoffrey IrvingGeoffrey Irving
469314
asked Dec 22 '18 at 6:14
Geoffrey IrvingGeoffrey Irving
469314
asked Dec 22 '18 at 6:14
Geoffrey IrvingGeoffrey Irving
469314
asked Dec 22 '18 at 6:14
Geoffrey IrvingGeoffrey Irving
469314
469314
1
$begingroup$
There is this method: projecteuclid.org/download/pdf_1/euclid.ss/1177012015
$endgroup$
– kimchi lover
Dec 22 '18 at 13:48
$begingroup$
It is easy to show that the mean is $1$ for any $n$, so the real issue is the Poisson distribution limit. If you know that the number of derangements (no fixed points) of $m$ values is the rounded $lceil m!/e rfloor$, then the probability of having $k$ fixed points out of $n$ is ${n choose k}lceil (n-k)!/e rfloor / n!$ which has a limit of $e^{-1}/k!$ as $n$ increases, implying convergence in distribution to a Poisson distribution with pmf $lambda^k e^{-lambda} / k!$ with $lambda=1$
$endgroup$
– Henry
Dec 24 '18 at 12:52
$begingroup$
@Henry: Yes, that's the calculation. It's an easy calculation, but I'm still interested in trying to do it via approximate independence methods (such as the Chen-Stein method from the first comment).
$endgroup$
– Geoffrey Irving
Dec 24 '18 at 19:20
$begingroup$
@GeoffreyIrving - perhaps so, but the approximate independence amounts to little more than saying $lceil m!/e rfloor approx m!/e$
$endgroup$
– Henry
Dec 25 '18 at 1:02
add a comment |
1
$begingroup$
There is this method: projecteuclid.org/download/pdf_1/euclid.ss/1177012015
$endgroup$
– kimchi lover
Dec 22 '18 at 13:48
$begingroup$
It is easy to show that the mean is $1$ for any $n$, so the real issue is the Poisson distribution limit. If you know that the number of derangements (no fixed points) of $m$ values is the rounded $lceil m!/e rfloor$, then the probability of having $k$ fixed points out of $n$ is ${n choose k}lceil (n-k)!/e rfloor / n!$ which has a limit of $e^{-1}/k!$ as $n$ increases, implying convergence in distribution to a Poisson distribution with pmf $lambda^k e^{-lambda} / k!$ with $lambda=1$
$endgroup$
– Henry
Dec 24 '18 at 12:52
$begingroup$
@Henry: Yes, that's the calculation. It's an easy calculation, but I'm still interested in trying to do it via approximate independence methods (such as the Chen-Stein method from the first comment).
$endgroup$
– Geoffrey Irving
Dec 24 '18 at 19:20
$begingroup$
@GeoffreyIrving - perhaps so, but the approximate independence amounts to little more than saying $lceil m!/e rfloor approx m!/e$
$endgroup$
– Henry
Dec 25 '18 at 1:02
1
1
$begingroup$
There is this method: projecteuclid.org/download/pdf_1/euclid.ss/1177012015
$endgroup$
– kimchi lover
Dec 22 '18 at 13:48
$begingroup$
There is this method: projecteuclid.org/download/pdf_1/euclid.ss/1177012015
$endgroup$
– kimchi lover
Dec 22 '18 at 13:48
$begingroup$
It is easy to show that the mean is $1$ for any $n$, so the real issue is the Poisson distribution limit. If you know that the number of derangements (no fixed points) of $m$ values is the rounded $lceil m!/e rfloor$, then the probability of having $k$ fixed points out of $n$ is ${n choose k}lceil (n-k)!/e rfloor / n!$ which has a limit of $e^{-1}/k!$ as $n$ increases, implying convergence in distribution to a Poisson distribution with pmf $lambda^k e^{-lambda} / k!$ with $lambda=1$
$endgroup$
– Henry
Dec 24 '18 at 12:52
$begingroup$
It is easy to show that the mean is $1$ for any $n$, so the real issue is the Poisson distribution limit. If you know that the number of derangements (no fixed points) of $m$ values is the rounded $lceil m!/e rfloor$, then the probability of having $k$ fixed points out of $n$ is ${n choose k}lceil (n-k)!/e rfloor / n!$ which has a limit of $e^{-1}/k!$ as $n$ increases, implying convergence in distribution to a Poisson distribution with pmf $lambda^k e^{-lambda} / k!$ with $lambda=1$
$endgroup$
– Henry
Dec 24 '18 at 12:52
$begingroup$
@Henry: Yes, that's the calculation. It's an easy calculation, but I'm still interested in trying to do it via approximate independence methods (such as the Chen-Stein method from the first comment).
$endgroup$
– Geoffrey Irving
Dec 24 '18 at 19:20
$begingroup$
@Henry: Yes, that's the calculation. It's an easy calculation, but I'm still interested in trying to do it via approximate independence methods (such as the Chen-Stein method from the first comment).
$endgroup$
– Geoffrey Irving
Dec 24 '18 at 19:20
$begingroup$
@GeoffreyIrving - perhaps so, but the approximate independence amounts to little more than saying $lceil m!/e rfloor approx m!/e$
$endgroup$
– Henry
Dec 25 '18 at 1:02
$begingroup$
@GeoffreyIrving - perhaps so, but the approximate independence amounts to little more than saying $lceil m!/e rfloor approx m!/e$
$endgroup$
– Henry
Dec 25 '18 at 1:02
add a comment |
0
active
oldest
votes
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%2f3049160%2fapproximate-independence-for-fixpoints-of-random-permutations%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3049160%2fapproximate-independence-for-fixpoints-of-random-permutations%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
1
$begingroup$
There is this method: projecteuclid.org/download/pdf_1/euclid.ss/1177012015
$endgroup$
– kimchi lover
Dec 22 '18 at 13:48
$begingroup$
It is easy to show that the mean is $1$ for any $n$, so the real issue is the Poisson distribution limit. If you know that the number of derangements (no fixed points) of $m$ values is the rounded $lceil m!/e rfloor$, then the probability of having $k$ fixed points out of $n$ is ${n choose k}lceil (n-k)!/e rfloor / n!$ which has a limit of $e^{-1}/k!$ as $n$ increases, implying convergence in distribution to a Poisson distribution with pmf $lambda^k e^{-lambda} / k!$ with $lambda=1$
$endgroup$
– Henry
Dec 24 '18 at 12:52
$begingroup$
@Henry: Yes, that's the calculation. It's an easy calculation, but I'm still interested in trying to do it via approximate independence methods (such as the Chen-Stein method from the first comment).
$endgroup$
– Geoffrey Irving
Dec 24 '18 at 19:20
$begingroup$
@GeoffreyIrving - perhaps so, but the approximate independence amounts to little more than saying $lceil m!/e rfloor approx m!/e$
$endgroup$
– Henry
Dec 25 '18 at 1:02