Probability of being "close" to a lattice point

25 Views Asked by At

Let $X = \{1, \cdots, n\}$, and let $T$ be the set of $t$-tuples over $X$. Now choose a random point $x$ from $[1, n]^t$ (note that $x$ is a tuple of real numbers, not necessarily a lattice point), and define $\epsilon_1, \cdots, \epsilon_{|T|}$ to be the distances (say Euclidean) between $x$ and each tuple in $T$. Finally, let $\epsilon$ be the smallest such $\epsilon_i$.

What is the probability that this smallest distance $\epsilon$ is less than a given parameter, say $\lambda$?

1

There are 1 best solutions below

0
On BEST ANSWER

The probability that the distance from some lattice point is $<\lambda$ is simply the hypervolume covered by $n$-dimensional hyperspheres of radius $\lambda$ centred at each point (cutting the sphere off if it’s at an edge/vertex). The formulae for these are well known, and assuming $\lambda$ is less than $1/2$ as so to not make the spheres overlap, this will give you your desired probability.