{"id":2696,"date":"2017-09-27T17:59:54","date_gmt":"2017-09-27T22:59:54","guid":{"rendered":"https:\/\/blogs.mathworks.com\/cleve\/?p=2696"},"modified":"2017-09-27T17:59:54","modified_gmt":"2017-09-27T22:59:54","slug":"how-far-apart-are-two-random-points-in-a-hypercube","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/cleve\/2017\/09\/27\/how-far-apart-are-two-random-points-in-a-hypercube\/","title":{"rendered":"How Far Apart Are Two Random Points in a Hypercube?"},"content":{"rendered":"<div class=\"content\"><!--introduction--><p>Two days ago I wrote about <a href=\"https:\/\/blogs.mathworks.com\/cleve\/2017\/09\/25\/how-far-apart-are-two-random-points-in-a-square\">random points in a square<\/a>.  At the last minute I added the paragraph asking about the generalization to random points in a cube. I have to admit that I didn't check the Web to see what was known about the question.<\/p><p>Shortly after my post appeared, Pieterjan Robbe of KU Leuven in Belgium submitted a comment pointing out that the problem has been studied extensively.  He provided several pointers.  The solution even has a name; it's called Robbins Constant.  I have listed a few of the references below.<\/p><!--\/introduction--><h3>Contents<\/h3><div><ul><li><a href=\"#f3ce7d66-8e52-4b59-b1f9-96510b129140\">Robbins Constant<\/a><\/li><li><a href=\"#700a2b8d-2c1b-4075-aef8-235555afaee4\">Numerical Integration<\/a><\/li><li><a href=\"#bc700ec9-7c5d-41c0-8887-83c5e931490a\">Analytic Solution<\/a><\/li><li><a href=\"#1bc027bd-f317-4fac-8f0b-890faabf3fd1\">Hypercubes and Vectorize<\/a><\/li><li><a href=\"#9949c83b-7660-4546-adec-587f0c691cf8\">Thanks<\/a><\/li><li><a href=\"#4021f936-66e8-4a5a-945b-a2c94f1f48a1\">References<\/a><\/li><\/ul><\/div><h4>Robbins Constant<a name=\"f3ce7d66-8e52-4b59-b1f9-96510b129140\"><\/a><\/h4><p>Robbins Constant is the value of this six-fold integral.<\/p><p>$$\\delta = \\int_0^1 \\int_0^1 \\int_0^1 \\int_0^1 \\int_0^1 \\int_0^1 \\! \\sqrt{(x_1-y_1)^2 + (x_2-y_2)^2 + (x_3-y_3)^2} \\ \\mathrm{d}x_1 \\mathrm{d}y_1 \\mathrm{d}x_2 \\mathrm{d}y_2 \\mathrm{d}x_3 \\mathrm{d}y_3 $$<\/p><p>A change of variables makes it a triple integral.<\/p><p>$$\\delta = 8  \\int_0^1\\int_0^1 \\int_0^1 \\! \\sqrt{x^2 + y^2 + z^2} \\ (1-x)(1-y)(1-z) \\ \\mathrm{d}x \\mathrm{d}y \\mathrm{d}z$$<\/p><h4>Numerical Integration<a name=\"700a2b8d-2c1b-4075-aef8-235555afaee4\"><\/a><\/h4><p>Numerical integration with the default tolerances gets about nine decimal places.<\/p><pre class=\"codeinput\">   format <span class=\"string\">long<\/span>\r\n   F = @(x,y,z) sqrt(x.^2+y.^2+z.^2).*(1-x).*(1-y).*(1-z)\r\n   delta = 8*integral3(F,0,1,0,1,0,1)\r\n<\/pre><pre class=\"codeoutput\">F =\r\n  function_handle with value:\r\n    @(x,y,z)sqrt(x.^2+y.^2+z.^2).*(1-x).*(1-y).*(1-z)\r\ndelta =\r\n   0.661707182095901\r\n<\/pre><h4>Analytic Solution<a name=\"bc700ec9-7c5d-41c0-8887-83c5e931490a\"><\/a><\/h4><p>The exact analytic solution is impressive.  I can't explain where it comes from.<\/p><p>$$\\delta = \\frac{1}{105}(4 + 17\\sqrt{2} - 6\\sqrt{3} + 21\\log{(1+\\sqrt{2})} +\r\n   84\\log{(1+\\sqrt{3})} - 42\\log{(2)} - 7\\pi)$$<\/p><p>Here is the numeric value.<\/p><pre class=\"codeinput\">   delta = (1\/105)*(4 + 17*sqrt(2) - 6*sqrt(3) + 21*log(1+sqrt(2)) + <span class=\"keyword\">...<\/span>\r\n            84*log(1+sqrt(3)) - 42*log(2) - 7*pi)\r\n<\/pre><pre class=\"codeoutput\">delta =\r\n   0.661707182267176\r\n<\/pre><h4>Hypercubes and Vectorize<a name=\"1bc027bd-f317-4fac-8f0b-890faabf3fd1\"><\/a><\/h4><p>I also received email from MathWorks colleague Matt Tearle informing me about <tt>vecnorm<\/tt>, a new function that is in MATLAB Release R2017b. Unlike the <tt>norm<\/tt> function that computes matrix norms, <tt>vecnorm<\/tt> treats the elements along a specified dimension as vectors and calculates the norm of each vector. <a href=\"https:\/\/www.mathworks.com\/help\/matlab\/ref\/vecnorm.html\">Here is<\/a> the documentation page.<\/p><p>I don't yet have R2017b on this computer, but Matt's email prompted me to think about vectorizing the simulation, even without <tt>vecnorm<\/tt>. While we're at it, let's generalize to <tt>d<\/tt> dimensional hypercubes. And, I'll make it a one-liner.<\/p><pre class=\"codeinput\">   n = 10000000;  <span class=\"comment\">% n samples.<\/span>\r\n   <span class=\"keyword\">for<\/span> d = 1:10   <span class=\"comment\">% d dimensions.<\/span>\r\n      delta = mean(sqrt(sum((rand(n,d)-rand(n,d)).^2,2)));\r\n      fprintf(<span class=\"string\">'%6d %7.4f\\n'<\/span>,d,delta)\r\n   <span class=\"keyword\">end<\/span>\r\n<\/pre><pre class=\"codeoutput\">     1  0.3335\r\n     2  0.5215\r\n     3  0.6617\r\n     4  0.7778\r\n     5  0.8786\r\n     6  0.9692\r\n     7  1.0517\r\n     8  1.1282\r\n     9  1.1997\r\n    10  1.2675\r\n<\/pre><h4>Thanks<a name=\"9949c83b-7660-4546-adec-587f0c691cf8\"><\/a><\/h4><p>Thanks to Pieterjan Robbe and Matt Tearle.<\/p><h4>References<a name=\"4021f936-66e8-4a5a-945b-a2c94f1f48a1\"><\/a><\/h4><p>D. P. Robbins, Problem 2629, Average distance between two points in a box, Amer. Mathematical Monthly, 85.4, 1978, p. 278.<\/p><p>D. H. Bailey, J. M. Borwein and R. E. Crandall, Advances in the Theory of Box Integrals, <a href=\"http:\/\/crd-legacy.lbl.gov\/~dhbailey\/dhbpapers\/BoxII.pdf\">&lt;http:\/\/crd-legacy.lbl.gov\/~dhbailey\/dhbpapers\/BoxII.pdf<\/a>&gt;.<\/p><p>Johan Philip, The Probability Distribution of the Distance Between Two Random Points in a Box, <a href=\"https:\/\/people.kth.se\/~johanph\/habc.pdf\">https:\/\/people.kth.se\/~johanph\/habc.pdf<\/a>.<\/p><p>Eric W. Weisstein, Hypercube Line Picking. MathWorld, <a href=\"http:\/\/mathworld.wolfram.com\/HypercubeLinePicking.html\">&lt;http:\/\/mathworld.wolfram.com\/HypercubeLinePicking.html<\/a>&gt;.<\/p><p>N. J. A. Sloane, editor, The On-Line Encyclopedia of Integer Sequences, Decimal Expansion of Robbins Constant, <a href=\"http:\/\/oeis.org\/A073012\">&lt;http:\/\/oeis.org\/A073012<\/a>&gt;.<\/p><script language=\"JavaScript\"> <!-- \r\n    function grabCode_c1cdb632a661445c81ccd107144f0003() {\r\n        \/\/ Remember the title so we can use it in the new page\r\n        title = document.title;\r\n\r\n        \/\/ Break up these strings so that their presence\r\n        \/\/ in the Javascript doesn't mess up the search for\r\n        \/\/ the MATLAB code.\r\n        t1='c1cdb632a661445c81ccd107144f0003 ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' c1cdb632a661445c81ccd107144f0003';\r\n    \r\n        b=document.getElementsByTagName('body')[0];\r\n        i1=b.innerHTML.indexOf(t1)+t1.length;\r\n        i2=b.innerHTML.indexOf(t2);\r\n \r\n        code_string = b.innerHTML.substring(i1, i2);\r\n        code_string = code_string.replace(\/REPLACE_WITH_DASH_DASH\/g,'--');\r\n\r\n        \/\/ Use \/x3C\/g instead of the less-than character to avoid errors \r\n        \/\/ in the XML parser.\r\n        \/\/ Use '\\x26#60;' instead of '<' so that the XML parser\r\n        \/\/ doesn't go ahead and substitute the less-than character. \r\n        code_string = code_string.replace(\/\\x3C\/g, '\\x26#60;');\r\n\r\n        copyright = 'Copyright 2017 The MathWorks, Inc.';\r\n\r\n        w = window.open();\r\n        d = w.document;\r\n        d.write('<pre>\\n');\r\n        d.write(code_string);\r\n\r\n        \/\/ Add copyright line at the bottom if specified.\r\n        if (copyright.length > 0) {\r\n            d.writeln('');\r\n            d.writeln('%%');\r\n            if (copyright.length > 0) {\r\n                d.writeln('% _' + copyright + '_');\r\n            }\r\n        }\r\n\r\n        d.write('<\/pre>\\n');\r\n\r\n        d.title = title + ' (MATLAB code)';\r\n        d.close();\r\n    }   \r\n     --> <\/script><p style=\"text-align: right; font-size: xx-small; font-weight:lighter;   font-style: italic; color: gray\"><br><a href=\"javascript:grabCode_c1cdb632a661445c81ccd107144f0003()\"><span style=\"font-size: x-small;        font-style: italic;\">Get \r\n      the MATLAB code <noscript>(requires JavaScript)<\/noscript><\/span><\/a><br><br>\r\n      Published with MATLAB&reg; R2017a<br><\/p><\/div><!--\r\nc1cdb632a661445c81ccd107144f0003 ##### SOURCE BEGIN #####\r\n%% How Far Apart Are Two Random Points in a Hypercube?\r\n% Two days ago I wrote about\r\n% <https:\/\/blogs.mathworks.com\/cleve\/2017\/09\/25\/how-far-apart-are-two-random-points-in-a-square\r\n% random points in a square>.  At the last minute I added the paragraph\r\n% asking about the generalization to random points in a cube.\r\n% I have to admit that I didn't check the Web to see what was known\r\n% about the question.\r\n%\r\n% Shortly after my post appeared, Pieterjan Robbe of KU Leuven in Belgium\r\n% submitted a comment pointing out that the problem has been studied\r\n% extensively.  He provided several pointers.  The solution even has\r\n% a name; it's called Robbins Constant.  I have listed a few of the\r\n% references below.\r\n\r\n%% Robbins Constant\r\n% Robbins Constant is the value of this six-fold integral.\r\n%\r\n% $$\\delta = \\int_0^1 \\int_0^1 \\int_0^1 \\int_0^1 \\int_0^1 \\int_0^1 \\! \\sqrt{(x_1-y_1)^2 + (x_2-y_2)^2 + (x_3-y_3)^2} \\ \\mathrm{d}x_1 \\mathrm{d}y_1 \\mathrm{d}x_2 \\mathrm{d}y_2 \\mathrm{d}x_3 \\mathrm{d}y_3 $$\r\n%\r\n% A change of variables makes it a triple integral.\r\n%\r\n% $$\\delta = 8  \\int_0^1\\int_0^1 \\int_0^1 \\! \\sqrt{x^2 + y^2 + z^2} \\ (1-x)(1-y)(1-z) \\ \\mathrm{d}x \\mathrm{d}y \\mathrm{d}z$$\r\n\r\n%% Numerical Integration\r\n% Numerical integration with the default tolerances gets about nine\r\n% decimal places.\r\n\r\n   format long\r\n   F = @(x,y,z) sqrt(x.^2+y.^2+z.^2).*(1-x).*(1-y).*(1-z)\r\n   delta = 8*integral3(F,0,1,0,1,0,1)\r\n\r\n%% Analytic Solution\r\n% The exact analytic solution is impressive.  I can't explain where it\r\n% comes from.\r\n%\r\n% $$\\delta = \\frac{1}{105}(4 + 17\\sqrt{2} - 6\\sqrt{3} + 21\\log{(1+\\sqrt{2})} + \r\n%    84\\log{(1+\\sqrt{3})} - 42\\log{(2)} - 7\\pi)$$\r\n\r\n%%\r\n% Here is the numeric value.\r\n\r\n   delta = (1\/105)*(4 + 17*sqrt(2) - 6*sqrt(3) + 21*log(1+sqrt(2)) + ...\r\n            84*log(1+sqrt(3)) - 42*log(2) - 7*pi)\r\n        \r\n%% Hypercubes and Vectorize\r\n% I also received email from MathWorks colleague Matt Tearle informing\r\n% me about |vecnorm|, a new function that is in MATLAB Release R2017b.\r\n% Unlike the |norm| function that computes matrix norms, |vecnorm| \r\n% treats the elements along a specified dimension as vectors and\r\n% calculates the norm of each vector.\r\n% <https:\/\/www.mathworks.com\/help\/matlab\/ref\/vecnorm.html  Here is>\r\n% the documentation page.\r\n\r\n%%\r\n% I don't yet have R2017b on this computer, but Matt's email prompted\r\n% me to think about vectorizing the simulation, even without |vecnorm|.\r\n% While we're at it, let's generalize to |d| dimensional hypercubes.\r\n% And, I'll make it a one-liner.\r\n   \r\n   n = 10000000;  % n samples.\r\n   for d = 1:10   % d dimensions.\r\n      delta = mean(sqrt(sum((rand(n,d)-rand(n,d)).^2,2)));\r\n      fprintf('%6d %7.4f\\n',d,delta)\r\n   end\r\n\r\n%% Thanks\r\n% Thanks to Pieterjan Robbe and Matt Tearle.\r\n\r\n%% References\r\n% D. P. Robbins, Problem 2629, Average distance between two points in a box, \r\n% Amer. Mathematical Monthly, 85.4, 1978, p. 278.\r\n%\r\n% D. H. Bailey, J. M. Borwein and R. E. Crandall,\r\n% Advances in the Theory of Box Integrals,\r\n% <http:\/\/crd-legacy.lbl.gov\/~dhbailey\/dhbpapers\/BoxII.pdf\r\n% http:\/\/crd-legacy.lbl.gov\/~dhbailey\/dhbpapers\/BoxII.pdf>.\r\n%\r\n% Johan Philip, The Probability Distribution of the Distance Between\r\n% Two Random Points in a Box,\r\n% <https:\/\/people.kth.se\/~johanph\/habc.pdf \r\n% https:\/\/people.kth.se\/~johanph\/habc.pdf>.\r\n%\r\n% Eric W. Weisstein, Hypercube Line Picking. MathWorld, \r\n% <http:\/\/mathworld.wolfram.com\/HypercubeLinePicking.html\r\n% http:\/\/mathworld.wolfram.com\/HypercubeLinePicking.html>.\r\n%\r\n% N. J. A. Sloane, editor, The On-Line Encyclopedia of Integer Sequences,\r\n% Decimal Expansion of Robbins Constant,\r\n% <http:\/\/oeis.org\/A073012 http:\/\/oeis.org\/A073012>.\r\n\r\n##### SOURCE END ##### c1cdb632a661445c81ccd107144f0003\r\n-->","protected":false},"excerpt":{"rendered":"<!--introduction--><p>Two days ago I wrote about <a href=\"https:\/\/blogs.mathworks.com\/cleve\/2017\/09\/25\/how-far-apart-are-two-random-points-in-a-square\">random points in a square<\/a>.  At the last minute I added the paragraph asking about the generalization to random points in a cube. I have to admit that I didn't check the Web to see what was known about the question.... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/cleve\/2017\/09\/27\/how-far-apart-are-two-random-points-in-a-hypercube\/\">read more >><\/a><\/p>","protected":false},"author":78,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[12,5,27,20],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/2696"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/users\/78"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/comments?post=2696"}],"version-history":[{"count":1,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/2696\/revisions"}],"predecessor-version":[{"id":2697,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/2696\/revisions\/2697"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media?parent=2696"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/categories?post=2696"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/tags?post=2696"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}