0
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Mar 8, 2012 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
    Commented Mar 8, 2012 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
    Commented Mar 8, 2012 at 17:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .