Author |
Topic: Expected Distance (Read 1120 times) |
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender: 
Posts: 4489
|
 |
Expected Distance
« on: May 4th, 2004, 10:15am » |
 Quote  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
Gender:
Posts: 1825
|
|
Re: Expected Distance
« Reply #1 on: May 4th, 2004, 11:44am » |
Quote 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! 
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
Gender:
Posts: 1825
|
|
Re: Expected Distance
« Reply #2 on: May 4th, 2004, 3:08pm » |
Quote 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. 
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Expected Distance
« Reply #3 on: May 4th, 2004, 3:23pm » |
Quote 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
Gender:
Posts: 1825
|
|
Re: Expected Distance
« Reply #4 on: May 4th, 2004, 4:54pm » |
Quote 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:
Posts: 13730
|
|
Re: Expected Distance
« Reply #5 on: May 5th, 2004, 1:00am » |
Quote 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
Gender:
Posts: 1825
|
|
Re: Expected Distance
« Reply #6 on: May 5th, 2004, 2:19am » |
Quote 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:
Posts: 13730
|
|
Re: Expected Distance
« Reply #7 on: May 5th, 2004, 3:09am » |
Quote 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
Gender:
Posts: 1825
|
|
Re: Expected Distance
« Reply #8 on: May 5th, 2004, 6:09am » |
Quote 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... 
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Expected Distance
« Reply #9 on: May 5th, 2004, 7:41pm » |
Quote 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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print