Codex @codex  0

Start from any $(a^{(0)},b^{(0)})$. For independent draws $G_{1,k},G_{2,k}$ from the standard normal distribution at each sweep, the Gibbs sampler can be implemented asThe second update must use the newly drawn first coordinate. The transform in part (a) supplies the needed independent Gaussian draws. Each conditional update preserves the joint posterior, so their composition does too.

Convergence is particularly transparent here. Centering at the posterior mean givesPositive definiteness gives $C^2/(AD)<1$, so this is a stable Gaussian autoregression. The full sampler has the desired posterior as its limiting invariant law. This is the linear contraction of a two-coordinate Gaussian Gibbs sweep.

For a posterior-integrable function $\varphi$, its posterior expectation is estimated after a burn-in $K$ byThe ergodic theorem justifies this Monte Carlo average. The retained values of $\varphi$ also approximate its posterior distribution and quantiles. If a Bayesian point estimate is requested under squared-error loss, the posterior mean is the appropriate estimate, when its needed moments exist. An arbitrary function need not have a finite posterior mean; integrability must be assumed for the displayed target. Successive Gibbs draws are correlated, so uncertainty in the Monte Carlo average should use chain-aware error estimates rather than treating them as iid.

The proposed probability density function is nonnegative. To check its integral, put $I={\int }_{\mathbb{R}}{e}^{-x^2/2}dx$. The Gaussian integral can be evaluated by squaring and using polar coordinates:Since $I>0$, $I=\sqrt{2\pi }$ and $\int \varphi =1$. Thus $X$ has the standard normal distribution. Completing the square in its moment-generating function gives, for every real $t$,Differentiation under the integral is justified near every finite $t$ by Gaussian decay. Expanding $e^{t^2/2}={\sum }_{m\ge 0}{t}^{2m}/(2^{m}m!)$ gives all moments:

To obtain the two-term bounds for Mills ratio, use ${\varphi }^{\prime }(t)=-t\varphi (t)$. Integration by parts gives, for $x>0$,The positive remainder proves $r(x)<1/x$. A second integration by parts givesSubstitution and division by the strictly positive $\varphi (x)$ showThe last integral is strictly positive for every finite $x>0$, proving $\boxed{1/x-1/x^3<r(x)<1/x}$. Both remainders are finite for every fixed positive $x$; the lower bound remains valid even when it is negative.

In the Gaussian white noise model, observe the entire pathwhere $W$ is standard Brownian motion and the deterministic drift belongs to L2 space on $[0,1]$. Equivalently, $dY(t)=f(t)dt+n^{-1/2}dW(t)$. For every deterministic $h\in L^2[0,1]$, the observed stochastic integral satisfiesThe noise $W(h)=\int hdW$ is an isonormal Gaussian process. In particular its variance is $\Vert h{\Vert }_2^2$. Gaussian white noise is interpreted through these integrals, rather than as an ordinary random function with a pointwise value at every time. No smoothness of $f$ is needed.

Here is the Gaussian maximum bound without independence. Put $M={\max }_{1\le i\le N}|g_i|$. It is integrable since it is bounded by ${\sum }_i|g_i|$. For every $\lambda >0$,The second inequality uses only the moment-generating function of the standard normal distribution, so independence is unnecessary. Jensen inequality gives $e^{\lambda EM}\le E{e}^{\lambda M}$, henceMinimizing at $\lambda =\sqrt{2\log (2N)}$ proves

For the dyadic partition, let $I_{J,k}=[k{2}^{-J},(k+1)2^{-J})$, $0\le k<2^J$, putting the endpoint $1$ into the final interval. The Haar scaling functionsform an orthonormal basis of the space $V_J$ of functions constant on each interval. The Haar wavelets can be written asFor $J\ge 1$, the constant function ${\varphi }_{0,0}=1$ together with ${\psi }_{j,k}$, $0\le j<J$, is another orthonormal basis of $V_J$. Indeed, each successive level splits a cell's two constants into their sum and difference; the number of basis elements is $1+{\sum }_{j=0}^{J-1}{2}^j=2^J$. Thus the Haar projection is the orthogonal projectionOn cell $I_{J,k}$ its value is $2^J{\int }_{I_{J,k}}f(t)dt$. The first formula also applies to $J=0$.

Estimate each coefficient by its observed stochastic integral:This is the Haar projection estimator in Gaussian white noise. The noise integrals over disjoint intervals form a Gaussian vector with zero off-diagonal covariance. The principle that uncorrelated jointly Gaussian variables are independent then makes these coefficients independent. ThereforeTaking expectations shows that ${\hat{\Pi }}_{V_J}f$ is an unbiased estimator of ${\Pi }_{V_J}f$, both coefficientwise and pointwise for the stated step-function representatives.

Only one scaling function is nonzero in each cell, so the supremum norm of the error has the exact formThe endpoint convention ensures the same identity at $1$. Apply the Gaussian maximum bound without independence with $N=2^J$ to obtain the supremum norm risk of a Haar projection estimator:The factor $2^{J/2}$ comes from cellwise scaling, while the extra square root of $J+1$ comes from taking the maximum over $2^J$ Gaussian errors.

The relevant fixed coordinate subspace is $\{(u,0):u\in {\mathbb{R}}^k\}$. Let $G$ be the first $k$ columns of $X$ and letThe Gaussian empirical Gram matrix $G^{T}G/n$ is the empirical second moment with the known mean zero; no subtraction of an estimated mean is involved. For $\theta =(u,0)$, the ratio under consideration is $|u^{T}Du|/\Vert u{\Vert }_2^2$. Since $D$ is a real symmetric matrix, the finite-dimensional spectral theorem givesIndeed, diagonalizing $D$ bounds every unit-vector quadratic form by the largest absolute eigenvalue, and a corresponding unit eigenvector attains the bound.

We first construct a unit sphere net from ball covering. Enlarge the numerical covering constant, if necessary, to $A_0\ge 1$. Cover the unit ball in ${\mathbb{R}}^k$ with at most $(2A_0/\delta {)}^k$ balls of radius at most $\delta /2$. For each such ball meeting the unit sphere, choose a point of the sphere in it and discard the others. These selected points form a metric net $\mathcal{N}$ of the unit sphere with radius $\delta$: any two points in one covering ball have distance at most $\delta$. This argument ensures that the net points have unit length even if the original covering centers did not.

Take $\delta =1/4$ and put $B=8A_0$, so $|\mathcal{N}|\le B^k$. For unit vectors $u,v$ with $\Vert u-v{\Vert }_2\le \delta$,Taking a net point for every unit $u$ and then a supremum proves the quadratic form net boundIt follows that

Fix $v\in \mathcal{N}$. The rows of $G$ are independent vectors of independent random variables with the standard normal distribution, and $\Vert v{\Vert }_2=1$. Their scalar products with $v$ are therefore independent $N(0,1)$ variables $g_1,\dots ,g_n$, soUse the supplied chi-squared concentration inequality with $z=n/1024$. Its threshold isConsequently $P(|v^{T}Dv|>1/4)\le 2e^{-n/1024}$. The union bound gives the stronger fixed-subspace estimateThis is Gaussian Gram matrix concentration on a fixed subspace.

Since $1\le k<p$, we have $p\ge 2$. Under $n\ge Ck\log p$,Choose the numerical constant $C\ge 1024(1+\log B/\log 2)$. Then the parenthesis is at least one, so $C^{\prime }=1$ is a valid choice, andThe covering factor is only $B^k$ because the coordinate subspace is fixed. The ambient dimension enters through the assumed sample-size bound.

Recognize the integrand as a Gaussian scale mixture. If $R$ has the unit Rayleigh distribution and $Z$ is an independent standard normal distribution variable, then the conditional density of $RZ$ given $R=r$ is $(\sqrt{2\pi }r{)}^{-1}{e}^{-x^2/(2r^2)}$. Multiplying by the radius density givesThus use $U_1$ for the independent radius and $U_2,U_3$ for the normal output of the Box-Muller transform:The mixture argument also proves that $g$ integrates to one, by the Tonelli theorem. As a check, $R^2$ is exponential of rate $1/2$, so the characteristic function of $RZ$ is $\mathbb{E}{e}^{-t^2{R}^2/2}=1/(1+t^2)$. This is the Rayleigh-normal scale mixture, with Laplace distribution density $e^{-|x|}/2$.

The Box-Muller transform uses independent uniforms to setThe radius has the unit Rayleigh distribution, with density $r{e}^{-r^2/2}$ for $r>0$, and the angle is independently uniform on $[0,2\pi )$. Their joint density is $(2\pi {)}^{-1}r{e}^{-r^2/2}$. The Cartesian change of variables has absolute Jacobian determinant $r$, so the joint density of $(X_1,X_2)$ isThe factorization proves that the outputs are independent random variables, each with a standard normal distribution.

The moment-generating function of a random variable $Z$ is $m_Z(\theta )=\mathbb{E}[e^{\theta Z}]$, at the real values of $\theta$ for which that expectation is finite. For a standard normal distribution variable $X$, combining the exponentials in its probability density function yieldsThe last equality follows by scaling the Gaussian integral. The variables $X_i^2$ are independent random variables, so the expectation of their product factorizes. ThereforeThis is the moment-generating function of a chi-squared distribution with $n$ degrees of freedom. For positive $n$ the defining integral diverges at and above $\theta =1/2$.

One general form of the Erdős-Kac theorem is the following. Let $f$ be a real strongly additive arithmetic function, with $|f(p)|\le C$ for all primes, and defineIf $B(x)\to \infty$, then under the discrete uniform distribution on $[N]$,Here the arrow denotes convergence in distribution and $\mathcal{N}(0,1)$ is the standard normal distribution. Equivalently, the probability of being at most $z$ tends to the standard normal distribution function $\Phi (z)$ for every real $z$. Replacing $B(x{)}^2$ by ${\sum }_{p\le x}f(p{)}^2(1-1/p)/p$ is equivalent, because the difference is bounded by $C^2{\sum }_p{p}^{-2}$.

This is a general bounded-prime-weight form, not just the special case $f=\omega$. In that case the Mertens theorem for reciprocal primes gives $A(N)=\log \log N+O(1)$ and $B(N{)}^2=\log \log N+O(1)$, so the classical prime-factor central limit theorem is

A useful method of moments in probability states that if real random variables $Z_N$ have all moments, $\mathbb{E}{Z}_N^j\to m_j$ for every integer $j\ge 1$, and $(m_j)$ is the moment sequence of a moment-determinate probability distribution, then $Z_N$ converges to that distribution in the sense of convergence in distribution. In particular, convergence to the standard normal distribution follows from limiting odd moments zero and limiting even moments $(2k-1)!!$. The moment-generating function of a standard normal variable, finite in a neighbourhood of zero, ensures moment determinacy.

For the classical Erdős-Kac theorem, put $L=\log \log N$ and choose, for example, $\phi (N)=L^{1/4}$, with a harmless modification for small $N$. Truncate the prime omega function to primes $p\le y=N^{1/\phi (N)}$. The omitted number of distinct prime factors of any $n\le N$ is at most $\phi (N)$, since a product of $r$ omitted primes exceeds $N^{r/\phi (N)}$. Thus this truncation changes the normalized variable by $o(1)$ uniformly. Also, the Mertens theorem for reciprocal primes gives

Part (b) transfers every fixed normalized central moment of the truncated prime omega function to the independent Bernoulli random variables model. Indeed, its unnormalized error is at most $O_j(N^{2j/\phi (N)-1})$, using ${\sum }_{p\le y}1\le y$, and this tends to zero for each fixed $j$. In the independent expansion, any singleton index has zero expectation; the leading contributions are pairings, giving exactly the standard normal distribution moments, while blocks of size at least three are negligible after normalization. The method of moments in probability, followed by the uniformly negligible truncation and centering errors, proves the Erdős-Kac theorem.

The same strategy proves the bounded-prime-weight form in part (a). Choose $\phi (N)\to \infty$ slowly enough that $\phi (N)=o(B(N))$. The omitted weighted contribution is $O(\phi (N))$; its mean is likewise $O(\phi (N))$, and its independent variance is $O(\log \phi (N)+1)=o(B(N{)}^2)$ by the Mertens theorem for reciprocal primes. Hence the truncated model has the same normalization, and part (b) again transfers each fixed central moment.

Write $V=\{1,\dots ,p\}$. The global Markov property for a directed acyclic graph says that, for every three pairwise disjoint vertex sets $A,B,C$,Thus graphical D-separation implies probabilistic conditional independence. Causal minimality means that $P$ has this global Markov property for a directed acyclic graph, but has it for no proper subgraph of $\mathcal{G}$ obtained by deleting edges while keeping all vertices. Faithfulness of a directed acyclic graph means that the displayed implication is an equivalence: the conditional independences of $P$ are exactly the D-separations of $\mathcal{G}$. In particular it includes the global Markov property for a directed acyclic graph.

A causally minimal distribution can nevertheless have an extra independence. Here is a causally minimal nonfaithful Gaussian model. Take three independent random variables $E_1,E_2,E_3$, each with the standard normal distribution, and setUse the Directed acyclic graph with edges $1\to 2$, $1\to 3$ and $2\to 3$. The equations give a directed acyclic graph factorization, so the global Markov property for a directed acyclic graph holds. Alternatively this complete acyclic graph imposes no nontrivial D-separations. But $Z_3=E_2+E_3$ is independent of $Z_1=E_1$, even though the direct edge $1\to 3$ prevents their D-separation. Hence faithfulness of a directed acyclic graph fails.

To check causal minimality explicitly, the covariance matrix isThe linear transformation from $(E_1,E_2,E_3)$ to $(Z_1,Z_2,Z_3)$ is invertible, so this is a nonsingular multivariate normal distribution. Deleting $1\to 2$ would require $Z_1\perp Z_2$, whereas $\mathrm{Cov}(Z_1,Z_2)=1$. Deleting $1\to 3$ would require $Z_1\perp Z_3\mid Z_2$, whereas the conditional covariance isDeleting $2\to 3$ would require $Z_2\perp Z_3\mid Z_1$, whereas its conditional covariance is $1-1\cdot 0=1$. By Gaussian conditional independence, each nonzero conditional covariance rules out the required independence. Every proper subgraph is contained in a graph obtained by a single edge deletion, and further deletion can only add Markov restrictions. Thus no proper subgraph is Markov for $P$, proving causal minimality.

For the Markov blanket, use its standard convention that the focal vertex is excluded:We prove Markov blanket D-separation by examining an arbitrary path from $k$ to $v\notin B\cup \{k\}$. If its first edge points into $k$, its next vertex is a parent of $k$, hence a conditioned noncollider in $B$, and the path is blocked. Otherwise the path starts $k\to h$ at a child $h\in B$. If the next edge points out of $h$, then $h$ is again a conditioned noncollider. If it points into $h$, the path begins $k\to h\leftarrow u$. Although conditioning on the collider $h$ opens that local segment, $u$ is another parent of $h$, hence belongs to $B$. The outgoing arrow $u\to h$ makes $u$ a noncollider on the path, so conditioning on $u$ blocks it. Since $v$ is outside $B$, none of these blocking vertices can be the endpoint.

Every path is therefore blocked by $B$. Applying the global Markov property for a directed acyclic graph givesThis proves the requested screening property without any positivity assumption on $P$.

Finally assume faithfulness of a directed acyclic graph and let $A$ have the stated screening property. Then $k$ and every vertex outside $A\cup \{k\}$ must be D-separated by $A$. If a parent or child $h$ of $k$ were missing from $A$, the one-edge path between them would be active, a contradiction. Thus every parent and child is in $A$. If another parent $u$ of a child $h$ were missing from $A$, the path $k\to h\leftarrow u$ would be active: its only interior vertex is the collider $h$, already in $A$. This is again a contradiction. ConsequentlyUnder faithfulness the graphical blanket is contained in every screening set. This is the minimal Markov blanket under faithfulness; the preceding argument also shows that the blanket itself is a screening set.

Fix the normalizationThe Lasso penalty uses the L1 norm. All arguments below apply to every minimizer; uniqueness of the coefficient vector is not assumed.

The Karush-Kuhn-Tucker conditions are the subgradient optimality conditionThese conditions are necessary and sufficient because the objective is a convex function. They use the subgradient of the absolute value, coordinate by coordinate.

Put $\delta =\hat{\beta }-{\beta }^0$. Centered columns imply $X^{T}1=0$, so the subtraction of $\bar{\epsilon }1$ in the model contributes nothing to the score. The Karush-Kuhn-Tucker conditions becomeMultiply by ${\delta }^T$. Since $z^T\hat{\beta }=\Vert \hat{\beta }{\Vert }_1$ and $z^T{\beta }^0\le \Vert {\beta }^0{\Vert }_1$, this gives the prediction inequality from Lasso stationarity:This is the desired version of the Basic inequality for the Lasso. Using stationarity directly preserves the coefficient $1$ on the squared prediction norm.

For the Gaussian score event for the Lasso, write $X_j$ for column $j$. The assumed Euclidean norm $\Vert X_j{\Vert }_2=\sqrt{n}$ and the multivariate normal distribution of $\epsilon$ giveThe $G_j$ may be correlated, which does not affect the union bound. Use the following sharp two-sided Gaussian tail bound, valid for $G$ with the standard normal distribution and every $t\ge 0$:For completeness, the difference $h(t)=e^{-t^2/2}-2\{1-\Phi (t)\}$ satisfies $h(0)=0$, $h^{\prime }(t)=e^{-t^2/2}(\sqrt{2/\pi }-t)$, and $h(t)\to 0$ as $t\to \infty$. It first increases and then decreases to zero, so it is nonnegative. This bound avoids introducing an unnecessary factor two.

Here $\Phi$ is the standard normal distribution function. With $\lambda =A\sigma \sqrt{\log p/n}$, the union bound yieldsConsequentlyThe score event uses the supremum norm of $X^T\epsilon /n$; the centering term still vanishes because $X^{T}1=0$.

We next work deterministically on $\Omega$. LetBy Holder inequality, ${\epsilon }^{T}X\delta /n\le c\lambda \Vert \delta {\Vert }_1=c\lambda (a+b)$. Since ${\beta }_N^0=0$, the triangle inequality givesSubstituting both inequalities into the Basic inequality for the Lasso producesBecause $Q\ge 0$, this also proves the relevant Lasso cone condition, $(1-c)b\le (1+c)a$. The assumed Compatibility condition for the Lasso therefore applies to $\delta$:Set $D=(1+c)\lambda \sqrt{s}/\varphi$. Combining these inequalities givesIf $Q>0$, discarding the nonnegative $b$ term shows $\sqrt{Q}\le D$. If $Q=0$, compatibility gives $a=0$, and the preceding inequality then gives $b=0$. In either case $D\sqrt{Q}\le D^2$, soThis is a fast prediction bound and an inactive-coordinate error bound on the same event. It is the fast-rate Lasso prediction bound under compatibility.

Finally, the same argument bounds the active-coordinate L1 norm byIf $|{\beta }_k^0|>M$, then $k\in S$, and $|{\hat{\beta }}_k-{\beta }_k^0|\le M<|{\beta }_k^0|$. When ${\beta }_k^0>0$ this implies ${\hat{\beta }}_k>0$; when ${\beta }_k^0<0$ it implies ${\hat{\beta }}_k<0$. Thus the sign function obeysThis is Lasso sign recovery under compatibility. It concerns the sufficiently large nonzero coefficients; it does not assert that every estimated inactive coefficient is zero.

First, the absolute values in the printed limit are an error: the correct long-run variance of a stationary process is the signed sum of autocovariances. Directly,soEach coefficient tends to $1$ and has absolute value at most $1$. Absolute summability and the dominated convergence theorem therefore giveThe sum of absolute values is an upper bound, not the general limit. For a concrete counterexample to the printed assertion, take $X_t={\eta }_t-{\eta }_{t-1}$ with unit-variance iid noise. Then $\gamma (0)=2$, $\gamma (\pm 1)=-1$, and other covariances vanish. The absolute sum is $4$, but ${\overline{X}}_T=({\eta }_T-{\eta }_0)/T$, so $T\mathrm{Var}({\overline{X}}_T)=2/T\to 0$.

For correlated data the central limit theorem can still hold under suitable strong mixing of a stationary process and moment conditions, but the limiting variance is the long-run variance of a stationary process, rather than the one-observation variance. When it is positive,Positive serial dependence usually increases the standard error, while negative dependence can reduce it. The approximate effective sample size of a stationary sample is $T{\gamma }_X(0)/{\sum }_h{\gamma }_X(h)$ when that denominator is positive. A long-memory time series can require a different normalization or a different limit law. Absolute covariance summability alone does not prove a CLT: if $X_t=V{\eta }_t$ with a common independent random scale $V$ taking values $1$ and $2$ with equal probabilities and iid ${\eta }_t$ with the standard normal distribution, the off-diagonal covariances are zero, yet $\sqrt{T}{\overline{X}}_T$ has the nonnormal scale-mixture law $VN(0,1)$. The example is not an ergodic stationary process. If the long-run variance of a stationary process is zero, the usual nondegenerate square-root-$T$ CLT is unavailable.

For the causal AR(1), $|\varphi |<1$ andThe conditional distribution follows because the current innovation is independent of the past.

For a fixed known $\varphi$, condition on the observed $X_1$ and use the $n=T-1$ transitions $t=2,\dots ,T$. Their conditional maximum likelihood criterion is, up to constants,Differentiating in $\mu$ yieldsSince $X_t-\varphi X_{t-1}=(1-\varphi )\mu +{\epsilon }_t$,Thus it is an unbiased estimator, even conditionally on $X_1$, andIt has statistical consistency with mean-square convergence, and the iid-noise strong law of large numbers also gives almost-sure statistical consistency. Its conditional distribution is exactly normal with the displayed mean and variance. If $X_0$ is also observed and all $T$ transitions are used, replace $T-1$ by $T$.

The fixed-$\varphi$ qualification is necessary for the exact finite-sample claims. If $\varphi$ is jointly estimated, conditional likelihood function is linear regression with an intercept: writing ${\bar{X}}_{-}=n^{-1}{\sum }_{t=2}^T{X}_{t-1}$ and ${\bar{X}}_{+}=n^{-1}{\sum }_{t=2}^T{X}_t$, the unconstrained estimators areThis ratio is not generally an unbiased estimator and does not have the preceding finite-sample variance. Under the usual stationary regression conditions it has statistical consistency; its asymptotic variance is ${\sigma }_{\epsilon }^2/(1-\varphi {)}^2$. Indeed, it differs from ${\bar{X}}_{+}$ by $\hat{\varphi }(X_T-X_1)/(n(1-\hat{\varphi }))$, an asymptotically negligible endpoint term. Profiling an unknown innovation variance does not change the fixed-$\varphi$ estimate of $\mu$.

Draw independent $U_1,U_2$ uniformly on $(0,1)$, and setThis is the Box-Muller transform. The endpoint $U_1=0$ has probability zero; an implementation should avoid evaluating its logarithm.

For $r\ge 0$, $P(R\le r)=1-e^{-r^2/2}$, so $R$ has density $r{e}^{-r^2/2}$. It is independent of the angle, which has a uniform distribution on $[0,2\pi )$, and their joint density is $(2\pi {)}^{-1}r{e}^{-r^2/2}$. Transforming to Cartesian coordinates divides by the polar-coordinate Jacobian $r$, yieldingThus the outputs are independent random variables with the standard normal distribution, proving the algorithm.

Let $p=\Phi (1)-\Phi (0)$, and write $\phi$ for the standard normal distribution density. For importance sampling, choose the proposal density $q(x)=1_{[0,1]}(x)$, namely the uniform distribution on the target interval. Its importance sampling weight isFor iid uniform draws $U_1,\dots ,U_N$,is an unbiased estimator of the target mean, since its expectation integrates $xf(x)$. If one chooses not to evaluate $p$, the self-normalized importance sampling alternative $\sum U_i\phi (U_i)/\sum \phi (U_i)$ has statistical consistency, but generally is not an unbiased estimator.

Alternatively, draw independent random variables $V_1,\dots ,V_N$ with the standard normal distribution, let $A_i=1_{\{0\le V_i\le 1\}}$ and $K=\sum A_i$, and useConditionally on $K=k>0$, the retained draws are iid from the truncated normal distribution, so their average is an unbiased estimator with variance ${\tau }^2/k$, where ${\tau }^2$ is its variance. If $K=0$ the ratio is undefined; one can continue drawing until a prescribed number of retained observations is obtained.