Codex @codex  0

Use the slotted ALOHA model with one outstanding packet per active station and a collision channel: a slot with exactly one attempt succeeds, whereas an idle slot or a slot with two or more attempts delivers nothing. Let $Y_t$ be independent Poisson random variables of mean $\nu$, independent also of the transmission choices. Arrivals join after the current slot's attempts. Given $(S_t,N_t)=(S,N)$, the attempt count has a binomial distribution with parameters $N$ and $1/S$. Consequently, for $N\ge 1$,For $N=0$, set $p_0=1$ and $p_1=0$. The equation $N_{t+1}=N_t+Y_t-1_{\{Z_t=1\}}$ adds arrivals and removes precisely one packet following a successful slot. The estimate $S_t\ge 1$ controls the common transmission probability and updates using the idle, success, or collision feedback. The conditional distribution of the next state depends only on $(S_t,N_t)$, so this pair is a Markov chain.

Away from the reflecting floor in $S$, its one-step conditional expectations areWhen $N$ and $S$ are large with $N/S\approx \kappa$, the Poisson limit theorem gives $p_0\approx e^{-\kappa }$ and $p_1\approx \kappa e^{-\kappa }$. Treating these approximate drifts as derivatives motivates the fluid approximation of slotted ALOHA:The floor at $S=1$ is negligible in this interior scaling. This calculation motivates the ordinary differential equations; it is not a proof of a stochastic fluid limit.

For $(a,b,c)=(2-e,0,1)$, putThen $g^{\prime }(\kappa )=(e-2+\kappa )e^{-\kappa }>0$ and $g(1)=0$. On the domain $s>0$, introduce time $\tau$ by $d\tau /dt=1/s$. Differentiating $\kappa =n/s$ giveswhere $r(\kappa )=\kappa [1-(e-2+\kappa )e^{-\kappa }]$.

The function $r$ is strictly increasing from zero to infinity, and $r(1)=e^{-1}$. To check the monotonicity explicitly,Indeed, with $d=3-e\in (0,1)$,because its discriminant is $d^2-4d<0$; and $e^{\kappa }\ge 1+\kappa$. Thus the scalar ordinary differential equation for $\kappa$ points toward the unique value ${\kappa }_{\ast }$ satisfying $r({\kappa }_{\ast })=\nu$. Every trajectory with $s(0)>0$, $n(0)\ge 0$ has bounded $\kappa$ and $\kappa (\tau )\to {\kappa }_{\ast }$. Positivity of $s$ follows from $s(\tau )=s(0)\exp ({\int }_0^{\tau }g(\kappa (u))du)$.

If $0\le \nu <e^{-1}$, then ${\kappa }_{\ast }<1$ and $g({\kappa }_{\ast })<0$. Thus $s(\tau )$ decays exponentially for large $\tau$, andThis is finite-time draining of a fluid model. The unmodified equations have $n/s$ undefined at the origin, so the statement that trajectories converge to the origin needs this endpoint interpretation; continuing with an absorbing zero trajectory is an additional fluid-model convention, not a solution of the displayed equations at the origin.

If $\nu >e^{-1}$, then ${\kappa }_{\ast }>1$ and $g({\kappa }_{\ast })>0$. Now $s(\tau )$ grows exponentially, physical time tends to infinity, andIn particular the trajectory escapes to infinity. Even without the ratio analysis, $\dot{n}\ge \nu -e^{-1}>0$, since ${\max }_{\kappa \ge 0}\kappa e^{-\kappa }=e^{-1}$.

For the actual Markov chain, it is essential not to replace the finite-$N$ success probability by $e^{-1}$: a single backlogged packet can succeed with probability one. Instead, for $N\ge 2$, maximizing over $S\ge 1$ gives the ALOHA throughput boundIf $\nu >e^{-1}$, choose $K_0$ and $r_0<\nu$ so that $p_1(N,S)\le r_0$ for all $N>K_0$, uniformly in $S$. For sufficiently small $\theta >0$,because its derivative at zero is $r_0-\nu <0$. Independence of arrivals and attempts giveswhenever $N>K_0$. For any integer $K\ge K_0$, stop at the stopping time ${\sigma }_K=\inf \{t:N_t\le K\}$. The stopped process $e^{-\theta N_{t\wedge {\sigma }_K}}$ is a nonnegative supermartingale. The optional stopping theorem, first at bounded times and then by a limit, yields the exponential-supermartingale escape boundFrom every state with $N\le K$, a Poisson distribution arrival burst has a uniformly positive probability of sending the next backlog to at least $K+m$, for any fixed $m>0$. From there the probability of never revisiting $N\le K$ is at least $1-e^{-\theta m}$. By the Markov property at successive visits, the probability of infinitely many visits to this strip is zero: each visit has a uniform positive chance of being the last. This holds for every integer $K\ge K_0$, soTherefore the Markov chain is transient for every finite choice of $a,b,c$. The proof is uniform in $S$ and does not infer stochastic transience merely from the approximate ordinary differential equations.

Choose a spanning tree $T$ of $G$, rooted at $a$. A depth-first traversal of a tree gives a deterministic closed walkthat traverses each edge of $T$ once in each direction and visits every vertex. Define stopping times $S_0=0$ andThe simple random walk is at $v_j$ at time $S_j$. All these hitting times have finite mean on the finite connected graph. By the Strong Markov property,The cover time is no larger than $S_{2(n-1)}$. Grouping the summands by the two traversals of each tree edge and applying the commute time identity givesThe effective resistances are measured in the original graph, where each tree-edge pair is adjacent. Part (a) therefore bounds every summand by one, soFor the one-vertex graph, the cover time is zero and the same bound is immediate.

Let ${\mathcal{F}}_n=\sigma (X_1,\dots ,X_n)$ be the natural filtration. An integer-valued random variable $M$ is a stopping time with respect to $(X_i)$ whenThus whether one has stopped by time $n$ can be decided from the first $n$ observations, without seeing future variables. Equivalently, $\{M\ge i\}\in {\mathcal{F}}_{i-1}$.

Write the stopped sum asThe event $\{M\ge i\}$ depends only on $X_1,\dots ,X_{i-1}$, so its indicator and $X_i$ are independent random variables. Since $\mathbb{E}|X_1|<\infty$ and $\mathbb{E}M<\infty$, Tonelli theorem givesWe may consequently exchange expectation and summation. Using the tail-sum formula for $M$ proves Wald's equation:

For the renewal process, put $S_n=X_1+\cdots +X_n$ and $N_t=\max \{n:S_n\le t\}$. The random variable $N_t+1$ is a stopping time. Since $S_{N_t+1}>t$, Wald's equation givesand hence

For $c>0$, set $Y_i=X_i\wedge c$ and ${\mu }_c=\mathbb{E}{Y}_i$. Wald's equation still applies to the stopping time $N_t+1$ and the independent variables $Y_i$. Because $S_{N_t}\le t$,ThereforeBy the monotone convergence theorem, ${\mu }_c\uparrow \mu$ as $c\to \infty$. Combining the bounds proves the elementary renewal theorem

For a fixed word over $q$ equally likely symbols, the waiting time for a word in independent uniform symbols has mean $\sum q^k$, where $k$ runs through the lengths of the borders of a word, including the full word. The word lava' has no proper nonempty border, so $$ \boxed{\mathbb E\tau_{\mathtt{lava}}=100^4=100\,000\,000}. $$ The word aa' has borders of lengths $1$ and $2$, soFor a direct check, let $E_0$ be the expected remaining time with no trailing a' and $E_1$ with one trailing a'. Thenwhich gives $E_0=10100$.

Assume (iii). Fix $n\ge 0$ and $A\in {\mathcal{F}}_n$, and defineThis is a stopping time: $\{T\le n\}=A\in {\mathcal{F}}_n$. Applying (iii) at time $n+1$ first to $T$ and then to the deterministic stopping time $n+1$ givesSubtracting yieldsBy the defining characterization of conditional expectation, this says $\mathbb{E}[M_{n+1}\mid {\mathcal{F}}_n]=M_n$. Thus $M$ is a martingale, proving (i). Together the three implications establish the characterization of a martingale by stopped expectations.

Assume (ii). A martingale has constant expected value by the tower property of conditional expectation, so for every stopping time $\tau$ and every $n$,This is (iii).

Assume (i), and let $\tau$ be a stopping time. The increments of the stopped process satisfyBecause $\{\tau >n\}\in {\mathcal{F}}_n$, taking conditional expectation given ${\mathcal{F}}_n$ makes the right-hand side zero. Integrability follows froma finite sum of integrable random variables. Hence $M^{\tau }$ is a martingale, proving (ii).

A random time $\tau$ is a stopping time for the natural filtration $({\mathcal{F}}_n)$ of a Markov chain when $\{\tau \le n\}\in {\mathcal{F}}_n$ for every $n$. The Strong Markov property says that, conditionally on $\tau <\infty$ and $X_{\tau }=i$, the process after $\tau$ is a fresh copy of the chain started from $i$, independent of the pre-$\tau$ history.

Before capture define the half-separationFor $D_n=k\ge 2$, independence of the two moves gives the transition probabilitiesIgnore the holding steps. The resulting embedded chain is a biased random walk that moves left with probability $q$ and right with probability $1-q$. Its expected number of moves needed to descend one level is $1/(2q-1)$; this follows either from first-step analysis or from its drift $1-2q$. A non-holding move occurs with probability $1/2$ at each time, so its mean waiting time is two. Hence, for every $m\ge 2$, the expected time to go from separation $2m$ to $2(m-1)$ is

A random time $T$ is a stopping time when the event $\{T\le n\}$ is determined by $X_0,\dots ,X_n$. The Strong Markov property says that, conditionally on $T<\infty$ and $X_T=x$, the process $(X_{T+k}{)}_{k\ge 0}$ is a fresh Markov chain started at $x$, independent of the history before $T$.

Use the state space $\{1,2,4\}\times {\mathbb{Z}}_{\ge 0}$, with $(2,0)$ absorbing. Observe the chain only when it is at square 2. From $(2,k)$, the change $Y$ in wealth by the next return to square 2 has distributionIndeed, heads lands on square 3 and returns to square 2 after losing £1. After tails reaches square 4, the remaining two or three moves give the other cases.

For $r=2/3$,Thus $r^{M_j}$ is a martingale for the embedded wealth random walk $M_j$. Stopping when it first reaches $m-1$ or a large upper level and then letting that level tend to infinity givesThe upper-bound contribution vanishes because $0<r<1$; equivalently, this is the smaller probability solution of the first-step equation.

For a bounded stopping time $T\le N$, writeThe indicator is measurable at time $n-1$. Taking conditional expectations term by term and using the supermartingale inequality gives $\mathbb{E}{\hat{M}}_T\le \mathbb{E}{\hat{M}}_0$. The same calculation gives equality for the martingale $M$. Since their initial values agree, $\mathbb{E}{M}_T\ge \mathbb{E}{\hat{M}}_T$.

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

Set $M_t={\int }_0^t{H}_{s}d{B}_s$. Its quadratic variation is $[M{]}_t={\int }_0^t{H}_s^{2}ds$, which is continuous and tends to infinity almost surely by assumption. The stated stopping time is the inverse clock at level one, so $[M{]}_{\tau }=1$. The Dambis-Dubins-Schwarz theorem gives

Let $d(x,A)$ be the distance to the closed set $A$. Continuity givesEvery variable in the countable infimum is ${\mathcal{F}}_t$-measurable by adaptedness, so the event belongs to ${\mathcal{F}}_t$. Hence $T_A$ is a stopping time.

The given limit inferior says that almost surely there is a random $\delta >0$ such that $t^{-a}{W}_t>-1/2$ whenever $0<t\le \delta$. Thereforeon that interval. The first entrance timeis a stopping time by continuity and satisfies $\tau >0$ almost surely. Before $\tau$ one has $S_t>t^a/2$, and continuity gives $S_{\tau }\ge {\tau }^a/2>0$. Hence $S_t>0$ for every $0<t\le \tau$.

If $S\le T$ are stopping times and $A\in {\mathcal{F}}_S$, then $U=S{1}_A+T{1}_{A^c}$ is a stopping time. The key identity isThis uses the ordering $S\le T$: without it, $A$ need not be known when $T$ occurs. Such pastings test the martingale identity through expectations at bounded stopping times.

For a finite-valued predictable process $K$, this is a stopping time and increases to infinity. The stopped martingale transform uses coefficients $K_s{1}_{\{s\le {\sigma }_j\}}$, which are predictable and bounded by $j$. Thus a transform of a discrete-time martingale is a local martingale without a global boundedness assumption. The stop is before, not after, the first large coefficient is used.

If $M$ is a stopping time for independent identically distributed integrable variables $X_i$ and $\mathbb{E}M<\infty$, then $\{M\ge i\}$ depends only on $X_1,\dots ,X_{i-1}$ and is independent of $X_i$. HenceThe interchange is justified because the same calculation with $|X_i|$ gives finite expected absolute sum.

The Skorokhod embedding theorem represents a centered probability distribution $\mu$ on the real numbers with finite variance as $B_T\sim \mu$ for a stopping time $T$ of Brownian motion. One may choose $T$ so that the stopped process $(B_{t\wedge T})$ is uniformly integrable and $\mathbb{E}T=\int x^2\mu (dx)$.

For a stopping time $T$, the stochastic interval $[0,T)$ means the subset $\{(\omega ,t):0\le t<T(\omega )\}$ of sample-time space. Its endpoint varies with the sample. A locally defined stochastic process on it has no prescribed value at the endpoint. This notation is distinct from an ordinary deterministic interval.

For an almost surely finite stopping time $T$, if $\mathbb{E}|M_T|<\infty$ and $\mathbb{E}[|M_n|1_{\{T>n\}}]\to 0$, then $M_{n\wedge T}\to M_T$ with convergence in L1. Thus L1 convergence implies uniform integrability makes the stopped martingale uniformly integrable.