Mixing
Estimating the smallest distance between $n$ points uniformly distributed on the unit circle.
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
I'm working on the following question and would like some hints or solutions
Let $n$ points be iid, uniformly distributed on the unit circle. Let
$Delta_n$ be the smallest distance between any two of these points.
Show that $n^theta Delta_nto 0$ in probability as $nto infty$, for all $0<theta<2$. HINT: Divide the circle into small arcs and find the probability that at
least one arc contains 2 or more points
So I tried following the hint, and I considered dividing up the circle into $n-1$ pieces that would give with probability 1, that two are in the same section. However, $n^theta/n-1$ does not go to zero. The other things I tried were $n^2$ pieces and $n$ pieces, but the probability calculations are rather messy for these and I'd be dealing with factorials, which does not seem like it would go well with this problem.
Source: Problem 2
probability probability-theory
asked Jul 20 at 21:02
iYOA
60549
add a comment |Â
up vote
3
down vote
favorite
I'm working on the following question and would like some hints or solutions
Let $n$ points be iid, uniformly distributed on the unit circle. Let
$Delta_n$ be the smallest distance between any two of these points.
Show that $n^theta Delta_nto 0$ in probability as $nto infty$, for all $0<theta<2$. HINT: Divide the circle into small arcs and find the probability that at
least one arc contains 2 or more points
So I tried following the hint, and I considered dividing up the circle into $n-1$ pieces that would give with probability 1, that two are in the same section. However, $n^theta/n-1$ does not go to zero. The other things I tried were $n^2$ pieces and $n$ pieces, but the probability calculations are rather messy for these and I'd be dealing with factorials, which does not seem like it would go well with this problem.
Source: Problem 2
probability probability-theory
asked Jul 20 at 21:02
iYOA
60549
Try starting with the following question. Given n points and m (> n) arcs, what is the probability that all the points are in different arcs? The answer to your question should follow.
– herb steinberg
Jul 20 at 21:21
I got that the probability is $fracm*(m-1)cdots(m-n+1)m^n$ but don't we need to be more specific about what $m$ is becuase $n^theta/m$ doesnt necessarily go to zero.
– iYOA
Jul 20 at 22:00
Can you make something of the following? In the limit, we are essentially dealing with points distributed according to a Poisson distribution with mean separation $2pi/n$. Then the minimum of $n$ variables, each with that distribution, has a mean value of $1/n$ times that, or $2pi/n^2$, and the result follows. Not exactly rigorous, but perhaps it can be turned into something rigorous.
– Brian Tung
Jul 20 at 22:46
Also, with the factorials, I'd make use of Stirling's approximation, if that's permissible.
– Brian Tung
Jul 20 at 22:48
I think stirling's approximation is fair game here, since we did indeed cover it in class.
– iYOA
Jul 21 at 22:02
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
I'm working on the following question and would like some hints or solutions
Let $n$ points be iid, uniformly distributed on the unit circle. Let
$Delta_n$ be the smallest distance between any two of these points.
Show that $n^theta Delta_nto 0$ in probability as $nto infty$, for all $0<theta<2$. HINT: Divide the circle into small arcs and find the probability that at
least one arc contains 2 or more points
So I tried following the hint, and I considered dividing up the circle into $n-1$ pieces that would give with probability 1, that two are in the same section. However, $n^theta/n-1$ does not go to zero. The other things I tried were $n^2$ pieces and $n$ pieces, but the probability calculations are rather messy for these and I'd be dealing with factorials, which does not seem like it would go well with this problem.
Source: Problem 2
probability probability-theory
asked Jul 20 at 21:02
iYOA
60549
I'm working on the following question and would like some hints or solutions
Let $n$ points be iid, uniformly distributed on the unit circle. Let
$Delta_n$ be the smallest distance between any two of these points.
Show that $n^theta Delta_nto 0$ in probability as $nto infty$, for all $0<theta<2$. HINT: Divide the circle into small arcs and find the probability that at
least one arc contains 2 or more points
So I tried following the hint, and I considered dividing up the circle into $n-1$ pieces that would give with probability 1, that two are in the same section. However, $n^theta/n-1$ does not go to zero. The other things I tried were $n^2$ pieces and $n$ pieces, but the probability calculations are rather messy for these and I'd be dealing with factorials, which does not seem like it would go well with this problem.
Source: Problem 2
probability probability-theory
asked Jul 20 at 21:02
iYOA
60549
edited Jul 20 at 22:40
asked Jul 20 at 21:02
iYOA
60549
asked Jul 20 at 21:02
iYOA
60549
asked Jul 20 at 21:02
iYOA
60549
60549
Try starting with the following question. Given n points and m (> n) arcs, what is the probability that all the points are in different arcs? The answer to your question should follow.
– herb steinberg
Jul 20 at 21:21
I got that the probability is $fracm*(m-1)cdots(m-n+1)m^n$ but don't we need to be more specific about what $m$ is becuase $n^theta/m$ doesnt necessarily go to zero.
– iYOA
Jul 20 at 22:00
Can you make something of the following? In the limit, we are essentially dealing with points distributed according to a Poisson distribution with mean separation $2pi/n$. Then the minimum of $n$ variables, each with that distribution, has a mean value of $1/n$ times that, or $2pi/n^2$, and the result follows. Not exactly rigorous, but perhaps it can be turned into something rigorous.
– Brian Tung
Jul 20 at 22:46
Also, with the factorials, I'd make use of Stirling's approximation, if that's permissible.
– Brian Tung
Jul 20 at 22:48
I think stirling's approximation is fair game here, since we did indeed cover it in class.
– iYOA
Jul 21 at 22:02
add a comment |Â
Try starting with the following question. Given n points and m (> n) arcs, what is the probability that all the points are in different arcs? The answer to your question should follow.
– herb steinberg
Jul 20 at 21:21
I got that the probability is $fracm*(m-1)cdots(m-n+1)m^n$ but don't we need to be more specific about what $m$ is becuase $n^theta/m$ doesnt necessarily go to zero.
– iYOA
Jul 20 at 22:00
Can you make something of the following? In the limit, we are essentially dealing with points distributed according to a Poisson distribution with mean separation $2pi/n$. Then the minimum of $n$ variables, each with that distribution, has a mean value of $1/n$ times that, or $2pi/n^2$, and the result follows. Not exactly rigorous, but perhaps it can be turned into something rigorous.
– Brian Tung
Jul 20 at 22:46
Also, with the factorials, I'd make use of Stirling's approximation, if that's permissible.
– Brian Tung
Jul 20 at 22:48
I think stirling's approximation is fair game here, since we did indeed cover it in class.
– iYOA
Jul 21 at 22:02
Try starting with the following question. Given n points and m (> n) arcs, what is the probability that all the points are in different arcs? The answer to your question should follow.
– herb steinberg
Jul 20 at 21:21
Try starting with the following question. Given n points and m (> n) arcs, what is the probability that all the points are in different arcs? The answer to your question should follow.
– herb steinberg
Jul 20 at 21:21
I got that the probability is $fracm*(m-1)cdots(m-n+1)m^n$ but don't we need to be more specific about what $m$ is becuase $n^theta/m$ doesnt necessarily go to zero.
– iYOA
Jul 20 at 22:00
I got that the probability is $fracm*(m-1)cdots(m-n+1)m^n$ but don't we need to be more specific about what $m$ is becuase $n^theta/m$ doesnt necessarily go to zero.
– iYOA
Jul 20 at 22:00
Can you make something of the following? In the limit, we are essentially dealing with points distributed according to a Poisson distribution with mean separation $2pi/n$. Then the minimum of $n$ variables, each with that distribution, has a mean value of $1/n$ times that, or $2pi/n^2$, and the result follows. Not exactly rigorous, but perhaps it can be turned into something rigorous.
– Brian Tung
Jul 20 at 22:46
Can you make something of the following? In the limit, we are essentially dealing with points distributed according to a Poisson distribution with mean separation $2pi/n$. Then the minimum of $n$ variables, each with that distribution, has a mean value of $1/n$ times that, or $2pi/n^2$, and the result follows. Not exactly rigorous, but perhaps it can be turned into something rigorous.
– Brian Tung
Jul 20 at 22:46
Also, with the factorials, I'd make use of Stirling's approximation, if that's permissible.
– Brian Tung
Jul 20 at 22:48
Also, with the factorials, I'd make use of Stirling's approximation, if that's permissible.
– Brian Tung
Jul 20 at 22:48
I think stirling's approximation is fair game here, since we did indeed cover it in class.
– iYOA
Jul 21 at 22:02
I think stirling's approximation is fair game here, since we did indeed cover it in class.
– iYOA
Jul 21 at 22:02
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
5
down vote
accepted
This is essentially the birthday problem, thinly disguised. (I'm a little dismayed it took me this long to see it.) If we divide the circle into $m$ equal segments, then the probability that there exists at least one segment shared by at least two of the $n$ points is $q = 1-fracm!m^n(m-n)!$. Stirling's approximation—
$$
k! approx left(frackeright)^ksqrt2pi k
$$
—allows us to rewrite $q$, roughly, as
$$
q approx 1-exp left(-fracn^22mright)
$$
Observe that for $m = n^theta$, $0 < theta < 2$, we have that $q approx 1-exp left(frac-n^2-theta2right) to 1$.
The Wikipedia article linked above gives a variety of ways to approximate the birthday coincidence probability. Pick a favorite. :-)
answered Jul 20 at 23:43
Brian Tung
25.2k32453
Thanks, the idea makes sense but I'm trying to work out the details and I seem to be getting stuck. For instance, how do you get that $fracm!m^n(m-n)!$ equals $exp(-n/m^2)$. Using stirling's approximation, I'm getting that it is $e^(-n)(fracmm-n)^(m-n+1/2)$, but I don't see how to further simplify it. Also, there might be a typo somewhere because if you set $m=n^theta$, we would have $exp(-n^1-2theta)$, not $exp(-n^2-theta)$.
– iYOA
Jul 21 at 22:48
@iYOA: Yeah, that was a whopper of a typo. I edited my answer, but you can check the edit history.
– Brian Tung
Jul 22 at 4:14
@iYOA: To answer your other question, see here for a pretty good exposition. It's about halfway down the page—look for "Stirling."
– Brian Tung
Jul 22 at 4:33
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
5
down vote
accepted
This is essentially the birthday problem, thinly disguised. (I'm a little dismayed it took me this long to see it.) If we divide the circle into $m$ equal segments, then the probability that there exists at least one segment shared by at least two of the $n$ points is $q = 1-fracm!m^n(m-n)!$. Stirling's approximation—
$$
k! approx left(frackeright)^ksqrt2pi k
$$
—allows us to rewrite $q$, roughly, as
$$
q approx 1-exp left(-fracn^22mright)
$$
Observe that for $m = n^theta$, $0 < theta < 2$, we have that $q approx 1-exp left(frac-n^2-theta2right) to 1$.
The Wikipedia article linked above gives a variety of ways to approximate the birthday coincidence probability. Pick a favorite. :-)
answered Jul 20 at 23:43
Brian Tung
25.2k32453
Thanks, the idea makes sense but I'm trying to work out the details and I seem to be getting stuck. For instance, how do you get that $fracm!m^n(m-n)!$ equals $exp(-n/m^2)$. Using stirling's approximation, I'm getting that it is $e^(-n)(fracmm-n)^(m-n+1/2)$, but I don't see how to further simplify it. Also, there might be a typo somewhere because if you set $m=n^theta$, we would have $exp(-n^1-2theta)$, not $exp(-n^2-theta)$.
– iYOA
Jul 21 at 22:48
@iYOA: Yeah, that was a whopper of a typo. I edited my answer, but you can check the edit history.
– Brian Tung
Jul 22 at 4:14
@iYOA: To answer your other question, see here for a pretty good exposition. It's about halfway down the page—look for "Stirling."
– Brian Tung
Jul 22 at 4:33
add a comment |Â
up vote
5
down vote
accepted
This is essentially the birthday problem, thinly disguised. (I'm a little dismayed it took me this long to see it.) If we divide the circle into $m$ equal segments, then the probability that there exists at least one segment shared by at least two of the $n$ points is $q = 1-fracm!m^n(m-n)!$. Stirling's approximation—
$$
k! approx left(frackeright)^ksqrt2pi k
$$
—allows us to rewrite $q$, roughly, as
$$
q approx 1-exp left(-fracn^22mright)
$$
Observe that for $m = n^theta$, $0 < theta < 2$, we have that $q approx 1-exp left(frac-n^2-theta2right) to 1$.
The Wikipedia article linked above gives a variety of ways to approximate the birthday coincidence probability. Pick a favorite. :-)
answered Jul 20 at 23:43
Brian Tung
25.2k32453
Thanks, the idea makes sense but I'm trying to work out the details and I seem to be getting stuck. For instance, how do you get that $fracm!m^n(m-n)!$ equals $exp(-n/m^2)$. Using stirling's approximation, I'm getting that it is $e^(-n)(fracmm-n)^(m-n+1/2)$, but I don't see how to further simplify it. Also, there might be a typo somewhere because if you set $m=n^theta$, we would have $exp(-n^1-2theta)$, not $exp(-n^2-theta)$.
– iYOA
Jul 21 at 22:48
@iYOA: Yeah, that was a whopper of a typo. I edited my answer, but you can check the edit history.
– Brian Tung
Jul 22 at 4:14
@iYOA: To answer your other question, see here for a pretty good exposition. It's about halfway down the page—look for "Stirling."
– Brian Tung
Jul 22 at 4:33
add a comment |Â
up vote
5
down vote
accepted
up vote
5
down vote
accepted
This is essentially the birthday problem, thinly disguised. (I'm a little dismayed it took me this long to see it.) If we divide the circle into $m$ equal segments, then the probability that there exists at least one segment shared by at least two of the $n$ points is $q = 1-fracm!m^n(m-n)!$. Stirling's approximation—
$$
k! approx left(frackeright)^ksqrt2pi k
$$
—allows us to rewrite $q$, roughly, as
$$
q approx 1-exp left(-fracn^22mright)
$$
Observe that for $m = n^theta$, $0 < theta < 2$, we have that $q approx 1-exp left(frac-n^2-theta2right) to 1$.
The Wikipedia article linked above gives a variety of ways to approximate the birthday coincidence probability. Pick a favorite. :-)
answered Jul 20 at 23:43
Brian Tung
25.2k32453
This is essentially the birthday problem, thinly disguised. (I'm a little dismayed it took me this long to see it.) If we divide the circle into $m$ equal segments, then the probability that there exists at least one segment shared by at least two of the $n$ points is $q = 1-fracm!m^n(m-n)!$. Stirling's approximation—
$$
k! approx left(frackeright)^ksqrt2pi k
$$
—allows us to rewrite $q$, roughly, as
$$
q approx 1-exp left(-fracn^22mright)
$$
Observe that for $m = n^theta$, $0 < theta < 2$, we have that $q approx 1-exp left(frac-n^2-theta2right) to 1$.
The Wikipedia article linked above gives a variety of ways to approximate the birthday coincidence probability. Pick a favorite. :-)
answered Jul 20 at 23:43
Brian Tung
25.2k32453
edited Jul 22 at 20:46
answered Jul 20 at 23:43
Brian Tung
25.2k32453
answered Jul 20 at 23:43
Brian Tung
25.2k32453
answered Jul 20 at 23:43
Brian Tung
25.2k32453
25.2k32453
Thanks, the idea makes sense but I'm trying to work out the details and I seem to be getting stuck. For instance, how do you get that $fracm!m^n(m-n)!$ equals $exp(-n/m^2)$. Using stirling's approximation, I'm getting that it is $e^(-n)(fracmm-n)^(m-n+1/2)$, but I don't see how to further simplify it. Also, there might be a typo somewhere because if you set $m=n^theta$, we would have $exp(-n^1-2theta)$, not $exp(-n^2-theta)$.
– iYOA
Jul 21 at 22:48
@iYOA: Yeah, that was a whopper of a typo. I edited my answer, but you can check the edit history.
– Brian Tung
Jul 22 at 4:14
@iYOA: To answer your other question, see here for a pretty good exposition. It's about halfway down the page—look for "Stirling."
– Brian Tung
Jul 22 at 4:33
add a comment |Â
Thanks, the idea makes sense but I'm trying to work out the details and I seem to be getting stuck. For instance, how do you get that $fracm!m^n(m-n)!$ equals $exp(-n/m^2)$. Using stirling's approximation, I'm getting that it is $e^(-n)(fracmm-n)^(m-n+1/2)$, but I don't see how to further simplify it. Also, there might be a typo somewhere because if you set $m=n^theta$, we would have $exp(-n^1-2theta)$, not $exp(-n^2-theta)$.
– iYOA
Jul 21 at 22:48
@iYOA: Yeah, that was a whopper of a typo. I edited my answer, but you can check the edit history.
– Brian Tung
Jul 22 at 4:14
@iYOA: To answer your other question, see here for a pretty good exposition. It's about halfway down the page—look for "Stirling."
– Brian Tung
Jul 22 at 4:33
Thanks, the idea makes sense but I'm trying to work out the details and I seem to be getting stuck. For instance, how do you get that $fracm!m^n(m-n)!$ equals $exp(-n/m^2)$. Using stirling's approximation, I'm getting that it is $e^(-n)(fracmm-n)^(m-n+1/2)$, but I don't see how to further simplify it. Also, there might be a typo somewhere because if you set $m=n^theta$, we would have $exp(-n^1-2theta)$, not $exp(-n^2-theta)$.
– iYOA
Jul 21 at 22:48
Thanks, the idea makes sense but I'm trying to work out the details and I seem to be getting stuck. For instance, how do you get that $fracm!m^n(m-n)!$ equals $exp(-n/m^2)$. Using stirling's approximation, I'm getting that it is $e^(-n)(fracmm-n)^(m-n+1/2)$, but I don't see how to further simplify it. Also, there might be a typo somewhere because if you set $m=n^theta$, we would have $exp(-n^1-2theta)$, not $exp(-n^2-theta)$.
– iYOA
Jul 21 at 22:48
@iYOA: Yeah, that was a whopper of a typo. I edited my answer, but you can check the edit history.
– Brian Tung
Jul 22 at 4:14
@iYOA: Yeah, that was a whopper of a typo. I edited my answer, but you can check the edit history.
– Brian Tung
Jul 22 at 4:14
@iYOA: To answer your other question, see here for a pretty good exposition. It's about halfway down the page—look for "Stirling."
– Brian Tung
Jul 22 at 4:33
@iYOA: To answer your other question, see here for a pretty good exposition. It's about halfway down the page—look for "Stirling."
– Brian Tung
Jul 22 at 4:33
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2858025%2festimating-the-smallest-distance-between-n-points-uniformly-distributed-on-the%23new-answer', 'question_page');
);
Post as a guest
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
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
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
Try starting with the following question. Given n points and m (> n) arcs, what is the probability that all the points are in different arcs? The answer to your question should follow.
– herb steinberg
Jul 20 at 21:21
I got that the probability is $fracm*(m-1)cdots(m-n+1)m^n$ but don't we need to be more specific about what $m$ is becuase $n^theta/m$ doesnt necessarily go to zero.
– iYOA
Jul 20 at 22:00
Can you make something of the following? In the limit, we are essentially dealing with points distributed according to a Poisson distribution with mean separation $2pi/n$. Then the minimum of $n$ variables, each with that distribution, has a mean value of $1/n$ times that, or $2pi/n^2$, and the result follows. Not exactly rigorous, but perhaps it can be turned into something rigorous.
– Brian Tung
Jul 20 at 22:46
Also, with the factorials, I'd make use of Stirling's approximation, if that's permissible.
– Brian Tung
Jul 20 at 22:48
I think stirling's approximation is fair game here, since we did indeed cover it in class.
– iYOA
Jul 21 at 22:02