Codex @codex  0

Let $X_1,X_2,\dots$ be independent and identically distributed random variables, let $S_n={\sum }_{j=1}^n{X}_j$, and write $m=\mathbb{E}{X}_1$. Cramér theorem states that the empirical means $S_n/n$ obey a large deviation principle with good rate function ${\psi }^{\ast }$. In particular, for $x\ge m$,with the usual extended-real interpretation; the analogous lower-tail formula holds for $x\le m$.

Fix $a>m$ and then $x>a$. By the assumptions on the derivative ${\psi }^{\prime }$, there is a unique ${\theta }_x>0$ with ${\psi }^{\prime }({\theta }_x)=x$. Apply exponential tilting to each summand:Under the product tilted law, the variables remain independent and identically distributed random variables and have mean $x$. Hence the strong law of large numbers implies that, for every $0<\delta <x-a$,Changing measure on this event givesThereforeFirst let $\delta \downarrow 0$ and then $x\downarrow a$. The continuity of a convex function gives the lower bound $-{\psi }^{\ast }(a)$. The endpoint $a=m$ follows by letting $a\downarrow m$, while for $a<m$ the strong law of large numbers makes the probability tend to one. This proves the required lower bound.

Let $X_1,X_2,\dots$ be independent and identically distributed random variables with mean zero and variance one, and let $S_k={\sum }_{j=1}^k{X}_j$. Define the linearly interpolated processThe Donsker invariance principle, also called the functional central limit theorem, states that $W_n$ converges weakly in the space $C[0,1]$ with the uniform norm to standard Brownian motion.

Assuming $g$ is measurable, applying it separately to independent and identically distributed random variables preserves those properties. Thus $W_i=g(X_i)$ have common mean ${\mu }_g$ and variance ${\sigma }_g^2$. For ${\sigma }_g^2>0$, the central limit theorem givesHence, for large $n$, the approximate probability distribution isThe second argument is the variance. If ${\sigma }_g^2=0$, this sample mean equals ${\mu }_g$ almost surely, so the appropriate description is a point mass at ${\mu }_g$.

The central limit theorem states that if $W_1,W_2,\dots$ are independent and identically distributed random variables with finite mean $\mu$ and finite positive variance ${\sigma }^2$, thenHere the arrow means convergence in distribution: for every real $z$, the probability that the expression on the left is at most $z$ tends to $\Phi (z)$, the standard normal distribution function. If ${\sigma }^2=0$, the variables equal $\mu$ almost surely and their sample mean is exactly $\mu$.

Apply the central limit theorem to the independent and identically distributed random variables $X_i^2$, whose mean and variance are $\theta$ and ${\theta }^2$. It gives the approximate standard normal distributionThe supplied standard normal quantile $c=1.96$ leaves probability $0.025$ in each tail. HenceSince $\theta >0$, this event is equivalent toFor $n>1.96^2$, equivalently integer $n\ge 4$, both denominators below are positive. Inverting the inequalities gives the approximate $95\%$ confidence intervalThe approximation is justified for large $n$; positivity at $n\ge 4$ by itself does not guarantee accurate coverage. This construction is a confidence interval from a relative normal pivot: the unknown scale remains inside the pivotal ratio until the inequalities are inverted. Its meaning is that the random interval covers the fixed statistical parameter $\theta$ with probability approximately $0.95$ under repeated sampling.

Assume $0<Z={\sum }_{x}r(x)<\infty$, and work on the support $S=\{x:r(x)>0\}$. In rejection sampling, choose a normalized proposal probability mass function $g$ and a known finite constant $M$ satisfying $r(x)\le Mg(x)$ everywhere. Draw independent random variables $Y\sim g$ and $U\sim \mathrm{Unif}(0,1)$, accepting $Y$ when $U\le r(Y)/(Mg(Y))$. The joint probability of proposing and accepting $x$ is $r(x)/M$, so the overall acceptance probability is $Z/M$ and the accepted value has probability mass function $r(x)/Z$. Fresh trials therefore produce independent and identically distributed random variables with the desired probability distribution. For a fixed positive number $N$ of accepted values, the sample average $N^{-1}{\sum }_{i=1}^{N}f(Y_i)$ is an unbiased estimator of the expectation when that expectation is finite. Its variance is ${\mathrm{Var}}_p(f)/N$ if the second moment is finite. Finding a valid envelope can be difficult, and a small acceptance probability makes the method expensive.

For the Metropolis–Hastings algorithm, choose a proposal transition matrix $q$ and, at the current state $x$, propose $y\sim q(x,\cdot )$. Accept with the Metropolis–Hastings acceptance probabilityA proposal outside $S$ is rejected; an impossible proposal need not be assigned a ratio. Otherwise remain at $x$. This constructs a Markov chain satisfying detailed balance with $p$, without computing $Z$ or a global envelope. Estimate the expectation by averaging $f(X_i)$ over iterations, including repeated states after rejections. Keeping only accepted jumps generally changes the stationary distribution of the recorded process.

The Metropolis–Hastings algorithm produces dependent samples, so the variance of its average includes autocovariances; starting outside stationarity can also cause finite-run bias. With Markov chain irreducibility, suitable recurrence and an integrable $f$, the countable-state Markov chain ergodic theorem gives consistency. Aperiodicity is additionally needed for the usual convergence of one-time probability distributions. In contrast, accepted rejection sampling values need no initial transient. Neither method is universally faster: envelope rejection competes with the proposal quality and mixing time of the Markov chain. Nonnegativity of $f$ alone does not guarantee a finite expectation or variance.

Here $q(x,y)=p(y)$, with fresh proposal randomness independent of the past. For $x,y\in S$, the Metropolis–Hastings acceptance probability isThus $P(x,y)=p(y)$ is independent of $x$, and $X_1,\dots ,X_N$ are independent and identically distributed random variables with probability distribution $p$, even if $X_0$ was chosen arbitrarily in $S$. The method becomes ordinary Monte Carlo method sampling from $p$. The average of $f(X_1),\dots ,f(X_N)$ is an unbiased estimator, with the variance stated in part (a). Including an arbitrary initial state would spoil this finite-sample property. This is the independent stationary proposal lemma.

Let $\mu =\mathbb{E}[X_1]$ and ${\sigma }^2=\mathrm{Var}(X_1)\in (0,\infty )$. For independent and identically distributed random variables, the central limit theorem statesThe limit is the standard normal distribution. If the variance is zero, then $X_i=\mu$ almost surely; the centered sums are zero, and division by $\sigma$ is not defined.

The strong law of large numbers says that, for real independent and identically distributed random variables $Z_1,Z_2,\dots$ with $\mathbb{E}|Z_1|<\infty$,The assertion is almost sure convergence of the entire sequence of sample means. Finite first absolute moment suffices; a finite variance is not required.

Put $q=1-p$ and ${\xi }_i=Y_i-Y_{i-1}$. The Markov property and the state-independent transition probabilities show that, conditional on the whole previous history, ${\xi }_i$ is $+1$ with probability $p$ and $-1$ with probability $q$. Multiplying these conditional probabilities for any finite step sequence proves that the ${\xi }_i$ are independent and identically distributed random variables, withBecause $Y_n=k+{\sum }_{i=1}^n{\xi }_i$, the strong law of large numbers givesIn particular, $Y_n\to +\infty$ almost surely. This stronger pathwise consequence will determine both eventual crossings and the asymptotic first-passage times.

Let $Y_1,Y_2,\dots$ be real independent and identically distributed random variables with finite expected value $\mu$ and variance $0<{\sigma }^2<\infty$. The central limit theorem statesEquivalently, the cumulative distribution functions of these normalized sums converge at every real point to the standard normal distribution function. The theorem itself does not require a finite moment-generating function.

The unit-time increments $D_j=N_j-N_{j-1}$ are independent and identically distributed random variables, by independent increments and stationary increments of the Poisson process. Each has the Poisson distribution of parameter one, hence expected value one and variance one. The central limit theorem therefore gives

Set $T_0=0$ and $E_j=T_j-T_{j-1}$. The Poisson interarrival times $E_j$ are independent and identically distributed random variables with the rate-one exponential distribution. In particular, $\mathbb{E}{E}_j=1$ and $\mathrm{Var}(E_j)=1$, so the finite, positive variance hypothesis of the central limit theorem holds. Since $T_n={\sum }_{j=1}^n{E}_j$,

The strong law of large numbers states that, for independent and identically distributed random variables $X_1,X_2,\dots$ with $\mathbb{E}|X_1|<\infty$,Thus, outside an event of probability zero, the sample mean converges to the common expected value.

For independent and identically distributed random variables $X_j\sim \mathcal{N}(0,{\sigma }^2)$, the linear combination of independent normal random variables $n^{-1/2}{\sum }_{j=1}^n{X}_j$ has expected value zero and variance $n^{-1}n{\sigma }^2={\sigma }^2$. ThusThis is exactly the requested $2$-stability. The paper's definition is a strictly stable distribution, since it allows no centering term.

The moment-generating function of a standard normal distribution gives $\mathbb{E}[e^{t{X}_j}]=e^{t^2/2}$. Using independence of the coordinates,The accepted draws are independent and identically distributed random variables, so their sample mean is an unbiased estimator and has varianceThis counts $n$ accepted draws, requiring $n{\sigma }^d$ proposals in expectation.

Let $m=\mathbb{E}X$ and $v=\mathrm{Var}(X)$, evaluated from the given polylogarithm formulas. Generate a large sample of independent and identically distributed random variables with r_sample_f, and compute its sample mean ${\overline{X}}_n$ and sample variance $S_n^2$ using mean and var. The central limit theorem gives the first standardized check:For the second check, the correct asymptotic variance of the sample variance involves the fourth central moment ${\mu }_4=\mathbb{E}[(X-m{)}^4]$:The denominator is not $\sqrt{2v^2}$ unless the probability distribution has the requisite fourth central moment, as does the normal distribution. Here the probability density function decays exponentially, so all required moments are finite.

To compute ${\mu }_4$, expand the denominator of the probability density function as a geometric series and integrate each nonnegative term. The gamma function integral gives the raw momentsThus $v=m_2-m_1^2$ and ${\mu }_4=m_4-4m_1{m}_3+6m_1^2{m}_2-3m_1^4$. The following R code implements both checks for chosen interior parameters and large n:

p <- 0.4
beta <- 1.3
n <- 100000
raw_m <- vapply(1:4, function(j) {
  -factorial(j) * polylog(j + 1, 1 - p) / (beta^j * log(p))
}, numeric(1))
m <- raw_m[1]
v <- raw_m[2] - m^2
mu4 <- raw_m[4] - 4 * m * raw_m[3] +
  6 * m^2 * raw_m[2] - 3 * m^4
x <- r_sample_f(n, p, beta)
c(mean_check = sqrt(n) * (mean(x) - m) / sqrt(v),
  variance_check = sqrt(n) * (var(x) - v) / sqrt(mu4 - v^2))

For each check separately, an absolute value below $1.96$ is consistent with its approximate $95\%$ confidence interval. Repeat with many independent samples: the two standardized statistics should each resemble a standard normal distribution, with about $5\%$ outside that range. Also vary $p$, $\beta$ and n; a systematic discrepancy that grows with $\sqrt{n}$ suggests a bias. The two checks from the same sample are generally dependent, so passing both is not itself a joint $95\%$ statement, nor can a finite test prove that a generator is correct.

The second central limit theorem follows from the central limit theorem for the sample variance: $\sqrt{n}(S_n^2-v)$ differs by a quantity tending to zero in probability from $n^{-1/2}{\sum }_i[(X_i-m{)}^2-v]$.

Generate independent and identically distributed random variables $X_1,\dots ,X_n$ with probability density function $p$, evaluate $\varphi (X_i)$ for each draw, and return the Monte Carlo estimatorLinearity of expectation makes this an unbiased estimator: $\mathbb{E}{\hat{\theta }}_n^{\mathrm{MC}}=\theta$. Independence and the specified variance give $\mathrm{Var}({\hat{\theta }}_n^{\mathrm{MC}})=1/n$. Its Monte Carlo standard error is therefore $n^{-1/2}$, and the strong law of large numbers gives convergence to $\theta$ almost surely.

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.