21
$\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
  • 3
    $\begingroup$ "Because this problem seems like it shouldn't require calculus." Hmmm, I would say exactly the opposite. $\endgroup$ – Did Feb 3 '19 at 8:30
29
$\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

| cite | improve this answer | |
$\endgroup$
  • 5
    $\begingroup$ He said without calculus. $\endgroup$ – Jimmy360 May 23 '15 at 0:54
  • 4
    $\begingroup$ @Sangchul Lee How do you find p.d.f. of $|X1−X2|$ ? $\endgroup$ – Archisman Panigrahi Dec 31 '16 at 6:26
  • $\begingroup$ Hi. How do you get the formula for the general n-dimensional case? Do you, by any chance, still know the source of this table? $\endgroup$ – McLawrence Apr 18 at 16:08
  • $\begingroup$ @ArchismanPanigrahi Here is an intuition. Imagine moving a slider of length x on a line segment of length L. The sliding amount which is L-x is proportional to the probability you see such an instance of slider at the end of choosing two random points on that line segment. $\endgroup$ – Ahmet Bilal Nov 5 at 12:42
  • $\begingroup$ @AhmetBilal The total probability of independently choosing two points in that region is $(L-x)^2$, and then the probability density will be its derivative $2(L-x)$. Is that what you meant? $\endgroup$ – Archisman Panigrahi Nov 5 at 14:50
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.

| cite | improve 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

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