13
$\begingroup$

Imagine that you choose two random points within a 1 by 1 square. What is the average distance between those two points? Using a random number generator, I'm getting a value of ~0.521402... can anyone explain why I'm getting this value, or what this number means?

More importantly, is there a way to solve this without using calculus and/or large random sampling?

$\endgroup$
  • 11
    $\begingroup$ The exact value is $\frac{1}{15}\left(\sqrt{2}+2+5\ln(1+\sqrt2)\right)$, according to bit.ly/1PBZFjd. I don’t know how you might find this without calculus. $\endgroup$ – Steve Kass May 22 '15 at 23:43
  • $\begingroup$ Why wouldn't you want to use calculus? $\endgroup$ – Yuval Filmus May 23 '15 at 2:29
  • $\begingroup$ Because this problem seems like it shouldn't require calculus. I know how to do it with calculus; it just seems like calculus shouldn't be necessary for a problem this basic. $\endgroup$ – J. Antonio Perez Jun 2 '15 at 23:55
  • $\begingroup$ Related: math.stackexchange.com/questions/1254129/…. $\endgroup$ – StubbornAtom Feb 25 '18 at 11:14
  • 1
    $\begingroup$ "Because this problem seems like it shouldn't require calculus." Hmmm, I would say exactly the opposite. $\endgroup$ – Did Feb 3 at 8:30
24
$\begingroup$

Let $(X_i, Y_i)$ for $i=1,2$ be i.i.d. and has uniform distribution on $[0, 1]^2$. Then $|X_1 - X_2|$ has PDF

$$ f(x) = \begin{cases} 2(1-x), & 0 \leq x \leq 1 \\ 0, & \text{otherwise} \end{cases}. $$

This shows that the average distance is

\begin{align*} \int_{0}^{1}\int_{0}^{1} 4(1-x)(1-y)(x^2 + y^2)^{1/2} \, dxdy &= \frac{1}{15}(2+\sqrt{2}+5\log(1+\sqrt{2})) \\ &\approx 0.52140543316472067833 \cdots. \end{align*}


If $l_n$ denotes the average distance between two uniformly chosen points in $[0, 1]^n$, then the following formula may help us estimate the decay of $l_n$ as $n \to \infty$:

$$ l_n = \frac{1}{\sqrt{\pi}} \int_{0}^{\infty} \left \{1 - \left( \frac{\sqrt{\pi} \operatorname{erf}(u)}{u} - \frac{1 - e^{-u^2}}{u^2} \right)^{n} \right\} \frac{du}{u^2}. $$

Using an estimate (which I believe to be true but was unable to prove)

$$ e^{-u^2 / 6} \leq \frac{\sqrt{\pi} \operatorname{erf}(u)}{u} - \frac{1 - e^{-u^2}}{u^2} \leq 1 $$

and hence we get

$$ l_n \leq \frac{1}{\sqrt{\pi}} \int_{0}^{\infty} \frac{1 - e^{-nu^2/6}}{u^2} \, du = \sqrt{\frac{n}{6}}. $$

For example, for $2 \leq n \leq 20$ we have

enter image description here

$\endgroup$
  • 5
    $\begingroup$ He said without calculus. $\endgroup$ – Jimmy360 May 23 '15 at 0:54
  • 3
    $\begingroup$ @Sangchul Lee How do you find p.d.f. of $|X1−X2|$ ? $\endgroup$ – Archisman Panigrahi Dec 31 '16 at 6:26
  • 1
    $\begingroup$ Is this the line of thought here:$X_1,X_2,Y_1,Y_2\stackrel{\text{i.i.d.}}{\sim}\mathcal{U}(0,1)$. Distance between the points $(X_1,Y_1)$ and $(X_2,Y_2)$ is given by $D=\sqrt{|X_2-X_1|^2+|Y_2-Y_1|^2}=\sqrt{U^2+V^2}$, say. $U$ and $V$ are i.i.d. with common pdf $f(x)=2(1-x)\mathbf{1}_{0<x<1}$. So joint density of $(U,V)$ is $f_{U,V}(u,v)=4(1-u)(1-v)\mathbf{1}_{0<u,v<1}$. Thus, $E(D)=4\int_0^1\int_0^1\sqrt{u^2+v^2}(1-u)(1-v)\,du\,dv$ ? $\endgroup$ – StubbornAtom Feb 25 '18 at 7:37
9
$\begingroup$

When you say "without calculus", then presumably you are talking about just using something like basic algebra or Euclidean geometry. However, as you have seen from the up-voted posted answers and comments, the exact answer involves natural logarithm. It is basically impossible to define natural logarithm without some sort of calculus and/or real analysis. So it seems you need calculus (or its more formal version, real analysis) to come up with the formula for this answer.

$\endgroup$
  • $\begingroup$ I think I disagree. One needs calculus to actually calculate natural logarithms but not to define them. One possible definition that many people could understand without having learned about calculus is: Imagine a vehicle that works such that at distance $d$ from its destination it travels with speed $d$ per second. The natural logarithm of $x$ is the time in seconds that it takes for the vehicle's distance (or speed) to be reduced by a factor $x$. It seems highly unlikely but not entirely impossible that one could prove the desired formula with such a definition without any calculus. $\endgroup$ – joriki Aug 15 '15 at 7:03
  • $\begingroup$ You might object that calculus is inherent in the notion of "speed", but I don't think that this is what the OP had in mind in saying "without calculus". The speed of a vehicle is a concept many people feel comfortable working with without knowing or needing a formal mathematical definition via limits of difference quotients. I think "without calculus" was meant to mean "without using the methods of calculus, such as differentiation, integration, calculating limits". $\endgroup$ – joriki Aug 15 '15 at 7:06
  • $\begingroup$ @jorki I have never seen any definition of logarithm or exponential that could actually be computed for arbitrary inputs without calculus-based ideas. As for your description in terms of traveling at variable speed, that inherently is appealing to calculus because you are describing "overall" (i.e., integral) reduction factor in terms of the cumulative effect of traveling at variable speed as relates to distance. Maybe that will help someone understand what a formula with logarithm means, but I doubt it can be used to compute arbitrary natural log without something like a series. $\endgroup$ – user2566092 Aug 15 '15 at 21:47
  • $\begingroup$ @jorki I'm not trying to put your opinions down, I just think that in a way we're both right. All I'm saying is that intuitive understanding of concepts does not always lead to derivation or calculability of formulas. $\endgroup$ – user2566092 Aug 15 '15 at 21:50
  • $\begingroup$ "log(x) is the limit of n(x^(1/n) -1 ) " can be understood and computed without understanding of calculus. $\endgroup$ – user3391229 Nov 1 '16 at 19:12
-5
$\begingroup$

You can calculate this numerically. Assume a grid of points and a square of length 100. Pseudocode:

total = 0 count = 0 for x in 0...100 for x0 in 0...100 for y in 0...100 for y0 in 0...100 total += ((x-x0)**2 + (y-y0)**2)**0.5 count += 1

answer = (total/count) / 100 #divide by 100 to normalize.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.