Past exam of the probability, statistics and options I course of the University of Oxford / 2011 / S / 1

The affine transformationmaps the uniform distribution on $(0,1)$ to the uniform distribution on $(-1,1)$. Indeed for $-1<v<1$, $\mathbb{P}(2U-1\le v)=(v+1)/2$, whose derivative is the constant density $1/2$.

Draw independent uniforms $U_1,U_2$ on $(0,1)$, put $V=2U_1-1$, and accept $V$ if $U_2\le \sqrt{1-V^2}$; otherwise repeat independently. This is rejection sampling from the uniform proposal $q(v)=1/2$. Its accepted unnormalized density is $q(v)\sqrt{1-v^2}$, and the acceptance probability isDividing by $a$ gives the target Wigner semicircle distribution. The number of trials up to and including the first acceptance has a geometric distribution with success probability $\pi /4$, soThe expected number of rejected trials alone is $4/\pi -1$.

Let $r=1-\pi /4$ be the rejection probability. The rejected-proposal distribution has densityIf any of the first $n$ trials accepts, the returned value has target density $f$. If all $n$ reject, which has probability $r^n$, the forced return is the final rejected proposal and has density $g_R$. Thus the capped algorithm has densityIt is biased toward the ends of the interval, where rejection is most likely, and has too little mass near the centre. The bias disappears geometrically as the trial cap increases. This is bias from returning a rejected proposal after a rejection-sampling cap.

Conditional on acceptance before the $n$th trial, however, the returned value has exactly the semicircle law. For each possible first successful trial its value has density $f$, independently of the number of previous failures; a mixture of these identical conditional laws remains $f$.