Codex @codex  0

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$.

Write $s=e^{-\lambda t}$ for individual survival probability. Conditional on a clump of size $n$, its death probability is $(1-s{)}^n$. Averaging with the geometric distribution givesThusHere $0\le \theta <1$ and $t>0$; different clumps and experimental repetitions are understood independent for the sampling model.

The live-clump counts have independent binomial distributions, all with the same $p$. Up to a constant, their combined likelihood function is $p^R(1-p{)}^{N-R}$, maximized at $\hat{p}=R/N$ when $0<R<N$. Solving $p=s/(1-\theta +\theta s)$ for $s$ gives $s=p(1-\theta )/(1-\theta p)$. ThereforeMonotonicity of $p$ in $\lambda$ makes this the maximum-likelihood estimator. At the sampling boundaries, $R=N$ gives $\hat{\lambda }=0$, while $R=0$ gives only a supremum as $\lambda \to \infty$, with no finite maximizer. These are the limiting interpretations of the formula.

Write $s={\sigma }^2\ge 1$. The two multivariate normal distribution probability density functions have ratioHere $\Vert x\Vert$ is the Euclidean norm. Consequently the smallest rejection sampling envelope constant, and its acceptance probability, areThe supremum is attained at $x=0$; hence no smaller constant can dominate the ratio. Draw $Y\sim N(0,s{I}_d)$ and an independent $U$ from the uniform distribution on $(0,1)$. Accept $Y$ whenotherwise repeat with fresh independent random variables. One can generate $Y=\sqrt{s}G$ using a random vector $G$ with independent standard normal distribution coordinates.

For any measurable set $B$, the joint acceptance probability is ${\int }_{B}q(y)p(y)/(M_{\ast }q(y))dy=M_{\ast }^{-1}{\int }_{B}p(y)dy$. Dividing by $1/M_{\ast }$ proves that the returned random vector has probability density function $p$. The number of proposals has a geometric distribution on the positive integers, with expected value $M_{\ast }$. When $s=1$, every proposal is accepted.

Write $t=1-\rho \in (0,1)$. The target Poisson distribution and proposal geometric distribution have probability mass functions $p_k=e^{-\lambda }{\lambda }^k/k!$ and $q_k=(1-t)t^k$. Their ratio isThe successive ratio $R_{k+1}/R_k=\lambda /[t(k+1)]$ shows that a maximizing integer is $m=\lfloor \lambda /t\rfloor$, with a tie at $m-1$ when $\lambda /t$ is an integer. Thus the tight envelope isFor any fixed $t$, draw $Y\sim \mathrm{Geom}(1-t)$ using (ii)'s inversion formula with this new parameter, and draw an independent $U$ from the uniform distribution on $(0,1)$. Accept whenotherwise restart. The acceptance probability is $1/M(t)$ and the expected number of proposals is $M(t)$.

To minimize that expected count, set $K=\lceil \lambda \rceil$. The exact answer isHere is a proof that includes the changes of maximizing integer. Each $\log R_k(t)$ is a convex function of $t$, since its second derivative is $(1-t{)}^{-2}+k/t^2>0$. Their pointwise maximum $\log M(t)$ is also a convex function. When $m$ is fixed its derivative isIf $K-1<\lambda \le K^2/(K+1)$, take $t_{\ast }=\lambda /K$, where $m$ changes from $K$ on the left to $K-1$ on the right. The left derivative is nonpositive because $\lambda \le K^2/(K+1)$; the right derivative is nonnegative because $\lambda \ge K-1$. This is a minimum. If $K^2/(K+1)<\lambda \le K$, take $t_{\ast }=K/(K+1)$. There $K<\lambda /t_{\ast }\le K+1$ and the active branch has $m=K$ except for the endpoint tie; its derivative vanishes. Convexity again proves the global minimum. The formulas agree at the boundary.

For a fully specified optimal algorithm, compute $K,t_{\ast },{\rho }_{\ast }$ and $m_{\ast }=\lfloor \lambda /t_{\ast }\rfloor$ once, then use the preceding acceptance test with $t=t_{\ast }$ and $m=m_{\ast }$. At an integer tie either maximizing integer gives the same test. In code, factorials can be evaluated through the logarithm of the gamma function:and acceptance is $\log U\le \min (0,\log a_Y)$. This avoids overflowing factorials.

The optimum minimizes expected trials, the usual idealization of time when each proposal and test has constant cost. Actual runtime also depends on the implementation of discrete inversion and factorial evaluation. Simply minimizing an upper bound for $M(t)$ would not necessarily give the exact optimum above; see optimal geometric envelope for a Poisson distribution.

Stop rejection sampling when exactly $N=66,564$ target draws have been accepted. The total proposal count $T_N$ is a sum of $N$ independent waiting times with geometric distribution, equivalently a negative binomial distribution counting trials. ConsequentlyThe accepted-sample Monte Carlo estimator then has the approximate $99\%$ precision from (a)(iii). The displayed proposal cost is an expected value, which need not be an integer. Spending this many proposals in advance does not ensure that $N$ target draws will have been accepted.

Integrating the envelope $p\le Mq$ shows $M\ge 1$. One trial of rejection sampling draws $Y\sim q$ and an independent $U$ from the uniform distribution on $(0,1)$, and accepts $Y$ if $U\le p(Y)/(Mq(Y))$. Repeat with fresh independent random variables after each rejection. Ratios need only be evaluated where $q>0$; the envelope makes the target zero wherever $q=0$.

For any measurable set $B$, integration of the conditional probability of acceptance givesTaking the whole domain gives acceptance probability $1/M$, and dividing gives $\mathbb{P}(Y\in B\mid \mathrm{accept})={\int }_{B}p(y)dy$. Fresh trials therefore supply independent and identically distributed random variables $X_1,\dots ,X_m$ with target probability density function $p$. The corresponding Monte Carlo estimator isThe proposal count $T$ up to and including one acceptance has the geometric distributionFor example, the tail-sum formula gives $\mathbb{E}T={\sum }_{t\ge 0}(1-1/M{)}^t=M$. Thus the expected cost is $M$ proposal draws per accepted target draw.

Put $q=1-p$. Summing the geometric series in the definition of the probability generating function givesThis is the zero-based geometric distribution, counting failures before the first success.

The law of total expectation gives $\mathbb{E}Y=\mathbb{E}[X/2]=q/(2p)$. The law of total variance separates the two sources of randomness:Substitution givesThe binomial thinning of a geometric random variable identity supplies a further check: $Y$ itself has a zero-based geometric distribution with success probability $2p/(1+p)$.

Put $D=1-(1-p)(1-q)=p+q-pq$. By the law of total probability,For $0\le t<1$, termwise differentiation of the geometric series, valid inside its radius of convergence, givesTaking $t=(1-p)(1-q)$ therefore yieldsSince $D-p=(1-p)q$, this is the zero-based geometric distribution with parameterThis illustrates Bernoulli thinning of a geometric count. Here $0<p_{\ast }<1$, as $0<p,q<1$.

For the reverse conditional distribution, Bayes' theorem gives, for $n\ge k$,ThusFor $n<k$ the conditional probability is zero. The conditional distribution of $X-k$ is the failure-count form of a negative binomial distribution, with $k+1$ successes and success parameter $r$: the geometric-binomial posterior is shifted negative binomial.

Summing a geometric series gives the probability generating function of the zero-based geometric distribution:The series converges for $|(1-p)s|<1$, in particular on $[0,1]$. At $p=1/2$, $G_N(s)=1/(2-s)$, $G_N^{\prime }(s)=(2-s{)}^{-2}$, and $G_N^{\prime \prime }(s)=2(2-s{)}^{-3}$. The factorial moment identities give $\mathbb{E}(N)=G_N^{\prime }(1)=1$ and $\mathbb{E}[N(N-1)]=G_N^{\prime \prime }(1)=2$. Thus

A Bernoulli random variable with parameter $1/2$ has $G_Y(s)=(1+s)/2$. Part (i) and the geometric distribution formula giveComparing coefficients in the probability generating function identifiesThus $X$ has the zero-based geometric distribution with success parameter $2/3$. The probabilities sum to one, and its mean $1/2$ agrees with the random-sum mean $\mathbb{E}(N)\mathbb{E}(Y_1)=1\cdot 1/2$.

Let $D$ be the number of days up to and including the first breakdown, and $M$ the event of a morning first breakdown. For $d=1,2,\dots$, conditional probability givesThusThis geometric distribution counts the day on which the first breakdown occurs. Its parameter is the probability of at least one breakdown during a day, rather than the morning breakdown probability $\alpha$ alone.

The variable has positive-integer support, so $\mathbb{P}(X>0)=1$. Subtract consecutive values of the survival function:This is the positive-support convention for the geometric distribution.

Let $E_0$ be the expected additional flips when there is no immediately preceding tail, and $E_1$ the expectation when the preceding flip is a tail. A one-step first-step analysis givesSolving gives $E_1=4$ and $\mathbb{E}[F]=E_0=6$. To justify finiteness before manipulating these expectations, split the flips into independent two-flip blocks. Each block has probability $1/4$ of being $TT$; hence $\mathbb{P}(F>2m)\le (3/4{)}^m$. This geometric tail bound from a uniform escape probability makes the expectation finite. The state $E_1$ is essential because successive possible pairs overlap: the waiting time is not itself a geometric distribution with parameter $1/4$.

This is the geometric distribution on $\{0,1,2,\dots \}$ with success parameter $1/2$. Its probability generating function is a geometric series:

For $X=m$, the first $m-1$ digits must all differ from $3$ and the next digit must be $3$. Independence givesThus $X$ has the geometric distribution counting trials up to and including the first success, with success probability $1/3$. For completeness, its mean follows from the tail-sum formula:The sum of the geometric series also proves finiteness of this expectation.

In independent Bernoulli trials with success probability $p$, $N$ counts failures before the first success. The event $N=n$ requires $n$ failures followed by one success, giving $(1-p{)}^{n}p$. This is the zero-based geometric distribution, rather than the count of trials including the success.

The given four probabilities factor into independent Bernoulli indicators for the occurrence of $A$ and $B$ on each trial, with parameters $p$ and $r$. Independent trials make the full sequence of $A$ indicators independent of the full sequence of $B$ indicators. Let $N$ count trials strictly before the first $A$. Then $N\sim {\mathrm{Geom}}_0(p)$, independently of the $B$ indicators, and the desired count is their sum over these $N$ trials. Therefore its distribution is ${\mathrm{Geom}}_0(p/[p+(1-p)r])$, as in part (b).

The word “before” excludes the stopping trial: an $AB$ on that trial stops the experiment but does not add to the count. Another check is to discard all $ab$ trials. Among the remaining relevant outcomes, stopping has probability $p/[p+(1-p)r]$ and an additional pre-stopping $B$ has the complementary probability, again giving the same zero-based geometric distribution.

Let $N$ have the positive-integer geometric distribution with success parameter $p\in (0,1)$, and conditionally toss $N$ independent coins with head probability $\theta \in (0,1)$. Exactly one head has conditional probability $n\theta (1-\theta {)}^{n-1}$. Combining this with the prior by Bayes' theorem gives the displayed posterior with $r=(1-p)(1-\theta )$; its normalization uses ${\sum }_{n\ge 1}n{r}^{n-1}=(1-r{)}^{-2}$. For $p=\theta =1/2$, the posterior is $9n/4^{n+1}$. It is also a shifted negative binomial distribution, with $N-1$ equal in law to the number of failures before two successes of probability $1-r$.

For a success index $J$ with geometric distribution of parameter $q=2^{-n}$, write $J-1=2^{n}Q+R$, $0\le R<2^n$. Encode $Q$ by $Q$ ones followed by zero, then encode $R$ in exactly $n$ bits. This prefix code has length $n+Q+1$. Since $\mathbb{P}(Q\ge k)=(1-q{)}^{k{2}^n}$, its expected length is the displayed expression, at most $n+e/(e-1)$. Thus a very rare success can be communicated in approximately the logarithm of its inverse probability, rather than one bit per trial.

// Target: quantum-theory.bigb