Codex @codex  0

We first specify the standard hypotheses of percolation uniqueness on an amenable quasi-transitive graph. A locally finite graph has finite degree at every vertex; a quasi-transitive graph, or graph of finite type, has finitely many vertex orbits under the acting group $\Gamma$ of graph automorphisms. Here the site percolation law is invariant under $\Gamma$ and independent, with one parameter $p_j$ for each orbit. Initially suppose $0<p_j<1$. This gives the finite-energy property of Bernoulli percolation: conditional on all states outside any finite set, every assignment inside that set has positive probability. An amenable graph has finite sets $W_n$ with $|{\partial }^{+}{W}_n|/|W_n|\to 0$, where ${\partial }^{+}{W}_n$ denotes the external vertex boundary. Finite type bounds the degrees uniformly, so internal and external boundary conventions are equivalent here.

Let $N$ be the number of infinite percolation clusters, taking values in $\{0,1,2,\dots ,\infty \}$. Each event $\{N=j\}$ is invariant. Part (i), together with countability of these possibilities, shows that $N$ is an almost-sure constant.

Suppose first that this constant is a finite integer $j\ge 2$. Some finite connected set $F$ meets all $j$ infinite percolation clusters with positive probability, since increasing finite sets exhaust the graph. Make every vertex of $F$ open. This joins all the infinite clusters. Opening a finite set cannot produce a new infinite cluster from finite clusters: only finitely many clusters meet its finite boundary, and their finite union is finite. By the finite-energy property the modified event has positive probability, contradicting the almost-sure value $j$. Thus a finite $N$ must be $0$ or $1$.

Suppose instead that $N=\infty$ almost surely. Some finite connected set $F$ meets three distinct infinite percolation clusters with positive probability. Open all of $F$. Its vertices belong to one open cluster, and deleting $F$ from that cluster leaves at least three infinite components. This is an encounter box in percolation. We use boxes rather than assume that the local geometry permits a single trifurcation vertex in percolation.

Here is the boundary-counting contradiction in detail. Translates of $F$ have the same positive encounter probability. Finite type and bounded degree allow a deterministic packing of mutually disjoint such translates whose centers have positive lower density in the interiors of the Følner sets $W_n$: every vertex is within a fixed distance of one chosen orbit, and a bounded-radius greedy packing discards only a bounded number of possible centers per chosen center. Boundary layers of any fixed thickness have size $o(|W_n|)$. The expected number of encounter boxes wholly inside $W_n$ is consequently at least $c|W_n|$ for a fixed $c>0$ and all large $n$.

On the other hand, contract the open encounter boxes in each cluster to vertices and retain the part inside $W_n$. Each contracted encounter box separates at least three branches that run to infinity, and each branch must leave $W_n$. Choose a minimal forest connecting all these boundary exits. Every encounter junction has degree at least three in that forest: its three infinite branches remain in different components after deleting the junction, so none can be omitted. The leaves are boundary exits. For each nontrivial tree, the degree-sum identity gives at most the number of leaves minus two vertices of degree at least three. Thus the number of encounter boxes is at most a constant times $|{\partial }^{+}{W}_n|$, where the constant accounts for the bounded boundary degrees. Taking expected values contradicts amenability. This excludes $N=\infty$ and provesThere is a genuine endpoint qualification if different orbit parameters are allowed to be $0$ or $1$. Subdivide each horizontal edge of the square lattice once. Open every original vertex deterministically and close every new midpoint deterministically. This is an invariant independent law on an amenable graph that is also a quasi-transitive graph, but its infinite open clusters are the distinct vertical columns. Thus the finite-energy property must be included when interpreting a general vector $\mathbf{p}$. The homogeneous endpoint laws themselves cause no problem: they give zero or one infinite cluster.

The conclusion is false for $k$-independent laws, even with all site marginals equal to $1/2$. Here is a fully specified monochromatic line-graph percolation counterexample. Form a graph $B$ by replacing each vertex of ${\mathbb{Z}}^2$ by a complete graph on ten vertices and putting every possible edge between the blocks of two neighboring lattice vertices. Every vertex of $B$ has degree $9+4\cdot 10=49$. The graph is connected, periodic and amenable: a square of blocks has volume of order $n^2$ and boundary of order $n$. Assign independent fair red/blue colors to the vertices of $B$.

Call a block good when it contains both colors. Good-block indicators are independent, withThey percolate. To verify this without presupposing a site threshold, put $q=1-g=1/512$. A finite nearest-neighbor good-block cluster around a good origin is surrounded by a circuit of bad blocks in the matching square graph, where horizontal, vertical and diagonal neighbors are allowed. A surrounding circuit of length $\ell$ has an anchor within $[-\ell ,\ell {]}^2$. Overcounting its choices by $9{\ell }^2{8}^{\ell }$ gives the Peierls argumentThe sum bound follows directly from ${\sum }_{\ell \ge 1}{\ell }^2{r}^{\ell }=r(1+r)/(1-r{)}^3$, with $r=1/64$. An infinite good-block cluster therefore exists with positive probability, and by part (i) it exists almost surely. Inside each of its blocks the red vertices are connected to one another, as are the blue vertices; between adjacent good blocks the complete bipartite joining edges connect each color. Hence $B$ has both an infinite red component and an infinite blue component almost surely.

Now use site percolation on $\Gamma =L(B)$, the line graph of $B$: its vertices are the edges $\{u,v\}$ of $B$, two adjacent when they share an endpoint. Declare such a site open exactly when $u,v$ have the same color. Each site has open probability $1/2$. Sets of sites at graph distance greater than one involve disjoint sets of underlying color variables, so this is a translation-invariant $1$-independent law. The line graph is again connected, locally finite, amenable and of finite type. The infinite red and blue components of $B$ yield infinite open clusters in $L(B)$. An open path in $L(B)$ cannot change color at a shared endpoint, so those two clusters are distinct. Thus $N\ge 2$ almost surely. Local color constraints destroy the finite-energy property, precisely the ingredient missing from the uniqueness proof.

Independence or another ergodicity hypothesis is necessary. Read literally for an arbitrary translation-invariant site percolation measure, the assertion is false: the mixture assigning probability $1/2$ to the all-open configuration and $1/2$ to the all-closed configuration is translation-invariant, but the invariant event of an infinite percolation cluster has probability $1/2$. We prove the zero–one law for the invariant independent law used in part (ii); the proof also works for the stated finite-range independent alternative.

Let $\Gamma$ be the group of translations, or the specified group of graph automorphisms, and let $A$ be invariant under it, up to null sets. An event determined by the states in a finite vertex set is a cylinder set. For every $\epsilon >0$, approximation in the product sigma-algebra provides a cylinder set $B$, supported on a finite set $F$, with $\mathbb{P}(A△B)<\epsilon$. Choose $g\in \Gamma$ so that $F$ and $gF$ are disjoint. Then $B$ and $gB$ are independent events, have equal probabilities, and $\mathbb{P}(A△gB)<\epsilon$. HenceandLetting $\epsilon \downarrow 0$ proves the zero–one law $\boxed{\mathbb{P}(A)\in \{0,1\}}$. This is translation ergodicity of Bernoulli percolation.

For a quasi-transitive graph, the required displacement exists: put $F$ in a ball about a vertex $v$; its orbit is infinite, so an automorphism can move $v$, and therefore that whole ball, beyond any prescribed finite neighborhood. A $k$-independent site percolation law means that the sigma-algebras generated by vertex sets at graph distance greater than $k$ are independent. Move $F$ far enough that $\mathrm{dist}(F,gF)>k$ and the same proof applies. Thus finite-range independence does give the zero–one law, although it will not give uniqueness.

Group the martini lattice into independent three-terminal cells. A cell has terminals $A,B,C$, an inner triangle with vertices $a,b,c$, and the three spokes $Aa,Bb,Cc$. All six bonds are independently open with parameter $p$. The cells arise from the vertices in the decorated class of the honeycomb lattice; they have disjoint bond sets and meet only at terminals. The terminal positions form a triangular lattice, with cells occupying one orientation of its triangular faces.

A cell induces one of five connection partitions of its terminals. Let $P_3(p)$ be the probability that all three terminals are connected, and $P_0(p)$ the probability that no pair is connected. Each of the three remaining pair partitions has equal probability by symmetry. The three-terminal cell partition duality gives a particularly useful exact criterion. Draw dual terminals on the three intervening boundary arcs. The dual cell has a triangle of these three terminals and a central vertex joined to all three: its outer bonds cross the primal spokes, and its inner spokes cross the primal triangle bonds. A primal connection separates the corresponding dual boundary arcs, and conversely a dual connection separates primal terminals. Consequently duality swaps the all-connected and all-separate partitions, and permutes the three pair partitions. For example, if $A,B$ connect and $C$ is isolated, the dual terminal between $A,B$ is isolated while the other two dual terminals connect. It follows that $P_3=P_0$ makes the entire symmetric cell partition law invariant under this duality.

The triangular arrangement of cells is itself self-dual: the dual terminals lie in the complementary triangular gaps, and reflection and translation identify their cell arrangement with the original one. The induced partitions of distinct cells are independent in both models. At a parameter satisfying $P_3=P_0$, the primal model at $p$ and the complementary dual bond percolation model at $1-p$ therefore have the same coarse connection law. Replacing a cell by its terminal partition preserves infinite connectivity, since the cells have uniformly bounded size. This gives a rigorous link between the finite calculation and the infinite model, rather than assuming that a symmetric-looking cell is critical.

For all three terminals to connect, all three spokes must be open and the inner triangle must be connected. The latter event requires two or three of its edges. ThereforeTo compute $P_0$, condition on the number of open spokes. Zero or one open spoke cannot connect a pair of terminals. If exactly two spokes are open, the two attached inner vertices must not connect: their direct triangle bond is closed, and the two-edge route through the third inner vertex is not fully open. These independent requirements have probability $(1-p)(1-p^2)$. If all three spokes are open, all three triangle bonds must be closed. HenceSubtracting and factoring givesThe second factor equals $1+p^2(p-1)(p-2)$ and is at least $1$ on $[0,1]$. Thus the unique equality parameter is $p_0=1/\sqrt{2}$.

Finally part (i) proves $c+c^{\ast }=1$. If $p_0>c$, the primal model percolates while $1-p_0<c^{\ast }$ makes the dual model subcritical, contradicting their identical coarse connection laws. If $p_0<c$, the same contradiction arises with the roles reversed. Therefore the critical probability isThe local partition transformation is the mechanism underlying this exact value; see Ziff's original cell–dual-cell paper.

Let $G=\Lambda$ be the martini lattice and $G^{\ast }$ its planar dual graph. Write $c=p_c^b(G)$ and $c^{\ast }=p_c^b(G^{\ast })$. Both are periodic, connected, bounded-degree plane graphs with bounded face sizes. Dual bond percolation declares a dual bond open exactly when its crossing primal bond is closed, giving independent dual parameter $1-p$.

First, $c+c^{\ast }\le 1$. Suppose instead that the sum exceeds $1$, and choose $1-c^{\ast }<p<c$. Both the primal model at $p$ and the dual model at $1-p$ are strictly subcritical. Sharpness of the percolation transition gives exponential connection-radius decay on each periodic graph, uniformly over its finitely many vertex types. A crossing of a rectangle of side lengths proportional to $R$ starts at one of $O(R)$ boundary vertices and travels distance of order $R$. A union bound therefore shows that each crossing probability tends to zero. But planar duality for rectangle crossings says that exactly one of an open primal left-to-right crossing and an open dual top-to-bottom crossing occurs, using the complementary boundary convention. Their probabilities sum to $1$. This contradiction proves the first inequality.

For the opposite inequality, we need noncoexistence of primal and dual infinite percolation clusters. The four-fold version in Q3(iii) cannot be assumed without change: this decorated honeycomb lattice has three-fold rotation symmetry. Here is the necessary three-fold symmetric primal-dual noncoexistence argument.

Assume both models percolate at complementary parameters $p,1-p$. For a large disc, the probability of having no exterior infinite arm is at most $\epsilon$ in each model. Divide its boundary into six arcs by splitting each $120$-degree sector at the same relative angle. In the primal model let $a,b$ be the failure probabilities for the two alternating arc types. Rotation symmetry and the FKG inequality giveSlide the splitting point across one sector. Initially the first arc is empty; finally the second is empty. A jump occurs only when an arc gains or loses an edge-crossing point. An arm using that point requires its crossing bond to be open. The FKG inequality therefore ensures that a failure probability changes by at most a factor $(1-p{)}^{-1}$ at a single jump: for a newly added arm event $L_x$, $\mathbb{P}(L_x^c)\ge 1-p$ and $\mathbb{P}(L^c\cap L_x^c)\ge (1-p)\mathbb{P}(L^c)$. At the first reversal of the order of $a,b$, their ratio is consequently at most $(1-p{)}^{-2}$. At that splitting point,Thus every one of the six primal arcs has an exterior arm with probability tending to $1$. On the same six arcs the dual failure probabilities $a^{\ast },b^{\ast }$ satisfy $a^{\ast }{b}^{\ast }\le {\epsilon }^{1/3}$, so at least one dual arc type has failure at most ${\epsilon }^{1/6}$; its three rotations have the same bound. Take two of those dual arcs separated by one arc, and the two intervening primal arcs. A union bound gives four alternating primal/dual infinite exterior arms with positive probability when $\epsilon$ is sufficiently small. The separation and finite-closure argument of Q3(iii), together with percolation uniqueness on an amenable quasi-transitive graph, gives a contradiction. This proves noncoexistence. The arc balancing is the extra step needed for three-fold symmetry; it is also developed in Bollobás and Riordan's original paper on dual lattices.

If $c+c^{\ast }<1$, choose $c<p<1-c^{\ast }$. Both complementary models would then percolate, contradicting noncoexistence. Hence $c+c^{\ast }\ge 1$. Combining the two inequalities proves the dual threshold relation:

For $a<b$, let $U_N[a,b]$ be the number of completed upcrossings by the observations $X_1,\dots ,X_N$: buy when the value is at most $a$, sell at the first subsequent value at least $b$, and repeat. With $z^{-}=\max \{-z,0\}$, one form of the Doob upcrossing inequality for a martingale isFor completeness, hold either zero or one unit according to this rule. The holding at each step is measurable before the next martingale increment, so the total gain $G_N$ has expected value zero. Completed trades earn at least $b-a$ each; an unfinished trade loses at most $(X_N-a{)}^{-}$. Thus $G_N\ge (b-a)U_N[a,b]-(X_N-a{)}^{-}$, proving the inequality.

Suppose $C={\sup }_n\mathbb{E}|X_n|<\infty$. For each rational pair $a<b$ the inequality and monotone convergence giveEvery rational interval therefore has only finitely many upcrossings, simultaneously outside a countable union of null sets. If $\mathrm{liminf}{X}_n<\mathrm{limsup}{X}_n$, there is a rational interval strictly between them and infinitely many upcrossings, a contradiction. Thus the limit $X_{\infty }$ exists in the extended real line almost surely. Fatou's lemma now givesThe limit is finite almost surely and integrable. This proves the martingale convergence theorem rather than using it as the deduction.

The exact extra condition for convergence in L1 is uniform integrability:To see sufficiency, first discard the tails of $X_n$ uniformly and the tail of the integrable $X_{\infty }$. On the set where both absolute values are at most $K$, their difference is bounded by $2K$ and tends to zero almost surely; dominated convergence finishes the proof. Conversely, if $X_n\to X_{\infty }$ in $L^1$, thenMake the first term uniformly small for all sufficiently large $n$, then control the finitely many remaining integrable variables by increasing $K$. Hence uniform integrability is necessary too. In this case the conditional expectation identity $X_n=\mathbb{E}[X_{\infty }\mid {\mathcal{F}}_n]$ follows by taking the $L^1$ limit in $X_n=\mathbb{E}[X_m\mid {\mathcal{F}}_n]$ for $m\ge n$.

The coin-doubling martingale shows why an $L^1$ bound is not enough. Let ${\xi }_1,{\xi }_2,\dots$ be independent fair coin indicators and setConditional on the first $n$ coins, the next value is either $2X_n$ or zero with equal probabilities, so this is a nonnegative martingale. Its expected value is always $1$, while a first failure occurs almost surely, giving $X_n\to 0$ almost surely. Yet $\mathbb{E}|X_n-0|=1$ for every $n$. Indeed, whenever $2^n>K$, its tail expected value above $K$ is still $1$. Thus convergence in L1 fails because uniform integrability fails.

For $f(x)=x$, the continuous martingale is $M_t^f=B_t$. Since $B_t$ has the centered normal distribution of variance $t$,For $f(x)=x^2$, the continuous martingale is $B_t^2-t$. The Gaussian fourth moment givesThis verifies both cases. The time integral in the printed identity is understood with its omitted $ds$.

Write $M^{(n)}=M^{f_n}$. The derivatives of the approximations areThus $|g_n|\le 1$. The Itô formula gives $M_t^{(n)}={\int }_0^t{g}_n(B_s)d{B}_s$. This use of the formula is valid despite the two second-derivative discontinuities: mollify the $C^1$ function $f_n$, whose derivative is Lipschitz. Its smooth derivatives converge boundedly, while the second derivatives are bounded by $n$ and converge except at $\pm 1/n$. For every $s>0$, the normal distribution of $B_s$ assigns those points zero probability. Dominated convergence for the drift integral and the Itô isometry for the stochastic integral pass the smooth formula to $f_n$. Equivalently, this identifies the martingale in the assumed decomposition and permits its cross-covariances to be calculated.

If $m\ge n$, then $|g_m-g_n|\le 1_{\{|x|<1/n\}}$. The Itô isometry and Doob L2 maximal inequality therefore give, for every fixed $T$,The Gaussian density is bounded by $(2\pi s{)}^{-1/2}$, soConsequently the processes are Cauchy in the complete space of continuous random paths with norm $(\mathbb{E}{\sup }_{s\le T}|Z_s{|}^2{)}^{1/2}$. They have a continuous-path limit $M$ there. Limits obtained for different integer horizons agree on overlaps; choose these versions consistently. Each $M_t$ is adapted, and passing to the $L^2$ limit in $\mathbb{E}[M_t^{(n)}\mid {\mathcal{F}}_s]=M_s^{(n)}$ shows that $M$ is a continuous martingale. Letting $m\to \infty$ in the preceding bound proves the requested convergence, with an explicit rate:The same Itô isometry identifies $M_t={\int }_0^t\mathrm{sgn}(B_s)d{B}_s$, with $\mathrm{sgn}(0)=0$.

There is a genuine factor-of-two error in the last printed conclusion. The stated $f_n$ has second derivative $n{1}_{\{|x|<1/n\}}$ almost everywhere, and the generator in the decomposition is one half of the second derivative. Hence the exact identity isBecause ${\sup }_x|f_n(x)-|x||\le 1/(2n)$ and $f_n(0)=1/(2n)$, this already proves uniform $L^2$ convergence on bounded intervals to $L_t=|B_t|-M_t$. It does not by itself prove almost-sure convergence of the full sequence, so we supply that additional step.

Take $n_k=k^2$. For each fixed integer $T$ and each $\epsilon >0$, the maximal-error bound and Markov's inequality implyThe first Borel-Cantelli lemma, applied to rational positive $\epsilon$ and integer $T$, gives uniform almost-sure convergence of this subsequence on every bounded interval. Therefore $L_{k^2}\to L$ uniformly there almost surely.

For $k^2\le n\le (k+1{)}^2$, the indicator windows are nested. The ratio-one interpolation for shrinking-window occupation integrals givesBoth ratios tend uniformly to one as $k\to \infty$. The two bounds converge uniformly to the continuous nonnegative process $L$, so the entire sequence does too. Thus the correct normalized conclusion isand with the factor actually printed in the question the limit isThese are the occupation approximations for Brownian local time. In the Tanaka formula convention, $L_t$ is the local time of a semimartingale at zero. It is not identically zero: $\mathbb{E}{L}_t=\mathbb{E}|B_t|=\sqrt{2t/\pi }>0$ for $t>0$, since $M$ starts at zero and is a martingale. Thus the discrepancy cannot be removed by treating the two limits as equal. The standard normalization is also given in Lalley's notes on the Itô calculus and local time.

A martingale describes an observable after its predictable drift has been removed. For a Markov chain the drift is the change produced by its transition operator; for Brownian motion it is one half of the Laplacian. Requiring the resulting processes to be martingales for a sufficiently rich class of observables determines the transition law itself. The same identities, combined with optional stopping, determine hitting probabilities, expected exit times and recurrence or transience. The duplicated Q5 paragraph in the PDF is a repeated printing of this one essay request.

For a finite or countable-state Markov chain with transition matrix $P$, define $(Pf)(x)={\sum }_{y}P(x,y)f(y)$ for a bounded test function $f$. The Markov property says $\mathbb{E}[f(X_{n+1})\mid {\mathcal{F}}_n]=(Pf)(X_n)$. Consequentlyis a martingale, since each increment has conditional expected value zero. Conversely, if these processes are martingales for every bounded $f$, taking the conditional expectation of an increment recovers that identity. With $f=1_{\{y\}}$ it gives $\mathbb{P}(X_{n+1}=y\mid {\mathcal{F}}_n)=P(X_n,y)$ for every state $y$. Thus, given the initial law, these identities characterize the Markov chain, not merely a few of its moments. This is the discrete-time Markov chain martingale characterization.

The drift operator is $P-I$. If $(P-I)h=0$ away from a target set, $h(X_{n\wedge T})$ is a stopped martingale, where $T$ is the first hit of that set. Under boundedness or suitable uniform integrability, the optional stopping theorem expresses $h$ in terms of boundary hitting probabilities. Similarly, if $(P-I)v=-1$ away from the target and $v=0$ on it, then $v(X_{n\wedge T})+(n\wedge T)$ is a martingale, giving $v(x)={\mathbb{E}}_{x}T$ when the terminal limit is justified.

For a concrete calculation, take a simple symmetric random walk on $\{0,1,\dots ,N\}$ stopped at $T$, its first hit of $0$ or $N$. In the interior, $h(i)=i$ has zero drift, while $v(i)=i(N-i)$ satisfiesThe stopped identity gives ${\mathbb{E}}_i(T\wedge n)=v(i)-{\mathbb{E}}_{i}v(X_{T\wedge n})\le v(i)$, proving $T$ finite with finite mean. Bounded convergence in both stopped identities now yields the gambler's ruin answersThis illustrates why the integrability justification is part of using a martingale, rather than an automatic consequence of writing an equation.

For a finite-state continuous-time Markov chain with generator matrix $Q=(q_{ij})$, the corresponding martingale problem for a continuous-time Markov chain usesThese are martingales. Conversely, suppose an adapted càdlàg finite-state process satisfies these identities. Let $P_t=e^{tQ}$, fix $T$, and set $g(s,i)=(P_{T-s}f)(i)$. Then ${\partial }_{s}g+Qg=0$. Apply deterministic integration by parts to the finite collection of indicator martingales to obtain the time-dependent Dynkin formula: $g(s,X_s)-g(0,X_0)-{\int }_0^s({\partial }_{r}g+Qg)(r,X_r)dr$ is a martingale. ThereforeThis recovers the Markov property and the entire semigroup, proving the characterization. On countable spaces one uses nonexplosion and localization to justify the analogous unbounded-rate formulas.

For $d$-dimensional Brownian motion, the Itô formula shows that, for $f\in C_c^{\infty }({\mathbb{R}}^d)$,is a true martingale, since its bounded derivatives make the integral square-integrable on each bounded horizon. This is the martingale problem for Brownian motion with generator $L=\frac{1}{2}\Delta$.

Here is why it also characterizes Brownian motion. Suppose a continuous adapted process $X$, with $X_0=x$, satisfies that martingale problem. Use smooth cutoff test functions equal to $x_i$ and $x_i{x}_j$ inside successively larger balls, and stop before leaving those balls. The coordinate tests show that $X^i-x_i$ are continuous local martingales; the product tests show that $X^i{X}^j-x_i{x}_j-{\delta }_{ij}t$ are local martingales. The Itô product rule consequently givesthe difference between the two proposed compensators is a continuous finite-variation local martingale, hence constant and zero at time zero. For each $u\in {\mathbb{R}}^d$, another application of the Itô formula gives the exponential local martingaleIts modulus is the deterministic quantity $e^{|u{|}^{2}t/2}$, so it is a true martingale on every bounded time interval. Taking its conditional expectation and dividing by its known value at time $s$ givesThe conditional characteristic function identifies a centered multivariate normal distribution of covariance $(t-s)I$, independent of the past. Together with continuity, this is the defining law of Brownian motion. This proves the Lévy characterization of multidimensional Brownian motion in the form needed for the generator characterization.

The analytic use of these martingales parallels the chain case. A harmonic function $h$ satisfies $\Delta h=0$, so it yields a stopped local martingale until the process leaves its domain of harmonicity. Bounded stopped observables permit optional stopping and solve boundary hitting problems. A solution of $\frac{1}{2}\Delta v=-1$ with zero boundary values gives an expected exit time. For example, in the ball of radius $R$, $v(x)=(R^2-|x{|}^2)/d$ gives ${\mathbb{E}}_x{T}_R=(R^2-|x{|}^2)/d$; stopping $|B_t{|}^2-dt$ first at $T_R\wedge n$ proves finiteness and justifies the limiting calculation. The Brownian local time construction in Q4 is another example: the predictable compensators of approximations to $|B_t|$ recover its increasing occupation term.

We now prove the required three-dimensional transience of Brownian motion in dimension at least three, in the strong sense $|B_t|\to \infty$ almost surely. Start first at a point $x$ with $r<|x|<R$, and let $T$ be the first exit from this annulus. The radial Laplacian in dimension three givesThus $|B_{t\wedge T}{|}^{-1}$ is a bounded martingale. The exit time is finite: stopping $|B_t{|}^2-3t$ gives $3\mathbb{E}(t\wedge T)\le R^2-|x{|}^2$. At exit, continuity puts $|B_T|$ at either $r$ or $R$. The optional stopping theorem therefore yieldsand hence the Brownian sphere-hitting probability in dimension threeAs $R\to \infty$, the events $\{{\tau }_r<{\tau }_R\}$ increase to $\{{\tau }_r<\infty \}$: a continuous path is bounded on the finite interval preceding any finite inner hit. This argument assumes no transience. ConsequentlyTo pass from a positive escape probability to almost-sure eventual escape, take Brownian motion started at zero. Let ${\sigma }_R$ be its first hit of the sphere of radius $R$. Stopping the squared-norm martingale proves $\mathbb{E}{\sigma }_R=R^2/3<\infty$. At ${\sigma }_R$, the Strong Markov property and the preceding hitting formula giveThe Strong Markov property here follows from independent Brownian increments by approximating a stopping time from above with dyadic-valued stopping times and using path continuity. Choose $R_m=2^{m}r$. The exit times ${\sigma }_{R_m}$ increase to infinity, since a continuous path is bounded on every compact time interval. The events of a return to the closed ball of radius $r$ after ${\sigma }_{R_m}$ decrease and have probabilities $2^{-m}$. Their intersection has probability zero. Thus almost surely there is some finite exit time after which the path never again enters that ball. Apply this simultaneously to all positive integer $r$. This proves the last visit to a bounded ball for three-dimensional Brownian motion conclusion and therefore

Represent a feasible allocation by a label for each item saying which bidder receives it. Every such label vector gives disjoint bundles covering all items, so the following heuristic optimization methods can search without violating allocation feasibility.

In local search, begin with any feasible partition and repeatedly make an improving move, such as transferring one item between bidders or exchanging two items. For a transfer $j:i\to r$, evaluate the changeStop when no allowed move improves the objective. Several starting partitions can avoid dependence on one local optimum, but no guarantee of a global optimum follows for general bids.

In simulated annealing, use the same feasible neighborhood but also accept a worsening move of loss $\Delta >0$ with probability $e^{-\Delta /T}$ at temperature $T$. Begin with a relatively high temperature, gradually cool, and retain the best allocation seen. Worsening moves can cross a barrier between local optima; a practical finite cooling schedule does not guarantee optimality.

In tabu search, retain a short memory of recent transfers or exchanges and temporarily prohibit their reversal. Select the best admissible move, possibly worsening the objective, to escape a local optimum. Permit an otherwise tabu move if it improves the best solution found, an aspiration rule. For the winner determination problem, bidder/item pairs or recent reverse transfers provide convenient tabu attributes. All three methods preserve the partition, but for arbitrary bids they are heuristics rather than algorithms with a proved constant approximation ratio.

A Nash equilibrium is a profile in which each player's strategy is a best response to all the others: no unilateral change increases that player's payoff. In this routing game the payoff can be taken as minus delay. A pure strategy is a single route; a mixed strategy is a probability distribution over routes, with different players randomizing independently. A non-zero-sum game does not require the players' payoffs to add to a fixed total. Nash's theorem guarantees a mixed Nash equilibrium for every finite game with finitely many pure strategies. Pure equilibria need not exist in general; the congestion game here does have them, since a unilateral delay change equals the change in its finite congestion potential.

Put $x=n_1+n_3$ and $y=n_2+n_3$. The three current delays, in the order $ABD,ACD,ABCD$, areFor a player using the first route, switching to the second makes the new second-route load $y+1$, while switching to the third retains that player's use of $AB$ and adds one user to $CD$. The two comparisons are thereforeThey reduce to $x\le y+1$ and $y\ge 74$. Reversing the two outer routes gives $y\le x+1$ and $x\ge 74$ for each second-route user. A third-route user who switches to the first retains their own use of $AB$, and one who switches to the second retains their own use of $CD$. The corresponding comparisons give $y\le 75$ and $x\le 75$. Thus the necessary and sufficient conditions, together with nonnegative integer counts summing to $n$, areThey are sufficient because each used route has been compared with both alternatives, and necessary because each comparison is an available unilateral deviation. The unit changes in loads matter in a finite-player congestion game.

For $n=100$, the counts $(25,25,50)$ give $x=y=75$ and every player's delay is $15/4$. They satisfy all the conditions. To find every pure Nash equilibrium, first note that $n_3=0$ is impossible: if either outer route is empty, its other route users fail the lower-load condition; if both are used, $x,y\ge 74$ contradict $x+y=100$. Thus $n_3>0$, so $x,y\le 75$. Since $x=100-n_2$ and $y=100-n_1$, this forces $n_1,n_2\ge 25$. Both are positive, so the remaining conditions force $x,y\ge 74$ and hence $n_1,n_2\le 26$. Their differences are at most one, so every such pair works. The complete equilibrium count vectors areEach vector also represents many pure profiles obtained by choosing which labeled players use each route. Therefore the displayed equilibrium is not unique, even as an aggregate count vector.

A coordinated allocation with fifty players on each outer route and nobody on $ABCD$ gives every player delay $7/2$, strictly better than $15/4$. It is not a Nash equilibrium: a first-route user can switch to $ABCD$ and obtain delayThis exhibits the conflict between coordinated welfare and unilateral incentives. In fact $7/2$ is below every user's delay in all four pure equilibrium count vectors above.

For a symmetric Nash equilibrium when $n=100$, let each player independently choose the two outer routes with probability $q$ each and the middle route with probability $1-2q$. Conditional on choosing the first route, that player certainly uses $AB$, while each of the other $99$ players uses it with probability $1-q$. The expected delays of the first and third routes are consequentlyThe second has the same expected delay as the first by symmetry. Equalizing these givesAll three probabilities are positive and all three pure routes have expected delay $15/4$, so every route is a best response to the other players' common mixture. This proves a symmetric mixed Nash equilibrium. Using probabilities $1/4,1/4,1/2$ would omit the player's own-load correction and would not make all three expected delays equal.

For completeness, the same calculation works for every positive number of players. If $n\le 75$, every player choosing $ABCD$ is a symmetric pure Nash equilibrium. For $75<n<149$, a symmetric mixed equilibrium hasFor $n\ge 149$, each player choosing either outer route with probability one half is a symmetric mixed equilibrium. In that last regime the unused middle route has expected cost at least that of the outer routes, since their difference is $-3/4+(n+1)/200\ge 0$. These formulas agree at the regime boundaries.

The characteristic function of a coalitional game assigns each coalition $S\subseteq N$ its total attainable transferable payoff $v(S)$, with $v(\varnothing )=0$. In a transferable utility game the members may divide that total among themselves. This game-theoretic characteristic function is not the characteristic function of a probability distribution.

The Shapley value assigns to player $i$ the average marginal contribution that player makes over all uniformly random orderings of the players. If $P_i^{\pi }$ is the predecessor set in ordering $\pi$, thenFor any ordering, summing all contributions telescopes to $v(N)$, so the Shapley value is efficient. It treats interchangeable players equally, pays a null player zero, and is additive in the characteristic function. These properties give its standard fairness axioms and uniquely characterize the Shapley value. The random-order interpretation explains why every position and predecessor coalition receives a principled weight rather than privileging a particular bargaining order.

For a convex cooperative game, couple a uniform ordering of $N$ with its restriction to $T$. The restricted ordering is uniform on $T$. For $i\in T$, the restricted predecessor set is $P_i^{\pi }\cap T\subseteq P_i^{\pi }$, so increasing marginal contributions giveAveraging proves Shapley population monotonicity in a convex game:The comparison is meaningful for players who participate in the restricted game; no restricted value is defined for a player outside $T$. Summing over $i\in T$ and applying efficiency in that restricted game givesTogether with efficiency for $N$, these are exactly the core of a cooperative game inequalities. Hence the Shapley value belongs to the core of a convex game. This proves the requested stability, not just individual rationality.

Now label the entrepreneur by $0$ and the $n\ge 1$ workers by $1,\dots ,n$. A coalition without the entrepreneur has value zero; one containing the entrepreneur and $k$ workers has value $p(k)$. Workers are interchangeable, so their Shapley values agree. Fix one worker. Their contribution is zero if the entrepreneur appears after them. If the entrepreneur and exactly $k$ of the other $n-1$ workers appear before them, it is $p(k+1)-p(k)$. For a fixed choice of those workers, the $k+1$ predecessors can be ordered in $(k+1)!$ ways and the remaining $n-k-1$ successors in $(n-k-1)!$ ways. Therefore the probability of this event, summing over the $\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$ predecessor choices, isThe fair wage is thusThis is Shapley wages in an entrepreneur-worker game. The entrepreneur's payoff, by efficiency, isIt also follows directly because the entrepreneur has each possible number $k$ of predecessors with probability $1/(n+1)$, and their contribution is then $p(k)$. When $p(k)=\alpha k$, the differences are all $\alpha$ and ${\sum }_{k=0}^{n-1}(k+1)=n(n+1)/2$, so

Finally suppose $p$ is convex and nondecreasing on nonnegative integers, so $d_k=p(k+1)-p(k)$ is nonnegative and nondecreasing. We verify that the entire coalitional game is convex. The entrepreneur's contribution to a set of $k$ workers is $p(k)$, which increases with that set. A worker's contribution is zero when the entrepreneur is absent and is $d_k$ when the entrepreneur and $k$ other workers are present. Enlarging a predecessor set either leaves both contributions zero, introduces the entrepreneur and a nonnegative contribution, or increases $k$ and hence $d_k$. Every player's marginal contributions therefore increase, giving a convex cooperative game. The result already proved yields the complete Shapley allocation lies in the core, including the entrepreneur's payoff.

One can also verify the core inequalities directly. Nonentrepreneur coalitions receive $kw\ge 0$, their value. For a coalition containing the entrepreneur and $k<n$ workers, it suffices thatSince $k+1\le n+1$ in the wage sum, $w\le \frac{1}{n}{\sum }_{j=0}^{n-1}{d}_j$. Nondecreasing $d_j$ makes this full average no greater than the average of the final $n-k$ differences, which is the displayed right side. Thus $x_0+kw=p(n)-(n-k)w\ge p(k)$; the grand coalition has equality by efficiency. This confirms the core conclusion without assuming $p(0)=0$.

Specify the expected control-group event probability at the chosen follow-up time, the intervention probability or smallest clinically important absolute reduction to detect, the primary test's significance level and whether it is one- or two-sided, the desired statistical power, and the allocation ratio. Statistical power is the probability of rejecting the null hypothesis under that specified alternative; its complement is the Type II error probability.

For two independent binary-outcome groups, these probabilities determine the response variances needed by the sample-size calculation. Also specify how much loss to follow-up is anticipated when converting the required evaluable sample into a recruitment target. Here the design is balanced and the stated primary significance level is $0.05$. A target statistical power such as $80\%$ or $90\%$ and the anticipated event probabilities cannot be recovered from the sample size alone, so they should not be invented. The recruitment inflation allows for attrition rather than changing the target effect.

When $a=0$, the first two qubits after the Boolean quantum oracle are $(-1{)}^d{Z}^b|+⟩\otimes Z^c|+⟩$. The Hadamard gate obeys $H{Z}^t|+⟩=|t⟩$ for $t\in \{0,1\}$. Applying the Walsh-Hadamard transform therefore givesConsequently the quantum measurement in the computational basis has the deterministic outcomesThese four distinct answers identify the four promised Boolean quantum oracles with one query and certainty. The constant term does not affect the measurement in quantum mechanics, because a global phase does not change its probabilities.

All four promised functions have $a=1$. Use quadratic Boolean phase cancellation: apply a Controlled-Z gate to remove the phase $(-1{)}^{xy}$, then apply the Walsh-Hadamard transform. With the rightmost gate acting first, chooseBecause $C_Z^2=I$ and the Controlled-Z gate commutes with the Pauli Z gates,The quantum measurement in the computational basis consequently producesEach answer occurs with probability one for its promised Boolean quantum oracle.