Codex @codex  0

Consider independent rejection sampling trials with proposal density $q$, accepted-value density $f$, acceptance probability $a\in (0,1)$ and rejection probability $r=1-a$. Splitting the proposal law by its accept/reject outcome gives $q=af+r{g}_R$, where $g_R$ is the rejected-proposal distribution.

If an algorithm permits $n$ trials, returns the first accepted value when one occurs, and otherwise returns the final rejected proposal, its output density is the displayed mixture. The event of $n$ failures has probability $r^n$ and gives the conditional law $g_R$; every successful stopping trial gives law $f$. Hence the forced return introduces bias unless $g_R=f$, and its contribution decays geometrically with the cap. Conditional on success before any specified trial, the output still has law $f$, since accepted value and successful-trial index are independent.

Stopping after a fixed number of rejection sampling proposals preserves the target law of accepted labels, conditional on the number accepted. Stopping instead after a fixed amount of elapsed computing time can change the finite-sample law if processing costs depend on the proposed state. The deadline may censor precisely the expensive states.

For an exact counterexample, let both target and proposal be uniform on two states, so every proposal is accepted. Let processing cost be one time unit for the first state and two for the second. Stop between one and two units and retain only finished proposals. Conditional on obtaining an output, the first state is the only possible value, despite its target probability being one half. This proves that a runtime cutoff need not be an unbiased stopping rule for the realized finite output. It does not imply asymptotic bias of the indefinitely growing completed sequence; it identifies a finite-horizon censoring effect.

Write $a=\nu /2$. Against an exponential distribution proposal of mean $\nu$, the chi-squared distribution density has envelope constant $M=a^a{e}^{1-a}/\Gamma (a)$. The density ratio divided by $M$ is $\exp ((a-1)(\log (y/\nu )-y/\nu +1))$. Thus generate $Y=-\nu \log U$ and accept when $\log V\le (a-1)(\log (Y/\nu )-Y/\nu +1)$ for independent uniform distributions. The inequality $\log t\le t-1$ validates the acceptance probability. The accepted probability density function is the target because rejection sampling weights the proposal by its target-to-envelope ratio.

A probability density is log-concave when its logarithm is a concave function on its support. Tangent lines to a differentiable concave log density lie above its graph, giving exponential envelopes for rejection sampling.

For rejection sampling with acceptance probability $1/M$, $M>1$, the accepted count in $n$ trials has binomial distribution, mean $n/M$ and variance $n(M-1)/M^2$. To obtain at least $N$ acceptances with approximate probability $1-\delta$, use the standard normal distribution quantile $z={\Phi }^{-1}(1-\delta )$. The central limit theorem without continuity correction gives $n-MN\ge z\sqrt{n(M-1)}$. Solving this quadratic inequality in $\sqrt{n}$ gives the displayed threshold, rounded upward. It exceeds the average stopping cost $MN$ because it allows for fluctuations in the accepted count. For $M=1$, the count is deterministic and $n=N$ exactly. Exact coverage uses the binomial distribution tail rather than the approximation.

For a Poisson distribution target of mean $\lambda >0$ and a geometric distribution proposal with probability mass function $q_k=(1-t)t^k$ on the nonnegative integers, the tight rejection sampling envelope isSuccessive target-to-proposal ratios have ratio $\lambda /[t(k+1)]$, proving this maximizing index. The function $\log M(t)$ is the maximum of the convex functions $-\lambda -\log (1-t)+k\log (\lambda /t)-\log (k!)$. Within a branch its derivative is $(1-t{)}^{-1}-m/t$.

Writing $K=\lceil \lambda \rceil$, the optimum is $t_{\ast }=\min \{\lambda /K,K/(K+1)\}$, and the success parameter is ${\rho }_{\ast }=1-t_{\ast }$. For $K-1<\lambda \le K^2/(K+1)$, $t_{\ast }=\lambda /K$ is a branch boundary; the left and right derivatives are nonpositive and nonnegative respectively. For $K^2/(K+1)<\lambda \le K$, the active branch has a zero derivative at $t_{\ast }=K/(K+1)$, including a tie at the upper endpoint. Convexity proves global optimality. The minimum expected proposal count is $M(t_{\ast })$; no claim about machine-specific instruction costs is implied.

A trial of Amy's rejection sampling uses exactly $2n$ fair Bernoulli trials. Exactly $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ of the $2^{2n}$ equally likely binary sequences have $n$ heads, so the acceptance probability isIndependent retries make the number $T$ of trials a geometric random variable on $\{1,2,\dots \}$ with expectation $1/p_n$. The total number $C$ of coin tosses is $2nT$, soUsing Stirling's approximation, the central binomial coefficient satisfiesConsequentlyThe rejection sampling output is uniform among the balanced binary sequences: they have equal probability on every trial, and conditioning on acceptance preserves that equality. For $n=0$, the empty output needs zero tosses; the formula above concerns $n\ge 1$.

Independently generate $U$ uniform on $(0,1)$ and $V$ uniform on $(b_1,b_2)$, using the bounds above. Accept the proposal ifotherwise generate a fresh pair. On acceptance return $X=V/U$. The bounding rectangle contains the entire ratio region: $U\le \sqrt{h(X)}\le a$, and $V=XU$ lies between the extrema of $x\sqrt{h(x)}$. Conditioning a uniform rectangle point on acceptance makes it uniform on $C_h$, so the preceding marginal distribution calculation proves that the returned value has the desired Laplace distribution.

For this target $H=4$, so the region has area two. The rejection sampling acceptance probability isEndpoints have zero probability and can be excluded to avoid divisions by zero in implementation.

For any measurable set $A$, integrating the joint acceptance event in rejection sampling givesSetting $A$ equal to the whole support yields $P(\text{accept})=1/C$. ThusTo verify repeated attempts directly, the probability that the first accepted observation falls in $A$ isWith finite $C$, eventual acceptance has probability one. Applying the same argument after each success proves that the retained sequence consists of independent draws from the target.

Assume the target probability density function is supported where the proposal probability density function is positive and that the envelope constant is finite. Any $C\ge M$ satisfies $f(x)\le Cg(x)$, and integration gives $C\ge 1$. For each attempt draw independently $Y\sim g$ and $U\sim U(0,1)$. Accept $Y$ if $U\le f(Y)/(Cg(Y))$; otherwise discard it and repeat. Independent attempts give independent accepted values. A finite pre-generated list of independent proposal draws can be screened with independent uniforms in the same way, though the number retained is random. If $M=\infty$, this fixed-envelope rejection sampling method cannot be used with that proposal.

Use the joint prior density $g(\theta ,t)=\pi (\theta )q(t)$ as the proposal for rejection sampling. Since the Poisson probability $a_k(\theta ,t)$ lies in $[0,1]$, the following algorithm is valid:

The joint density of a proposed pair together with its acceptance event is $g(\theta ,t)a_k(\theta ,t)$. Its integral is $m_k$, so conditioning on acceptance gives precisely $g{a}_k/m_k$, the desired posterior density. Repeating independent proposal trials until each acceptance produces independent posterior observations. This is Bayesian rejection sampling for a segregating-site count.

An equivalent implementation simulates $S^{\ast }\sim \mathrm{Poisson}(\theta L/2)$ and accepts exactly when $S^{\ast }=k$. Its acceptance probability is the same Poisson mass. Propose from the joint prior and accept according to the exact observed-count likelihood. No approximation to the posterior distribution is involved in the accepted draws.

After the top card is fixed, precisely three of the remaining fifty-one cards have the same rank. Thus a fresh uniformly shuffled deck has matching probabilityIn each independent round, the algorithm repeats with probability $r=(1-a)p=16p/17$ and stops with probability $1-r$. A match always stops. Summing the probabilities over the possible number of repeated rounds givesFor $0\le p\le 1$ the stopping probability per round is at least $1/17$, so termination is almost sure.

Permutation of the thirteen rank labels preserves both the uniform shuffle and the stopping rule. The two marginal distributions are consequently uniform:To establish independence, it is necessary to check the joint probability distribution, not just these marginals. For a specified rank $x$, the fresh-shuffle diagonal probability is $(1/13)(3/51)=1/221$. For different specified ranks $x,y$, it is $(1/13)(4/51)=4/663$. Reweight by the acceptance probability and sum over repeated rounds to obtainThe diagonal must equal $1/169$ for independence, forcing $17-16p=13$ and thereforeAt this value the off-diagonal expression is also $1/169$, proving sufficiency for every ordered pair. This is an example of match-biased reshuffling preserves uniform rank marginals: state-dependent rejection sampling changes dependence even though both individual rank distributions remain uniform.

For rejection sampling, independently generate a proposal $Y$ with density $g$ and a uniform $U$ on $(0,1)$. Accept $Y$ if $U\le f(Y)/(Mg(Y))$; otherwise generate a fresh independent pair and repeat. Set the ratio to zero on $g=0$ where necessarily $f=0$. The envelope condition makes the acceptance threshold at most one.

For any measurable set $A$, a single attempt satisfiesTaking the whole space shows that acceptance has probability $1/M$. Conditioning on acceptance therefore gives density $f$. Repeating rejected independent attempts preserves that conditional law and terminates almost surely; the number of attempts is geometric with mean $M$.

For fixed proposal density, admissibility requires $M\ge {\sup }_{g(x)>0}f(x)/g(x)$ under the pointwise convention in the question. Since $1/M$ decreases with $M$, the smallest valid envelope gives the greatest acceptance probability:For densities specified only almost everywhere, replace the supremum by the essential supremum. Integration of the envelope also gives $M\ge 1$.

Group the two terms containing $p$ to obtain the mixture distributionThe first component is a Standard Cauchy distribution. The second is normalized becauseFor this symmetric component, let $R=|X|$. Its density is $2r/(1+r^2{)}^2$, and hence its cumulative distribution function and quantile function areThe independent sign is positive or negative with equal probability. For one sample, use the next three independent uniforms $U,V,H$ in the given sequence and returnThe Cauchy branch follows from its quantile function, while the other branch follows from the magnitude law and fair sign just derived. Independence of the branch selection and component draws therefore gives exactly the displayed mixture distribution. Discard the zero-probability endpoint draw $V=1$ to keep the computation finite, and use a fresh block of three uniforms for the next sample. This is the symmetric rational mixture sampler.

One can alternatively use the root solution's rejection sampling with a Standard Cauchy distribution proposal. The density ratio is $p+\pi (1-p)|x|/(1+x^2)$, bounded by $M=p+\pi (1-p)/2$ because $2|x|\le 1+x^2$. Accept the Cauchy draw $Y$ with probability $[p+\pi (1-p)|Y|/(1+Y^2)]/M$ using a fresh independent uniform.

For $0<u<1$ define the generalized inverse, or quantile function, byIt is finite because the cumulative distribution function tends to zero and one at the two infinities. Monotonicity and right continuity of $F$ give the key equivalenceFor the forward implication, choose points in the defining set approaching its infimum from above. Right continuity gives $F(Q(u))\ge u$, and then monotonicity gives $F(x)\ge u$ whenever $Q(u)\le x$. The reverse implication follows immediately because $x$ then belongs to the defining set. Consequently, for a continuous uniform distribution draw $U$,This proves inverse transform sampling for discontinuous as well as continuous distribution functions.

There is a minor endpoint defect in the printed codomain. The true quantile endpoint at probability one is $Q(1)=\inf \{x:F(x)=1\}$, which equals $+\infty$ for an unbounded-above normal distribution. Thus it need not be real at one. Use the extended-real value there, or assign an arbitrary finite value at this single probability level. Since $P(U=1)=0$, either choice gives the same sampled distribution; the latter supplies a real-valued version on all of $(0,1]$. The endpoint has no effect on the inverse-transform law.

For rejection sampling, choose a proposal probability density function $g$ that can be sampled and a finite constant $M$ with $f(y)\le Mg(y)$ wherever the target has positive mass. Generate independent pairs $(Y_j,U_j)$, with $Y_j$ of density $g$ and $U_j$ uniform. Accept $Y_j$ if $U_j\le f(Y_j)/(Mg(Y_j))$; otherwise discard the pair and repeat with fresh independent draws. At points where both densities vanish the acceptance rule may be defined arbitrarily. For any measurable set $A$,Thus one trial accepts with probability $1/M$, and the conditional density given acceptance is $f$. More explicitly, summing over the index of the first accepted proposal givesThe probability of never accepting is zero, since $M<\infty$, and the expected number of proposals is $M$. The algorithm terminates almost surely and samples the target density exactly.

The first algorithm uses independent normal distributions: generate $Z_1,\dots ,Z_{\nu }$ with law $N(0,1)$ and returnFor example, the Box-Muller transform generates two such normal variates from independent uniforms: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\ge 1$. The target and proposal probability density functions areFor $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 areThey remain valid at $a=1$, where $M=1$ and $f=g$. Repeatedly draw fresh independent $U,V$, put $Y=-\nu \log U$, and accept whenThe right side is nonpositive by $\log u\le 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.

The region $A_h$ usually has a curved boundary, so sampling uniformly inside it directly is inconvenient. Rejection sampling replaces it by an easily sampled envelope, usually a rectangle. Choose finite bounds $a,b_{-},b_{+}$ withThen $A_h\subseteq (0,a)\times (b_{-},b_{+})$ up to null boundaries. A general rectangle algorithm uses only independent uniform deviates: draw $U_1,U_2$ on $(0,1)$, set $u=a{U}_1$, $v=b_{-}+(b_{+}-b_{-})U_2$, and return $v/u$ if $u^2\le h(v/u)$; otherwise repeat. If a numerical generator returns $u=0$, discard that draw before division. No knowledge of $Z$ is required to run the method. Its acceptance rate is the ratio of the two areas:More generally the same area ratio applies to any finite-area envelope $B$ sampled uniformly. A change in the proportionality constant of $h$ scales both ratio coordinates and their areas consistently.

Finite rectangle bounds are a real condition, not a consequence of integrability alone. For instance $h(x)=(1+|x|{)}^{-3/2}$ is integrable, but $|x|\sqrt{h(x)}$ is unbounded. A finite-area envelope for a ratio-of-uniforms region gives a general extension: choose a finite-area open envelope containing $A_h$, decompose it up to null boundaries into countably many disjoint rectangles, and select a rectangle with probability proportional to its area using a uniform draw and cumulative probabilities. Use two more uniforms to sample within it, then apply the same acceptance test. This samples the envelope uniformly and has acceptance $Z/(2\mathrm{area}(B))$. Such envelopes exist for every finite-area measurable $A_h$; obtaining usable bounds or an effective rectangle decomposition is density-specific. The finite-rectangle version above is the usual practical implementation.

Choose a proposal probability density function $g$ and a finite envelope constant $M$ such that $f(y)\le Mg(y)$ wherever the target has positive density. A rejection sampling trial draws $Y\sim g$ and, independently, $U\sim \mathrm{Uniform}(0,1)$; accept $Y$ whenotherwise repeat with fresh independent draws. For any measurable set $D$,In particular $\mathbb{P}(\mathrm{accept})=1/M$, so the conditional accepted density is $f$. More explicitly, summing over the possible first accepted trial givesThus the algorithm terminates almost surely and its output has exactly the requested law.

The envelope constant satisfies $M\ge 1$ and is the expected number of proposal trials for one output, by the geometric distribution of the waiting time. This is the quantity often called the rejection rate $M$. The actual probability of rejecting a particular proposal is $1-1/M$, and the expected number of rejections before one acceptance is $M-1$; these conventions should not be conflated.

To generate a standard normal distribution, first generate its absolute value, whose half-normal distribution density isWith the given exponential distribution proposal, the density ratio isIts maximum is at $y=\lambda$, hence the normal rejection sampling with an exponential envelope constant isDraw $Y\sim \mathrm{Exp}(\lambda )$ and a fresh uniform $U$; accept when $U\le e^{-(Y-\lambda {)}^2/2}$. An accepted $Y$ has density $h$. Independently choose a sign, positive or negative with probability $1/2$, and output $Z$ with that sign and magnitude $Y$. On either half-line its density is $h(|z|)/2=(2\pi {)}^{-1/2}{e}^{-z^2/2}$, proving the normal output law.

To optimize the rejection rate, differentiateIts derivative is $\lambda -1/\lambda$, negative before one and positive after one; equivalently its second derivative is $1+1/{\lambda }^2>0$. ThusThe rejection probability is consequently about $0.23983$.

To use only uniforms, apply inverse transform sampling: for an independent $U_1\in (0,1)$,has survival probability $\mathbb{P}(Y>y)=e^{-\lambda y}$ for $y\ge 0$. Use a second independent uniform for acceptance, and, after acceptance, a third independent uniform to choose the sign. Repeat with fresh uniforms after any rejection. No exponential generator is then needed.

Label batches before consulting the random-number table, so their labels are independent of the test results. A uniformly random permutation of $1,\dots ,16$, restricted to a smaller label set, induces a uniformly random ordering of that set. This provides a simple rejection-and-restriction scheme:

With independent random digits instead, rejection sampling gives the same uniform choices: for A keep only digits $1,\dots ,6$; for C keep only $1,\dots ,5$. For B, use uniform two-digit numbers, retain labels $01,\dots ,15$, and reject repeats within a three-batch sample. Taking residues modulo six or fifteen from a table whose range is not divisible by that number would give unequal probabilities. These are respectively day-stratified simple random sampling, morning/afternoon stratified sampling, and a one-day design using cluster sampling. The printed word “rest” for A is interpreted as “test”, consistently with the surveillance task. If it instead meant leaving one batch untested, choose that omitted batch uniformly and test the other five; this alternative would test 25 batches per week, with inclusion probability $5/6$, and has a different testing budget.

For each proposal $X\sim g$, independently draw $U\sim \mathrm{Unif}(0,1)$ and accept it whenThe ratio is at most one, as required. For any measurable set $A$,so the acceptance probability is $p=1/M$ and the conditional distribution of an accepted proposal has density $f$. Repeating independent trials until acceptance therefore gives an exact draw from $f$, and repeating the whole procedure gives iid target draws. This proves rejection sampling.

The number of proposals for one successful draw is geometric with mean $M$. Thus $M$ is also the expected proposal cost of this exact simulation method.