Suppose we have a univariate random variable $X\sim\mathcal{P}$ with probability density function $f(x):\mathbb{R}\to\mathbb{R}$, $\int\_{-\infty}^{\infty}f(x) dx = 1$, we then draw $n$ samples $x\_1,x\_2,\dots,x\_n$ iid from $\mathcal{P}$. What's the probability that the next sample $x\_{n+1}$ is at least $\varepsilon$ away from any of the previous samples $x\_1,x\_2,\dots,x\_n$? $\varepsilon > 0$ is a fixed constant.


I tried to formulate this problem as:
Given $x\_1,x\_2,\dots,x\_n$ i.i.d from $\mathcal{P}$, the probability of the new sample fall outside the $\varepsilon$ ball of any previous samples is (given you know $x\_{n+1}=x$, the previous n samples are all far away from it):
$\prod\_{i=1}^{n} Pr(\|x-x\_i\|>\varepsilon)=\left[1-\int\nolimits\_{x-\varepsilon}^{x+\varepsilon}f(y) dy\right]^n$, then take the expecatation of $x$, we have 
$\int\nolimits\_{-\infty}^{\infty}\left[1-\int\nolimits\_{x-\varepsilon}^{x+\varepsilon}f(y) dy\right]^nf(x)dx$ is the probability of $x\_{n+1}$ fall outside of the $\varepsilon$ ball of any of $x\_1,x\_2,\dots,x\_n$.


My question is, what conditions is required for $f(x)$ to let this probability go to $0$ as $n\to\infty$.


i.e. when does $\lim\limits\_{n\to\infty}\int\nolimits\_{-\infty}^{\infty}\left[1-\int\nolimits\_{x-\varepsilon}^{x+\varepsilon}f(y) dy\right]^nf(x)dx = 0$ hold for $f(x)$?



Expected number of trials to cover certain probability mass for a probability density function?
No conditions are needed: Divide the real line up into intervals of length $\epsilon$: $I\_k=[k\epsilon,(k+1)\epsilon)$. Now you choose a point in $I\_k$ with some probability $p\_k=\int\_{I\_k}f$.


In order for $x\_{n+1}$ to be at a distance $\epsilon$ from the other points chosen so far, it must be the first point to land in the interval $I\_k$.


The probability of this happening is $\sum\_{k\in\mathbb Z} p\_k(1-p\_k)^n$, so it is sufficient to show that for any probability distribution $(p\_k)$ on $\mathbb Z$, the above sum converges to 0.


Notice that the $k$th term in the sum is monotonically decreasing to 0 and even for $n=0$ is integrable. (A very simple case of) the monotone convergence theorem implies that the sum converges to 0 as $n\to\infty$. Since this is an upper bound for what you want, you're done.


