TOPICS
Search

Hypercube Line Picking


Let two points x and y be picked randomly from a unit n-dimensional hypercube. The expected distance between the points Delta(n), i.e., the mean line segment length, is then

 Delta(n)=int_0^1...int_0^1_()_(2n)sqrt((x_1-y_1)^2+(x_2-y_2)^2+...+(x_n-y_n)^2)dx_1...dx_ndy_1...dy_n.
(1)

This multiple integral has been evaluated analytically only for small values of n. The case Delta(1) corresponds to the line line picking between two random points in the interval [0,1].

HypercubeLinePlot

The first few values for Delta(n) are given in the following table.

nOEISDelta(n)
1--0.3333333333...
2A0915050.5214054331...
3A0730120.6617071822...
4A1039830.7776656535...
5A1039840.8785309152...
6A1039850.9689420830...
7A1039861.0515838734...
8A1039871.1281653402...

The function Delta(n) satisfies

 1/3n^(1/2)<=Delta(n)<=(1/6n)^(1/2)sqrt(1/3[1+2(1-3/(5n))^(1/2)])
(2)

(Anderssen et al. 1976), plotted above together with the actual values.

HypercubeLinePickingIntegrands

M. Trott (pers. comm., Feb. 23, 2005) has devised an ingenious algorithm for reducing the 2n-dimensional integral to an integral over a 1-dimensional integrand I_n(x) such that

 Delta(n)=int_0^inftyI_n(x)dx.
(3)

The first few values are

I_1=(2e^(-x^2))/(3sqrt(pi))
(4)
I_2=(e^(-x^2)erf(x))/(3x)+(4e^(-2x^2))/(15sqrt(pi))+(4e^(-x^2))/(15sqrt(pi))
(5)
I_3=-2/5e^(-x^2)sqrt(pi)erf^2(x)+(4e^(-2x^2)erf(x))/(5x)+(e^(-x^2)erf(x))/(5x)-(12e^(-3x^2))/(35sqrt(pi))+(68e^(-2x^2))/(105sqrt(pi))+(8e^(-x^2))/(105sqrt(pi))
(6)
I_4=-(2e^(-x^2)pierf^3(x))/(15x)-(136)/(105)e^(-2x^2)sqrt(pi)erf^2(x)-(32)/(105)e^(-x^2)sqrt(pi)erf^2(x)+(197e^(-3x^2)erf(x))/(210x)+(104e^(-2x^2)erf(x))/(105x)+(e^(-x^2)erf(x))/(14x)-(676e^(-4x^2))/(945sqrt(pi))+(16e^(-3x^2))/(35sqrt(pi))+(146e^(-2x^2))/(315sqrt(pi))+(16e^(-x^2))/(945sqrt(pi)).
(7)

In the limit as x->0, these have values for n=1, 2, ... given by 1/sqrt(pi) times 2/3, 6/5, 50/21, 38/9, 74/11, ... (OEIS A103990 and A103991).

This is equivalent to computing the box integral

 Delta_n(s)=s/(Gamma(1-1/2s))int_0^infty(1-[d(u)]^n)/(u^(s+1))du
(8)

where

d(u)=int_0^1int_0^1e^(-u^2(x-y)^2)dxdy
(9)
=int_0^1int_0^1(e^(-u^2)-1+sqrt(pi)uerf(u))/(u^2)du
(10)

(Bailey et al. 2006).

These give closed-form results for n=1, 2, 3, and 4:

Delta(1)=1/3
(11)
Delta(2)=1/(15)[sqrt(2)+2+5ln(1+sqrt(2))]
(12)
Delta(3)=1/(105)[4+17sqrt(2)-6sqrt(3)+21ln(1+sqrt(2))+42ln(2+sqrt(3))-7pi]
(13)
Delta(4)=(136)/(105)sqrt(2)tan^(-1)(1/2sqrt(2))-(34)/(105)pisqrt(2)+8/(105)sqrt(3)+(73)/(630)sqrt(2)+4/5Cl_2(alpha)-4/5Cl_2(alpha+1/2pi)+(197)/(420)ln3+1/(14)ln(1+sqrt(2))-4/5alphaln(1+sqrt(2))-1/5piln(1+sqrt(2))+(52)/(105)ln(2+sqrt(3))-(23)/(135)-(16)/(315)pi+(26)/(15)K
(14)
Delta(5)=(65)/(42)K-(380)/(6237)sqrt(5)+(568)/(3465)sqrt(3)-4/(189)pi-(449)/(3465)-(73)/(63)sqrt(2)tan^(-1)(1/4sqrt(2))-(184)/(189)ln2+(64)/(189)ln(sqrt(5)+1)+1/(54)ln(1+sqrt(2))+(40)/(63)ln(sqrt(2)+sqrt(6))-5/(28)piln(1+sqrt(2))+(52)/(63)piln2+(295)/(252)ln3+4/(215)pi^2+(3239)/(62370)sqrt(2)-8/(21)sqrt(3)cot^(-1)(sqrt(15))-(52)/(63)piln(sqrt(2)+sqrt(6))-5/7alpha+5/7Cl_2(alpha)-5/7Cl_2(alpha+1/2pi)+(52)/(63)K_1,
(15)

where Cl_2(z) is a Clausen function, K is Catalan's constant, and

 alpha=sin^(-1)((sqrt(2))/6-2/3).
(16)

The n=4 case above was published for the first time in this work; the simplified form given above is due to Bailey et al. (2007). Attempting to reduce Delta(5) to quadratures gives closed-form pieces with the exception of the single piece

K_1=pi[1/2ln(2+sqrt(3))-int_0^infty(e^(-2x^2)erf^3(x))/xdx]
(17)
=int_3^4(sec^(-1)x)/(sqrt((x-3)(x-1)))dx
(18)
=int_0^(I[cos^(-1)2])sec^(-1)(2+coshtheta)dtheta
(19)

which appears to be difficult to integrate in closed form (Bailey et al. 2007, p. 272).

The value Delta(3) obtained for cube line picking is sometimes known as the Robbins constant.


See also

Cube Line Picking, Hypercube Point Picking, Mean Line Segment Length, Robbins Constant, Square Line Picking, Square Point Picking, Square Triangle Picking, Unit Square Integral

Explore with Wolfram|Alpha

References

Anderssen, R. S.; Brent, R. P.; Daley, D. J.; and Moran, A. P. "Concerning int_0^1...int_0^1sqrt(x_1^2+...+x_k^2)dx_1...dx_k and a Taylor Series Method." SIAM J. Appl. Math. 30, 22-30, 1976.Bailey, D. H.; Borwein, J. M.; and Crandall, R. E. "Box Integrals." J. Comput. Appl. Math. 206, 196-208, 2007.Bailey, D. H.; Borwein, J. M.; and Crandall, R. E. "Advances in the Theory of Box Integrals." Math. Comput. 79, 1839-1866, 2010.Bailey, D. H.; Borwein, J. M.; Calkin, N. J.; Girgensohn, R.; Luke, D. R.; and Moll, V. H. Experimental Mathematics in Action. Wellesley, MA: A K Peters, p. 272, 2007.Finch, S. R. "Geometric Probability Constants." §8.1 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 479-484, 2003.Le Lionnais, F. Les nombres remarquables. Paris: Hermann, p. 30, 1983.Robbins, D. "Average Distance between Two Points in a Box." Amer. Math. Monthly 85, 278, 1978.Sloane, N. J. A. Sequences A073012, A091505, A103983, A103984, A103985, A103986, A103987, A103988, A103989, A103990, and A103991 in "The On-Line Encyclopedia of Integer Sequences."Trott, M. "The Area of a Random Triangle." Mathematica J. 7, 189-198, 1998.

Referenced on Wolfram|Alpha

Hypercube Line Picking

Cite this as:

Weisstein, Eric W. "Hypercube Line Picking." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/HypercubeLinePicking.html

Subject classifications