AnalyticBridge

A Data Science Central Community

Challenge of the Week

Three points A, B, C are randomly distributed on a plane, with the following constrainsts:

• distance between A and B is equal to p
• distance between B and C is equal to q

What would be the average (expected value) for the distance r between A and C?

Of course the maximum is r = p + q. But what is the average? You can imagine A, B and C as being three cities. Without loss of generality, you can assume that A and B are fixed, and only C is random.

Views: 3456

Replies to This Discussion

So, I took the integral from 0 to 2pi of p^2 + q^2 - 2*p*q*cos(t) and normalized by 2pi.  You end up with r^2 = p^2 + q^2 as the average.  So, r = sqrt(p^2+q^2).

Keith Portman

Interesting, the average corresponds to the case where the triangle is right.

Hi Keith,

If p = q your solution would mean E[r] =p * sqrt(2)  where I find E[r] = p*(4/pi)

please see my post below .

I did not try to solve it myself, but I thought that the solution would imply a number like pi rather than SQRT(2). In short, this problem can be used (with p = q = 1) in Monte Carlo simulations to estimate pi.

Without integration obviously Mean(cos(x)) = 0

I did the integral of x from 0 to pi of sqrt( p^2 + q^2 -2p*qcos(x))/pi

The answer comes down to an elliptic integral.  The expectation of r is given by:

E[r] =    2 * (p+q) * Elliptic(4pq/((p+q)^2 )  /   pi

Without loss of generality lets assume that  p < q.  Then E[r] is approximately

E[r] = (p+q) * ( 1- (p/q) + (5/4)(p/q)^2 - (5/4)(p/q)^3 + (81/128)(p/q)^4 )

and when p and q are the same E[r] -> p*(4/pi) which is approximately p*(81/64) according to the formula above

and when p is much smaller than q we have

E[r] -> p+q

and as p ->0 then we have E[r] -> q

Osorio Meirelles

A better approximation with more terms:

E[r] = (p+q) * ( 1- (p/q) + (5/4)(p/q)^2 - (5/4)(p/q)^3 + (81/64)(p/q)^4 )

- (81/64)*(p/q)^5 + (325/256)*(p/q)^6 -(325/256)*(p/q)^7 + (20825/32768)*(p/q)^8 )

the average = max(p,q)

Omar FOUDAL

Just to elaborate on the solution :-)

Very nice question,

but it is hard to answer without knowing how is the distribution of 'random' points.

considering it has 3 deg of freedom and 2 bounds, without loss of generality we can we can map e.g. B to the origin and A on the x axis. now C is bound to lay on the circle of radius q around the origin.

To successfully approach this problem one needs to know the distribution of q.

Assuming P(w) the probability density of C laying so that ABC forms an angle w and applying the Law of Cosine.
the solution is given by r^2 = \Integral_0_{2\pi} [p^2+q^2-2p*q*cos(w)] P(dw)

the case of P(w) uniform is given below.

The mean of both p and q will be equal (from the same Wald distribution), which means r can be considered the mean chord length of a circle. Chord length is easy to calculate, and the angle ABC exists as a uniform distribution between 0 and 180 degrees (with mean 90 degrees).

Or r = sqrt(2p^2)

Osorio has it right for an otherwise uniformly distributed point set. The average of r in that case is a complete elliptic integral of the second kind. A reasonably well-converging approximation is

<r> = (p + q) * [1 - Sum_(k=1)^inf ((2k-1)!!/2k!!)^2 * m^k/(2k-1)], where m = 4pq/(p+q)^2.

The first few terms are: (p + q) * [1 - (1/4)m - (3/64)m^2 - (45/2304)m^3 - ...]

For an otherwise non-uniformly distributed point set, Davide has the right idea.

At least two responses implied a claim that E(r^2)=[E(r)]^2, which is clearly not true, otherwise all variances would have to equal zero (!).

This integral appears often in tactical naval calculations when one is trying to understand how a ship's speed (p) affects its rate of encountering ships at another speed (q) in random orientations.

1

2

3

4