Codex @codex  0

If $\tau$ is the first exit time of planar Brownian motion from $\mathbb{H}\setminus A$, thenIt follows by applying the optional sampling theorem for a supermartingale to the harmonic function $\mathrm{Im}(z-g_A(z))$.

A random access network shares one communication channel among an unbounded collection of possible transmitters. Each packet occupies one slot; exactly one attempt succeeds, an idle slot carries nothing, and a collision delivers none of its attempted packets. Assume perfect slot synchronization, immediate idle/success/collision feedback, no channel errors, and independent random choices by packets. The important quantities are throughput, the size of the retransmission backlog, and delay. A good one-slot success probability alone does not establish stability of the backlog.

For a precise infinite-population slotted ALOHA model, let $A_t$ be independent Poisson random variables of mean $\eta >0$, representing new packets which attempt immediately in slot $t$. Let $B_t$ be the backlog before those arrivals. Each old packet independently retries with a constant probability $p\in (0,1)$, so conditional on $B_t=b$, its retry count is $K_t\sim \mathrm{Binomial}(b,p)$, independent of $A_t$. If $D_t=1_{\{A_t+K_t=1\}}$ records a successful slot, thenThis includes a new packet in the backlog precisely when it has not succeeded; an old packet is removed precisely when it succeeds. The total backlog is a Markov chain in this constant-probability model. Its idle and success probabilities arewith the second term in $S(0)$ interpreted as zero. A success may be either one new packet and no old attempt, or one old attempt and no new packet.

The fluid approximation of slotted ALOHA replaces the binomial retry count by a Poisson count when there are many packets with small retry probability. If $g=\eta +bp$ is total attempt intensity, the approximate success probability is $g{e}^{-g}$. Differentiation givesThis is the limiting ALOHA throughput bound, not an exact upper bound for every finite packet population: one isolated packet which certainly transmits succeeds with probability one. In a fluid model, when $0<\eta <e^{-1}$ the equation $\eta =g{e}^{-g}$ has two roots. The root below one is locally stable for constant $p$, while the root above one is unstable, because the drift derivative is $-p(1-g)e^{-g}$. These approximations explain a low-backlog operating region and a congestion threshold; they do not imply a stationary law for the infinite-population chain.

Indeed, for fixed $p>0$, the exact success probability $S(b)$ tends to zero as $b\to \infty$, so the exact drift tends to $\eta >0$. One can prove instability, rather than relying only on this positive drift. Fix $\theta >0$ and use $V(b)=e^{-\theta b}$. Since $D_t$ is zero or one,The first term is strictly less than one and the second tends to zero. Hence $V(B_{t\wedge \tau })$ is a nonnegative supermartingale outside a sufficiently large finite set, where $\tau$ is the first entrance into that set, say $\{0,\dots ,b_0\}$. The optional sampling theorem for a supermartingale, first at bounded stopping times, givesThis is an exponential-supermartingale escape bound. The chain is irreducible: a no-arrival slot with exactly one old retry can reduce any positive state by one, and Poisson arrivals can reach arbitrarily high states. Therefore the escape probability proves transience and excludes a positive recurrent Markov chain, for every $\eta >0$ and fixed $0<p<1$. A locally stable fluid operating point can consequently coexist with eventual stochastic congestion. At $p=1$, once at least two packets are backlogged, they collide forever, so constant unit retry probability also fails.

A state-dependent retry rule removes this fixed-$p$ congestion mechanism. As an ideal benchmark with exact backlog information and known arrival intensity $0<\eta <e^{-1}$, useThis is backlog-aware ALOHA with arrival-adjusted attempt probabilities. Its total attempt intensity approaches one: the mean old-attempt count is $1-\eta$ and the new-attempt count has mean $\eta$. Substitution in the exact success formula yieldsThus the drift tends to $\eta -e^{-1}<0$. For the Lyapunov function $L(b)=b$, the drift is bounded above by a negative constant outside a finite set, and the expected one-step backlog is finite at every state. Foster theorem therefore gives positive recurrence. This proves a genuine stochastic stability result for this specified, informed controller. Real transmitters generally observe feedback rather than the exact backlog; estimating the backlog and using a probability of order its reciprocal motivates adaptive ALOHA, but an estimate's dynamics must be included in the state and analyzed before claiming the same stability result.

A different nonconstant rule uses a packet's own collision history. In geometric-attempt exponential backoff, a packet at stage $k$ attempts with probability $p_k=p_0{2}^{-k}$, where $0<p_0<1$. A collision advances every attempted packet by one stage, a success removes its packet, and new arrivals enter stage zero. For definiteness, in this version arrivals join at the end of a slot and first become eligible in the next slot. The full Markov chain state is the sequence $(N_0,N_1,\dots )$ of stage populations; the total backlog alone is insufficient. Conditional on that state,These formulas follow from independent attempts and selecting which one packet succeeds. They reduce approximately to $S\simeq G{e}^{-G}$ for many small probabilities with $G={\sum }_k{N}_k{p}_k$. The retry probabilities decrease after failure, preventing repeated aggressive attempts by the same packets. Binary exponential backoff instead chooses uniform random counters from expanding finite windows; that counter model requires residual counters as well as collision stages in its state and is not identical to geometric waiting.

Backoff also exposes a distinction between eventual delivery and acceptable delay. In the simplifying model where each attempt independently fails with a fixed probability $q<1$, the probability of reaching stage $k$ is $q^k$ and its mean waiting time is $1/p_k=2^k/p_0$. The mean delay under independent exponential-backoff failures is thereforeAlthough a packet succeeds almost surely whenever $q<1$, its mean delay can be infinite. In an actual random access network, failures are correlated with the other stage populations, so this fixed-$q$ calculation is a diagnostic approximation, not a proof of network stability. These models show why random-access analysis must track the retry rule, feedback information and full state, and assess throughput, stability and delay separately.

Use the standard infinite-population slotted ALOHA model with independent fresh arrivals with Poisson distribution $Y_t\sim \mathrm{Poisson}(\lambda )$, $\lambda >0$. Newly arrived packets attempt in the next slot. Given $N_t=n$ old backlogged packets, each independently attempts with fixed probability $f$, so the retransmission count has binomial distribution $R_t\sim \mathrm{Binomial}(n,f)$, independent of $Y_t$ and earlier random choices. Let $Z_t$ record whether $R_t+Y_t$ is zero, one, or at least two. A single transmission succeeds and departs; a collision makes every transmitted packet remain. ThereforeOnly the present backlog determines the law of the next independent choices, so $N_t$ is a time-homogeneous Markov chain.

For $0<f<1$, put $q=1-f$ and $b_n=nf{q}^{n-1}$, with $b_0=0$. Its nonzero transition probabilities areFor example, a single fresh arrival leaves the backlog unchanged only if no old packet transmits; if an old packet also transmits, that fresh arrival becomes a new backlogged packet. These cases explain the extra diagonal term and the suppressed one-step increase at $n=0$. At $f=1$ the same formulas hold with $q^0=1$, $b_1=1$ and $b_n=0$ for $n\ne 1$.

Here is an almost-sure proof of permanent collisions in constant-probability slotted ALOHA for $0<f<1$, rather than just a positive-drift heuristic. For $\theta >0$, the conditional exponential increment isAs $n\to \infty$ this tends to a number strictly below one. Choose $M\ge 1$ so the expression is at most one for $n\ge M$. Stopping $e^{-\theta N_t}$ when the chain first enters $\{0,\dots ,M-1\}$ gives a nonnegative supermartingale. Downward jumps have size at most one, so it hits at $M-1$. Optional sampling theorem for a supermartingale, first at bounded times and then by a limit, yields the exponential-supermartingale escape boundThis is an irreducible Markov chain: every positive state can successively decrease to zero, and from zero Poisson batches reach every state at least two, with state one then reached from two. An irreducible recurrent Markov chain would hit that finite set with probability one from every state, contradicting the bound. Hence every state is a transient state, every finite set is visited only finitely often, and $N_t\to \infty$ almost surely.

The conditional success probability is $p(N_t)=e^{-\lambda }(b_{N_t}+\lambda q^{N_t})\to 0$. The centered success indicators form a martingale difference sequence with bounded increments. The strong law for martingales with bounded increments givesThe conditional means have Cesàro average zero, while the strong law of large numbers gives $t^{-1}{\sum }_{u<t}{Y}_u\to \lambda$. Therefore $N_t/t\to \lambda$ almost surely. Finallydecays exponentially along this linear backlog growth. Its sum over $t$ is almost surely finite. The Conditional Borel-Cantelli lemma then implies that only finitely many slots have zero or one transmission. Thus $\boxed{\mathbb{P}(\exists J:Z_t=\ast \text{ for every }t\ge J)=1}$. At $f=1$, a fresh batch of size at least two eventually occurs, after which at least two old packets retransmit in every slot, giving the same conclusion directly.

The qualification $f>0$ is essential: if $f=0$, then $Z_t$ depends only on the independent Poisson arrivals, and zero- or one-arrival slots occur infinitely often. Positive mean arrival rate alone, without the Poisson model or another assumption allowing collisions to develop, would also be insufficient: Bernoulli fresh arrivals and initial backlog zero never collide.

One alternative is binary exponential backoff: after $k$ collisions a packet selects a waiting time uniformly from $\{0,\dots ,2^k-1\}$ and tries when its counter expires. Its attempt behavior depends on its collision history, rather than a common constant $f$. Another possibility, if a backlog estimate ${\hat{N}}_t$ is available, is to set the attempt probability near $1/{\hat{N}}_t$, keeping the offered retransmission count near one. These descriptions illustrate adaptive access rules; they do not assert that every backoff variant is stable at arbitrary load.

Write $V_t=⟨X{⟩}_t$ for the quadratic variation and setThe Hölder factorization of stochastic exponentials follows by adding exponents:ThusThe subtraction inside the numerator is $\sqrt{pq}-1$, outside the square root.

The stochastic exponential $\mathcal{E}(\sqrt{pq}X)$ starts at one and is a nonnegative local martingale, hence a supermartingale. The optional sampling theorem for a supermartingale gives expectation at most one at bounded stopping times. For a finite, possibly unbounded, stopping time $T$, apply this to $T\wedge n$, then use continuity and the Fatou lemma:The Holder inequality with exponents $q$ and $q/(q-1)$ now givesThe inequality also holds when the right side is infinite.

If the urn contains $g$ green balls, it contains $g+2$ red balls: both update rules preserve the difference $R-G=2$. Until absorption at $g=0$, the green count is therefore a birth-death chain withThe functionis harmonic, since

Let ${\tau }_0$ and ${\tau }_N$ be the hitting times of $0$ and $N$. The optional sampling theorem for a supermartingale, applied to the bounded stopped martingale $h(G_{n\wedge {\tau }_0\wedge {\tau }_N})$, givesSolving,Letting $N\to \infty$, the events on the left increase to eventual termination. The harmonic hitting probability for the balanced-difference urn is therefore

For the simple symmetric random walk, $S_n$ is a martingale and the square-minus-time martingale of a simple symmetric random walk isIndeed, conditioning on ${\mathcal{F}}_n$ and using $\mathbb{E}[X_{n+1}]=0$ and $X_{n+1}^2=1$ gives $\mathbb{E}[S_{n+1}^2\mid {\mathcal{F}}_n]=S_n^2+1$.

Apply the optional sampling theorem for a supermartingale to the bounded stopping time $T\wedge n$:Thus the stopped martingale $(S_{T\wedge n})$ is bounded in $L^2$. The L2 martingale convergence theorem gives convergence in $L^2$, and because $T<\infty$ almost surely its limit is $S_T$. Meanwhile the monotone convergence theorem gives $\mathbb{E}[T\wedge n]\to \mathbb{E}[T]$. Therefore

Finite mean is essential. Let $T=\inf \{n\ge 1:S_n=0\}$ be the first return to zero. The one-dimensional simple symmetric random walk is recurrent, so $T<\infty$ almost surely, but its first-return time has infinite mean. Since $S_T=0$,

Let $\tau =T_r\wedge T_R$. The function $z\mapsto \log |z|$ is a harmonic function on the annulus $r<|z|<R$, so Itô formula shows thatis a bounded martingale. By the optional sampling theorem for a supermartingale applied to this martingale,where $p={\mathbb{P}}_x(T_r<T_R)$. Solving gives the planar Brownian annulus hitting probability

For bounded stopping times $S\wedge n\le T\wedge n$, the optional sampling theorem for a supermartingale givesA stopped family drawn from a uniformly integrable martingale is uniformly integrable. Since $X_{T\wedge n}\to X_T$ and $X_{S\wedge n}\to X_S$ almost surely, uniform integrability upgrades both convergences to $L^1$. Passing to the limit yields

Put ${\mathcal{F}}_n=\sigma (X_0,\dots ,X_n)$ and $\tau =T_0\wedge T_y$. Before $\tau$, the integer-valued increment belongs to $\{-1,0,1\}$. The martingale property givesTheir sum is at least $1/2$, so each conditional probability is at least $1/4$. From any state in $\{1,\dots ,y-1\}$, a run of at most $y$ upward moves reaches $y$ and has conditional probability at least $4^{-y}$. Applied in successive blocks of $y$ steps, this givesso $\tau <\infty$ almost surely.

The stopped process $X_{n\wedge \tau }$ takes values in $[0,y]$, hence is a bounded martingale and has uniform integrability. The optional sampling theorem for a supermartingale givesbecause $X_{\tau }$ is zero or $y$. Therefore

The function $z\mapsto \log |z|$ is a harmonic function on the annulus $r_1<|z|<r_2$. The Itô formula therefore makes $\log |B_{t\wedge \tau }|$ a bounded martingale. The optional sampling theorem for a supermartingale giveswhere $p=\mathbb{P}(|B_{\tau }|=r_1)$. Solving this linear equation yields the planar Brownian annulus hitting probability

Let $\rho =t\wedge {\tau }_0\wedge {\tau }_1$ and apply the Itô formula to $u(t-s,B_s)$ for $0\le s\le \rho$. The heat equation cancels the drift, so the stopped process is a bounded martingale. The optional sampling theorem for a supermartingale gives $u(t,x)={\mathbb{E}}_x[u(t-\rho ,B_{\rho })]$. On the three mutually exclusive terminal events, the initial and Dirichlet boundary conditions identify this value asThis is the probabilistic representation of the heat equation with time-dependent Dirichlet data.

Because $\tilde{F}$ solves the differential equation from part (c), the Itô formula makes $\tilde{F}(V_t)$ a local martingale before $\tau$. The defining improper integral converges at both endpoints: its integrand is asymptotic to $(-u{)}^{1-d}$ near zero and to $|u{|}^{d-3}$ at minus infinity. Since $1<d<2$, both exponents are integrable. Henceso the stopped local martingale is a bounded martingale.

If ${\tau }_x<{\tau }_y$, then $V_t\to 0$ and $\tilde{F}(V_t)\to 0$. If ${\tau }_y<{\tau }_x$, then $V_t\to -\infty$ and $\tilde{F}(V_t)\to I$. The hitting times cannot coincide because $X_t-Y_t$ stays positive. The optional sampling theorem for a supermartingale and bounded convergence theorem therefore giveConsequentlywhich is the Two-sided SLE boundary swallowing probability.

The recursion makes $U$ a supermartingale and gives $U_t\ge Z_t$ at every date. The optional sampling theorem for a supermartingale for the bounded stopping time $\tau$ therefore gives

For every stopping time $\tau$, the martingale case of the optional sampling theorem for a supermartingale gives $\mathbb{E}{X}_{\tau }=X_0=0$. HenceUse the optimal stopping time from part c and the pathwise inequalityTaking expectations gives

The optional sampling theorem for a supermartingale at a bounded stopping time giveswhere $V_0$ is constant because ${\mathcal{F}}_0$ is trivial. Since $Z_{\tau }\le V_{\tau }$ almost surely,

Let $D\subset {\mathbb{R}}^d$ be bounded, choose $R$ with $D\subset B(0,R)$, and let $T$ and ${\tau }_R$ be the respective exit times. Then $T\le {\tau }_R$. Sinceis a martingale, the optional sampling theorem for a supermartingale at ${\tau }_R\wedge n$ givesMonotone convergence theorem now gives

Let $T=\inf \{t\ge 0:X_t\notin (-a,b)\}$, and suppose the jumps of $X$ have absolute value at most $c$. A nonconstant centered finite-variance Lévy process oscillates, so $T<\infty$ almost surely. Before $T$ the process lies in $(-a,b)$, and at $T$ its bounded overshoot gives $X_T\in [-a-c,b+c]$. Thus the variables $X_{T\wedge n}^2$ are uniformly bounded.

Apply the optional sampling theorem for a supermartingale to the martingale from part (c):Bounded convergence theorem on the left and monotone convergence theorem on the right yield