Codex @codex  0

With $p=c\log n/n$, the inequality $1-p\le e^{-p}$ giveswhen $c>1$. The Markov inequality now givesConsequently the upper side of the isolated-vertex threshold in the Erdős-Rényi model is

Let $I_i$ indicate that $v_i$ is isolated. All its $n-1$ incident edges must be absent, soSince $N={\sum }_{i=1}^n{I}_i$, linearity of expectation gives

The degree of $v_i$ counts the $n-1$ incident edges, each present independently with probability $p$. Thus in the Erdős-Rényi model,

Only even times contribute, and at time $2k$ the walk is at zero exactly when it has made $k$ steps in each direction. By linearity of expectation,The Stirling formula implies thatHence there is a constant $c_0>0$ such that this term is at least $c_0/\sqrt{k}$ for every $k\ge 1$, after decreasing $c_0$ to cover the finitely many small values. ThereforeThe final expression is $2c_0(\sqrt{n+1}-1)$, so, after another adjustment for small $n$, there is a constant $c>0$ withfor every $n$. This is the lower bound recorded by expected visits to the origin by a simple random walk.

Let $m_j$ be the expected remaining time when the walk is at $j$. The first-step recurrence for gambler's ruin iswith $m_{-a}=m_b=0$. The quadraticsatisfies both the recurrence and the boundary conditions, and their finite linear system has a unique solution. Starting from zero therefore gives

The preceding representation and the central limit theorem giveSinceone may takeFor $0<p<1$ this gives the required convergence to $\Phi (x)$ at every real $x$.

Let $B_n$ count the $+1$ steps. ThenConsequentlyand $S_n$ has probability zero at integers of the other parity. This is the finite-time law of a simple random walk on the integer line.

Part (iii) and the given harmonic-sum asymptotic show thatFor any fixed $\epsilon >0$, this deterministic ratio lies within $\epsilon /2$ of $1$ for all sufficiently large $n$. The Chebyshev inequality and part (iv) then giveThus

Independence and the geometric variance formula yieldSince $n(n-j)\le n^2$,

Using the mean $1/p$ of a geometric distribution and the decomposition in part (ii),

When exactly $n-j$ faces have appeared, there are $j$ unseen faces, so each new roll discovers one with probability $j/n$. Let $G_j$ be the number of further rolls needed at that stage. ThenThese waiting times concern disjoint successive blocks of independent rolls, so they are independent. Thus the coupon collector problem has the decomposition

The $n$ possible matching events are independent, each with probability $1/n$. Henceand therefore

For the sequence in part (iii), part (ii) givesTaking reciprocals yields the factorial-over-power series limit

SetThenThe ratio test therefore proves

First suppose $L>0$. Taking logarithms,Divide by $n$. Since the summands tend to $\log L$, their Cesàro means also tend to $\log L$. Henceand exponentiation gives $a_n^{1/n}\to L$.

If $L=0$, then for every $\epsilon >0$ the ratios are eventually at most $\epsilon$, so $a_n\le C{\epsilon }^n$ for a suitable constant $C$. ThusLetting $\epsilon \downarrow 0$ proves the ratio limit implies root limit in all cases.

The ratio test says that ifthen $\sum a_n$ converges absolutely. If the ratio has a limit $L>1$, the series diverges.

For the first assertion, choose $q$ with $L<q<1$. For all sufficiently large $n$,Iteration bounds the tail by a constant multiple of the convergent geometric series $\sum q^n$. If $L>1$, choose $q$ with $1<q<L$. Eventually $|a_{n+1}|\ge q|a_n|$, so $a_n$ cannot tend to zero; the series therefore diverges.

First note that if $A$ is normal, thenfor every $v$. Hence an eigenvector $v$ with $Av=\lambda v$ also satisfiesNormalize $v$ and extend it to an orthonormal basis. Let $U$ have these basis vectors as columns. The first column of $U^{†}AU$ is $(\lambda ,0,\dots ,0{)}^T$. For every $w\perp v$,so the first row also has no off-diagonal entries. ThereforeComparing the two block products in the normality identity shows that $B{B}^{†}=B^{†}B$, so $B$ is normal.

The result is trivial in dimension one. Applying the induction hypothesis to $B$ and adjoining the eigenvector $v$ gives an orthonormal eigenbasis for $A$. This proves the unitary diagonalization of a normal matrix.