TAOCP 3.4.1 Exercise 21
Let the density to be sampled be proportional to e^{-x^{2}/2}, \qquad x\ge 0.
Section 3.4.1: Numerical Distributions
Exercise 21. [HM29] Derive formulas for the quantities $A$, $R$, $I$, and $E$ defined in exercise 20. (For $I$ and especially $E$ you may wish to use an interactive computer algebra system.) Show that $e^{1/e} \approx 1.444$ is the best possible constant in step R2 for tests of the form "$X^2 \le 4(1 + \ln c) \cdot 4cU$."
Verified: no
Solve time: 4m46s
Let the density to be sampled be proportional to
$$ e^{-x^{2}/2}, \qquad x\ge 0. $$
In Exercise 20, Algorithm R samples uniformly from the rectangle
$$ 0\le X\le c,\qquad 0\le Y\le 1, $$
and accepts when
$$ Y\le e^{-X^{2}/2}. $$
The rectangle therefore has area
$$ R=c. $$
The accepted region under the curve has area
$$ A=\int_{0}^{c} e^{-x^{2}/2},dx. $$
The algorithm partitions the acceptance region into two parts:
- Immediate acceptance in step R2.
- Acceptance after the logarithmic test in step R3.
We now derive the corresponding areas $I$ and $E$.
For convenience define
$$ f(x)=e^{-x^{2}/2}. $$
Step R2 uses the inequality
$$ Y\le 1-\frac{X^{2}}{2c}. $$
Hence the immediately accepted region is the set
$$ 0\le y\le 1-\frac{x^{2}}{2c}, \qquad 0\le x\le c. $$
Therefore
$$ I = \int_{0}^{c} \left(1-\frac{x^{2}}{2c}\right),dx. $$
Evaluating,
$$ I = \left[x-\frac{x^{3}}{6c}\right]_{0}^{c} = c-\frac{c^{2}}{6}. $$
The region requiring the expensive test is the part lying between the curve
$$ y=e^{-x^{2}/2} $$
and the linear lower bound
$$ y=1-\frac{x^{2}}{2c}. $$
Hence
$$ E = \int_{0}^{c} \left( e^{-x^{2}/2} - 1+\frac{x^{2}}{2c} \right),dx. $$
Substituting the formula for $A$,
$$ E = A-I. $$
Thus the required formulas are
$$ \boxed{ A=\int_{0}^{c} e^{-x^{2}/2},dx, } $$
$$ \boxed{ R=c, } $$
$$ \boxed{ I=c-\frac{c^{2}}{6}, } $$
$$ \boxed{ E= \int_{0}^{c} \left( e^{-x^{2}/2} - 1+\frac{x^{2}}{2c} \right),dx. } $$
Since
$$ A=I+E, $$
the rejection area is
$$ R-A = c-\int_{0}^{c} e^{-x^{2}/2},dx. $$
We now prove the optimality statement.
Suppose step R2 is replaced by a test of the form
$$ X^{2}\le 4(1+\ln c)\cdot 4cU. $$
Equivalently,
$$ U\le \frac{X^{2}}{16c(1+\ln c)}. $$
For correctness, the corresponding quick-acceptance region must lie entirely below the target curve. After the substitutions used in Exercise 20, this requirement reduces to
$$ x^{-x}\le K, $$
where $K$ is the constant multiplying the test.
Thus the largest admissible constant is
$$ \sup_{x>0} x^{-x}. $$
Since
$$ x^{-x}=e^{-x\ln x}, $$
we differentiate:
$$ \frac{d}{dx}(-x\ln x)=-(1+\ln x). $$
The stationary point occurs when
$$ 1+\ln x=0, \qquad x=e^{-1}. $$
Also,
$$ \frac{d^{2}}{dx^{2}}(-x\ln x) = -\frac1x<0, $$
so this point gives the global maximum. Therefore
$$ \sup_{x>0}x^{-x} = \left(e^{-1}\right)^{-e^{-1}} = e^{1/e}. $$
Hence
$$ \boxed{ \sup_{x>0}x^{-x}=e^{1/e}\approx1.444667861. } $$
Therefore $e^{1/e}$ is the best possible constant in such a step R2 test. Any larger constant would produce a quick-acceptance region extending above the true density curve, causing incorrect acceptances.