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

        riddles >> hard >> Expected Distance
        
(Message started by: THUDandBLUNDER on May 4th, 2004, 10:15am)
Title: Expected Distance
Post by THUDandBLUNDER on May 4th, 2004, 10:15am
What is the expected distance between two random points in a unit square?
Title: Re: Expected Distance
Post by Sir Col on May 4th, 2004, 11:44am
I'm still playing with the theoretical probability, but I have an experimental probability. I did this by drawing a 1 cm by 1 cm square, closing my eyes and plotting a random point on the page. When two points were inside the square I measured the distance between them. The problem is that my ruler only measures inches! ::)

So instead I used a computer (with around one million trials), and I got a probability of approximately [hide]0.52138[/hide].


(I won't bother hiding this, as there is nothing significant)

Let the two points be (x1,y1) and (x2,y2). Each distance: x1, x2, y1, and y2 can be represented by a continuous uniform random variable, P~U(0,1). Let the distance between the points be d, such that E(D)=E([sqrt]((X1-X2)2+(Y1-Y2)2)).
Title: Re: Expected Distance
Post by Sir Col on May 4th, 2004, 3:08pm
Okay, I've been making an embarrassing attempt at this, but I'll share what I've done so far. I'm almost certain that I've made a fundamental oversight in working with combinations of these uniform distributions.

E[(X1-X2)2] = E[X12]+E[X12]-2E[X1X2]

E[X2] = 0[int]1 x2 dx = 1/3
E[X1X2] = 0[int]1 0[int]1 x12 x22 dx2 dx1 = 1/4

So E[(X1-X2)2] = 1/3+1/3-2*1/4 = 1/6

Similarly, E[(Y1-Y2)2]= 1/6

Therefore, E[D2] = E[(X1-X2)2+(Y1-Y2)2] = 1/3

Even if what I have done is correct (which I am seriously doubting), I'm not sure how to proceed from here.  ???
Title: Re: Expected Distance
Post by towr on May 4th, 2004, 3:23pm
a numerical integral (for 0[int]10[int]1 0[int]10[int]1 [sqrt][(x1 - x2)2 + (y1 - y1)2] dx1dx2dy1dy2 )  gives me 0.5213396139
There must be some clever way to get the exact number though..
Title: Re: Expected Distance
Post by Sir Col on May 4th, 2004, 4:54pm
I've already tried playing with that monster, but with little success. It's that wretched square root!

Concentrating on the inner integrand: [int] [sqrt][(x1-x2)2+(y1-y2)2] dx1, let u=(y1-y2)

(i) writing as [int] u(1+[(x1-x2)/u]2)1/2 dx, then using the binomial series expansion leads to a very ugly expression!
(ii) writing as [int] (x12-2x2x1+x22 + u2)1/2 dx = [(x12 - 2x2x1 + x22 + u2)1/2 (x1 + x2) + (u2-x22) log(x1 + x2 + (x12-2x2x1+x22 + u2)1/2)]/2, but this is going nowhere fast!

Another idea is using the result: Var[D]=E[D2]–E[D]2. So if we can find Var[D], we can find E[D].

Incidentally, a simulation of one billion trials I ran came up with E[D]~=0.521382
Title: Re: Expected Distance
Post by towr on May 5th, 2004, 1:00am
Perhaps it might help to start discrete, and then take the limit to go to the continuous equivalent.
Title: Re: Expected Distance
Post by Sir Col on May 5th, 2004, 2:19am
That's an interesting idea...

Using a 2x2 lattice, there are 4x1 and 2x[sqrt]2 lengths. So E(D)=(4/6)1+(2/6)2[sqrt]2=(1+[sqrt]2)/3~=0.805

Using a 3x3 lattice, we have 12x(1/2), 8x(1/[sqrt]2), 6x1, 8x([sqrt]5/4), and 2x[sqrt]2. So E(D)=(6+3[sqrt]2+2[sqrt]5)/18~=0.817

Hmm? I can't see a way to generalise this, and I would have expected the 3x3 case to be less than the 2x2 case.
Title: Re: Expected Distance
Post by towr on May 5th, 2004, 3:09am
for the 2x2 lattice, there are 4 points, each having a distance to all 4 points, so 16 distances.
(8*1 + 4*[sqrt]2 + 4 * 0)/ 16 = (2+[sqrt]2)/4 ~= 0.85355

and you need to divide by (n-1), because the sides of the square aren't length 1, but (n-1), so each distance is stretched.

here's the numbers for 2 through 10
0.8535533905
0.7266556366
0.6693383231
0.6368912450
0.6160634032
0.6015775736
0.5909261016
0.5827672848
0.5763191356

of course in hindsight
[sum]x1=1n[sum]x2=1n [sum]y1=1n[sum]y2=1n [sqrt][(x1 - x2)2 + (y1 - y2)2]/(n4 (n-1))
probably isn't any easier to solve..
Title: Re: Expected Distance
Post by Sir Col on May 5th, 2004, 6:09am
Obviously P(P1=P2)=0 for continuous points, but with a discrete model can you pick the same point twice? Hmm... I suppose that independence is required, but are you then choosing TWO random points?

Me thinks that a new insight/direction is required to make further progress with this...  :-/
Title: Re: Expected Distance
Post by SWF on May 5th, 2004, 7:41pm
This one is standard integration. That first integral is a basic one- even printed in the abbreviated integral table inside the front cover of my calculus book. The main challenge is that it can get messy, if you are not careful.

I don't know if it is the easiest way, but I did the first two integrals in polar coordinates, which simplfies the integrand at the expense of more complicated integration limits. The average distance ends up as:

 2/15 + sqrt(2)/15 + (1/3)*ln(1+sqrt(2))


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board