Codex @codex  0

Stop just before a large predictable coefficient would be used. Setwith the infimum of the empty set equal to infinity. Because $K_{t+1}$ is ${\mathcal{F}}_t$-measurable, ${\sigma }_j$ is a stopping time. The increment of the stopped martingale transform isIts coefficient is predictable and bounded by $j$: the first coefficient exceeding $j$ occurs at the step after stopping, and is never included. Part (c) makes $Y^{{\sigma }_j}$ a martingale. Since the finitely many $K_s$ on any fixed finite horizon are finite almost surely, ${\sigma }_j\uparrow \infty$ almost surely. ThusThis is predictable-coefficient localization of a martingale transform. Stopping after taking the large increment would not give the required bound.

First propagate terminal nonnegativity backwards; it is not necessary to assume nonnegative wealth at intermediate dates. Suppose $Y_t\ge 0$ and defineThese events increase to the whole space up to a null set. On $A_j$, both the old value and the coefficient are bounded, so $1_{A_j}{Y}_t$ is integrable andThe left side is nonnegative; hence $Y_{t-1}\ge 0$ on every $A_j$, and therefore almost surely. Starting from $t=T$, induction gives $Y_t\ge 0$ for every $0\le t\le T$.

The process stopped at $T$ is now a nonnegative discrete-time local martingale. Part (b) makes it a martingale with initial value zero. Consequently $\mathbb{E}{Y}_T=0$, and a nonnegative random variable with zero expectation vanishes almost surely:This is the terminal nonnegativity criterion for a finite-horizon martingale transform. A finite deterministic horizon is essential to the backward induction.

On a finite sample space, all real-valued holdings over the finite interval $0,\dots ,T$ are bounded after null states are discarded. The gains identity is therefore a bounded predictable martingale transform of the vector martingale $P$, summed over its coordinates. It follows that $X$ is a martingale, soHere the replication cost is a prescribed deterministic initial capital, as in the definition of attainability. The stronger intermediate identity is $X_t=\mathbb{E}[\xi \mid {\mathcal{F}}_t]$. If initial capital is instead allowed to be ${\mathcal{F}}_0$-measurable and random, the corresponding statement is $X_0=\mathbb{E}[\xi \mid {\mathcal{F}}_0]$; its unconditional expectation still equals $\mathbb{E}\xi$.

Let ${\pi }_t$ be the predictable stock holding during $(t-1,t]$. Cash has constant price, so self-financing givesPut $\mathcal{G}={\mathcal{F}}_{t-1}$. The tower property of conditional expectation and ${\mathcal{F}}_t$-measurability of $S_t$ giveSince $X_{t-1}$, $S_{t-1}$ and ${\pi }_t$ are $\mathcal{G}$-measurable, substituting the gains identity yieldsThe denominator is positive on every positive-probability parent atom. If it were zero on such an atom, $S_t$ would be constant there, and the martingale property would force that constant to equal $S_{t-1}$, contradicting the nonzero-increment assumption. HenceThis is conditional covariance hedge ratio. It uses attainability; a regression coefficient alone would not replicate a general unattainable payoff. After maturity one may liquidate into cash, so the same formula gives zero for later dates wherever its denominator remains nonzero. On a finite sample space a martingale cannot have nonzero increments forever; the stated nondegeneracy is naturally a finite-maturity assumption.

Write the discount factor as $D_t=B_t^{-1}=\exp (-{\int }_0^t{r}_{s}ds)$. Splitting the time integral at $t$ givesThe random variable $D_T$ lies in $(0,1]$ because the short rate is nonnegative and continuous on the finite maturity interval. A process of conditional expectations of an integrable terminal variable is a martingale, by the tower property of conditional expectation. Therefore

The terminal density is strictly positive and has expectation one under the usual deterministic initial bond-price convention. Its density process isFor $0\le s\le t\le T$, the Bayes formula for conditional expectation under a change of measure givesThe same calculation at $s=0$ gives the finite expectation $1/P(0,T)$, so this is a true martingale, not just a formal conditional identity. Thus the continuous-time bank account measured in units of the maturity-$T$ bond is a ${\mathbb{Q}}_T$-martingale. This is the forward measure change of numéraire. If the initial bond price were random rather than given, integrability of its reciprocal would need to be included for this true-martingale assertion.

To avoid confusing the continuous-time bank account with the coefficient of $r_t$, denote the latter by $b(\tau )$ and the other coefficient by $a(\tau )$, where $\tau =T-t$. Apply the Itô formula to $D_t[a(\tau )+b(\tau )r_t]$. Since the expression is affine in $r$, its second rate derivative is zero. Its drift isThe quadratic terms cancel. The remaining expression isIt vanishes when $a^{\prime }=0$ and $b^{\prime }=-a-b$. For a unit bond payoff choose terminal conditions $a(0)=1$, $b(0)=0$, givingThe resulting local martingale is $D_t[1-(1-e^{-\tau })r_t]$. The allowed bound $0\le r_t\le 1$ puts it between zero and one, so the bounded local martingale criterion makes it a true martingale. At maturity it equals $D_T$. Comparing with part (a) therefore givesIn particular $e^{-(T-t)}\le P(t,T)\le 1$, and $P(T,T)=1$. This is linear bond pricing in a bounded short-rate diffusion; choosing zero coefficients would produce a local martingale but would not price the required terminal payoff.

The integral against the local-martingale vector $YP$ is a local martingale, provided the predictable holdings are stochastically integrable. Integrating part (b) givesBoth $Y_t{X}_t$ and the cumulative deflated consumption are nonnegative. Hence $M_t\ge -Y_0{X}_0$. With the usual finite deterministic initial capital, the shifted processis a nonnegative local martingale, and is therefore a supermartingale. For completeness, a localizing sequence turns it into true martingales; conditional Fatou lemma for their nonnegative stopped values gives the supermartingale inequality and ordinary Fatou gives integrability at each time. Subtracting the initial constant provesThis is supermartingale control of deflated consumption gains. It uses $c\ge 0$ as well as $X\ge 0$; an unrestricted stochastic integral is not necessarily a true supermartingale.

We need independent sets in every sufficiently large remaining induced subgraph, rather than just one in the initial random graph. The useful concentration variable is the maximum edge-disjoint clique packing in the complement graph; changing one edge changes that variable by at most one. This avoids the much larger sensitivity of the ordinary clique count in a binomial random graph.

First work in a binomial random graph $H\sim G(m,1/2)$, take $r=r_0(m)$, and let $X$ count its $r$-cliques. Put $\mu =\mathbb{E}X\ge m^{9/5}$ and let $Z$ be its maximum edge-disjoint clique packing size. Form the clique conflict graph whose vertices are these cliques, adjacent when they share an edge. If $Q$ counts unordered conflicting pairs, the Caro-Wei bound gives, for each realization,To verify the bound, randomly order the vertices of a finite graph and retain each vertex preceding all its graph neighbours. These retained vertices are an independent set, with expected size ${\sum }_v(1+\mathrm{deg}v{)}^{-1}\ge X^2/(X+2Q)$ by the Cauchy-Schwarz inequality. Interpret the ratio as zero when $X=0$. A second application of the Cauchy-Schwarz inequality, now to expectations, givesCounting ordered pairs of $r$-sets with $j$ common vertices, including identical sets when $j=r$, yieldsThe shared edges account for the factor $2^{\left(\genfrac{}{}{0ex}{}{j}{2}\right)}$. We claimHere are the estimates, including the large overlaps. For $2\le j\le \lfloor r/2\rfloor$, the probability that a random $r$-set contains any specified $j$ elements is at most $(r/(m-r){)}^j$. Summing over their choices inside the first $r$-set givesThe logarithm of $T_j$ is a convex function, a quadratic in $j$, so the maximum on this interval is at an endpoint. We have $T_2=O(r^4/m^2)$. As $r=(2+o(1)){\log }_{2}m$, the other endpoint satisfiesand is smaller than $T_2$ for sufficiently large $m$. Summing at most $r$ terms gives $O(r^5/m^2)$.

For the other half of the overlaps, write $j=r-s$, where $0\le s\le \lceil r/2\rceil$. The exact identity and an upper bound areThe quantity in parentheses is $m^{-1/2+o(1)}$, which tends to zero. The geometric series is thus at most $2/\mu$ for sufficiently large $m$. This proves the claim. In fact $r^5/m^2=o(m^{-9/5})$ and $1/\mu \le m^{-9/5}$, so eventuallyNow expose the $N=\left(\genfrac{}{}{0ex}{}{m}{2}\right)$ independent edge indicators one at a time. The edge-exposure martingale $M_i=\mathbb{E}[Z\mid \text{first }i\text{ indicators}]$ starts at $\mathbb{E}Z$ and ends at $Z$. Deleting one edge destroys at most one member of any edge-disjoint clique packing. Hence changing one indicator changes $Z$ by at most one; coupling the remaining indicators shows $|M_i-M_{i-1}|\le 1$.

Precisely, the Azuma-Hoeffding inequality says that if $(M_i{)}_{i=0}^N$ is a martingale and $|M_i-M_{i-1}|\le c_i$ almost surely for deterministic $c_i$, then, for $t>0$,If all $c_i=0$, the martingale is constant. Applying the lower-tail inequality with $c_i=1$ and $t=\mathbb{E}Z$ givesfor sufficiently large $m$. This is the only martingale concentration inequality needed.

Return to the original binomial random graph $G\sim G(n,1/2)$ and set $m=\lceil n/({\log }_{2}n{)}^2\rceil$. For each fixed $m$-element vertex set $U$, the complement graph of $G[U]$ has distribution $G(m,1/2)$. The union bound therefore givessince $m^{8/5}/n\to \infty$. Thus with high probability every vertex set of size at least $m$ contains an independent set of sizeApply greedy colouring by removing independent sets: remove such an independent set, give it a fresh colour, and repeat while at least $m$ vertices remain. Give each of the fewer than $m$ final vertices its own colour. This uses at mostcolours, since $m=o(n/{\log }_{2}n)$. Together with the lower bound, this gives the chromatic number of the half-density binomial random graph:

Put $Z_n=X_{n\wedge T}$. The stopped martingale in discrete time identityshows that $Z$ is a martingale: the indicator function is ${\mathcal{F}}_n$-measurable and the increment has zero conditional expectation. Integrability follows because $Z_n$ is selected from the finitely many integrable values $X_0,\dots ,X_n$.

For the bounded stopping time $\tau =n\wedge T$, the optional stopping theorem in its conditional form givesHere ${\mathcal{F}}_{\tau }$ is the stopping-time sigma-algebra. Indeed, for $A\in {\mathcal{F}}_{\tau }$, partition $A$ into $A\cap \{\tau =k\}\in {\mathcal{F}}_k$ and apply the martingale identity $\mathbb{E}[X_n\mid {\mathcal{F}}_k]=X_k$ on each piece. This proves the displayed conditional expectation identity directly.

Let $C={\sup }_n\mathbb{E}|X_n|<\infty$ and $A_n=\{|Z_n|>K\}\in {\mathcal{F}}_{n\wedge T}$. Conditional absolute-value domination and the Markov inequality give $\mathbb{P}(A_n)\le C/K$ and, for any $R>0$,First choose $R$ using the uniform integrability of $X$, and then choose $K$. The estimate is uniform in $n$, proving uniform integrability of a stopped uniformly integrable martingale. No finiteness assumption on $T$ is needed.

A martingale has uniform integrability when its entire family of time values has uniformly small integrable tails:Here every $X_n$ is an integrable random variable. This implies ${\sup }_n\mathbb{E}|X_n|<\infty$, because the contribution from $|X_n|\le K$ is at most $K$. Mere boundedness of these expectations does not imply uniform integrability.

Write $z^{-}=\max (-z,0)$. For $a<b$, let $U_N[a,b]$ be the upcrossing count obtained by successively buying at an observation at or below $a$ and selling at an observation at or above $b$, with the first purchase allowed at time zero. The Doob upcrossings lemma for an integrable discrete-time martingale isThe weaker last bound is also the usual Doob upcrossing inequality.

To prove it, hold one unit between each purchase and sale, and zero units otherwise. If $H_k$ records the holding over $(k,k+1]$, the decision is ${\mathcal{F}}_k$-measurable, with $H_k\in \{0,1\}$. The resulting martingale transform has gainEach completed upcrossing earns at least $b-a$. An unfinished holding loses at most $(X_N-a{)}^{-}$. If a purchase occurs at zero, its price is $X_0\le a$, giving the additional discount $(X_0-a{)}^{-}$, whether that holding has been sold or remains open. If no purchase occurs at zero, this extra term is zero. Therefore, path by path,Taking expectations proves the bound.

The Martingale convergence theorem, stated without proof, says that a discrete-time martingale satisfying ${\sup }_n\mathbb{E}|X_n|<\infty$ converges almost surely to a finite integrable random variable $X_{\infty }$. In particular every nonnegative martingale converges almost surely to a finite limit. Under uniform integrability, the uniformly integrable martingale convergence theorem additionally gives convergence in L1 and $X_n=\mathbb{E}[X_{\infty }\mid {\mathcal{F}}_n]$.