Sample from Poisson process with no collisions.
On a 2D square $[0, 1]^2$, I can draw a random configuration of points $c = (n, (x_i)_{1..n})$ with interesting independence properties using a Poisson point process: draw the number of points $n hookrightarrow mathcal{P}(lambda)$, and then $n$ coordinates $x_i hookrightarrow mathcal{U}([0, 1]^2)$. Let us call $mathcal{F}$ the support of this process (all possible configurations) and $mathcal{D}(mathcal{F})$ the corresponding distribution over this support.
I wish now that each point is the center of a disk of radius $r$, and that no two disks collide. $mathcal{F}$ is thus reduced into $mathcal{F}^-$ because we have to remove all configurations with collisions. But it is not empty. The new process is: draw a configuration $c hookrightarrow mathcal{D}(mathcal{F})$, reject it until there is no collision in $c$. This yields a new distribution $c hookrightarrow mathcal{D}'(mathcal{F}^-)$.
A naive way to sample from $mathcal{D}'(mathcal{F}^-)$ is to simulate the process. But the rejection rate gets really high when $lambda$ and $r$ get big.
Is there a clever way to sample from $mathcal{D}'(mathcal{F}^-)$ with lower rejection rate?
Can approaches like random tiling with Markov chains be adapted to such a continous case?
sampling poisson-process collision-detection
asked Dec 4 '18 at 11:21
iago-litoiago-lito
295312
add a comment |
On a 2D square $[0, 1]^2$, I can draw a random configuration of points $c = (n, (x_i)_{1..n})$ with interesting independence properties using a Poisson point process: draw the number of points $n hookrightarrow mathcal{P}(lambda)$, and then $n$ coordinates $x_i hookrightarrow mathcal{U}([0, 1]^2)$. Let us call $mathcal{F}$ the support of this process (all possible configurations) and $mathcal{D}(mathcal{F})$ the corresponding distribution over this support.
I wish now that each point is the center of a disk of radius $r$, and that no two disks collide. $mathcal{F}$ is thus reduced into $mathcal{F}^-$ because we have to remove all configurations with collisions. But it is not empty. The new process is: draw a configuration $c hookrightarrow mathcal{D}(mathcal{F})$, reject it until there is no collision in $c$. This yields a new distribution $c hookrightarrow mathcal{D}'(mathcal{F}^-)$.
A naive way to sample from $mathcal{D}'(mathcal{F}^-)$ is to simulate the process. But the rejection rate gets really high when $lambda$ and $r$ get big.
Is there a clever way to sample from $mathcal{D}'(mathcal{F}^-)$ with lower rejection rate?
Can approaches like random tiling with Markov chains be adapted to such a continous case?
sampling poisson-process collision-detection
asked Dec 4 '18 at 11:21
iago-litoiago-lito
295312
add a comment |
On a 2D square $[0, 1]^2$, I can draw a random configuration of points $c = (n, (x_i)_{1..n})$ with interesting independence properties using a Poisson point process: draw the number of points $n hookrightarrow mathcal{P}(lambda)$, and then $n$ coordinates $x_i hookrightarrow mathcal{U}([0, 1]^2)$. Let us call $mathcal{F}$ the support of this process (all possible configurations) and $mathcal{D}(mathcal{F})$ the corresponding distribution over this support.
I wish now that each point is the center of a disk of radius $r$, and that no two disks collide. $mathcal{F}$ is thus reduced into $mathcal{F}^-$ because we have to remove all configurations with collisions. But it is not empty. The new process is: draw a configuration $c hookrightarrow mathcal{D}(mathcal{F})$, reject it until there is no collision in $c$. This yields a new distribution $c hookrightarrow mathcal{D}'(mathcal{F}^-)$.
A naive way to sample from $mathcal{D}'(mathcal{F}^-)$ is to simulate the process. But the rejection rate gets really high when $lambda$ and $r$ get big.
Is there a clever way to sample from $mathcal{D}'(mathcal{F}^-)$ with lower rejection rate?
Can approaches like random tiling with Markov chains be adapted to such a continous case?
sampling poisson-process collision-detection
asked Dec 4 '18 at 11:21
iago-litoiago-lito
295312
On a 2D square $[0, 1]^2$, I can draw a random configuration of points $c = (n, (x_i)_{1..n})$ with interesting independence properties using a Poisson point process: draw the number of points $n hookrightarrow mathcal{P}(lambda)$, and then $n$ coordinates $x_i hookrightarrow mathcal{U}([0, 1]^2)$. Let us call $mathcal{F}$ the support of this process (all possible configurations) and $mathcal{D}(mathcal{F})$ the corresponding distribution over this support.
I wish now that each point is the center of a disk of radius $r$, and that no two disks collide. $mathcal{F}$ is thus reduced into $mathcal{F}^-$ because we have to remove all configurations with collisions. But it is not empty. The new process is: draw a configuration $c hookrightarrow mathcal{D}(mathcal{F})$, reject it until there is no collision in $c$. This yields a new distribution $c hookrightarrow mathcal{D}'(mathcal{F}^-)$.
A naive way to sample from $mathcal{D}'(mathcal{F}^-)$ is to simulate the process. But the rejection rate gets really high when $lambda$ and $r$ get big.
Is there a clever way to sample from $mathcal{D}'(mathcal{F}^-)$ with lower rejection rate?
Can approaches like random tiling with Markov chains be adapted to such a continous case?
sampling poisson-process collision-detection
sampling poisson-process collision-detection
asked Dec 4 '18 at 11:21
iago-litoiago-lito
295312
asked Dec 4 '18 at 11:21
iago-litoiago-lito
295312
asked Dec 4 '18 at 11:21
iago-litoiago-lito
295312
asked Dec 4 '18 at 11:21
iago-litoiago-lito
295312
asked Dec 4 '18 at 11:21
iago-litoiago-lito
295312
295312
add a comment |
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%2f3025439%2fsample-from-poisson-process-with-no-collisions%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%2f3025439%2fsample-from-poisson-process-with-no-collisions%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
