wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Clustered Points
        
(Message started by: THUDandBLUNDER on Jun 30^th, 2004, 6:02am)

Title: Clustered Points
Post by THUDandBLUNDER on Jun 30^th, 2004, 6:02am

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)?

Title: Re: Clustered Points
Post by towr on Jun 30^th, 2004, 6:41am

::[hide]dⁿ ??
no wait, that would be for a specific range [a,a+d]
So take the leftmost point and call it a, and we get d^n-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..)
[/hide]::

Title: Re: Clustered Points
Post by Eigenray on Jun 30^th, 2004, 11:07am

Well, the first thing that comes to mind is[hide]
d^n-1(n^n/2(1-d) + 2d/n!)[/hide],
but it's probably wrong, considering that it doesn't work for n=1.

Title: Re: Clustered Points
Post by Barukh on Jun 30^th, 2004, 12:00pm

I think the answer is: [smiley=blacksquare.gif]~~1 - (1-d)ⁿ~~[smiley=blacksquare.gif].

::) Late evening gibberish...

Title: Re: Clustered Points
Post by towr on Jun 30^th, 2004, 12:19pm

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)

Title: Re: Clustered Points
Post by Eigenray on Jun 30^th, 2004, 1:05pm

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: [hide]Divide the interval into N pieces, such that k = dN >> n[/hide].
Sol: [hide]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 k^n-1/(n-1)! ways.
2) x > N-k. Then we pick n numbers from N-k to N, which we can do in about kⁿ/n! ways.
In total, there are about (N-k)k^n-1/(n-1)! + kⁿ/n! = Nk^n-1/(n-1)! - (n-1)kⁿ/n! ways, and dividing by the total number of possibilities ~ Nⁿ/n!, gives p ~ nd^n-1 - (n-1)dⁿ.
And hopefully the approximations are accurate enough to make this thing converge as N goes to infinity[/hide].

Title: Re: Clustered Points
Post by Barukh on Jul 1^st, 2004, 10:43am

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)² = 2d - d².

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, and there are 6 such prisms. However, every 2 prisms intersect in a square pyramid with volume (1-d)³/3. Therefore, the sought probability equals 1 – 3(1-d)² + 2(1-d)³ = 3d² - 2d³.

Here, (at least my) imagination stops, but I believe this may be generalized (safely!). ;D