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)$?


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.

| cite | improve this answer | |
  • $\begingroup$ Thank you very much for the reply. I have two more concerns about generalising this proof however. 1) If we make $\epsilon\to 0$, (i.e. change the $\sum_k$ to integral), does this still hold due to monotone convergence theorem? (I didn't get to learn real analysis quite well as an engineering student.) 2) If we take $X$ to be a multivariate random variable on $\mathbb{R}^n$, we need then generalise the intervals to $\epsilon$ balls. Does the proof need some kind of covering theorem (I'm guessing) to support it? $\endgroup$ – nil Mar 8 '12 at 15:42
  • $\begingroup$ Sorry for the confusion, but in 2), I wanted to say $\mathbb{R}^d$, a d-dimensional random variable, not $\mathbb{R}^n$. $\endgroup$ – nil Mar 8 '12 at 16:11
  • $\begingroup$ Same argument. Just split up $\mathbb R^d$ into cubes of diameter less than $\epsilon$. There are still countably many cubes so there's a way to number them 1,2,3,4,\ldots. $\endgroup$ – Anthony Quas Mar 8 '12 at 17:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.