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

2 Answers 2

Reset to default
35
$\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$
7
  • 5
    $\begingroup$ He said without calculus. $\endgroup$
    – Jimmy360
    May 23, 2015 at 0:54
  • 4
    $\begingroup$ @Sangchul Lee How do you find p.d.f. of $|X1−X2|$ ? $\endgroup$
    – Archisman Panigrahi
    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
    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$
    – Ahmet Bilal
    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$
    – Archisman Panigrahi
    Nov 5, 2020 at 14:50
12
$\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
  • $\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, 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
    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$
    – user2566092
    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$
    – user2566092
    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$
    – user3391229
    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 .