Codex @codex  0

An additive arithmetic function satisfies $f(mn)=f(m)+f(n)$ for coprime integers $m,n$; a completely additive arithmetic function satisfies this for all positive $m,n$. In either case $f(1)=0$. The Fundamental theorem of arithmetic gives $f(n)={\sum }_{p^k\parallel n}f(p^k)$, where $p^k\parallel n$ means that the prime valuation of $n$ at $p$ is exactly $k$.

Under the discrete uniform distribution on $[N]$, the expectation of the indicator function of $p^k\parallel n$ isThe formula remains valid when $p^{k+1}>N$. Applying linearity of expectation to the finite prime power decomposition proves the required mean formula:

For the last assertion, write the excess prime-factor multiplicity directly as a sum of nonnegative indicator functions:Here $\omega$ is the prime omega function and $\Omega$ is the total number of prime factors. The expectation is bounded independently of $N$, sinceThus Markov inequality gives vanishing probability on every diverging scale:

For an additive arithmetic function $f$, one standard form of the Turán-Kubilius inequality usesIt states, with an absolute constant,For real $f$, this also bounds the variance under the discrete uniform distribution, because centering at the actual expectation minimizes the mean square.

For the prime omega function, $f(p^k)=1$. The Mertens theorem for reciprocal primes states ${\sum }_{p\le N}1/p=\log \log N+O(1)$. The contribution of higher prime powers is bounded by ${\sum }_{p}1/(p(p-1))\le 1$, as proved in 1(a). It follows that $A_{\omega }(N)=\log \log N+O(1)$ and $B_{\omega }(N{)}^2\ll \log \log N$. Writing $L=\log \log N$, the Turán-Kubilius inequality and Chebyshev inequality therefore yieldThe bounded error in $A_{\omega }-L$ is absorbed by, for example, using the threshold $0.005L$ around $A_{\omega }$ for sufficiently large $N$.

For the multiplication table problem, call a pair $(a,b)\in [N{]}^2$ good when $\omega (a),\omega (b)\ge 0.99L$ and $\omega (\gcd (a,b))\le 0.1L$. The preceding Chebyshev inequality excludes only $O(N^2/L)$ pairs by either of the first two conditions. For the greatest common divisor condition, linearity of expectation under uniform sampling of the two coordinates givesMarkov inequality therefore excludes only another $O(N^2/L)$ pairs.

The prime factors of a product form the union of those of its factors. Consequently, for every good pair,On the other hand, apply the proved concentration estimate at $N^2$. Since $\log \log (N^2)=L+\log 2$, for large $N$ every integer $m\le N^2$ with $\omega (m)\ge 1.88L$ is exceptional there. There are only $O(N^2/L)$ such integers. Products of good pairs lie in this exceptional set; products having only bad representations are at most as numerous as the bad pairs. This proves the multiplication-table upper bound, using distinct prime factors alone:

Assume the 1000 individuals are initially disease-free. The event being counted is onset during the ten-year period, not occupancy of the pre-clinical state at its end. Using the estimated transition intensity as a constant onset rate and linearity of expectation, the expected number of onsets isThe first-order approximation $1000\times 0.005\times 10=50$ is close, but does not account for depletion of the disease-free group.

Choose any strictly positive pricing kernel $Z\in \mathcal{Z}$. The assumed componentwise expectations and the linearity of expectation giveThe integrand is nonnegative, so its expectation is also nonnegative and hence zero. A nonnegative random variable with zero expectation vanishes almost surely. Since $Z>0$ almost surely, this forces $H\cdot P=0$ almost surely. Both conclusions follow:The strict positivity of the pricing kernel is essential: a kernel allowed to vanish could miss a positive payoff on its zero set. No normalization $\mathbb{E}Z=1$ is assumed in this abstract market; that normalization follows only if a unit-priced unit-payoff cash asset is included.

Couple the walk on the cycle graph to a simple symmetric random walk $S_j$ on the integer line by taking $Y_j=S_j\mathrm{mod}n$, using the same $\pm 1$ increments. The visited integer interval has distinct residues until its length reaches $n$; an interval of exactly $n$ consecutive integers contains every residue once. Consequently the cover time on the cycle is exactly $T_n$ in this coupling.

Since $T_1=0$, telescope the range-expansion times and use linearity of expectation, without assuming those times are independent:This is the expected cover time of a cycle. The restriction $n\ge 3$ makes the two neighbours distinct, matching the supplied transition rule.

The binomial theorem makes the sum of the proposed probability mass function equal to $(p+1-p{)}^N=1$; every term is nonnegative. Realize the associated binomial distribution as $K=B_1+\cdots +B_N$, where the $B_j$ are independent variables with the Bernoulli distribution of parameter $p$. Each has expected value $p$ and variance $p(1-p)$. Linearity of expectation and variance additivity for independent random variables yieldAt $p=0$ or $p=1$ this is a constant random variable; the same formulas apply, with the endpoint mass understood by continuity.

Fix an edge $e=\{u,v\}$ and orient it from $u$ to $v$. For each spanning tree $T$, let ${\gamma }_T$ be its unique graph path from $u$ to $v$. Assign a signed unit graph path flow $j_T$ to oriented edges: value $+1$ in the direction used by ${\gamma }_T$, value $-1$ on the reversed orientation, and zero otherwise. Define its meanEach $j_T$ has net divergence one at $u$, minus one at $v$ and zero elsewhere, so $J$ is a unit flow. The mean spanning-tree path current also satisfies the Kirchhoff cycle law. Although its verification is permitted to be omitted, a short counting argument makes it explicit. Let ${\mathcal{F}}_{uv}$ be the two-component spanning forests separating $u$ and $v$, write $A_F$ for the component containing $u$, and let $N_T$ be the number of spanning trees. Deleting an edge used by the oriented tree graph path gives one such forest. Conversely adjoining an edge across its two components gives a unique tree with that edge on its $u$-to-$v$ graph path. ConsequentlyThe gradient form proves the Kirchhoff cycle law directly and is Ohm's law for unit edge resistance. The Kirchhoff node law then gives $Lh={\delta }_u-{\delta }_v$, and the electrical unit flow is unique: the difference between two such voltages is a harmonic function on a graph and hence constant on the connected finite graph.

If $e\in T$, its single-edge route is the unique tree graph path from $u$ to $v$, so $j_T(u,v)=1$. If $e\notin T$, that tree graph path does not use $e$, so $j_T(u,v)=0$. ThereforeBy Ohm's law, $J(u,v)=h(u)-h(v)$; for a unit terminal current, this voltage difference is exactly the effective resistance between the terminals. We have proved the requested edge-inclusion formula for a uniform spanning tree:Now use linearity of expectation and the fact that every spanning tree has exactly $n-1$ edges. This gives Foster's theorem:The sums here use unoriented edges exactly once. For unit conductance this is the displayed identity; with conductances $c_e$ the inclusion probability and summand become $c_e{R}_{\mathrm{eff}}(e)$.

Group the random resistance cost by unoriented edges. For $e=\{x,y\}$, its resistance contributes once whenever the walk traverses it in either direction. Pathwise,The graph is finite and the commute has finite expected value. Linearity of expectation, or Tonelli theorem for these nonnegative terms, therefore permits taking expectations of the sum. By the directed edge occupation in a random-walk commute, both directed traversal counts have expected value $R_{\mathrm{eff}}(a,z)$. ThusApply Foster's theorem from part (a) to obtainThe factor two counts the two orientations of each edge. It would be lost by treating the expected directed count in part (b) as an expected count for both directions together. The same distinct-terminal and simple-random-walk conventions from part (b) remain in force.

Choose a Uniformly random maximal chain in a Boolean lattice by taking a uniformly random permutation of $X$ and successively adjoining its elements. A fixed $r$-element set occurs on this maximal chain in a Boolean lattice with probability $r!(n-r)!/n!={\left(\genfrac{}{}{0ex}{}{n}{r}\right)}^{-1}$. Because an antichain meets every such chain in a partially ordered set at most once, linearity of expectation gives the LYM inequality:Here $L(\mathcal{A})$ is the Lubell mass.

For equality in the LYM inequality, the integer $|\mathcal{A}\cap \mathcal{C}|\le 1$ must equal one for every maximal chain in a Boolean lattice, since every chain has positive probability. Choose $A\in \mathcal{A}$ of rank $r$. If $0<r<n$, take $x\in A$ and $y\notin A$, and choose a permutation with its first $r$ elements equal to $A$, its $r$th element $x$, and its next element $y$. Interchanging those two adjacent elements changes precisely the rank-$r$ member of the corresponding maximal chain in a Boolean lattice, replacing $A$ by $A^{\prime }=A\setminus \{x\}\cup \{y\}$. All other members are unchanged and none belongs to the antichain. The new chain must still meet $\mathcal{A}$, so $A^{\prime }\in \mathcal{A}$.

Successive exchanges connect all $r$-element subsets: exchange an element outside a desired target for an element missing from it, decreasing the number of differences each time. Thus $\mathcal{A}$ contains the whole rank-$r$ level. Every set of another rank is comparable with some set in that level, so the antichain contains nothing else. If $r=0$ or $r=n$, its sole possible member is already the whole corresponding level. Conversely, every full level meets every maximal chain in a Boolean lattice exactly once. Hence

Write $N_m=|B(m)|$ and $\theta =\theta (p)>0$. By translation invariance and linearity of expectation,Let $r={\mathbb{P}}_p(R(m)\ge \theta N_m/2)$. Since $0\le R(m)\le N_m$, splitting the expectation at the threshold givesRearranging produces the slightly stronger estimateOnly the mean and boundedness of the random variable are used; independence of the vertex-membership events is unnecessary.

Let $X_i=1_{A_i}$ be the indicator random variable of $A_i$. Then $X={\sum }_i{X}_i$, so linearity of expectation givesUsing variance of a sum andwe obtain

For the circular array, let $X_i$ indicate that bulbs $i$ and $i+1$ are both on, with indices read modulo $n$. Then $\mathbb{E}{X}_i=p^2$. Non-neighbouring indicators are independent, whileThere are $n$ individual terms and $2n$ ordered neighbouring pairs in the double covariance sum, so

The event $B$ is exactly $\{X\ge 1\}$. If $p=n^{-0.6}$, Markov inequality givesIf $p=n^{-0.4}$, then $B^c=\{X=0\}$ implies $|X-\mathbb{E}X|\ge \mathbb{E}X$. By Chebyshev inequality,Therefore $\boxed{\mathbb{P}(B)\to 1}$ in the second regime.

By independence of the two simple random walks, linearity of expectation, and symmetry of their transition probabilities,The Chapman-Kolmogorov equation identifies the inner sum as $p_{00}(2n)$, soA simple random walk on the integer line can return to $0$ only at an even time. Since it is recurrent at $0$, part (a) givesTherefore $\boxed{\mathbb{E}Z=\infty }$.

For a uniform set family $\mathcal{A}\subseteq [n{]}^{(r)}$, the Local LYM inequality isTo prove it, count the incident pairs $(B,A)$ with $B\in \partial \mathcal{A}$, $A\in \mathcal{A}$, and $B\subset A$. Every $A$ contributes exactly $r$ pairs, whereas every $B$ belongs to at most $n-r+1$ members of $[n{]}^{(r)}$. Thereforewhich is the displayed inequality after using the binomial coefficient identity $r\left(\genfrac{}{}{0ex}{}{n}{r}\right)=(n-r+1)\left(\genfrac{}{}{0ex}{}{n}{r-1}\right)$.

The LYM inequality says that every antichain $\mathcal{A}\subseteq \mathcal{P}([n])$ satisfiesFor the proof from the local inequality, take the lowest occupied level below the middle and replace that level by its upper shadow. The result remains an antichain: any new containment involving a set in the upper shadow would already give a containment involving the member of $\mathcal{A}$ immediately below it. The dual form of the Local LYM inequality says that this replacement cannot decrease the Lubell mass. Repeating upward below the middle, and similarly replacing high levels by their lower shadows, eventually puts the whole family in one middle level. Its final Lubell mass is at most one, so the original mass is also at most one.

For the maximal chain in a Boolean lattice proof, choose a Uniformly random maximal chain in a Boolean lattice. An $h$-element set lies on it with probability $1/\left(\genfrac{}{}{0ex}{}{n}{h}\right)$. Because an antichain meets each chain at most once, the expected value of the number of its members on the chain is at most one. By linearity of expectation, that expected value is precisely the displayed sum.

The Sperner theorem follows because $\left(\genfrac{}{}{0ex}{}{n}{|A|}\right)\le \left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$ for every $A$. If equality holds in the resulting cardinality bound, every member lies on a largest level. For even $n$ this is the unique middle level. For odd $n$, the two middle levels have equal size; the regular connected inclusion graph between them and equality in Local LYM inequality force a chosen portion of the lower level to be either empty or the whole level. Hence the maximum antichains are exactly the complete middle level, with either middle level allowed when $n$ is odd.

A fixed edge is monochromatic exactly when none of the $r$ hyperplanes separates its endpoints. Each hyperplane fails to cut it with probability at most $1/3$, and the hyperplanes are independent. ThereforeLet $B={\sum }_{ij\in E}{1}_{\{c(i)=c(j)\}}$ count monochromatic edges. Applying linearity of expectation to these indicator random variables givesIndependence between different edges is unnecessary; only the independently sampled hyperplanes are used. The $r$ signs provide at most $2^r$ colors, whether or not every sign region is nonempty.

For $ϵ(n)=an+b$, linearity of expectation gives $⟨ϵ(n)⟩=am+b$. The mean therefore satisfiesIf $\beta >ak$, the coefficient of $m$ is negative and the stable equilibrium isIf $\beta <ak$, the positive feedback from batch addition dominates deaths and $m(t)$ grows exponentially at rate $ak-\beta$. At the threshold $\beta =ak$, it grows linearly as $m(t)=m(0)+(\lambda +kb)t$.

For each edge $e$, let $I_e$ be the indicator random variable of the event that precisely one endpoint lies in $U$. Independent inclusion of the two endpoints with probability $1/2$ givesBecause $X={\sum }_{e\in E(G)}{I}_e$, linearity of expectation givesSome realization therefore has $X\ge m/2$. Retaining its crossing edges gives a subgraph that is bipartite, with vertex classes $U$ and $V(G)\setminus U$, proving the random cut lower bound.

Now suppose $n$ is an even number and instead choose $U$ uniformly among all subsets of size $n/2$. For a fixed edge $uv$,and the reverse orientation has the same probability. ThusAnother application of linearity of expectation givesAt least one such balanced choice attains this expectation, and its crossing edges give the required subgraph that is bipartite. This is the balanced random cut lower bound.

The binomial random graph $G(n,p)$ has vertex set $[n]=\{1,\dots ,n\}$, and each unordered pair of distinct vertices is included as an edge independently with probability $p$.

Let $X_t$ count copies of the complete graph $K_t$. Each $t$-element vertex set forms a copy with probability $p^{\left(\genfrac{}{}{0ex}{}{t}{2}\right)}$, so linearity of expectation givesThe event $E_t$ is $\{X_t\ge 1\}$. By the first moment method,This is the clique count in a binomial random graph.

The empty-bin indicators are not independent. For distinct $i,k$,whereas $\mathbb{P}(Z_i=1)\mathbb{P}(Z_k=1)=(1-1/n{)}^{2m}$.

Each bin is empty precisely when all $m$ balls avoid it, soThe linearity of expectation does not require independence and gives

Colour every vertex of a graph independently and uniformly with three colours, and retain precisely the edges whose endpoints have different colours. Each edge is retained with probability $2/3$, so linearity of expectation gives expected retained edge countSome colouring therefore retains at least $2e(G)/3$ edges. Its retained subgraph is three-colourable, and deleting edges if necessary leaves exactlyedges without increasing its chromatic number. This is the three-colourable two-thirds subgraph lemma.

To prove sharpness, take $G=K_n$. If $H\subseteq K_n$ is three-colourable and its colour classes have sizes $n_1,n_2,n_3$, then they are independent sets, sowhere the final inequality follows from Cauchy-Schwarz inequality. Since $e(K_n)=n(n-1)/2$,Given $\epsilon >0$, choose $n$ with $2/[3(n-1)]\le \epsilon$. Then every three-colourable subgraph has at most $(2/3+\epsilon )e(G)$ edges.