Expected distance between two points with missing coordinates - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T22:09:38Z http://mathoverflow.net/feeds/question/23404 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/23404/expected-distance-between-two-points-with-missing-coordinates Expected distance between two points with missing coordinates Frank 2010-05-04T04:57:21Z 2010-05-06T14:19:50Z <p>What is the expected distance between two points when one of the points has some unknown (or missing) coordinate values?</p> <p>The two points are in the same finite dimensional real space. Assume that the probability density function that describes the missing coordinates varies uniformly between $[-1,1]$.</p> <p>Here is an <a href="http://www.datafilehost.com/download-5248e1e6.html" rel="nofollow">Adobe PDF file </a> showing the solution for a point that has either one or two unknown coordinate values. I would appreciate any information leading to a solution for the general case of $m$ missing coordinates, or useful lower and upper bounds for the expected distance between these two points.</p> http://mathoverflow.net/questions/23404/expected-distance-between-two-points-with-missing-coordinates/23715#23715 Answer by Willie Wong for Expected distance between two points with missing coordinates Willie Wong 2010-05-06T14:19:50Z 2010-05-06T14:19:50Z <p>You can rephrase your question as follows: first we subtract the known vector from both and then take care of the known coordinates. So assuming the coordinates of the two points are $(\alpha,\beta)$ and $(\gamma,X)$ where $\alpha,\gamma \in \mathbb{R}^m$ are known, and $\beta \in \mathbb{R}^n$ is known, but $X$ represent the unknown coordinates constrainted to lie inside the cube $[-1,1]^n$, the integral to evaluate becomes $$\frac{1}{2^n}\int_{[-1,1]^n} \sqrt{ |\alpha-\gamma|^2 + |\beta - X|^2 } dX$$ In the lower dimensional case this can be integrated. But an analytical expression in higher dimensions is elusive. For the case $\alpha = \gamma$ and $\beta = 0$, some bounds were obtained in an old paper of Anderssen et al. <a href="http://dx.doi.org/10.1137/0130003" rel="nofollow">http://dx.doi.org/10.1137/0130003</a> For more general probability distributions there is a recent paper with some bounds by Burgstaller and Pillichshammer. <a href="http://journals.cambridge.org/action/displayAbstract?aid=6622208" rel="nofollow">http://journals.cambridge.org/action/displayAbstract?aid=6622208</a></p> <p>Of course, one can get a fairly trivial bound by Cauchy-Schwartz $$\int_{[-1,1]^n} f(X) dX \leq 2^{n/2} \left( \int_{[-1,1]^n} f(X)^2 dX \right)^{1/2}$$ and that $$\int_{[-1,1]^n} R^2 + |\beta - X|^2 dX = 2^n (R^2 + \beta^2) + \int_{[-1,1]^n} X^2 dX$$ the last term is simply evaluated as $n 2^n / 3$, so putting it all together we have the upper bound for the expected value by $$\frac{1}{2^n}\int_{[-1,1]^n} \sqrt{ |\alpha-\gamma|^2 + |\beta - X|^2 } dX \leq \sqrt{ |\alpha -\gamma|^2 + \beta^2 + \frac{n}{3}}$$ which is slight improvement over the utterly trivial upper/lower bound of $\sqrt{|\alpha-\gamma|^2 + \beta^2 \pm n}$ if you just maximize/minimize each coordinates. </p>