预期的成对方形欧几里德点之间的距离 -- probability-theory 领域 和 randomized-algorithms 领域 和 euclidean-distance 领域 cs 相关 的问题

expected pairwise square euclidean distance between points


简体版||繁體版
3
vote

问题

中文

如何显示 $ x $ $θ(d)之间的预期成对方形欧几里德距离$

其中 $ x $ $(x_1,... x_n)$ 生成的点在单位中随机均匀,d是D维立方体, $ x =(x(1),... x(d))$ 泛型点其-th组件 $ x(i)$ $ [0,1] $ 中统一地选择独立于其他组件和点。

$ theta(d)$ 表示最大可能的距离是d。

我试图向Bertrand Paradox打造这个问题,但我不认为是对的。也许这表明 $ e(|| x-y || 2)=θ(d)$ ,因为是一个提示,但我不知道如何。

im跟随这条路径: https://stats.stackexchange.com/questions/22488/probability-that-uniformly-random-points-in-a-rectangle-have-euclidean-distance

但与我的观点不同。

谢谢。

英文原文

How can I show that the expected pairwise square euclidean distance between points in $X$ is $xcex98(d)$?

Where $X$ is a $(x_1,...x_n)$ of points generated uniformly at random in the unit, d is d-dimensional cube , $x=(x(1),...x(d))$ the generic point has its -th component $x(i)$ chosen uniformly at random in$ [0,1] $independently of other components and points.

$\Theta(d)$ represent the largest possible distance is d.

I try to reconduct this problem to Bertrand Paradox but i dont think is right. Maybe I that show that $E(||xxe2x88x92y||2)=xcex98(d)$ , because is a hint but i dont know how.

i m following this path: https://stats.stackexchange.com/questions/22488/probability-that-uniformly-random-points-in-a-rectangle-have-euclidean-distance

but is different to my point.

Thanks.

        
 
 

回答列表

1
 
vote
vote
最佳答案
 

let $ vec {x}, vec {y} $ 是两个随机 $ d $ $ [0,1] ^ d $ 均匀地选择的等级矢量。也就是说, $ x_1, ldots,x_d,y_1, ldots,y_d $ 都是均匀分布的均匀随机样本,而不是 $ [0,1] $ 。然后 $$ mathbb {e} [ | vec {x} - vec {y} | ^ 2] = mathbb {e} left [ sum_ {i = 1} ^ d(x_i-y_i)^ 2 light] = sum_ {i = 1} ^ d mathbb {e} [(x_i-y_i)] ^ 2 = d operatorname * { mathbb {e}} _ {x,y sim [0,1]} [(x-y)^ 2]。 $$ $ c = mathbb {e} [(x-y)^ 2] $ 。然后在 $ [0,1] ^ d $ $ cd $ 中的预期平方距离。

明确计算 $ c $ 显式: $$ c = mathbb {e} [((x-1/2) - (y-1/2))^ 2] = mathbb {e} [(x-1/2)^ 2] + 2 mathbb {e} [(x-1/2)(y-1/2)] + mathbb {e} [(y-1 / 2)^ 2] = \ 2 mathbb {e} [(x-1/2)^ 2] + 2 mathbb {e} [x-1/2] mathbb {e} [y-1/2] = 2 mathbb {e} [(x-1/2)^ 2] = \ 2 int_0 ^ 1(x-1/2)^ 2 ,dx = 2 int_0 ^ 1 x ^ 2-x + frac {1} {4} ,dx = 2 left( frac {1} {3} - frac {1} {2} + frac {1} {4} 右)= frac {1} {6}。 $$

 

Let $\vec{x},\vec{y}$ be two random $d$-dimensional vectors chosen uniformly and independently from $[0,1]^d$. That is, $x_1,\ldots,x_d,y_1,\ldots,y_d$ are all uniform random samples of the uniform distribution over $[0,1]$. Then $$ \mathbb{E}[\|\vec{x}-\vec{y}\|^2] = \mathbb{E}\left[\sum_{i=1}^d (x_i-y_i)^2\right] = \sum_{i=1}^d \mathbb{E}[(x_i-y_i)]^2 = d \operatorname*{\mathbb{E}}_{x,y \sim [0,1]} [(x-y)^2]. $$ Let $C = \mathbb{E}[(x-y)^2]$. Then the expected squared distance of two points in $[0,1]^d$ is $Cd$.

It is not hard to calculate $C$ explicitly: $$ C = \mathbb{E}[((x-1/2) - (y-1/2))^2] = \mathbb{E}[(x-1/2)^2] + 2\mathbb{E}[(x-1/2)(y-1/2)] + \mathbb{E}[(y-1/2)^2] = \\ 2\mathbb{E}[(x-1/2)^2] + 2\mathbb{E}[x-1/2] \mathbb{E}[y-1/2] = 2\mathbb{E}[(x-1/2)^2] = \\ 2\int_0^1 (x-1/2)^2 \, dx = 2\int_0^1 x^2-x+\frac{1}{4} \, dx = 2\left(\frac{1}{3} - \frac{1}{2} + \frac{1}{4}\right) = \frac{1}{6}. $$

 
 
         
         

相关问题

3  预期的成对方形欧几里德点之间的距离  ( Expected pairwise square euclidean distance between points ) 
如何显示 $ x $ 是 $θ(d)之间的预期成对方形欧几里德距离$ ? 其中 $ x $ 是 $(x_1,... x_n)$ 生成的点在单位中随机均匀,d是D维立方体, $ x =(x(1),... x(d))$ 泛型点其-th组件 $ x(i)$ 在 $ [0,1] $ 中统一地选择独立于其他组件和点。 $...

3  最接近的对有多快?  ( How fast is closest pair ) 
我正在阅读最近的论文"在副时期在副时期的相关性,以应用程序到学习间隔和最接近的对问题" ,Gregory Valiant在$ R ^ D $中查找近似最接近的对。勇敢说这个问题的当前上限是$ o(n ^ 2)$。 然而,在维基百科上,据说2D划分和征服算法可以推广以满足任意数量的尺寸为$ O(n text {log...

2  给定遍历路径的最佳项目位置  ( Optimal item locations given traversal paths ) 
我具有与(已知)距离关联的给定的完全连接的无向图,或者距离矩阵,其中节点或矩阵行/列代表位置。 此外,我有许多项目小或等于位置的数量,以及物品的有限数量的遍历路径。 遍历路径是固定顺序,其中通过通过项目被放置的位置来传递项目。通过在不同位置之间添加遍历距离来计算遍历时间/遍历距离通过传递。此外,所有遍历路径都在同一位...

1  网格上的点之间的总距离,时间复杂性低于$ O(n ^ 2)$  ( Total distance between points on a grid with time complexity lower than on2 ) 
我有$ n $ points,形成一个带空白的网格,我需要找到一个算法,该算法将计算那些点的总距离,时间复杂性低于$ O(n ^ 2)$。 以$ n = 5 $的网格的示例将是以下一组点: $(1,0)$,$(0,1)$,$(2,0)$,$(2,1)$,$(2,2)$。正如您所看到的$ x $,$ y $坐标只能具有...

2  “孤独的点”算法  ( Loneliest point algorithm ) 
问题: 我正在寻找一个算法,可以找到set $ r $ 和另一个set $ s subseteq r $ 。 具体地,给定有限一组点 $ s $ 在 $ n $ -dimensional空间,让 $ r $ 是 $ s $ 的最小边界框(所以跨越界限的产品方面)。我对此类型的集合 $ r $ ,目前,我只...

2  可以仅使用XOR的eUCLIDEAN距离功能来计算  ( Can the euclidean distance function be computed using only xors ) 
eulidean距离函数$ d $ of $ x $,$ y $给出: $ D(x,y)= sqrt {x ^ 2-y ^ 2} $ 让我们假设$ x $和$ y $是固定点号,或$ x,y $是某些子字段$ f_n $的元素$ f_p $。我们甚至可以假设$ x,y $有精确的$ n $十进制数字。任何促进...

0  聚类非重叠时间序列  ( Clustering non overlapping time series ) 
我有数千次不同的不同长度和不同的时间。我想将它们分组,以便我知道最佳选择作为ML算法的输入并记录它们是相关的。那些时间系列来自车站,其中一些是非活动的,有些仍然活跃。 我的目标最终是使用集群中的活动站中的数据,以便通过假设信号的相关性在时间保持相同的情况下来模拟非活动状态。 我能够获得欧几里德距离和距离矩阵(用于DT...

1  二元定点垂钓 - 距离计算浮点欧几里德距离计算的计算复杂性比较  ( Computational complexity comparison of floating point euclidean distance calcula ) 
这可能与不同的应用有关,但我的感兴趣的应用是基于高维特征向量的相似性搜索系统。在这些系统中,由于基于欧几里德距离的搜索成本高,因此矢量被编码为二进制矢量。然后,搜索是基于汉明距离计算完成的,该计算应该比欧几里德对应物更快。我的问题是几乎,这个速度为普通架构多少? 更正式,假设我们有一个数据库$ mathrm {x...

3  如何防止欧几里德距离和马哈拉诺比斯距离中的溢出和下溢  ( How to prevent overflow and underflow in the euclidean distance and mahalanobis ) 
我在我的项目中工作时,当我是必要的问题,或者至少谨慎,防止在计算这两个距离的计算中的溢出和下溢。 我记得有一个实施斜边的计算来防止这种情况。大多数语言实现者,并且以 showot 而闻名 欧几里德距离的计算保持相同的"模式" ,我认为如果 99887665544330 控制溢出和下溢也应该注意欧几里德距离。我很失望...

3  从高维凸壳到目标点T的距离  ( Distance from high dimensional convex hull to target point t ) 
我在欧几里德空间中具有高尺寸点,具有凸壳H(未知);而在那个空间中的某些目标点t在h中或在h上。 而不是担心明确计算h和与它的距离,是有效的方式来计算从t到h最近点的距离?我在思考一些涉及与吐痰飞机的二元空间分区的东西,但不能弄清楚如何制定方法(尤其是选择哪个飞机)。 ...

2  找到欧几里德飞机上的点列表到给定的参考点  ( Finding nearest of a list of points on euclidian plane to a given reference poin ) 
<强>问题制剂:的给定一个列表$ L $ $ N $在欧几里得平面和参考点$ R $还在于平面上的点,找到最近点$ P 以L $这样,对于所有$ x in l $,$ | pr | le | xr | $。 <强> aditional的约束:平凡算法只会迭代所有候选中$ L $分,计算其到$ R $距离,并选...

1  修改4个点的错误成对距离以获得共面  ( Modifying the erroneous pairwise distances of 4 points to get coplanarity ) 
考虑四点 $ i,j,k,l $ <$ <$ 他们的成对欧几里德距离 $ d(ij)$ $ d(ik)$ $ d(il)$ $ d(jk)$ $ d(jl)$ $ d(kl)$ 说,我们知道点数$ j $,$ k $和$ l $的坐标。 但是,我们不知道$ i $的地方,与$ i $的测量距离是错误的,...

0  结合多个*搜索的最佳方法是什么?  ( Whats the best way to combine multiple a searches ) 
我有一个看起来像这样的图表 必须访问突出显示节点,并且必须访问蓝色节点,Stickman必须是路径的开始。权重是每个节点之间的欧几里德距离。 我想使用*搜索每个单独的节点,然后是*搜索以找到下一个节点的路径,以及下一个等,直到达到蓝节点。 解决我应该访问每个节点的最佳方法是什么? 如果你注意到,最接近的粉红色节...

2  马哈拉诺比斯点到平面算法的距离  ( Mahalanobis distance of point to plane algorithm ) 
我试图了解来自这个 paper 。算法如下所示: 计算点的协方差 $ s_ {uu} $ 使用SVD将白化变换应用于协方差矩阵,其中<跨度 class="math-container" > $ s_ {uu} = rvr ^ t $ 。 $ r $ 是旋转矩阵和 $ v $ 是scale $ v = dia...

2  欧几里德飞机的部分TSP  ( Partial tsp in euclidian plane ) 
我对旅行推销员问题的以下变种有人感兴趣,有时称为部分tsp 。我对欧几里德版本的父母很常见: 输入:一个设置$ {x_1, dots,x_n } subset mathbb {r} ^ 2 $ $ n $ points在平面中,一个整数$ k Le N $。 输出:游览$ k $ point $ x_ {...

0  算法的方法,以在许多类似对象的列表中查找最近的3-D对象到给定的测试用例  ( Approach for algorithm to find closest 3 d object in a list of many similar obje ) 
让我们说我有许多(数千千万千万)对象的列表,每个对象的每个对象都有一个给定的3-d顶点(我的当前实现使用每个8个顶点,但如果可以减少这个数字它会导致性能增加非常显着)。这些顶点当前从0-255存储为浮点数,但如果需要,也可以改变该范围,假设它不会过于急剧降低精度。此外,我可以将这些对象存储在任何数据结构中,这些对象对...

2  均匀地分割一组飞机上并将其分类  ( Splitting a set of points in the plane evenly and sorting it ) 
输入:一组点P(x,y)。它有两个版本的IT - PX,按x和py排序,按y排序。 输出:px的两个偶数半数,按y排序。 这里的诀窍是它必须在线性时间工作,否则,它是相当毫无用的。到目前为止,我提出的是找到px的中点,让我们称之为px [mid],然后通过py迭代,检查每个点的x坐标是否大于px [mid],然后...

2  近似算法访问无向加权,完整图中的所有节点,具有最短的边缘权重和  ( Approximation algorithm to visit all nodes in an undirected weighted complete ) 
我正在寻找一种在以下约束中提供最小值'旅行成本'的算法: 一个完整的,连接的加权图, 顶点在3D欧几里德空间中定义, 顶点数量相对较少(小于500) 没有限制可以访问节点的次数 一个固定的起始顶点 无要求顶点结束。 我已经看过最小的生成树算法,但这些可能会产生次擎子,因为它们可以针对最低总和的边缘重量进行优化。 ...

10  从带有点距离加权的边缘恢复从图形嵌入的点  ( Recovering a point embedding from a graph with edges weighted by point distance ) 
假设我向您提供具有加权边的无向图,并告诉您每个节点对应于3D空间中的一个点。每当两个节点之间的边缘时,边缘的权重是点之间的距离。 您的目标是重建点的相对位置,仅给出可用距离(由边缘权重表示)。例如,如果我给了你 $ d_ {0,1} = d_ {0,2} = d_ {0,3} = d_ {1,2} = d_ {1, ...

2  如何将Pearson距离嵌入欧几里德空间  ( How to embed pearson distance into euclidean space ) 
我有很多数值矢量,每个维度1000。我想根据他们的 Pearson距离。这适用,但是将所有载体彼此进行比较是二次时间和太慢。理想情况下,我希望能够执行有效的近似邻居搜索。 如果我可以将向量嵌入到欧几里德空间中,那么我可以使用标准工具来执行此操作。 有没有办法将使用Pearson距离从空间嵌入向欧几里德空间的空间中...

5  如何根据段的长度检测相交的段  ( How to detect intersecting segments based on length of the segments ) 
作为更大问题的一部分,我试图基于距离矩阵来检测哪些段在发起矩阵的原始2D空间中交叉。我没有坐标(lat / long,x / y或任何其他点)。 作为一个例子,在下面的图像上,顶部图的问题的答案是:广告,BC。虽然对于底部图,是AC,BD。 我们拥有的信息只是距离矩阵: 距离矩阵顶部 $ begin {align...

3  是否应该平面欧几里德图是平面的直线图?  ( Should planar euclidean graphs be planar straight line graphs ) 
一个 euclidean图,定义 权重等于欧几里德的加权图 指定嵌入中的边缘的长度 和图形称为平面为 可以在没有图形边缘的平面中绘制 最后,a 平面直线图(pslg) 嵌入平面中的平面图,使得其边缘被映射成直线段。 通过这三个定义,我不能得出结论,如果欧几里德平面图应该是pslg。 例如,给定欧几里德...

0  将一组点缩小到较小的区域  ( Scaling down a set of points into a smaller area ) 
可见性图 $ g(p)=(v,e)$ set $ p = { P_1, dots,p_n } $ 点的定义如下。 每个顶点 $ u v $ ,对应于p点 $ p_u 以p $ 。 在e $ 中存在边缘 $ uv 如果行段 $ overline {p_up_v $ 不包含 $ p $ 中的任何其他点。 假...

3  高效算法来实现一组坐标约束  ( Efficient algorithm to fulfil a set of coordinate constraints ) 
我有一组标记点和一组点之间的一组点,由较低和上距离组成。肯定会有3D空间中的点排列,满足所有距离约束。 我希望生成满足所有约束的点的安排。只要每个布置独立地从其他布置产生任何方法就可以允许任何方法。 哪些算法最适合?主要在效率方面。 作为扩展,我将如何包含三个点定义的角度的约束?并且在四点限定的二偏角角度(点ABCD...

3  算法以适应3D空间中的点  ( Algorithm to mimimally pair up points in 3d space ) 
给出了一套$ n $ point $ p $和一套$ n $ point $ q $ 3维数空间,什么是最快的算法在$ p $以$ q $以$ p $以$ q $为单位$ P $的点之间的距离的平方和$ q $之间的相应点之间的距离是最小化的? $ p $的每个点必须与$ q $只有一个,反之亦然。 查看问题的另一...

相关问题

3  预期的成对方形欧几里德点之间的距离 
3  最接近的对有多快? 
2  给定遍历路径的最佳项目位置 
1  网格上的点之间的总距离,时间复杂性低于$ O(n ^ 2)$ 
2  “孤独的点”算法 
2  可以仅使用XOR的eUCLIDEAN距离功能来计算 
0  聚类非重叠时间序列 
1  二元定点垂钓 - 距离计算浮点欧几里德距离计算的计算复杂性比较 
3  如何防止欧几里德距离和马哈拉诺比斯距离中的溢出和下溢 
3  从高维凸壳到目标点T的距离 
2  找到欧几里德飞机上的点列表到给定的参考点 
1  修改4个点的错误成对距离以获得共面 
0  结合多个*搜索的最佳方法是什么? 
2  马哈拉诺比斯点到平面算法的距离 
2  欧几里德飞机的部分TSP 
0  算法的方法,以在许多类似对象的列表中查找最近的3-D对象到给定的测试用例 
2  均匀地分割一组飞机上并将其分类 
2  近似算法访问无向加权,完整图中的所有节点,具有最短的边缘权重和 
10  从带有点距离加权的边缘恢复从图形嵌入的点 
2  如何将Pearson距离嵌入欧几里德空间 
5  如何根据段的长度检测相交的段 
3  是否应该平面欧几里德图是平面的直线图? 
0  将一组点缩小到较小的区域 
3  高效算法来实现一组坐标约束 
3  算法以适应3D空间中的点 



© 2021 it.wenda123.org All Rights Reserved. 问答之家 版权所有