29
$\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$
5
  • 13
    $\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
    Commented May 22, 2015 at 23:43
  • 4
    $\begingroup$ Why wouldn't you want to use calculus? $\endgroup$ Commented May 23, 2015 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$ Commented Jun 2, 2015 at 23:55
  • $\begingroup$ Related: math.stackexchange.com/questions/1254129/…. $\endgroup$ Commented Feb 25, 2018 at 11:14
  • 8
    $\begingroup$ "Because this problem seems like it shouldn't require calculus." Hmmm, I would say exactly the opposite. $\endgroup$
    – Did
    Commented Feb 3, 2019 at 8:30

2 Answers 2

36
$\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$
8
  • 5
    $\begingroup$ He said without calculus. $\endgroup$
    – Jimmy360
    Commented May 23, 2015 at 0:54
  • 4
    $\begingroup$ @Sangchul Lee How do you find p.d.f. of $|X1−X2|$ ? $\endgroup$ Commented Dec 31, 2016 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
    Commented Apr 18, 2020 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$ Commented Nov 5, 2020 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$ Commented Nov 5, 2020 at 14:50
13
$\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$
6
  • 1
    $\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
    Commented Aug 15, 2015 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
    Commented Aug 15, 2015 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$ Commented Aug 15, 2015 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$ Commented Aug 15, 2015 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$ Commented Nov 1, 2016 at 19:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .