Author |
Topic: Clustered Points (Read 428 times) |
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender: 
Posts: 4489
|
 |
Clustered Points
« on: Jun 30th, 2004, 6:02am » |
 Quote  Modify
|
If n points are randomly and independently distributed over the interval [0,1], what is the probability that all n are clustered within a distance d of each other (where d < 1)?
|
|
 IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Clustered Points
« Reply #1 on: Jun 30th, 2004, 6:41am » |
Quote Modify
|
::dn ??
no wait, that would be for a specific range [a,a+d]
So take the leftmost point and call it a, and we get dn-1..
Which isn't quite the answer either I think.. (at least not to this question, now if we were dealing with a circle instead..)
::
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Clustered Points
« Reply #2 on: Jun 30th, 2004, 11:07am » |
Quote Modify
|
Well, the first thing that comes to mind is
dn-1(nn/2(1-d) + 2d/n!),
but it's probably wrong, considering that it doesn't work for n=1.
|
| « Last Edit: Jun 30th, 2004, 11:14am by Eigenray » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Clustered Points
« Reply #3 on: Jun 30th, 2004, 12:00pm » |
Quote Modify
|
I think the answer is: [smiley=blacksquare.gif]1 - (1-d)n[smiley=blacksquare.gif].
 Late evening gibberish...
|
| « Last Edit: Jul 1st, 2004, 5:38am by Barukh » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Clustered Points
« Reply #4 on: Jun 30th, 2004, 12:19pm » |
Quote Modify
|
Well that works for two points, but if the number of points goes to infinity they'd be within distance d of each other with probability one according to that formula..
(Of course my earlier attempts don't even work for n=2)
|
| « Last Edit: Jun 30th, 2004, 12:21pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Clustered Points
« Reply #5 on: Jun 30th, 2004, 1:05pm » |
Quote Modify
|
The thing I put before was a pitiful attempt to visualize in n-dimensional space. It's not even bounded. Anyway, I think I have it:
Hint: Divide the interval into N pieces, such that k = dN >> n.
Sol: Let's count. First we pick the smallest number x, and there are two cases:
1) x < N-k. Then we pick (n-1) numbers from bins x to x+k, in approximately kn-1/(n-1)! ways.
2) x > N-k. Then we pick n numbers from N-k to N, which we can do in about kn/n! ways.
In total, there are about (N-k)kn-1/(n-1)! + kn/n! = Nkn-1/(n-1)! - (n-1)kn/n! ways, and dividing by the total number of possibilities ~ Nn/n!, gives p ~ ndn-1 - (n-1)dn.
And hopefully the approximations are accurate enough to make this thing converge as N goes to infinity.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
Interesting approach, Eigenray! I believe your answer is correct. Here's my (incomplete) analysis.
I also tried the geometric approach. Case n=2 is equivalent to the well known problem of 2 friends meeting (I'm not sure that's the right name), and is depicted in the attached figure. The shaded areas are those where 2 points are farther than d. That gives the probability 1 – (1-d)2 = 2d - d2.
Carelessly generalizing, I presented the obviously wrong formula last night. Today, I took the case n=3 more carefully, considering the 3D cube. Here, every 2 points that are at least d apart, correspond to a triangular prism of volume (1-d)2/2, and there are 6 such prisms. However, every 2 prisms intersect in a square pyramid with volume (1-d)3/3. Therefore, the sought probability equals 1 – 3(1-d)2 + 2(1-d)3 = 3d2 - 2d3.
Here, (at least my) imagination stops, but I believe this may be generalized (safely!). 
|
| « Last Edit: Jul 1st, 2004, 10:44am by Barukh » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print