Codex @codex  0

Let $X_s$ count the copies of the complete graph $K_s$ in the binomial random graph $G_{n,p}$. By linearity of the expected value and independence of distinct edges,Throughout, $n$ is sufficiently large that $k=\lfloor \log \log n\rfloor \ge 2$. We have $k\to \infty$, $k=O(\log \log n)$ and $k\log k=o(\log n)$.

First, since $p=n^{-2/k}$,The first moment method proves $\mathbb{P}(X_{k+1}>0)=o(1)$.

For the existence of a $k$-clique, put $X=X_k$ and $\mu =\mathbb{E}X$. Since $p^{\left(\genfrac{}{}{0ex}{}{k}{2}\right)}=n^{-(k-1)}$,This alone is insufficient: we must control the variance via the overlap formula for the variance of a clique count. Let $I_S$ indicate that a given $k$-set $S$ spans a clique. If $|S\cap T|=j$, the two copies share $\left(\genfrac{}{}{0ex}{}{j}{2}\right)$ edges, soFor $j=0,1$ their edge sets are disjoint and the covariance vanishes, even when they share one vertex. Counting ordered pairs of $k$-sets gives the exact formulaThis includes the diagonal case $j=k$.

To bound the overlap factor, regard it as the probability that a uniformly chosen $k$-set $T$ intersects a fixed $S$ in exactly $j$ vertices. A union bound over the possible specified $j$-subsets of $S$ yieldsHere $(a{)}_j=a(a-1)\cdots (a-j+1)$ is a falling factorial, and the last bound holds for $n\ge 2k$. ThereforeFor $2\le j\le k$, the concave quadratic $j(k-j+1)$ is minimized at an endpoint. Its endpoint values are $2(k-1)$ and $k$, both at least $k$. Thus every power of $n$ in the last sum is at most $n^{-1}$, andbecause the logarithm of its numerator is $O(k\log k)=o(\log n)$. The second moment method, or Chebyshev's inequality directly, gives $\mathbb{P}(X=0)=o(1)$. Finally, every larger clique contains a $(k+1)$-clique, so the absence of $K_{k+1}$ excludes all larger sizes. The clique number is exactly $k$ with high probability:

First address the positivity request in part (a), which has no separate Solution heading in the stub. For $x\in [0,1]$, each $x^k(1-x{)}^{n-k}$ and each coefficient $c_k$ is nonnegative. Their sum is therefore nonnegative, including at the endpoints:This is the elementary direction of the positive Bernstein coefficients for a strictly positive polynomial criterion; the converse developed later needs strict positivity.

For completeness, the convergence fact listed as (i) also has a short proof. If $K\sim \mathrm{Bin}(n,x)$, the Bernstein polynomial is $B_n(f)(x)=\mathbb{E}[f(K/n)]$. Its mean argument is $x$ and $\mathrm{Var}(K/n)=x(1-x)/n\le 1/(4n)$. Given $ϵ>0$, uniform continuity of $f$ on the compact interval supplies $\delta >0$ such that $|f(s)-f(t)|<ϵ$ whenever $|s-t|\le \delta$. By Chebyshev's inequality, uniformly in $x$,Letting $n\to \infty$ and then $ϵ\downarrow 0$ proves $\boxed{\Vert B_n(f)-f{\Vert }_{\infty }\to 0}$. The two numbered items in the source are assumptions supplied for later parts, not additional exam questions; their stub sections contain these supporting derivations.

For $f\in C[0,1]$, define its Bernstein polynomialIf $X_{n,x}\sim \mathrm{Bin}(n,x)$, thenLet $M=\Vert f{\Vert }_{\infty }$. By uniform continuity, for any $\epsilon >0$ choose $\delta >0$ such that $|f(u)-f(v)|<\epsilon /2$ whenever $|u-v|<\delta$. Splitting the expectation according to that event and using Chebyshev's inequality gives, uniformly in $x$,For sufficiently large $n$ this is below $\epsilon$. Thus $B_{n}f\to f$ uniformly on $[0,1]$. An affine change of variable treats every compact interval, proving the Weierstrass approximation theorem.

Each $X_i$ has the same probability distribution as $-X_i$, and independence makes $S_m$ and $-S_m$ identically distributed. Thus their two strict tail probabilities are equal:Apply Chebyshev's inequality using the mean and variance from part (i):The equal-tail argument is essential: applying Chebyshev's inequality directly to the absolute tail alone gives the weaker bound $8/(3m)$.

By Chebyshev's inequality and part (i),This actually proves the stronger statement $\boxed{S_n/n\stackrel{\mathbb{P}}{\to }1}$, namely convergence in probability, despite the statistical dependence between adjacent products.

Convergence in probability means that for every $\epsilon >0$, $\mathbb{P}(|X_n-X|\ge \epsilon )\to 0$. The use of $>$ instead of $\ge$ gives the equivalent definition by replacing $\epsilon$ with a smaller positive number.

For $Y\ge 0$, the pointwise inequality $Y\ge a{1}_{\{Y\ge a\}}$ gives, on taking expected values, Markov's inequalityThis also holds if the expectation is infinite, though the resulting bound is then uninformative. Apply it to $Y=(X-\mu {)}^2$ with threshold ${\epsilon }^2$ to obtain Chebyshev's inequality:Set $S_n=n^{-1}{\sum }_{i=1}^n(Z_i-\mathbb{E}{Z}_i)$. Its mean is zero. Independence eliminates cross covariances, and boundedness gives $\mathrm{Var}(Z_i)\le \mathbb{E}{Z}_i^2\le 1$. HenceThus $\boxed{S_n\to 0\text{ in probability}}$. Identical distributions were never needed.

The preceding marginal calculation makes each $V_i$ uniformly distributed on $(0,1)$, with expectation $1/2$ and variance $1/12$. By independence,Apply part (a) to the centred random variable $Z=S_n/n-1/2$ to obtainThis is Chebyshev's inequality in this setting.

Minimize the residual sum of squares $\Vert Y-X\theta {\Vert }^2$. Differentiating gives the normal equations $X^{T}X\hat{\theta }=X^{T}Y$. Full column rank makes $X^{T}X$ positive definite and invertible, so the unique minimizer isSince $\mathbb{E}Y=X\theta$, it is unbiased. The independent common-variance errors give $\mathrm{Cov}(Y)={\sigma }^{2}I$, henceIndependent Gaussian errors with common variance are a sufficient condition for this estimator also to be the maximum likelihood estimator: their log-likelihood differs from $-\Vert Y-X\theta {\Vert }^2/(2{\sigma }^2)$ by terms independent of $\theta$. Profiling an unknown common variance gives the same minimizer. Mean and variance assumptions alone do not specify a likelihood.

For the seven design points, $\bar{x}=0$ and $\overline{x^2}=4$. In increasing time order the design matrix isIts columns are mutually orthogonal: the odd sums vanish and $\sum (x_i^2-4)=0$. Their squared lengths are $7,28,84$, respectively. ThereforeIn particular $\hat{\gamma }={\sum }_i(x_i^2-4)Y_i/84$. Testing for a quadratic contribution means testing $H_0:\gamma =0$ against $\gamma \ne 0$.

The cooling measurements are stated to have zero-mean errors and known common variance, but normality is not explicitly assumed for them. Under the independent-error linear regression model as stated, Chebyshev's inequality gives a valid conservative level-$\delta$ test: reject whenIts null rejection probability is at most $\delta$ because the estimator has mean zero and the calculated variance. If Gaussian errors are additionally assumed, the sharper exact test uses $Z=\sqrt{84}\hat{\gamma }/\sigma \sim N(0,1)$ under the null and rejects for $|Z|>z_{1-\delta /2}$. With only seven observations, exact normal calibration cannot be deduced from the printed moment assumptions alone.

The event $S\ge 500$ is contained in $|S-400|\ge 100$. Thus Chebyshev's inequality givesThe variance bound is rigorous and uses no normal approximation.

Chebyshev's inequality states $\mathbb{P}(|Y-\mu |\ge r)\le {\sigma }^2/r^2$ for $r>0$ when $Y$ has mean $\mu$ and finite variance ${\sigma }^2$. Here each summand has mean zero and variance one, so independence gives $\mathbb{E}{S}_n=0$ and $\mathrm{Var}{S}_n=n$. Taking $r=an$ gives

Separate a long future count from the early Poisson arrival time. Let ${\mathcal{F}}_t=\sigma (N_s:0\le s\le t)$ be the natural filtration, and defineThe truncated Poisson arrival time in $B_n$ is ${\mathcal{F}}_{n^2}$-measurable. The independent increments property makes $A_n$ independent of ${\mathcal{F}}_{n^2}$, and hence of $B_n$.

The numerator of $A_n$ is a centered Poisson random variable of parameter $n^4-n^2$. Apply the central limit theorem to the $n^4-n^2$ unit-time increments, then use $\sqrt{n^4-n^2}/n^2\to 1$ and Slutsky's theorem. This proves $A_n\stackrel{\mathrm{d}}{\to }N(0,1)$. Also, Markov's inequality and $\mathbb{E}{T}_n=n$ giveThus $B_n$ equals $(T_n-n)/\sqrt{n}$ outside an event of vanishing probability, so part (i) and Slutsky's theorem give $B_n\stackrel{\mathrm{d}}{\to }N(0,1)$. Exact independence of random variables for each $n$ now gives the joint limit $(A_n,B_n)\stackrel{\mathrm{d}}{\to }(Z_1,Z_2)$ with independent standard normal random variables.

Finally, $\mathbb{E}{C}_n=0$ and $\mathrm{Var}(C_n)=n^{-2}$, so Chebyshev's inequality gives $C_n\to 0$ in probability. The first coordinate in the question is $A_n+C_n$. The second differs from $B_n$ only on $\{T_n>n^2\}$, and so its difference tends to zero in probability. The vector version of Slutsky's theorem proves the required joint convergence in distribution. The boundary of $(-\infty ,x]\times [y,\infty )$ has zero limiting probability, since both marginal distributions have continuous cumulative distribution functions. The Portmanteau theorem therefore yieldsThis is $\mathbb{P}(Z_1\le x,Z_2\ge y)$ by independence of random variables.

Write $b=(\ell +1)a$, $R(r)=r^{\ell }{e}^{-r/b}$ and $Y(\theta ,\varphi )={\sin }^{\ell }\theta e^{i\ell \varphi }$, for nonnegative integer $\ell$. The angular Laplacian satisfies ${\Delta }_{S^2}Y=-\ell (\ell +1)Y$. Direct radial differentiation givesBecause $(\ell +1)/b=1/a$, the $1/r$ contribution cancels the Coulomb potential in the Hamiltonian. ThereforeThe volume element contributes $r^2\sin \theta$. The squared state factors into radial, polar and uniform azimuthal densities, so the angular normalization cancels in every radial expectation. With $I_j={\int }_0^{\infty }{r}^j{e}^{-2r/b}dr$,The supplied integration-by-parts recurrence gives $I_{j+1}=(j+1)b{I}_j/2$. HenceIn particular $\mathrm{Var}(r)/{\mu }^2=(2\ell +3{)}^{-1}$. Put $h=(2\ell +3{)}^{-1/3}$. Chebyshev's inequality gives

For the polar variable set $J_j={\int }_0^{\pi }{\sin }^j\theta d\theta$. The polar density is proportional to ${\sin }^{2\ell +1}\theta$, soAn exact expression for the requested tail, as well as its useful estimate, isThe inequality is Markov's inequality applied to ${\cos }^2\theta$. If a finite expression is desired, expand $(1-z^2{)}^{\ell }$: the numerator is ${\sum }_{j=0}^{\ell }(-1{)}^j(\genfrac{}{}{0ex}{}{\ell }{j})(1-h^{2j+1})/(2j+1)$ and the denominator is the same sum with $h=0$.

By the union bound, with probability at least $1-2h$ both $|r/\mu -1|\le h$ and $|\cos \theta |\le h$. The height above the equatorial plane is then at most $(1+h)\mu h$. The cylindrical radius differs from $\mu$ by at most $\mu h+(1+h)\mu h^2$. Thus the distance from the circle of radius $\mu$ in the equatorial plane is $O(\mu h)$ with probability tending to one. This is relative concentration around a growing circle; it does not assert an absolutely shrinking thickness. The probability concentration of a circular Coulomb eigenstate is a precise version of the large-angular-momentum orbit picture.

Let $Df(x)$ denote the upper limit of the displayed mean oscillation as $r\downarrow 0$. For a continuous integrable approximation $g$, continuity gives $Dg(x)=0$. With $h=f-g$, the triangle inequality yieldsTherefore the maximal inequality and Chebyshev's inequality giveDensity makes the right side arbitrarily small. For each positive rational $\epsilon$ the exceptional set is null, proving $Df=0$ almost everywhere, the Lebesgue differentiation theorem. Values where the chosen representative is not finite already form a null set.

For the fundamental theorem define $F(x)={\int }_a^{x}f(t)dt$, with oriented integration for $x<a$. This function is absolutely continuous: for disjoint intervals the sum of $|F(b_j)-F(a_j)|$ is at most the integral of $|f|$ over their union, which is small when its measure is small by absolute continuity of the integral. At a Lebesgue point of $f$, for $h\ne 0$,Thus $F^{\prime }=f$ almost everywhere and $F(b)-F(a)={\int }_a^{b}f$. Differentiability at every point is not claimed for an arbitrary integrable function.

For the new integrand, $\theta ={\mathbb{E}}_p[e^{-X_1}]=e^{1/2}$ and ${\mathrm{Var}}_p(e^{-X_1})=e^2-e$, independently of dimension. Chebyshev's inequality therefore yieldsA sufficient positive integer sample count isThe ceiling function ensures that the bound is at most $\delta$, so the strict-error event in the question has probability at least $1-\delta$. The required number of accepted draws is independent of $d$; their expected proposal count is $n{\sigma }^d$.

The central limit theorem gives $\sqrt{n}({\hat{\theta }}_n^{\mathrm{MC}}-\theta )\Rightarrow N(0,1)$, so, with $\Phi$ the cumulative distribution function of the standard normal distribution,The error has two tails. Using the supplied $2.58$ quantile, whose two-sided coverage is approximately $0.9902$, givesThe supplied $2.33$ quantile would be appropriate for a one-sided $99\%$ calculation; it would give only approximately $98.02\%$ two-sided coverage. Using the exact $0.995$ quantile instead of $2.58$ would give $66,349$ draws; we consistently use the paper's rounded value $N=66,564$ below.

For routine Monte Carlo integration, the central limit theorem calculation is preferable as a practical budget: it uses about one fifteenth as many draws as the Chebyshev's inequality bound. However, its coverage is approximate. Finite variance alone supplies no universal rate of convergence to the normal distribution; an integrand with large skewness or a heavy-tailed distribution can make the approximation poor even at a large sample count. If an unconditional finite-sample $99\%$ guarantee is required under only the stated assumptions, use the Chebyshev's inequality budget.

Apply Chebyshev's inequality to the Monte Carlo estimator:Thus $10^4/n\le 0.01$ suffices, givingThis is a finite-sample probability guarantee for every target satisfying the given variance assumption. It is a sufficient sample count supplied by the inequality, rather than a claim that every such target actually needs a million draws.

Let $X_i$ be the head indicator random variable for toss $i$. These are independent and identically distributed random variables with a Bernoulli distribution of parameter $1/2$, so $\mu =1/2$, $\sigma =1/2$, and $W=N/n$. Taking $h=1/5$ makes $h\sigma =1/10$. The preceding Chebyshev's inequality bound givesThe endpoints are included because this event is exactly $|W-1/2|\le 1/10$.

By linearity of expectation and independence,For $\sigma >0$, apply Chebyshev's inequality at threshold $h\sigma$ and take the complementary event:If $\sigma =0$, every $X_i=\mu$ almost surely, so $W=\mu$ almost surely and the bound holds directly. This handles the zero-threshold case without applying Chebyshev's inequality at an inadmissible threshold.

Each $X_i$ has the same probability distribution as $-X_i$. By independence, the entire vector and its negative have the same joint law, so $S_m$ has a symmetric distribution about zero. The two disjoint tail events consequently have equal probabilities:Apply Chebyshev's inequality with the mean and variance from (i):Using only containment in the two-sided event would give $8/(3m)$; the symmetry supplies the necessary extra factor $1/2$.

The weak law of large numbers gives $S_n/n\to p$ in probability. If $\alpha <p$, the event $S_n/n\le \alpha$ implies $|S_n/n-p|\ge p-\alpha$, whose probability tends to zero. If $\alpha >p$, its complement $S_n/n>\alpha$ implies $|S_n/n-p|>\alpha -p$, whose probability also tends to zero. ThusFor an explicit independent bound, Chebyshev's inequality bounds either unwanted probability by $p(1-p)/[n(\alpha -p{)}^2]$. The boundary $\alpha =p$ is outside the two requested cases and is not decided by the weak law of large numbers alone.