wu :: forums
« wu :: forums - Expected Distance »

Welcome, Guest. Please Login or Register.
Dec 23rd, 2024, 7:45am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: towr, Eigenray, SMQ, ThudnBlunder, Grimbal, william wu, Icarus)
   Expected Distance
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Expected Distance  (Read 1125 times)
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
*****




The dewdrop slides into the shining Sea

   


Gender: male
Posts: 4489
Expected Distance  
« on: May 4th, 2004, 10:15am »
Quote Quote Modify Modify

What is the expected distance between two random points in a unit square?
IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
Sir Col
Uberpuzzler
*****




impudens simia et macrologus profundus fabulae

   
WWW

Gender: male
Posts: 1825
Re: Expected Distance  
« Reply #1 on: May 4th, 2004, 11:44am »
Quote Quote Modify Modify

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! Roll Eyes
 
So instead I used a computer (with around one million trials), and I got a probability of approximately 0.52138.
 
 
(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)).
IP Logged

mathschallenge.net / projecteuler.net
Sir Col
Uberpuzzler
*****




impudens simia et macrologus profundus fabulae

   
WWW

Gender: male
Posts: 1825
Re: Expected Distance  
« Reply #2 on: May 4th, 2004, 3:08pm »
Quote Quote Modify Modify

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[X1X 2]
 
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.  Huh
IP Logged

mathschallenge.net / projecteuler.net
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Expected Distance  
« Reply #3 on: May 4th, 2004, 3:23pm »
Quote Quote Modify Modify

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..
« Last Edit: May 4th, 2004, 3:27pm by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Sir Col
Uberpuzzler
*****




impudens simia et macrologus profundus fabulae

   
WWW

Gender: male
Posts: 1825
Re: Expected Distance  
« Reply #4 on: May 4th, 2004, 4:54pm »
Quote Quote Modify Modify

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
« Last Edit: May 5th, 2004, 1:52am by Sir Col » IP Logged

mathschallenge.net / projecteuler.net
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Expected Distance  
« Reply #5 on: May 5th, 2004, 1:00am »
Quote Quote Modify Modify

Perhaps it might help to start discrete, and then take the limit to go to the continuous equivalent.
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Sir Col
Uberpuzzler
*****




impudens simia et macrologus profundus fabulae

   
WWW

Gender: male
Posts: 1825
Re: Expected Distance  
« Reply #6 on: May 5th, 2004, 2:19am »
Quote Quote Modify Modify

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.
IP Logged

mathschallenge.net / projecteuler.net
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Expected Distance  
« Reply #7 on: May 5th, 2004, 3:09am »
Quote Quote Modify Modify

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..
« Last Edit: May 5th, 2004, 3:21am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Sir Col
Uberpuzzler
*****




impudens simia et macrologus profundus fabulae

   
WWW

Gender: male
Posts: 1825
Re: Expected Distance  
« Reply #8 on: May 5th, 2004, 6:09am »
Quote Quote Modify Modify

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...  Undecided
IP Logged

mathschallenge.net / projecteuler.net
SWF
Uberpuzzler
*****





   


Posts: 879
Re: Expected Distance  
« Reply #9 on: May 5th, 2004, 7:41pm »
Quote Quote Modify Modify

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))
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

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