Codex @codex  0

Because the events are pairwise disjoint events, their count can only be zero or one. The event that the count is zero is the complement of an event of their union. Finite additivity therefore gives

Now use $N\ge 1$ for the fixed number of independently located ships. Normalize the radius to one and write their positions as unit vectors $a_1,\dots ,a_N$. A point $x$ on the sphere is reached by ship $i$ precisely when $a_i\cdot x>0$, so each ship reaches an open hemisphere. Coverage fails exactly when there is a unit vector $x$ with $a_i\cdot x\le 0$ for every $i$. Equivalently, all ship positions lie in some closed hemisphere.

With probability one no pair of ship vectors is antipodal and no three are linearly dependent: the exceptional choices lie on sets of zero surface area. For such a configuration, containment in a closed hemisphere implies containment in an open hemisphere. To see this, choose its inward normal $u$, so $u\cdot a_i\ge 0$. At most two vectors lie on its boundary. If there are two, their sum has positive dot product with each, since they are not antipodal; if there is one, use that vector itself. Perturb $u$ slightly in this direction. The boundary dot products become positive while all already positive dot products remain positive. Thus the strict and non-strict containment conditions have the same probability here.

Condition on the unoriented axes $\{a_i,-a_i\}$. Choose representatives $b_i$ by any fixed sign convention. By uniform sampling and independence, the actual positions are $a_i={\epsilon }_i{b}_i$ with $N$ independent fair signs ${\epsilon }_i\in \{-1,1\}$. Conditional on these axes, each of the $2^N$ sign choices has probability $2^{-N}$.

The great circles $b_i\cdot u=0$ partition the sphere into $R_N=N(N-1)+2$ open regions. In each region the sign vector $\sigma (u)=(\mathrm{sgn}(b_i\cdot u){)}_i$ is constant. No sign vector labels two different regions: its strict inequalities define a convex cone, and normalized line segments within that cone connect any two points of its spherical section. The regions of a general-position great-circle arrangement therefore yield exactly $R_N$ realized sign vectors.

The chosen positions lie in an open hemisphere if and only if some $u$ has $u\cdot a_i>0$ for every $i$, that is, ${\epsilon }_i=\mathrm{sgn}(b_i\cdot u)$ for every $i$. Failure of coverage thus corresponds exactly to one of the $R_N$ realized sign choices. These choices are mutually exclusive events, each of conditional probability $2^{-N}$, so the first part applies:The result is independent of the axes. Averaging gives the coverage of a sphere by random open hemispheres:For $N=1,2,3$ this is zero; for $N=4$ it is $1/8$. If no ship lands, coverage has probability zero separately. The counting uses equiprobable orientation signs, not an assumption that the spherical regions have equal area.

The probability generating function isFor independent random variables, the bounded factors $z^X$ and $z^Y$ have factorizing expectation, soThis includes complex $z$ in the indicated disk by absolute convergence.

For the dice construction, encode the labels of an ordinary die by $F(z)=z+z^2+\cdots +z^6$. Its probability generating function is $F(z)/6$. A useful factorization into polynomial factors isUse redistribution of polynomial factors for dice to defineBoth polynomials have nonnegative integer coefficients, no constant term, and coefficient sum six. They therefore describe fair six-sided dice with strictly positive face labelsWhen these dice are thrown with independent outcomes, the sum has probability generating function $A(z)B(z)/36=F(z{)}^2/36$. Equality of coefficients proves equality of every sum probability, including all totals from two to twelve, with zero probability outside that range. Both dice are nonstandard, completing the construction.

An irreducible Markov chain has the property that for every pair of states $i,j$ there is an integer $n\ge 0$ with $(P^n{)}_{ij}>0$. Equivalently every state can reach every other state along a finite path of positive-probability transitions.

Irreducibility and the presence of another state imply $P_{ii}<1$: otherwise $i$ would be absorbing and could not reach that other state. Hence the proposed matrix has nonnegative entries and row sums ${\sum }_{j\ne i}{P}_{ij}/(1-P_{ii})=1$.

Observe the original Markov chain only at times when it changes state. Starting from $i$, the next different state is $j\ne i$ with probabilityEach holding run has a finite geometric length almost surely. The Strong Markov property at the successive change times therefore identifies the observed process as the discrete-time jump chain with transition matrix $\tilde{P}$.

Any positive-probability path of the original chain gives a path of this new chain after repeated consecutive states are deleted. Every remaining edge has positive $\tilde{P}$ probability, so $\tilde{P}$ is irreducible. For recurrence, starting at any state $i$, repeated application of the Markov property at return times shows that the original recurrent chain visits $i$ infinitely often almost surely. A single sojourn cannot account for infinitely many visits, because every sojourn is finite almost surely. There must therefore be infinitely many separate visits to $i$ in the observed chain too. Thus $\tilde{P}$ is recurrent, proving that recurrence survives deletion of self-transitions.

The Rao-Blackwell theorem states that if an estimator $D$ has finite second moment and $T$ is a sufficient statistic, then $D^{\ast }(T)=\mathbb{E}[D\mid T]$ can be chosen without knowing the parameter. It has the same expectation as $D$ and no larger variance. In particular an unbiased estimator remains unbiased and its squared-error risk cannot increase. Sufficiency makes the conditional distribution, hence the function of $T$ used here, parameter-independent.

The tower property gives $\mathbb{E}{D}^{\ast }=\mathbb{E}D$. The law of total variance givesso the variance decreases, with equality exactly when $D$ is already a function of $T$ almost surely. Since the bias is unchanged, the same identity proves the squared-error risk claim. More generally the corresponding convex-loss inequality follows from conditional Jensen's inequality.

For the given geometric distribution, the joint mass is $(1-p{)}^n{p}^{\sum x_j-n}$ on positive-integer sample vectors. Thus $T={\sum }_j{X}_j$ is a one-dimensional sufficient statistic. Directly, conditional on $T=t$, every positive-integer composition of $t$ into $n$ parts has the same probability; there are $\left(\genfrac{}{}{0ex}{}{t-1}{n-1}\right)$ such compositions, independently of $p$.

The simple estimator $D=1_{\{X_1>1\}}$ is unbiased for $p$, since $\mathrm{Pr}(X_1>1)=p$. For $n\ge 2$, compositions with $X_1>1$ are counted by subtracting one from their first part, giving $\left(\genfrac{}{}{0ex}{}{t-2}{n-1}\right)$ when $t>n$. Consequently the Rao-Blackwell estimator of a geometric failure probability isAt $T=n$ its value is zero, as it must be when all observations are one. For the possible one-observation case, use $\hat{p}=1_{\{T>1\}}$; the displayed fraction would otherwise be undefined at $T=1$. The conditional-expectation argument proves unbiasedness without needing to sum the negative-binomial mass explicitly.

The directed positive-transition graph gives the communicating classes $\{1,3,6\}$, $\{2,4\}$ and $\{5\}$. The first and last classes are closed; $\{2,4\}$ is open. In particular the PDF's fourth row has all six entries equal to $1/6$. The converted TeX incorrectly drops the last entry; that incomplete row is not a transition distribution.

The finite irreducible closed class $C=\{1,3,6\}$ reaches state six almost surely. For example, from every state in $C$ there is a uniformly positive probability of hitting six within a bounded number of steps, so the probability of avoiding it for successive blocks tends to zero. Put $h_i={\mathrm{Pr}}_i(T_6<\infty )$, with $h_1=h_3=h_6=1$ and $h_5=0$. First-step conditioning at states two and four givesSolving $4h_2-h_4=2$ and $5h_4-h_2=3$ yields $\boxed{h_2=13/19}$, with $h_4=14/19$.

Starting in state three, the chain remains in $C$. In the order $(1,3,6)$ its transition matrix isIts characteristic polynomial is $(\lambda -1)(\lambda +1/4)(\lambda +1/6)$. Thus, by the Cayley-Hamilton theorem, $q_n=(M^n{)}_{2,3}$ is a linear combination of $1,(-1/4{)}^n,(-1/6{)}^n$. The initial values are $q_0=0$, $q_1=1/3$, and $q_2=(1/3)(1/2+1/3+1/4)=13/36$. Solving for the three coefficients givesThe limiting value $12/35$ agrees with the state-six probability of the stationary distribution $(8/35,3/7,12/35)$ of this closed class.

For a real potential, the Time-dependent Schrödinger equation and its complex conjugate giveThe potential terms cancel. The expression on the right is a total derivative, givingFor the plane wave, ${\psi }_t=-i\omega \psi$ and ${\psi }_{xx}=-k^2\psi$. With zero potential, substitution givesIt is a free-particle momentum eigenstate with momentum $\hslash k$, energy $\hslash \omega$ and uniform probability flux. On the whole real line it is a generalized state, not a normalized square-integrable wavefunction; wave packets or box normalization give the corresponding physical interpretation.

Use $I_i=1_{A_i}$ and interpret the printed overlap term as $2\Delta ={\sum }_i{\sum }_{j\in J_i}\mathrm{Pr}(A_i\cap A_j)$; its unindexed $A,B$ are a typographical slip. Take $i\notin J_i$, as usual. If necessary, deleting $i$ from its own neighbourhood gives the proof below with a smaller nonnegative right-hand side, so the stated bound still follows.

If $\lambda =0$, every indicator is zero almost surely and the Poisson distribution with parameter zero is the same point mass. Suppose $\lambda >0$. For any $B\subseteq {\mathbb{Z}}_{\ge 0}$, put $h_B(k)=1_{k\in B}$ and let $Z$ have Poisson distribution with mean $\lambda$. Solve the Poisson Stein equationFor example, for $k\ge 1$ one can takeThe full weighted sum is zero, so using its complementary tail also shows this solution is bounded. The allowed Stein factor is $\Vert \Delta g{\Vert }_{\infty }\le \min (1,{\lambda }^{-1})$, where $\Delta g(k)=g(k+1)-g(k)$.

DefineJoint independence of $A_i$ from all events outside its neighbourhood makes $I_i$ independent of $W_i$, so $p_i\mathbb{E}g(W_i+1)=\mathbb{E}{I}_{i}g(W_i+1)$. Adding and subtracting those terms givesA difference over $m$ integer steps has magnitude at most $m\Vert \Delta g{\Vert }_{\infty }$. In the first sum the step count is $I_i+V_i$; in the second, on $I_i=1$, it is $V_i$. Consequently the absolute value is at mostThe Stein equation identifies the left side with $|\mathrm{Pr}(W\in B)-\mathrm{Pr}(Z\in B)|$. Taking the supremum over $B$ is the definition of total variation distance, proving the Stein-Chen bound with the Poisson Stein factor:

For the random uniform hypergraph, index indicators by four-vertex sets. Each such set is a hypergraph clique exactly when its four triples are all present, so its probability is $p^4$. Distinct sets use disjoint triple indicators unless their intersection has size three; disjoint underlying trials give the required joint independence. A fixed four-set has $d=4(n-4)$ dependent others, and each overlapping pair requires seven distinct triples, with joint probability $p^7$. Thus, with $N=\left(\genfrac{}{}{0ex}{}{n}{4}\right)$ and $\lambda =N{p}^4$, the bracket isSince $\lambda \min (1,{\lambda }^{-1})\le 1$,This calculation applies for $n\ge 4$ and $p>0$; if $p=0$ or $n<4$, the count and its Poisson parameter are zero and the conclusion is immediate.

The asymmetric Lovász local lemma says the following. For finitely many bad events with a dependency graph of events, if $0\le x_i<1$ satisfythenHere independence from nonneighbors is independence from their whole generated system, not just pairwise independence.

Prove by induction on $|S|$ that $\mathrm{Pr}(A_i\mid {\bigcap }_{j\in S}{A}_j^c)\le x_i$ whenever $i\notin S$, with all conditioning probabilities positive. At $S=\varnothing$, the hypothesis gives $\mathrm{Pr}(A_i)\le x_i$. Split $S$ into its neighbor part $S_1$ and nonneighbor part $S_2$. ThenThe numerator uses joint nonneighbor independence. The denominator is exposed one event at a time; every conditional bad-event probability involves fewer than $|S|$ conditioning events, so induction supplies the product lower bound. The same product argument gives positivity of the conditioning events before using the fraction. Finally expose all complements in any order and multiply their conditional probabilities to obtain the claimed lower bound.

For maximum dependency degree $d\ge 1$ and event probabilities at most $p$, choose $x_i=1/(d+1)$. Since $(1+1/d{)}^d\le e$, the symmetric Lovász local lemma follows fromFor $d=0$, the events are jointly independent and avoidance has positive probability whenever $p<1$, so the displayed sufficient criterion also holds.

To obtain the local lemma Ramsey lower bound, colour the edges of $K_N$ independently with two equally likely colours. For every $k$-set $S$, the event that it is monochromatic has probability $p=2^{1-\left(\genfrac{}{}{0ex}{}{k}{2}\right)}$. Events with intersections of size at most one depend on disjoint edge trials. Counting potentially shared pairs givesThe Lovász local lemma excludes all monochromatic $K_k$ if $ep(d+1)\le 1$. For $N\le ck{2}^{k/2}$, Stirling's approximation and $\left(\genfrac{}{}{0ex}{}{N-2}{k-2}\right)\le N^{k-2}/(k-2)!$ give, uniformly for $c$ bounded above and away from zero,For a concrete approach to the limiting constant, choose $c_k=(\sqrt{2}/e)(1-3\log k/k)$ and take the integer part of $c_{k}k{2}^{k/2}$. Then $(e{c}_k/\sqrt{2}{)}^k\le k^{-3}$ for all sufficiently large $k$, so the criterion holds. Such a colouring shows $R(k)>N$, and thereforeThe undefined $o(i)$ printed in the PDF is read as the intended $o(1)$, with $k\to \infty$.

For the cycle, independently choose one of the twelve vertices in each part. Ignore cycle edges whose endpoints lie in the same part, since both endpoints cannot be selected. Every other edge defines a bad event of probability $1/144$. It uses just the choices in its two endpoint parts. A part's twelve vertices meet at most twenty-four cycle edges, so a bad event has at most $48-1=47$ neighbors in a dependency graph of events. Since $e(47+1)/144=e/3<1$, the Lovász local lemma gives a selection with no selected adjacent pair. Thus an independent transversal of size $n$ exists, for every stated partition.

Expose the independent coordinates in order and let $M_i=\mathbb{E}[f\mid X_1,\dots ,X_i]$, $M_0=\mathbb{E}f$. This is the Doob exposure martingale. For fixed earlier coordinates, write $h_i(x)=\mathbb{E}[f\mid X_i=x,\text{earlier coordinates}]$. The remaining coordinates have the same distribution for all $x$, and the coordinate-change hypothesis gives $|h_i(x)-h_i(y)|\le c_i$. Thus the conditional range of $M_i-M_{i-1}$ has length at most $c_i$, and its conditional mean is zero.

Here is the Hoeffding lemma needed for the sharp constant. If a mean-zero random variable $Y$ lies in an interval of length $c$, set $\psi (s)=\log \mathbb{E}{e}^{sY}$. Its second derivative is the variance under the exponentially tilted law. Under any such law, variance is at most $c^2/4$, by comparison with squared distance from the interval midpoint. Since $\psi (0)={\psi }^{\prime }(0)=0$, integration gives $\psi (s)\le s^2{c}^2/8$ for all real $s$. Applying this conditionally and iterating the tower property yieldsThe exponential Markov bound now givesFor $C>0$ choose $s=4t/C$. Apply the same argument to $-f$ and add the two tails, proving the McDiarmid inequalityFor $C=0$, $f$ is constant almost surely, and every positive-deviation probability is zero.

For the neighbourhood application, the ambient points must be elements of $\mathcal{P}[n]$, equivalently binary strings; the printed $y\in [n]$ is a type error. An $n$-element ambient set could not generally satisfy the stated exponential-size lower bound. Use the uniform product probability space on the Boolean cube and set $F(y)=d(y,A)$. Flipping one coordinate changes this Hamming distance by at most one, so $C=n$. Put $\mu =\mathbb{E}F$. Since $\mathrm{Pr}(F=0)=|A|/2^n\ge \epsilon$, the proved two-sided inequality gives, for $\mu >0$,Consequently $\mu \le \sqrt{(n/2)\log (2/\epsilon )}=t/2$; the same bound is immediate if $\mu =0$. ThereforeThis proves the Boolean cube expansion from bounded differences:The meaningful range is $0<\epsilon \le 1$; real radii are interpreted by the inequality on the integer-valued Hamming distance. The converted TeX's final $2^{2n}$ is another corruption: the original PDF has $2^n$.

The assertion with the same $\epsilon$ in the degree interval and the final colour bound is false as printed. Fix $r=2$, $\epsilon =1/10$, let $G=K_{22m+1}$, and take $D=20m$. Every degree is $22m=(1+\epsilon )D$, while every pair hypergraph codegree is one. For any proposed $\delta >0$, choose $m$ large enough that $1\le \delta D$. Nevertheless a matching in a graph contains at most $11m$ edges, whereas there are $(22m+1)11m$ edges in total. Thus every edge coloring requires at least $22m+1$ colours, exceeding $(1+\epsilon )D=22m$. The obstruction persists with arbitrarily small relative hypergraph codegree.

The meaningful asymptotic target separates the output tolerance from the input regularity error. For fixed rank $r$ and target $\eta >0$, choose a sufficiently small $\delta =\delta (r,\eta )$ and require degrees in $[(1-\delta )D,(1+\delta )D]$ as well as pair hypergraph codegrees at most $\delta D$. The semi-random method then gives ${\chi }^{\prime }(G)\le (1+\eta )D$. Here is the requested proof essay for that corrected conclusion, including its random rounds, tracking requirements and completion step.

A useful way to run all colour classes together is the auxiliary matching construction for hypergraph edge colouring. Use $K=\lceil D\rceil$ initial colours. Create a task vertex for each original edge $e$, and a resource vertex $(v,c)$ for each original vertex and colour. An assignment $(e,c)$ is an $(r+1)$-edge consisting of its task and the resources $(v,c)$ for all $v\in e$. A matching in a hypergraph in this auxiliary system is a proper partial colouring: a task cannot get two colours, and two edges sharing $v$ cannot use the same resource $(v,c)$.

The auxiliary task degrees are $K$, resource degrees are $d_G(v)$, and its pair hypergraph codegrees are at most $\max (1,\delta D)$. It is therefore nearly regular with small hypergraph codegrees. For $r\ge 2$ and a nonempty original hypergraph, the hypergraph codegree condition also forces $D\ge 1/\delta$; taking $\delta$ small absorbs rounding and ensures a large working degree. Rank one is immediate by assigning distinct colours to edges at each vertex.

The extra balance condition is important. Let $S_v$ be the set of tasks corresponding to edges through original vertex $v$. A matching in a hypergraph missing a small fraction of all tasks need not leave few tasks in each $S_v$. The Rödl nibble must leave at most $\beta D$ unmatched tasks in every such star, where one may choose $\beta =\eta /(4r)$. This local requirement, rather than just a global almost-perfect matching in a hypergraph, is what permits a cheap final edge colouring.

Run a Rödl nibble on the auxiliary system, whose rank is $s=r+1$. In a round of working degree $D_j$, sample each surviving assignment independently with probability $\alpha /D_j$, for a small fixed $\alpha$. Accept the sampled assignments that meet no other sampled assignment. Delete every auxiliary vertex touched by any sampled assignment, including conflicted ones, before proceeding. The accepted assignments are a matching in a hypergraph, and later assignments cannot reuse a consumed task or resource. Record each discarded but uncoloured task as waste; it must be counted in the final residual graph.

For an auxiliary vertex of degree $(1\pm \xi )D_j$, the probability of remaining untouched isFor an auxiliary edge through a surviving vertex, the other $s-1$ vertices survive with probability approximately $e^{-(s-1)\alpha }$. Their incident trial families overlap in at most $O_s(\delta D)$ trials by the hypergraph codegree bound, so the overlap error in this product calculation is small. This leads to the degree trajectorywhile the surviving fraction of task vertices is approximately $e^{-\alpha }$ per round. For a sampled assignment, a union bound over at most $s(1+O(\xi ))D_j$ conflicting assignments gives collision probability at most $s\alpha (1+O(\xi ))$. More explicitly, for a fixed task the expected number of ordered sampled conflict pairs having the first assignment through that task is at mostThis bounds its waste probability. Thus productive deletion is first order in $\alpha$, and collision loss is second order.

The technical tracking step makes these expected value calculations locally simultaneous and keeps their errors from accumulating. Its requirements are: residual auxiliary degrees stay near their trajectory after controlled pruning; each original star has the predicted number of surviving tasks; and every star's total collision and pruning waste is small. The standard probabilistic tools enter at distinct points.

Within a fixed round, task-survival indicators are independent: trial families for different tasks are disjoint, even when their assignments share resources. Conditional Chernoff bounds therefore control the number of surviving tasks in each star. Collision loss has short certificates consisting of pairs of selected intersecting assignments. The number selected through one resource has a binomial distribution of bounded mean. Chernoff bounds truncate these numbers at a suitable logarithmic cutoff; after truncation one trial has only a logarithmically bounded effect on the certified collision count. A certifiable function concentration bound, or a corresponding exposure argument, then controls loss in each star. These rare local overload events have polynomially bounded local dependency neighborhoods in the working degree, so the Lovász local lemma can select a simultaneous outcome independent of the total number of vertices.

Residual-degree counts require additional care because they are not sums of independent indicators. Two survival tests share at most a hypergraph codegree's worth of trials; expanding their joint probabilities bounds their covariance by the corresponding relative overlap. For a residual-degree count $Z$ with $D_j$ summands, overlapping summands and shared survival trials give a variance bound of the formChebyshev's inequality then bounds $\mathrm{Pr}(|Z-\mathbb{E}Z|>\xi D_j)$ by $C_s(D_j^{-1}+\zeta )/{\xi }^2$. This gives a small exceptional fraction when the relative hypergraph codegree is sufficiently small; it does not by itself make every degree good. The tracking argument records and prunes these exceptional configurations, bounding their contribution to each star by codegree-weighted exposure and the same local-loss bookkeeping. Markov's inequality controls exceptional mass, and repeated conditional concentration controls the retained counts. One must not apply an independent Chernoff bound directly to a residual degree or infer a uniform star bound just from a global expected loss. Keeping the pruning loss explicitly is the key distinction between a valid Rödl nibble argument and those shortcuts.

Choose the parameters in this order: first $r,\eta$ and $\beta$; next $\alpha$ so small that $s\alpha \log (4/\beta )\ll \beta$; nextand finally the initial regularity/hypergraph codegree tolerance $\delta$ small enough for all $T$ tracking and pruning errors. This is a bounded number of rounds depending on the tolerances, not on the graph order. After $T$ rounds, the surviving task fraction is at most approximately $\beta /4$, while accumulated collision loss is $O_s(T{\alpha }^2)=O_s(\alpha \log (4/\beta ))$. Reserving the remaining margin for tracking and pruning leaves at most $\beta D$ uncoloured edges at every original vertex. The working degree is still a fixed positive multiple of $D$, namely about $D{e}^{-r\alpha T}$, so the large-degree estimates remain applicable throughout.

Finally use a fresh palette on the residual original hypergraph. Its maximum degree is at most $\beta D$; an edge meets at most $r(\beta D-1)$ others. Greedy colouring therefore needs at most $r\beta D+1$ fresh colours. The total is at mostfor sufficiently large $D$, already ensured by choosing $\delta$ small. This completes the passage from the locally balanced Rödl nibble to the hypergraph chromatic index bound. The degree tolerance must be the small input parameter $\delta$; replacing it by the entire output allowance $\eta$ removes the slack and leads precisely to the complete-graph counterexample above.

For $x\in \Omega$ and nonempty $A$, letThe Talagrand convex distance isEquivalently,For completeness, let $v_{\ast }$ be a closest point of the finite convex hull to zero. If $v_{\ast }\ne 0$, minimality gives $v_{\ast }\cdot (v-v_{\ast })\ge 0$ for every $v\in V$. Taking $\alpha =v_{\ast }/\Vert v_{\ast }\Vert$ proves that the supremum is at least $\Vert v_{\ast }\Vert$. Conversely each permitted $\alpha$ has ${\inf }_{v\in V}\alpha \cdot v\le \alpha \cdot v_{\ast }\le \Vert v_{\ast }\Vert$ by Cauchy-Schwarz. The weights are nonnegative because the hull has nonnegative coordinates. If $v_{\ast }=0$, both sides are zero. This proves the dual definition used below.

We prove Talagrand's convex distance inequality by induction on the number of factors. Write $\Omega ={\Omega }^{\prime }\times X_n$, with measure $\mu \otimes \nu$, and $F_A=d_T(\cdot ,A{)}^2$. For a last-coordinate value $z$, let $A_z=\{y^{\prime }:(y^{\prime },z)\in A\}$. Choose a section $B=A_b$ of largest probability $m=\mu (B)>0$, and put $a_z=\mu (A_z)/m\in [0,1]$. The total event probability is $p=\mathrm{Pr}(A)=m{\sum }_z\nu (z)a_z$.

If $A_z$ has positive probability, combine mismatch vectors from $A_z$ and from $B$. A weight $t$ on the second section contributes at most $t$ in the last coordinate. Convexity of the squared Euclidean norm gives, for every $0\le t\le 1$,The last-coordinate contribution is actually zero if $z=b$, so the displayed upper bound remains valid. Hölder's inequality and the induction hypothesis yieldFor a zero-probability section use $t=1$ directly, so no division by zero or exponent of an infinite quantity is needed.

The scalar estimate for Talagrand product induction isHere is its proof. For $a>0$ set $L=-\log a$. If $L\le 1/2$, take $t=2L$; the logarithm of the left expression is $L-L^2$. Put $h(L)=\log (2-e^{-L})-L+L^2$. Then $h(0)=h^{\prime }(0)=0$ andsince $(2u-1{)}^2-u=(4u-1)(u-1)\ge 0$ for $u=e^L\ge 1$. Thus $h\ge 0$. If $L\ge 1/2$, choose $t=1$. The already proved boundary case gives $e^{1/4}\le 2-e^{-1/2}\le 2-a$. The same direct choice covers $a=0$.

Average the resulting section bounds over $z$:where the last inequality is equivalent to $(m-p{)}^2\ge 0$. The induction starts on the zero-coordinate singleton, where every positive-probability event is the whole space and the moment is one. HenceWe assume $\mathrm{Pr}(A)>0$; a zero-probability event has no finite right-hand bound to prove. Markov's inequality also gives

For the subsequence application, let $L(x)$ be the longest increasing subsequence length for independent sequence coordinates. A witness of length $\ell$ uses only $\ell$ positions. If $L(x)=\ell \ge b$ and $y$ satisfies $L(y)\le a<b$, at least $\ell -a$ witness positions must change: all unchanged witness positions remain in increasing order. Put weights $1/\sqrt{\ell }$ on the witness and zero elsewhere. The dual distance definition giveswhere the latter expression increases with $\ell$ for $a\ge 0$. Therefore the increasing-subsequence certificate concentration bound isIf the lower event has probability zero the conclusion is immediate.

Let $m$ be an integer median, so $\mathrm{Pr}(L\le m),\mathrm{Pr}(L\ge m)\ge 1/2$. Taking the two thresholds in the bound gives, for $t>0$,For $t>m$ the lower event is empty. In a nonempty sequence $m\ge 1$. Integration of these tails gives an explicit mean-median estimate: use $m+t\le 2m$ for $t\le m$ and $m+t\le 2t$ for $t\ge m$, obtainingWriting $\mu =\mathbb{E}L$, the median property also gives $m\le 2\mu$. Consequently, for a universal constant $C$, all $u\ge 0$ satisfyThus the subsequence length is concentrated near its mean on the scale $\sqrt{\mu }$, rather than the generic coordinate-exposure scale $\sqrt{n}$. This argument applies directly to finite-valued independent sequences. Independent continuous samples follow by refining finite coordinate discretizations; the strict-order pattern stabilizes almost surely when ties have probability zero. A uniform random permutation is the rank sequence of independent continuous samples, so it has the same subsequence-length concentration. Arbitrarily dependent random sequences are not covered by the product-space assumption.

For $\theta >0$, the one-parameter Poisson-Dirichlet distribution is a probability distribution on decreasing random mass sequences. A precise construction uses a Poisson random measure $\Xi$ on $(0,\infty )$ with intensityArrange its points as $J_1>J_2>\cdots$ and put $T={\sum }_i{J}_i$. The intensity is diffuse, so there are almost surely no ties. There are infinitely many points because the intensity has infinite mass near zero, but their sum is finite almost surely: the Campbell first-moment formula gives $\mathbb{E}T=\int u{\rho }_{\theta }(du)=\theta <\infty$. Also $T>0$ almost surely, since the probability of having no points is zero. DefineIts law is $PD(\theta )$, also written $PD(0,\theta )$. In particular, $p_1$ is the largest component; the ordering is part of the definition.

The Laplace functional of a Poisson random measure determines the total:For the integral identity, differentiate the integral with respect to $s$, obtaining $1/(1+s)$, and use its value zero at $s=0$. Thus $T$ has the Gamma distribution with shape $\theta$ and rate one, and density $t^{\theta -1}{e}^{-t}/\Gamma (\theta )$.

We use the Mecke formula for a Poisson random measure in its point-removal formHere the process inside the expectation on the right has the original law. To justify this identity, first take finite intensity. Conditional on a Poisson count $n$, its points are independent samples from normalized intensity. Expanding the expectation as a sum over $n$ and singling out one of the $n$ points replaces $n/n!$ by $1/(n-1)!$; the remaining points have the original Poisson law. For sigma-finite intensity, restrict the selected point to a finite-intensity set, condition on the independent outside process, and then exhaust the space. monotone convergence theorem proves the formula for nonnegative $H$; absolute integrability allows signed $H$.

Apply it with $H(u,\eta )=\phi (u/(u+\int v\eta (dv)))$. For the polynomial in question, $|\phi (x)|\le Cx$ on $[0,1]$, so ${\sum }_i|\phi (p_i)|\le C$ and all signed interchanges are justified. Integrating over the gamma law of the remaining total givesSet $s=u+t$ and $x=u/s$, so $u=sx$, $t=s(1-x)$ and the Jacobian is $s$. The integrand factors as $\phi (x)x^{-1}(1-x{)}^{\theta -1}{s}^{\theta -1}{e}^{-s}$. The integral defining the Gamma function cancels $\Gamma (\theta )$, yieldingFor example, setting $\phi (x)=x^k$ gives $\mathbb{E}{\sum }_i{p}_i^k=\theta B(k,\theta )=\Gamma (k)\Gamma (\theta +1)/\Gamma (k+\theta )$ for integers $k\ge 1$.

The same nonnegative calculation identifies the mean measure of Poisson-Dirichlet components for arbitrary nonnegative test functions. Write $N_a=\#\{i:p_i>a\}$. If $1/2\le a<1$, at most one component exceeds $a$, so $N_a=1_{\{p_1>a\}}$. Hence the identity directly gives the upper part of the probability distribution of the largest component of a Poisson-Dirichlet partition:Its density on $(1/2,1)$ is $\theta x^{-1}(1-x{)}^{\theta -1}$. For $\theta =1$, this tail is $-\log a$, and $\mathbb{P}(p_1>1/2)=\log 2$. On the other hand, selecting index $I$ with conditional probabilities $\mathbb{P}(I=i\mid (p_j))=p_i$ weights the mean measure of a point process by $x$. Thus $p_I$ has density $\theta (1-x{)}^{\theta -1}$, the $\mathrm{Beta}(1,\theta )$ law of a size-biased distribution. That beta law describes the selected component.

For completeness, the whole probability distribution of $p_1$ can also be specified; below one half the expected count $\mathbb{E}{N}_a$ is not itself the tail probability. Repeating the point-removal formula for $m$ ordered distinct jumps gives the factorial moment densities of Poisson-Dirichlet components:Indeed, integrate over $m$ selected jumps $u_i$ and the remaining gamma total $t$, then put $s=t+{\sum }_i{u}_i$, $x_i=u_i/s$. The Jacobian is $s^m$; the factors ${\prod }_i{u}_i^{-1}{t}^{\theta -1}$ and the Jacobian leave $s^{\theta -1}$, whose Gamma function again cancels the normalizing constant. Since $N_a<1/a$, the finite binomial identity for the indicator of $N_a=0$ now gives, for $0<a<1$,The $m=0$ term is one; an empty integration region contributes zero. This is inclusion-exclusion, since $1_{\{N_a=0\}}={\sum }_m(-1{)}^m(N_a{)}_m/m!$. Extend this cumulative distribution function by zero for $a\le 0$ and one for $a\ge 1$. For $a\ge 1/2$ only the terms $m=0,1$ can contribute, recovering the simpler formula above.