For sufficiently large d, with high probability the distances between all pairs of points will be essentially the same
Answers
Answered by
0
Let Z2i=(xi−yi)2. We have that Z2i/2follows χ2(1) distribution and thusE(Z2i)=2andVar(Z2i)=8Therefore,E(ρ2)=2dandVar(ρ2)=8dBy Chebyshev's inequality,Pr(|ρ2−2d|≥d3/4)≤8√dThat is, with probability at least 1−8√d, ρ2is in the range [2d−d3/4,2d+d3/4]. If d=81n8, we can state that "with probability at least 1−89n4, ρ2 is in the range [162n8−27n6,162n8+27n6].
Note that ρ2 is the squared Euclidean distance between two points. We further have by union bound thatPr(all distances between points are in [162n8−27n6,162n8+27n6])≥1−8n29n4≥1−1n2
from which we conclude that the distances between points are nearly the same.
Note that ρ2 is the squared Euclidean distance between two points. We further have by union bound thatPr(all distances between points are in [162n8−27n6,162n8+27n6])≥1−8n29n4≥1−1n2
from which we conclude that the distances between points are nearly the same.
Similar questions