= Solution
The first algorithm uses independent <normal distributions>: generate $Z_1,\ldots,Z_\nu$ with law $N(0,1)$ and return
$$
\boxed{Y=\sum_{j=1}^{\nu}Z_j^2.}
$$
For example, the <Box-Muller transform> generates two such normal variates from independent uniforms:
$$
Z_1=\sqrt{-2\log U}\cos(2\pi V),\qquad
Z_2=\sqrt{-2\log U}\sin(2\pi V).
$$
To verify this, $R^2=-2\log U$ has density $e^{-s/2}/2$ and $2\pi V$ is an independent uniform angle. Converting the resulting polar density to Cartesian coordinates gives $(2\pi)^{-1}e^{-(z_1^2+z_2^2)/2}$, which factors into two independent <normal distributions>. Independent pairs therefore give the required sum, discarding a spare coordinate when $\nu$ is odd. Its <moment-generating function> is $(1-2t)^{-\nu/2}$, that of the <chi-squared distribution>.
A genuinely different algorithm uses <exponential-envelope rejection sampling for a chi-squared variable>. Put $a=\nu/2\geq1$. The target and proposal <probability density functions> are
$$
f(y)=\frac{y^{a-1}e^{-y/2}}{2^a\Gamma(a)},\qquad
g(y)=\frac1\nu e^{-y/\nu},\quad y>0.
$$
For $a>1$, differentiating $\log(f/g)$ gives $(a-1)(1/y-1/\nu)$, so the maximum is at $y=\nu$. The envelope constant and normalized density ratio are
$$
M=\frac{a^ae^{1-a}}{\Gamma(a)},\qquad
\frac{f(y)}{Mg(y)}=\exp\left((a-1)\left[\log(y/\nu)-y/\nu+1\right]\right).
$$
They remain valid at $a=1$, where $M=1$ and $f=g$. Repeatedly draw fresh independent $U,V$, put $Y=-\nu\log U$, and accept when
$$
\boxed{\log V\leq(a-1)\left[\log(Y/\nu)-Y/\nu+1\right].}
$$
The right side is nonpositive by $\log u\leq u-1$, so this is a legitimate acceptance probability. The joint probability of proposing and accepting in $dy$ is $g(y)f(y)/(Mg(y))\,dy=f(y)\,dy/M$; conditional on acceptance the density is exactly $f$. This proves the <rejection sampling> algorithm, rather than only identifying the target law.
For $\nu=2$ I prefer the second method: it reduces to a single exponential draw with no rejection. The first method is simple and attractive when normal draws are already available or $\nu$ is small. For larger $\nu$, the second method avoids generating $\nu$ normals: its acceptance probability is $1/M$, asymptotic to $\sqrt{2\pi}/(e\sqrt a)$ by <Stirling's formula>. Its expected number of proposals grows like $\sqrt\nu$, rather than the linear number of normal draws in the first method. Both are exact ideal-uniform algorithms; actual runtime also depends on the implementation.
Back to article page
