6
$\begingroup$

So I am really struggling with this problem and could use some help.

Consider the Epanechnikov kernel given by $$f_e(x)=\frac{3}{4}\left( 1-x^2 \right)$$

According to Devroye and Gyorfi's "Nonparametric Density Estimation: The $L_1$ View", to generate a sample of a distribution having $f_e$ as its density function we can use the following method (see p.236):

  1. Generate iid $U_1$,$U_2$,$U_3$ ~ Uniform(-1,1).
  2. If $\left| U_3\right| \geq \left| U_2\right|$ and $\left| U_3\right| \geq \left| U_1\right|$, deliver $U_2$; otherwise deliver $U_3$.

I have to prove this works. I thought this was related to either the acceptance-rejection method or maybe order statistics. I have spent a fair bit of time trying both approaches but I am stuck. Any pointers will be greatly appreciated.

$\endgroup$
3
  • 1
    $\begingroup$ A very quick indication, for I am in a hurry: the probability of not being the highest $|U_i|$ and less than $u$ is proportional to$$\mathbb{P}(U\le u)-\frac{1}{3}\mathbb{P}(U_{(3)}\le u)=u-\frac{u^3}{3}$$whose derivative gets you $f_e(u)$. $\endgroup$
    – Xi'an
    Sep 22, 2015 at 15:58
  • 1
    $\begingroup$ Note that - like many of Luc's books that are out of print - the book is available in pdf form from his luc.devroye.org web page. $\endgroup$
    – Glen_b
    Sep 22, 2015 at 17:10
  • $\begingroup$ An accept-reject algorithm would simulate $U,V\sim\mathcal{U}(0,1)$ and take $X=\pm U$ if $V\le U^2$. Else it would repeat the simulation. $\endgroup$
    – Xi'an
    Sep 22, 2015 at 20:45

2 Answers 2

6
$\begingroup$

Consider this alternative description of the same algorithm:

  1. Generate iid $X_1, X_2, X_3$ with Uniform$(0,1)$ distributions.

  2. Select one of the two smallest of the $X_i$ at random, with equal probability. Call this value $X$.

  3. Randomly negate $X$ with probability $1/2$.

Parts (1) and (3) reflect the fact that a Uniform$(-1,1)$ variate is the random negation of a Uniform$(0,1)$ variate. Part (2) is a restatement of step (2) in the question.

It comes down to computing the distribution of $X$. To this end, let $0 \le t \le 1$. The event that $X \le t$ decomposes into two disjoint possibilities:

  1. At least two of the $X_i$ lie in $[0, t]$, guaranteeing that $X$ (which must be among them) will lie in $[0, t]$. This is a binomial probability given by $$\binom{3}{2}t^2(1-t) + \binom{3}{3}t^3 = t^2(3-2t).$$

  2. Exactly one of the $X_i$ lies in $[0, t]$ and it is the one randomly chosen. The random choice multiplies the chance (another binomial probability) by $1/2$, giving $$\binom{3}{1}t(1-t)^2 \times \frac{1}{2} = \frac{3}{2}t(1-t)^2.$$

Therefore the distribution function is

$$F(t) = t^2(3-2t) + \frac{3}{2}t(1-t)^2 = \frac{3}{2} t - \frac{1}{2}t^3,$$

whence the density function is

$$f(t) = F^\prime(t) = \frac{3}{2}(1 - t^2).$$

Figure

The blue shaded area represents $f$ while the red shaded area shows how it is extended symmetrically about $0$ to define a distribution supported on the interval $[-1,1]$ with density $f_e = \frac{1}{2}f$.

Extending $f$ to the domain $[-1,1]$ by symmetry (which is what part (3) does) will not change its functional form (which is already symmetric about $0$, since $(-t)^2 = t^2$) but must halve the height to maintain its normalization, whence

$$f_e(t) = \frac{1}{2}\left(\frac{3}{2}(1 - t^2)\right) = \frac{3}{4}(1-t^2).$$


By the way, a simpler way to generate such a sample is to take the median of three iid Uniform$(0,2)$ variates. Here's R code:

n <- 1e5
x <- apply(matrix(runif(3*n, -1, 1), 3), 2, median)

(It takes two or three seconds to generate 100,000 values.) Comparing the histogram of this sample to the kernel confirms its accuracy:

enter image description here

$\endgroup$
1
$\begingroup$

Although it only is a too long comment that comes a day late and a dollar short, my explanation, which is highly related to the more detailed and to the point answer by whuber, is that the outcome of Devroye's algorithm with those three uniforms is indeed distributed from the mixture of the distributions of the first order statistic and of the second order statistic for three uniforms on (0,1), since it is not the third order statistic,$$f^*(u)=\frac{1}{2}f_{(1:3)}(u)+\frac{1}{2}f_{(2:3)}(u)$$Given that the generic density for an order statistic is$$f_{(k:n)}(x)=(k-1)!(n-k-1)!\,F(x)^{k-1}\,(1-F(x))^{n-k-1}(x)\,f(x),$$we get$$f^*(u)=\frac{1}{2} 3(1-x)^2 + \frac{1}{2} 6x(1-x)=\frac{3}{2}-\frac{3x^2}{2}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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