What's the dimension?

I know this is a computer science question, but the solution can be worked out exactly with a bit of calculus. First, the distance formula. In 2 dimensions, it is $d = \sqrt{(x_2-x_1)^2 + (y_2-y_1)^2}$ . This generalizes to higher dimensions by adding more terms under the square root. In other words, the total distance squared is the sum of the squares of the distances in each dimension. Since the question asks about the average distance, we can do the same but using the sum of the average distance squared. The average of the distance squared is given by:

$\frac{1}{1-0}\frac{1}{1-0}\int_0^1 \int_0^1(x-y)^2 dx dy=\frac 16$

Since this is true in each dimension, the average distance in $n$ dimensions is $\sqrt{n/6}$ . 24 dimensions makes this exactly 2, so we need 25 dimensions to make the average greater than 2.

Note: I have used x and y here because I’m too lazy to type $x_1$ and $x_2$ multiple times. x and y are independent values along the same dimension, not perpendicular ones

Here's a Python script that implements Monte Carlo simulation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

from random import random
from math import sqrt
n = 1
while True:
  dis = 0.000000
  N = 1000000
  i = 0
  while i<N:
    temp = 0
    for j in range(n):
      temp+=(random()-random())**2
    dis+=sqrt(temp)
    i+=1
  dis/=N
  if dis>2:
    print n
    break
  n+=1

Which on running gives
Output 25