Probability of overlap of random intervals dropped on unit circle
$begingroup$
Suppose I have a circle with circumference $A$. Along the circumference of this circle, I randomly drop $N$ arcs with fixed length $a < A$. Now suppose I drop a single additional arc ($N+1$). What is the probability $P(N, a/A)$ that this arc does not overlap with any previously dropped arcs?
My intuition is that this has something to do with the Stirling numbers, because given something like $3$ arcs, the overlap scheme could be no overlapping, three possible ways of three overlapping, or all overlapping. However, I cannot figure out how to approach the problem of finding the probability of overlap. I found some relevant notes on meeting probabilities here and here, but I can't quite see how to apply this to my problem
probability combinatorics stochastic-processes permutations
asked Dec 3 '18 at 23:21
wil3wil3
1155
$endgroup$
add a comment |
$begingroup$
Suppose I have a circle with circumference $A$. Along the circumference of this circle, I randomly drop $N$ arcs with fixed length $a < A$. Now suppose I drop a single additional arc ($N+1$). What is the probability $P(N, a/A)$ that this arc does not overlap with any previously dropped arcs?
My intuition is that this has something to do with the Stirling numbers, because given something like $3$ arcs, the overlap scheme could be no overlapping, three possible ways of three overlapping, or all overlapping. However, I cannot figure out how to approach the problem of finding the probability of overlap. I found some relevant notes on meeting probabilities here and here, but I can't quite see how to apply this to my problem
probability combinatorics stochastic-processes permutations
asked Dec 3 '18 at 23:21
wil3wil3
1155
$endgroup$
1
$begingroup$
What do you mean, "randomly?"
$endgroup$
– Ben W
Dec 3 '18 at 23:36
$begingroup$
The midpoint of the dropped interval is selected randomly on $[0, 2 pi]$, independently of where previous intervals have been dropped
$endgroup$
– wil3
Dec 3 '18 at 23:38
1
$begingroup$
I think this may not have a closed-form answer. It is clear that we need only consider cases where $aleq A/2$. Let us, as a special case, consider that $ageq A/3$ and that the radius is 1. Then the probability is given by $frac{N!}{(2pi)^N}int_{theta_1}^{2pi-a}int_{theta_2}^{2pi-a}cdotsint_{theta_{N-1}}^{2pi-a}int_{theta_N+Theta}^{2pi-a}dtheta_{N+1};dtheta_Ncdots dtheta_3;dtheta_2$, where $theta_1=0$. Of course, the computation here depends heavily on the fact that $ageq A/3$. If $a<A/3$ then the computation will be dramatically different.
$endgroup$
– Ben W
Dec 4 '18 at 0:21
$begingroup$
@BenW I looked at the paper linked in the answer below (which uses counting arguments rather than defining a pdf) and it looks like it works---would you agree? I can't quite tell yet if there is a subtle issue with the paper (perhaps with the boundary conditions)
$endgroup$
– wil3
Dec 4 '18 at 1:01
1
$begingroup$
you may be right. Frankly, I've had a few drinks and will have to wait till tomorrow to respond intelligently to your question. You may be right. But my intuition tells me this is far more complicated than we might wish.
$endgroup$
– Ben W
Dec 4 '18 at 1:17
add a comment |
$begingroup$
Suppose I have a circle with circumference $A$. Along the circumference of this circle, I randomly drop $N$ arcs with fixed length $a < A$. Now suppose I drop a single additional arc ($N+1$). What is the probability $P(N, a/A)$ that this arc does not overlap with any previously dropped arcs?
My intuition is that this has something to do with the Stirling numbers, because given something like $3$ arcs, the overlap scheme could be no overlapping, three possible ways of three overlapping, or all overlapping. However, I cannot figure out how to approach the problem of finding the probability of overlap. I found some relevant notes on meeting probabilities here and here, but I can't quite see how to apply this to my problem
probability combinatorics stochastic-processes permutations
asked Dec 3 '18 at 23:21
wil3wil3
1155
$endgroup$
Suppose I have a circle with circumference $A$. Along the circumference of this circle, I randomly drop $N$ arcs with fixed length $a < A$. Now suppose I drop a single additional arc ($N+1$). What is the probability $P(N, a/A)$ that this arc does not overlap with any previously dropped arcs?
My intuition is that this has something to do with the Stirling numbers, because given something like $3$ arcs, the overlap scheme could be no overlapping, three possible ways of three overlapping, or all overlapping. However, I cannot figure out how to approach the problem of finding the probability of overlap. I found some relevant notes on meeting probabilities here and here, but I can't quite see how to apply this to my problem
probability combinatorics stochastic-processes permutations
probability combinatorics stochastic-processes permutations
asked Dec 3 '18 at 23:21
wil3wil3
1155
asked Dec 3 '18 at 23:21
wil3wil3
1155
asked Dec 3 '18 at 23:21
wil3wil3
1155
asked Dec 3 '18 at 23:21
wil3wil3
1155
asked Dec 3 '18 at 23:21
wil3wil3
1155
1155
1
$begingroup$
What do you mean, "randomly?"
$endgroup$
– Ben W
Dec 3 '18 at 23:36
$begingroup$
The midpoint of the dropped interval is selected randomly on $[0, 2 pi]$, independently of where previous intervals have been dropped
$endgroup$
– wil3
Dec 3 '18 at 23:38
1
$begingroup$
I think this may not have a closed-form answer. It is clear that we need only consider cases where $aleq A/2$. Let us, as a special case, consider that $ageq A/3$ and that the radius is 1. Then the probability is given by $frac{N!}{(2pi)^N}int_{theta_1}^{2pi-a}int_{theta_2}^{2pi-a}cdotsint_{theta_{N-1}}^{2pi-a}int_{theta_N+Theta}^{2pi-a}dtheta_{N+1};dtheta_Ncdots dtheta_3;dtheta_2$, where $theta_1=0$. Of course, the computation here depends heavily on the fact that $ageq A/3$. If $a<A/3$ then the computation will be dramatically different.
$endgroup$
– Ben W
Dec 4 '18 at 0:21
$begingroup$
@BenW I looked at the paper linked in the answer below (which uses counting arguments rather than defining a pdf) and it looks like it works---would you agree? I can't quite tell yet if there is a subtle issue with the paper (perhaps with the boundary conditions)
$endgroup$
– wil3
Dec 4 '18 at 1:01
1
$begingroup$
you may be right. Frankly, I've had a few drinks and will have to wait till tomorrow to respond intelligently to your question. You may be right. But my intuition tells me this is far more complicated than we might wish.
$endgroup$
– Ben W
Dec 4 '18 at 1:17
add a comment |
1
$begingroup$
What do you mean, "randomly?"
$endgroup$
– Ben W
Dec 3 '18 at 23:36
$begingroup$
The midpoint of the dropped interval is selected randomly on $[0, 2 pi]$, independently of where previous intervals have been dropped
$endgroup$
– wil3
Dec 3 '18 at 23:38
1
$begingroup$
I think this may not have a closed-form answer. It is clear that we need only consider cases where $aleq A/2$. Let us, as a special case, consider that $ageq A/3$ and that the radius is 1. Then the probability is given by $frac{N!}{(2pi)^N}int_{theta_1}^{2pi-a}int_{theta_2}^{2pi-a}cdotsint_{theta_{N-1}}^{2pi-a}int_{theta_N+Theta}^{2pi-a}dtheta_{N+1};dtheta_Ncdots dtheta_3;dtheta_2$, where $theta_1=0$. Of course, the computation here depends heavily on the fact that $ageq A/3$. If $a<A/3$ then the computation will be dramatically different.
$endgroup$
– Ben W
Dec 4 '18 at 0:21
$begingroup$
@BenW I looked at the paper linked in the answer below (which uses counting arguments rather than defining a pdf) and it looks like it works---would you agree? I can't quite tell yet if there is a subtle issue with the paper (perhaps with the boundary conditions)
$endgroup$
– wil3
Dec 4 '18 at 1:01
1
$begingroup$
you may be right. Frankly, I've had a few drinks and will have to wait till tomorrow to respond intelligently to your question. You may be right. But my intuition tells me this is far more complicated than we might wish.
$endgroup$
– Ben W
Dec 4 '18 at 1:17
1
1
$begingroup$
What do you mean, "randomly?"
$endgroup$
– Ben W
Dec 3 '18 at 23:36
$begingroup$
What do you mean, "randomly?"
$endgroup$
– Ben W
Dec 3 '18 at 23:36
$begingroup$
The midpoint of the dropped interval is selected randomly on $[0, 2 pi]$, independently of where previous intervals have been dropped
$endgroup$
– wil3
Dec 3 '18 at 23:38
$begingroup$
The midpoint of the dropped interval is selected randomly on $[0, 2 pi]$, independently of where previous intervals have been dropped
$endgroup$
– wil3
Dec 3 '18 at 23:38
1
1
$begingroup$
I think this may not have a closed-form answer. It is clear that we need only consider cases where $aleq A/2$. Let us, as a special case, consider that $ageq A/3$ and that the radius is 1. Then the probability is given by $frac{N!}{(2pi)^N}int_{theta_1}^{2pi-a}int_{theta_2}^{2pi-a}cdotsint_{theta_{N-1}}^{2pi-a}int_{theta_N+Theta}^{2pi-a}dtheta_{N+1};dtheta_Ncdots dtheta_3;dtheta_2$, where $theta_1=0$. Of course, the computation here depends heavily on the fact that $ageq A/3$. If $a<A/3$ then the computation will be dramatically different.
$endgroup$
– Ben W
Dec 4 '18 at 0:21
$begingroup$
I think this may not have a closed-form answer. It is clear that we need only consider cases where $aleq A/2$. Let us, as a special case, consider that $ageq A/3$ and that the radius is 1. Then the probability is given by $frac{N!}{(2pi)^N}int_{theta_1}^{2pi-a}int_{theta_2}^{2pi-a}cdotsint_{theta_{N-1}}^{2pi-a}int_{theta_N+Theta}^{2pi-a}dtheta_{N+1};dtheta_Ncdots dtheta_3;dtheta_2$, where $theta_1=0$. Of course, the computation here depends heavily on the fact that $ageq A/3$. If $a<A/3$ then the computation will be dramatically different.
$endgroup$
– Ben W
Dec 4 '18 at 0:21
$begingroup$
@BenW I looked at the paper linked in the answer below (which uses counting arguments rather than defining a pdf) and it looks like it works---would you agree? I can't quite tell yet if there is a subtle issue with the paper (perhaps with the boundary conditions)
$endgroup$
– wil3
Dec 4 '18 at 1:01
$begingroup$
@BenW I looked at the paper linked in the answer below (which uses counting arguments rather than defining a pdf) and it looks like it works---would you agree? I can't quite tell yet if there is a subtle issue with the paper (perhaps with the boundary conditions)
$endgroup$
– wil3
Dec 4 '18 at 1:01
1
1
$begingroup$
you may be right. Frankly, I've had a few drinks and will have to wait till tomorrow to respond intelligently to your question. You may be right. But my intuition tells me this is far more complicated than we might wish.
$endgroup$
– Ben W
Dec 4 '18 at 1:17
$begingroup$
you may be right. Frankly, I've had a few drinks and will have to wait till tomorrow to respond intelligently to your question. You may be right. But my intuition tells me this is far more complicated than we might wish.
$endgroup$
– Ben W
Dec 4 '18 at 1:17
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
This can be quite delicate but lots are known, going back to a classic paper by Flatto and Konheim available here.
Let $n-1$ uniform points be independently selected on the circle, and denote the the $n$ interval lengths they (with probability one, being distinct) split the circle into by $X_1,ldots,X_n.$
For example, the following quantities are calculated in this paper and they can directly answer your question and similar questions.
answered Dec 3 '18 at 23:41
kodlukodlu
3,390716
$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%2f3024861%2fprobability-of-overlap-of-random-intervals-dropped-on-unit-circle%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
This can be quite delicate but lots are known, going back to a classic paper by Flatto and Konheim available here.
Let $n-1$ uniform points be independently selected on the circle, and denote the the $n$ interval lengths they (with probability one, being distinct) split the circle into by $X_1,ldots,X_n.$
For example, the following quantities are calculated in this paper and they can directly answer your question and similar questions.
answered Dec 3 '18 at 23:41
kodlukodlu
3,390716
$endgroup$
add a comment |
$begingroup$
This can be quite delicate but lots are known, going back to a classic paper by Flatto and Konheim available here.
Let $n-1$ uniform points be independently selected on the circle, and denote the the $n$ interval lengths they (with probability one, being distinct) split the circle into by $X_1,ldots,X_n.$
For example, the following quantities are calculated in this paper and they can directly answer your question and similar questions.
answered Dec 3 '18 at 23:41
kodlukodlu
3,390716
$endgroup$
add a comment |
$begingroup$
This can be quite delicate but lots are known, going back to a classic paper by Flatto and Konheim available here.
Let $n-1$ uniform points be independently selected on the circle, and denote the the $n$ interval lengths they (with probability one, being distinct) split the circle into by $X_1,ldots,X_n.$
For example, the following quantities are calculated in this paper and they can directly answer your question and similar questions.
answered Dec 3 '18 at 23:41
kodlukodlu
3,390716
$endgroup$
This can be quite delicate but lots are known, going back to a classic paper by Flatto and Konheim available here.
Let $n-1$ uniform points be independently selected on the circle, and denote the the $n$ interval lengths they (with probability one, being distinct) split the circle into by $X_1,ldots,X_n.$
For example, the following quantities are calculated in this paper and they can directly answer your question and similar questions.
answered Dec 3 '18 at 23:41
kodlukodlu
3,390716
answered Dec 3 '18 at 23:41
kodlukodlu
3,390716
answered Dec 3 '18 at 23:41
kodlukodlu
3,390716
answered Dec 3 '18 at 23:41
kodlukodlu
3,390716
3,390716
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%2f3024861%2fprobability-of-overlap-of-random-intervals-dropped-on-unit-circle%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$
What do you mean, "randomly?"
$endgroup$
– Ben W
Dec 3 '18 at 23:36
$begingroup$
The midpoint of the dropped interval is selected randomly on $[0, 2 pi]$, independently of where previous intervals have been dropped
$endgroup$
– wil3
Dec 3 '18 at 23:38
1
$begingroup$
I think this may not have a closed-form answer. It is clear that we need only consider cases where $aleq A/2$. Let us, as a special case, consider that $ageq A/3$ and that the radius is 1. Then the probability is given by $frac{N!}{(2pi)^N}int_{theta_1}^{2pi-a}int_{theta_2}^{2pi-a}cdotsint_{theta_{N-1}}^{2pi-a}int_{theta_N+Theta}^{2pi-a}dtheta_{N+1};dtheta_Ncdots dtheta_3;dtheta_2$, where $theta_1=0$. Of course, the computation here depends heavily on the fact that $ageq A/3$. If $a<A/3$ then the computation will be dramatically different.
$endgroup$
– Ben W
Dec 4 '18 at 0:21
$begingroup$
@BenW I looked at the paper linked in the answer below (which uses counting arguments rather than defining a pdf) and it looks like it works---would you agree? I can't quite tell yet if there is a subtle issue with the paper (perhaps with the boundary conditions)
$endgroup$
– wil3
Dec 4 '18 at 1:01
1
$begingroup$
you may be right. Frankly, I've had a few drinks and will have to wait till tomorrow to respond intelligently to your question. You may be right. But my intuition tells me this is far more complicated than we might wish.
$endgroup$
– Ben W
Dec 4 '18 at 1:17