{"id":2680,"date":"2017-09-25T14:32:55","date_gmt":"2017-09-25T19:32:55","guid":{"rendered":"https:\/\/blogs.mathworks.com\/cleve\/?p=2680"},"modified":"2017-09-27T18:07:31","modified_gmt":"2017-09-27T23:07:31","slug":"how-far-apart-are-two-random-points-in-a-square","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/cleve\/2017\/09\/25\/how-far-apart-are-two-random-points-in-a-square\/","title":{"rendered":"How Far Apart Are Two Random Points in a Square?"},"content":{"rendered":"<div class=\"content\"><!--introduction--><p>How far apart can you expect two points chosen at random in the unit square to be? I found this problem on the YouTube channel maintained by Presh Talwalkar, <a href=\"https:\/\/www.youtube.com\/user\/MindYourDecisions\">Mind Your Decisions<\/a>. He correctly calls it <a href=\"https:\/\/www.youtube.com\/watch?v=i4VqXRRXi68&amp;t=7s\">a very hard puzzle<\/a>. At first, I guessed the answer might be $1\/2$.  But the correct answer is more interesting than that.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/talwalkar.gif\" alt=\"\"> <\/p><!--\/introduction--><h3>Contents<\/h3><div><ul><li><a href=\"#958806d3-c60e-4ccb-99a0-71fb75db450a\">Simulation<\/a><\/li><li><a href=\"#7f84f8db-ebe3-4d3b-b83b-68700d4b0cd4\">Quadruple Integral<\/a><\/li><li><a href=\"#d8db45ec-7473-4dce-ae79-46c84646e295\">Double Integral<\/a><\/li><li><a href=\"#80a4d97d-ee99-450f-8e14-9caa4339c565\">Numerical Integration<\/a><\/li><li><a href=\"#0506fe87-e445-4130-b84c-d517eff4b4cb\">Polar Coordinates<\/a><\/li><li><a href=\"#382b8666-b407-4db4-bb78-d9a42b776205\">Symbolic Integration<\/a><\/li><li><a href=\"#6684ceba-784f-479e-a22c-f77bbf8fb547\">Numerical value<\/a><\/li><li><a href=\"#abdaf50a-e6db-4d97-ba88-350626def598\">This Is My Final Answer<\/a><\/li><li><a href=\"#f33edbf6-303a-4053-b4dc-c18618ecd8d6\">Three Dimensions<\/a><\/li><li><a href=\"#5fa25f44-1c89-446e-97f0-02c91729fbcf\">Thanks<\/a><\/li><\/ul><\/div><h4>Simulation<a name=\"958806d3-c60e-4ccb-99a0-71fb75db450a\"><\/a><\/h4><p>Let's do a Monte Carlo simulation to get a numerical estimate. Sampling one million pairs of points doesn't take much time.<\/p><pre class=\"codeinput\">   n = 1000000;\r\n   sum = 0;\r\n   rng(0)\r\n   <span class=\"keyword\">for<\/span> k = 1:n\r\n       x = rand(1,2);\r\n       y = rand(1,2);\r\n       delta = norm(x-y);\r\n       sum = sum + delta;\r\n   <span class=\"keyword\">end<\/span>\r\n   format <span class=\"string\">short<\/span>\r\n   delta = sum\/n\r\n<\/pre><pre class=\"codeoutput\">delta =\r\n    0.5214\r\n<\/pre><p>It turns out that this run of the simulation generates a result that is accurate to  the four digit precision of <tt>format short<\/tt>. But can we find the exact value?<\/p><h4>Quadruple Integral<a name=\"7f84f8db-ebe3-4d3b-b83b-68700d4b0cd4\"><\/a><\/h4><p>The expected distance, $\\delta$, can be expressed as this quadruple integral, but the Symbolic Toolbox cannot find a closed form.<\/p><p>$$\\delta = \\int_0^1 \\int_0^1 \\int_0^1 \\int_0^1 \\! \\sqrt{(x_1-y_1)^2 + (x_2-y_2)^2} \\ \\mathrm{d}x_1 \\mathrm{d}y_1 \\mathrm{d}x_2 \\mathrm{d}y_2$$<\/p><h4>Double Integral<a name=\"d8db45ec-7473-4dce-ae79-46c84646e295\"><\/a><\/h4><p>Make the substitutions $x = x_1 - y_1$ and $y = x_2 - y_2$ and consider the integral over the four regions where these variables are positive or negative.  The four integrals are equal to each other and we obtain this double integral.<\/p><p>$$\\delta = 4 \\int_0^1 \\int_0^1 \\! \\sqrt{x^2 + y^2} \\ (1-x)(1-y) \\ \\mathrm{d}x \\mathrm{d}y$$<\/p><h4>Numerical Integration<a name=\"80a4d97d-ee99-450f-8e14-9caa4339c565\"><\/a><\/h4><p>Let's tackle this double integral numerically.<\/p><pre class=\"codeinput\">   F = @(x,y) 4*sqrt(x.^2+y.^2).*(1-x).*(1-y);\r\n   delta = integral2(F,0,1,0,1)\r\n<\/pre><pre class=\"codeoutput\">delta =\r\n    0.5214\r\n<\/pre><h4>Polar Coordinates<a name=\"0506fe87-e445-4130-b84c-d517eff4b4cb\"><\/a><\/h4><p>Switch to polar coordinates, $r$ and $\\theta$.  The $\\sqrt{x^2+y^2}$ term is simply $r$ and the double integral has two equal halves about the $45^o$ line, $\\theta = \\pi\/4$.<\/p><p>$$\\delta\/8 = \\int_0^{\\pi\/4} \\int_0^{\\sec{\\theta}} r (1-r\\cos{\\theta}) (1-r\\sin{\\theta}) \\ r \\mathrm{d}r \\mathrm{d}\\theta$$<\/p><h4>Symbolic Integration<a name=\"382b8666-b407-4db4-bb78-d9a42b776205\"><\/a><\/h4><p>The integrand is a polynomial in $r$.<\/p><pre class=\"codeinput\">   syms <span class=\"string\">r<\/span> <span class=\"string\">theta<\/span> <span class=\"string\">real<\/span>\r\n   F = expand(r^2*(1-r*cos(theta))*(1-r*sin(theta)))\r\n<\/pre><pre class=\"codeoutput\">F =\r\nr^2 - r^3*sin(theta) - r^3*cos(theta) + r^4*cos(theta)*sin(theta)\r\n<\/pre><p>The Toolbox can integrate this polynomial easily.<\/p><pre class=\"codeinput\">   inner = int(F,r,0,sec(theta))\r\n<\/pre><pre class=\"codeoutput\">inner =\r\n1\/(12*cos(theta)^3) - sin(theta)\/(20*cos(theta)^4)\r\n<\/pre><p>The Toolbox can also do the outer integral over $\\theta$.<\/p><pre class=\"codeinput\">   outer = int(inner,theta,0,pi\/4)\r\n<\/pre><pre class=\"codeoutput\">outer =\r\nlog(2^(1\/2) + 1)\/24 + 2^(1\/2)\/120 + 1\/60\r\n<\/pre><p>Multiply by 8.<\/p><pre class=\"codeinput\">   delta = 8*outer\r\n<\/pre><pre class=\"codeoutput\">delta =\r\nlog(2^(1\/2) + 1)\/3 + 2^(1\/2)\/15 + 2\/15\r\n<\/pre><p>Generate a <tt>latex<\/tt> representation for $\\delta$ to cut and paste later into this post.<\/p><pre class=\"codeinput\">   latex(delta);\r\n<\/pre><h4>Numerical value<a name=\"6684ceba-784f-479e-a22c-f77bbf8fb547\"><\/a><\/h4><pre class=\"codeinput\">   format <span class=\"string\">long<\/span>\r\n   delta = double(delta)\r\n<\/pre><pre class=\"codeoutput\">delta =\r\n   0.521405433164721\r\n<\/pre><h4>This Is My Final Answer<a name=\"abdaf50a-e6db-4d97-ba88-350626def598\"><\/a><\/h4><p>Here is the result.<\/p><p>$$\\delta =\r\n\\frac{\\ln\\left(\\sqrt{2}+1\\right)}{3}+\\frac{\\sqrt{2}}{15}+\\frac{2}{15}$$<\/p><h4>Three Dimensions<a name=\"f33edbf6-303a-4053-b4dc-c18618ecd8d6\"><\/a><\/h4><p>What about three dimensions? How far apart can you expect two points chosen at random in the unit cube to be? I'll leave that as a challenge and invite anyone who thinks they know the answer to post a comment.<\/p><h4>Thanks<a name=\"5fa25f44-1c89-446e-97f0-02c91729fbcf\"><\/a><\/h4><p>Thanks to Presh Talwalkar for this little nugget.<\/p><script language=\"JavaScript\"> <!-- \r\n    function grabCode_4605bcb308bf4a25bc7dcabdf3c3a242() {\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='4605bcb308bf4a25bc7dcabdf3c3a242 ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 4605bcb308bf4a25bc7dcabdf3c3a242';\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_4605bcb308bf4a25bc7dcabdf3c3a242()\"><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\n4605bcb308bf4a25bc7dcabdf3c3a242 ##### SOURCE BEGIN #####\r\n%% How Far Apart Are Two Random Points in a Square?\r\n% How far apart can you expect two points chosen at random in the unit\r\n% square to be?\r\n% I found this problem on the YouTube channel maintained by \r\n% Presh Talwalkar, <https:\/\/www.youtube.com\/user\/MindYourDecisions\r\n% Mind Your Decisions>.\r\n% He correctly calls it <https:\/\/www.youtube.com\/watch?v=i4VqXRRXi68&t=7s\r\n% a very hard puzzle>.\r\n% At first, I guessed the answer might be $1\/2$.  But the correct\r\n% answer is more interesting than that.\r\n%\r\n% <<talwalkar.gif>>\r\n\r\n%% Simulation\r\n% Let's do a Monte Carlo simulation to get a numerical estimate.\r\n% Sampling one million pairs of points doesn't take much time.\r\n \r\n   n = 1000000;\r\n   sum = 0;\r\n   rng(0)\r\n   for k = 1:n\r\n       x = rand(1,2);\r\n       y = rand(1,2);\r\n       delta = norm(x-y);\r\n       sum = sum + delta;\r\n   end\r\n   format short\r\n   delta = sum\/n\r\n   \r\n%%\r\n% It turns out that this run of the simulation generates a result\r\n% that is accurate to  the four digit precision of |format short|.\r\n% But can we find the exact value?\r\n\r\n%% Quadruple Integral\r\n% The expected distance, $\\delta$, can be expressed as this quadruple\r\n% integral, but the Symbolic Toolbox cannot find a closed form. \r\n%\r\n% $$\\delta = \\int_0^1 \\int_0^1 \\int_0^1 \\int_0^1 \\! \\sqrt{(x_1-y_1)^2 + (x_2-y_2)^2} \\ \\mathrm{d}x_1 \\mathrm{d}y_1 \\mathrm{d}x_2 \\mathrm{d}y_2$$\r\n\r\n%% Double Integral\r\n% Make the substitutions $x = x_1 - y_1$ and $y = x_2 - y_2$ and consider\r\n% the integral over the four regions where these variables are positive\r\n% or negative.  The four integrals are equal to each other and we obtain\r\n% this double integral.\r\n%\r\n% $$\\delta = 4 \\int_0^1 \\int_0^1 \\! \\sqrt{x^2 + y^2} \\ (1-x)(1-y) \\ \\mathrm{d}x \\mathrm{d}y$$\r\n\r\n%% Numerical Integration\r\n% Let's tackle this double integral numerically.\r\n\r\n   F = @(x,y) 4*sqrt(x.^2+y.^2).*(1-x).*(1-y);\r\n   delta = integral2(F,0,1,0,1)\r\n\r\n%% Polar Coordinates\r\n% Switch to polar coordinates, $r$ and $\\theta$.  The $\\sqrt{x^2+y^2}$\r\n% term is simply $r$ and the double integral has two equal halves about\r\n% the $45^o$ line, $\\theta = \\pi\/4$.\r\n%\r\n% $$\\delta\/8 = \\int_0^{\\pi\/4} \\int_0^{\\sec{\\theta}} r (1-r\\cos{\\theta}) (1-r\\sin{\\theta}) \\ r \\mathrm{d}r \\mathrm{d}\\theta$$\r\n\r\n%% Symbolic Integration\r\n% The integrand is a polynomial in $r$.\r\n\r\n   syms r theta real\r\n   F = expand(r^2*(1-r*cos(theta))*(1-r*sin(theta)))\r\n   \r\n%%\r\n% The Toolbox can integrate this polynomial easily.\r\n\r\n   inner = int(F,r,0,sec(theta))\r\n      \r\n%%\r\n% The Toolbox can also do the outer integral over $\\theta$.\r\n\r\n   outer = int(inner,theta,0,pi\/4)\r\n   \r\n%%\r\n% Multiply by 8.\r\n\r\n   delta = 8*outer\r\n   \r\n%%\r\n% Generate a |latex| representation for $\\delta$ to cut and paste later\r\n% into this post.\r\n\r\n   latex(delta);\r\n   \r\n%% Numerical value\r\n\r\n   format long\r\n   delta = double(delta) \r\n   \r\n%% This Is My Final Answer\r\n% Here is the result.\r\n%\r\n% $$\\delta =\r\n% \\frac{\\ln\\left(\\sqrt{2}+1\\right)}{3}+\\frac{\\sqrt{2}}{15}+\\frac{2}{15}$$\r\n\r\n%% Three Dimensions\r\n% What about three dimensions?  \r\n% How far apart can you expect two points chosen at random in the unit\r\n% cube to be?\r\n% I'll leave that as a challenge and invite anyone who thinks they know\r\n% the answer to post a comment.\r\n\r\n\r\n%% Thanks\r\n% Thanks to Presh Talwalkar for this little nugget.\r\n\r\n\r\n##### SOURCE END ##### 4605bcb308bf4a25bc7dcabdf3c3a242\r\n-->","protected":false},"excerpt":{"rendered":"<div class=\"overview-image\"><img decoding=\"async\"  class=\"img-responsive\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/talwalkar.gif\" onError=\"this.style.display ='none';\" \/><\/div><!--introduction--><p>How far apart can you expect two points chosen at random in the unit square to be? I found this problem on the YouTube channel maintained by Presh Talwalkar, <a href=\"https:\/\/www.youtube.com\/user\/MindYourDecisions\">Mind Your Decisions<\/a>. He correctly calls it <a href=\"https:\/\/www.youtube.com\/watch?v=i4VqXRRXi68&amp;t=7s\">a very hard puzzle<\/a>. At first, I guessed the answer might be $1\/2$.  But the correct answer is more interesting than that.... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/cleve\/2017\/09\/25\/how-far-apart-are-two-random-points-in-a-square\/\">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,26,20],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/2680"}],"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=2680"}],"version-history":[{"count":1,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/2680\/revisions"}],"predecessor-version":[{"id":2681,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/2680\/revisions\/2681"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media?parent=2680"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/categories?post=2680"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/tags?post=2680"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}