Math, asked by nurbutashi7500, 1 year ago

For sufficiently large d, with high probability the distances between all pairs of points will be essentially the same

Answers

Answered by rishav16104
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.
Similar questions