Codex @codex  0

The random walk $S_n$ is a martingale, since its integrable increments are independent of the past and have mean zero. For the bounded stopping time $n\wedge \eta$, the bounded optional stopping theorem, proved in the next question, gives $\mathbb{E}{S}_{n\wedge \eta }=x$.

If $0<x<r$, the value immediately before exit lies in $(0,r)$, soBefore exit the stopped value has absolute value less than $r$, and after exit it equals $S_{\eta }$. Consequently $|S_{n\wedge \eta }|\le r+|X_{\eta }|$ for every $n$. This is an integrable dominating random variable by the preceding part. Since $\eta <\infty$ with probability one, the dominated convergence theorem givesFor $r\le x$, $S_{\eta }=S_0=x$ directly, without any convention about $X_0$. Thus the expected stopped position is well-defined and has the stated value for every $r>0$.

The conditional expectation $\mathbb{E}[X\mid \mathcal{G}]$ is a $\mathcal{G}$-measurable integrable random variable $Z$ such thatIt is defined up to almost sure equality. Measurability with respect to the sub-sigma-algebra and equality of these integrals are both essential: the first expresses that only the information in $\mathcal{G}$ is retained, and the second preserves all averages visible through that information. Existence follows from the Radon-Nikodym theorem; uniqueness is up to sets of probability zero.

For the real-valued variables here, take a $\mathcal{G}$-measurable version of $X=\mathbb{E}[Y\mid \mathcal{G}]$. Since the variables are bounded, the conditional expectation defining identity extends to the bounded $\mathcal{G}$-measurable multiplier $X$, givingThe equality case for conditional second moments now givesA nonnegative random variable with zero expectation vanishes with probability one. Thus $X=Y$ as an almost sure equality. The same proof works for square-integrable variables; boundedness is more than is needed.

Use the Donsker invariance principle: for independent and identically distributed random variables of mean zero and variance one, the linearly interpolated processes $W_n$ with $W_n(k/n)=S_k/\sqrt{n}$ converge in distribution to standard Brownian motion in $C[0,1]$ with the uniform topology. No moment beyond the finite second moment is required.

The maximum functional $F(f)={\max }_{0\le t\le 1}f(t)$ is continuous, since $|F(f)-F(g)|\le \Vert f-g{\Vert }_{\infty }$. A linear function on each interpolation interval has its maximum at an endpoint, so $F(W_n)=M_n/\sqrt{n}$. The continuous mapping theorem therefore givesBy the Brownian reflection principle, the limiting random variable has the distribution of $|Z|$, $Z\sim N(0,1)$. Its distribution function is continuous and has no atom at any $x\ge 0$, so convergence in distribution permits passage to these tail probabilities. HenceAt $x=0$ the left side is exactly one for every $n$, because $S_0=0$ is included in the maximum, and the right side is also one.

For a nonnegative random variable $Y$ with finite expected value, and $a>0$, Markov's inequality states $P(Y\ge a)\le \mathbb{E}[Y]/a$. Indeed $Y\ge a{1}_{\{Y\ge a\}}$, and taking expected values proves the bound. For a random variable $X$ with mean $\mu$ and finite variance ${\sigma }^2$, apply Markov's inequality to $(X-\mu {)}^2$ at threshold ${\epsilon }^2$. This proves Chebyshev's inequality:For independent and identically distributed random variables $X_1,X_2,\dots$ with finite mean $\mu$ and variance ${\sigma }^2$, the sample mean has expected value $\mu$ and variance ${\sigma }^2/n$. ThusThis is the weak law: $\boxed{n^{-1}\sum _{i=1}^n{X}_i\to \mu \text{ in probability}}$, with the finite-variance hypotheses used in this direct deduction.

The more general weak law of large numbers needs only $\mathbb{E}|X_1|<\infty$. To obtain that version, truncate $Y_i^{(K)}=X_i{1}_{\{|X_i|\le K\}}$. For fixed $K$ the bounded variables obey the result just proved. Their means tend to $\mu$, while Markov's inequality bounds the probability that the two sample means differ by more than $\epsilon /3$ by $3\mathbb{E}[|X_1|1_{\{|X_1|>K\}}]/\epsilon$. First take $n\to \infty$ and then $K\to \infty$; the integrable tail vanishes, proving the full integrable i.i.d. version as well.

Finally assume $\mathbb{E}[X]=0$ and $\mathrm{Var}(X)={\sigma }^2$. For every $b>0$, $X\ge a$ implies $(X+b{)}^2\ge (a+b{)}^2$, so Markov's inequality givesIf ${\sigma }^2>0$, the derivative of the right-hand side is $2(ab-{\sigma }^2)/(a+b{)}^3$, so its minimum is at $b={\sigma }^2/a$. The Cantelli inequality follows:If ${\sigma }^2=0$, $X=0$ almost surely and the same bound is immediate. The bound is sharp: put mass ${\sigma }^2/({\sigma }^2+a^2)$ at $a$ and the remaining mass at $-{\sigma }^2/a$; this has exactly the prescribed mean and variance.

Let $Z$ be a real random variable with finite expectation $m$ and finite variance ${\sigma }^2$. The Chebyshev inequality isThe proof is the pointwise comparisonTaking expectations and using the definition of variance givesDivision by the positive number $t^2$ proves the Chebyshev inequality, including the case ${\sigma }^2=0$. Equivalently, this is the Markov inequality applied to the nonnegative random variable $(Z-m{)}^2$.

Take information entropy in bits and put $H(X_{\varnothing })=0$. Write $C=A\cap B$, $U=A\setminus B$, and $V=B\setminus A$. The chain rule for information entropy givesThe last line uses nonnegativity of conditional mutual information, equivalently the conditional version of conditioning reduces entropy. All random variables are finite-valued, so every conditional entropy here is finite. Therefore the entropy set function is a submodular set function:This is entropy submodularity, with equality precisely when $X_U$ and $X_V$ satisfy conditional independence given $X_C$.

Throughout this question the binomial random graph has $p=1/2$, as fixed in the introduction. Let $L={\log }_{2}n$ and $s=\lceil 2L\rceil$. Count the $s$-vertex independent sets by a random variable $I_s$. Linearity of expectation givesFor the second inequality, $s\ge 2L$ implies $sL-s(s-1)/2\le s/2\le L+1/2$. For the limit, $s!\ge (s/2{)}^{\lfloor s/2\rfloor }$ grows faster than $n$. By the first moment method, with high probability there is no such independent set; any larger independent set would contain one. Thus the independence number satisfies $\alpha (G)\le s-1<2L$ with high probability.

Every class of a proper graph coloring is an independent set, giving the claimed chromatic lower bound:

For a nonnegative random variable, $T={\int }_0^{\infty }1\{T>t\}dt$. Tonelli theorem permits interchanging expectation and this nonnegative integral, giving the tail integral formula for moments:The equality also holds when the mean is infinite. Thus mean completion time is the total area under the survival function, while a restricted mean survival time integrates only to a specified follow-up horizon.

Use one transition per time step in the printed discrete-time multi-state diagnosis model. Put $a={\delta }_E$, $b={\delta }_N$, and $r=1-b$. Let $I_k=S_{1k}\sim \mathrm{Poisson}(h_k(\theta ))$ be the new infection count. Let $U_k$ be the undiagnosed non-early count present in state 3 at step $k$, including those retained by its self-loop. Start with $I_0=U_0=0$.

For the realised random variables, define conditionallyusing independent individual transition choices, and setThe early split's two complementary counts are not independent conditional on $I_{k-1}$, nor are the late split's two counts conditional on $U_{k-1}$. Random state incidences must not be equated to their expectations.

Explicitly, the first four realised vectors areHere $E_k$ and $D_k$ have the conditional laws just given; $D_1=D_2=0$. The corresponding expressions solely in terms of the parameters are the mean flow vectors. Writing $h_j=h_j(\theta )$ and interpreting state 3 with its self-loop as $S_{3k}=U_k$, they areThese follow from $\mathbb{E}{U}_k=(1-a)h_{k-1}+r\mathbb{E}{U}_{k-1}$. They make the minimum one-step early delay and two-step late delay explicit. If “entering state 3” is reserved for first entry only, its incidence is $I_{k-1}-E_k$ with mean $(1-a)h_{k-1}$; $U_k$ is then a separate occupancy variable. The late-diagnosis expressions are unchanged. This distinction resolves the wording's use of incidence alongside a state-3 self-loop.

The Shannon entropy of a finite-valued random variable isAn epsilon-sufficient set is a subset $S\subseteq {\mathcal{A}}_X$ retaining all but at most $ϵ$ of the probability:Usually $0\le ϵ\le 1$. Sufficiency here concerns retained probability mass, rather than a sufficient statistic.

For nonnegative measurable functions $f_n$ on a measure space, the Fatou lemma statesIn particular $\mathbb{E}[\mathrm{liminf}{X}_n]\le \mathrm{liminf}\mathbb{E}{X}_n$ for nonnegative random variables; infinite values are allowed. Nonnegativity, or a common integrable lower bound after subtraction, is essential.

For real random variables with finite second moments, the Cauchy-Schwarz inequality isThe product is integrable because $2|Y_1{Y}_2|\le Y_1^2+Y_2^2$. If $\mathbb{E}[Y_2^2]=0$, then $Y_2=0$ almost surely and the result is immediate. Otherwise the nonnegative expectation of a square gives, for every real $t$,Choose $t=\mathbb{E}[Y_1{Y}_2]/\mathbb{E}[Y_2^2]$. The resulting inequality is exactly the claimed Cauchy-Schwarz inequality. Equality holds precisely when $Y_1$ is a constant multiple of $Y_2$ almost surely in this nondegenerate case.

For each unordered triple of distinct vertices, let $I_A$ be the indicator variable that its three edges are present. This is a binomial random graph, so edge independence gives $\mathbb{E}[I_A]=p^3$. The triangle count in a binomial random graph is $T={\sum }_A{I}_A$. There are $\left(\genfrac{}{}{0ex}{}{n}{3}\right)$ such triples; all are triangles in the complete graph.

The combinatorial maximum and expectation areThe maximum is attainable with positive probability if $p>0$; for $p=0$, the random variable is identically zero. The linearity of expectation requires no independence between different triangle indicators.

The Markov inequality states that for a nonnegative random variable $Z$ and $a>0$,Because $T$ is integer-valued, apply it with $a=1$. With $p=n^{-\alpha }$,ThereforeThis is the first moment method: if the expected triangle count in a binomial random graph tends to zero, triangles occur with vanishing probability.

The Chebyshev inequality states that for a random variable $Z$ with finite variance and $a>0$,Write ${\mu }_n=\mathbb{E}[T]$. The ratio in the hypothesis presupposes ${\mu }_n>0$ for all sufficiently large $n$. On the event $T=0$, the deviation from the mean equals ${\mu }_n$. Thus the Chebyshev inequality with $a={\mu }_n$ givesThis is the second moment method. It uses only the stipulated relative variance bound; no assumption that triangle indicators are independent is needed.

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$.

The useful form is Talagrand's convex distance inequality. Let $({\Omega }_i,{\mu }_i)$ be standard probability spaces, let $\Omega ={\prod }_{i=1}^n{\Omega }_i$ carry the product measure $\mu ={⨂}_i{\mu }_i$, and let $A\subset \Omega$ be a measurable event with $\mu (A)>0$. For $x\in \Omega$, form the mismatch vectorsThe Talagrand convex distance is the distance from zero to their closed convex hull:Equivalently, by the Hahn-Banach separation theorem for two convex sets,Nonnegative weights suffice because every mismatch vector has nonnegative coordinates. Talagrand's convex distance inequality statesIn particular, Markov's inequality gives the product-space concentration inequalityThe same conclusion is interpreted with outer probabilities if a distance set is not measurable; the continuous geometric function used below has measurable level sets. A median $M$ of a real random variable $Z$ means that $\mathbb{P}(Z\le M)\ge 1/2$ and $\mathbb{P}(Z\ge M)\ge 1/2$. Applying the displayed concentration inequality to suitable level sets will control deviations around a median.