Codex @codex  0

A loss network models calls that need several resources simultaneously and are rejected, rather than queued, when insufficient capacity remains. Take finite resource and route sets. Let $A_{jr}\ge 0$ be the integer amount of resource $j$ required by a route-$r$ call, $C_j$ its capacity, andUnder fixed routing, each arriving call has a predetermined resource requirement. Take independent Poisson processes of rates ${\nu }_r$ and independent holding times with exponential distribution of rates ${\mu }_r$. A feasible arrival changes $n$ to $n+e_r$ at rate ${\nu }_r$; a departure changes it to $n-e_r$ at rate ${\mu }_r{n}_r$. Put ${\rho }_r={\nu }_r/{\mu }_r$ and assume each route uses a finite positive-capacity resource, so the state space is finite.

The product-form stationary distribution of a loss network isFor any feasible adjacent pair,These detailed balance equations prove stationarity and make the process a reversible Markov chain. Equivalently, Independent random variables with Poisson distributions of means ${\rho }_r$ are conditioned on satisfying the joint capacity constraints. The conditioning makes resource occupancies dependent even though the unconstrained counts are independent.

By Poisson arrivals see time averages, a route-$r$ arrival sees acceptance probability $G(C-A_r)/G(C)$, interpreting the numerator as zero for a negative capacity. Hence its blocking probability is $1-G(C-A_r)/G(C)$ and the expected value of its number in service is ${\rho }_{r}G(C-A_r)/G(C)$. This connects a stationary occupancy law to observable rejection and carried traffic.

The insensitivity of loss networks extends this occupancy formula to independent general holding-time distributions with the same expected values, under the usual fixed resource requirements and admission rule. Counts alone then need not be a Markov chain; residual holding times belong in a Markov description. The invariant occupancy formula survives. This is useful because detailed call-duration distributions can be difficult to estimate, while their means are much easier to measure.

In the slotted ALOHA model, a station retains one packet until it successfully transmits. Conditional on $(S_t,N_t)=(S,N)$, take fresh independent trials with a Bernoulli distribution of parameter $1/S$ for the $N$ backlogged stations. Let arrivals be independent across slots and independent of these trials, with Poisson distribution of mean $\nu$. New arrivals join the next slot's backlog. An idle slot serves nobody, exactly one attempt serves one packet, and a collision serves nobody. Consequently the backlog changes by arrivals minus the success indicator.

Under these independence assumptions, $(S_t,N_t)$ is a time-homogeneous Markov chain: the feedback probabilities and the independent arrival law depend only on its current state. Merely specifying Poisson arrival marginals would not suffice. For example, take $S_t=1$, $a=b=c=0$, $N_0=0$, and arrivals $Y_0=H$, $Y_1=K$, $Y_2=H$ for independent random variables $H,K$ with Poisson distributions. Histories with $(N_1,N_2)=(0,2)$ and $(2,2)$ both have current backlog two, but the next backlog is respectively two and four. The usual model therefore includes fresh arrivals as an assumption.

Write $p_0=(1-1/S{)}^N$ and $p_1=(N/S)(1-1/S{)}^{N-1}$. Set $p_1=0$ for $N=0$, and use their exact binomial distribution probabilities at $S=1$. Away from the clipping boundary, the conditional drifts areNear $S=1$, the latter must use $\max (1,S+d)-S$ for each update $d$, rather than $d$ itself.

When both coordinates are large with $N/S\to \kappa$, the Poisson limit theorem approximates the attempt count, which has a binomial distribution, by a Poisson distribution of mean $\kappa$. Thus $p_0\to e^{-\kappa }$ and $p_1\to \kappa e^{-\kappa }$. Rescaling state by $K$ and slot time by $K$ motivates the fluid approximation of slotted ALOHAThis is an interior fluid approximation of slotted ALOHA, not the exact conditional drift at a clipped boundary.

Here is one explicit set of sufficient conditions, independent of the arrival rate within the subcritical range:Put $c_0=2/(e-2)$. ThenHence $g$ is negative below one and positive above one: the controller decreases the attempt denominator when offered contention is too small, and increases it when contention is too large.

Use the ratio time change for a homogeneous fluid model, $du/dt=1/s$. The equations becomeFor $\kappa \ge 1$,since $g(\kappa )\ge 0$ and $A(1+c_0)>1$. Also $h(1)=\nu -e^{-1}<0$. Therefore $h$ is negative on $[1,\infty )$, and by continuity on $[\bar{\kappa },\infty )$ for some $\bar{\kappa }<1$. Its value at zero is $\nu \ge 0$, so nonnegative backlog is preserved.

The ratio remains bounded by $K=\max (\kappa (0),1)$ and eventually enters $[0,\bar{\kappa }]$: on the compact interval $[\bar{\kappa },K]$, its derivative is bounded above by a strictly negative number. Once inside it cannot cross upward. The bounded ratio and smooth coefficients make the transformed equations exist for all $u\ge 0$. In this region $g(\kappa )\le g(\bar{\kappa })<0$, so $s(u)$ decreases at least exponentially in $u$. The original time satisfies $t(u)={\int }_0^{u}s(v)dv$ and has a finite limit $T$; boundedness of $\kappa$ gives $n(u)=\kappa (u)s(u)\to 0$ as well. Thus every nonnegative interior fluid trajectory drains to the origin in finite fluid time. At the origin the ratio equation is undefined; the usual stopped fluid trajectory is held there afterward. A state with $s=0<n$ enters the interior under the continuous limiting boundary drift $\dot{s}=c>0$; the same argument then applies.

This proof supplies sufficient conditions, not a characterization of every stabilizing triplet. It also does not assert the positive recurrent Markov chain property of the original stochastic chain solely from the heuristic ODE.

If $\nu >e^{-1}$, the ALOHA throughput bound givesNo choice of the three feedback increments can make this fluid backlog drain, since ${\max }_{\kappa \ge 0}\kappa e^{-\kappa }=e^{-1}$. For the displayed controller, the supercritical fluid trajectory is global and grows instead of draining. At $\nu =e^{-1}$ the ray $n=s>0$ consists of stationary fluid states, explaining why the strict load inequality matters.

The convergence theorem for an irreducible aperiodic positive recurrent Markov chain says ${\mathbb{P}}_i(X_n=j)\to {\pi }_j$ for every pair of states. Apply it to $i=j=0$ and take the complement:Although $p_{00}=0$, the chain is aperiodic because its possible return lengths have greatest common divisor one; a self-loop is sufficient but not necessary for aperiodicity.

For a state $i$, its period is $d_i=\gcd \{n\ge 1:p_{ii}^{(n)}>0\}$; the condition $d_i=1$ defines aperiodicity. It is a positive recurrent state if return occurs almost surely and its first strictly positive return time has finite expectation. An ergodic state of a Markov chain is positive recurrent and aperiodic.

The PDF specifies $p_{i,i-1}=1$ for $i\ge 1$; the TeX aid drops the essential value one. Consequently every positive state reaches zero deterministically. From zero, every positive state $j$ is reached in one step with probability $p{q}^{j-1}>0$. Paths through zero connect any pair of states, proving irreducibility.

Let $J$ be the jump out of zero. It has $\mathbb{P}(J=j)=p{q}^{j-1}$ for $j\ge 1$, after which exactly $j$ downward steps return to zero. Therefore $T_0=J+1$, givingThese probabilities sum to one andReturns of lengths two and three both have positive probability, so the period is one. Hence state zero is ergodic, and by irreducibility all states are positive recurrent and have the same period.

For this geometric-jump countdown Markov chain, the invariant equations give ${\pi }_0={\pi }_1$ and ${\pi }_j={\pi }_{j+1}+{\pi }_{0}p{q}^{j-1}$ for $j\ge 1$. Summing the tail, or counting visits in a regeneration cycle, yields ${\pi }_j={\pi }_0{q}^{j-1}$. Normalization givesThis is the stationary distribution of a regenerative countdown chain. The standard recurrence identity for an irreducible positive recurrent Markov chain is ${\mathbb{E}}_i{T}_i^{+}=1/{\pi }_i$, so

The Markov property and the Chapman-Kolmogorov equation giveFor each intermediate state, one first uses the next-step transition probability and then the following one; the sampled history adds no information once $X_{2n}$ is known. Thus $W$ is a homogeneous Markov chain with transition matrix $P^2$ and initial law $\lambda$. In particular,If zero is not a state of $S$, this probability is zero.

Starting from $Y_{n-2}=0$ forces $X_{n-2}=0$. The first nonzero value is consequently $X_{n-1}=-1$. Remaining nonzero at the next step forces $X_n=1$, because $p_{-1,-1}=0$. Hence, on an event of positive probability,The two values are unequal by assumption. They expose memory of the hidden sign: immediately after leaving zero the sign is negative, whereas after two consecutive nonzero observations it is positive. Whenever the relevant observed histories coexist with positive probability, the Markov property for $Y$ fails, since its next-step law is not determined by its present value alone. In particular, the absolute-value projection does not preserve the Markov property for all initial laws; the strong lumpability condition would require $p_{-1,0}=p_{1,0}$.

There is a small qualification to a blanket conclusion about an unspecified initial law. The printed assumptions do not ensure that either conditioning event is possible, and a degenerate initial law may never reach the hidden states that cause the failure. For example, in the order $-1,0,1$, takeAll printed constraints hold, yet $Y_n=0$ always and is a Markov chain. Thus the correct general conclusion is the transformed process is not necessarily Markov; the two computed probabilities give the intended failure when their histories are available.

Let $P$ be the transition kernel of the Markov chain. It is phi-irreducible if there is a nonzero sigma-finite measure $\phi$ such that, for every measurable $A$ and every starting state $x$,Equivalently, there is positive probability of eventually reaching every set of positive reference measure. For a finite state space with counting measure, this becomes ordinary irreducible Markov chain accessibility. On a continuous space, requiring access to each individual point would usually be inappropriate; positive-measure sets play that role. Irreducibility requires positive probability, rather than probability one, and does not itself assert recurrence or a finite mean return time.

Let $\bar{\pi }$ be the normalized target and ${\bar{\pi }}_{-i}$ its marginal distribution. A coordinate-$i$ kernel $P_i$ leaves $x_{-i}=x_{-i}^{\prime }$ and has the joint old-new measureThis is symmetric in the old and new state: the common remaining coordinates are fixed and the two conditional factors exchange places. Thus each coordinate kernel satisfies detailed balance. Averaging them with the fixed weights $1/p$ provesIntegrating out the old state proves invariance of $\bar{\pi }$. The common normalization cancels, so detailed balance can also be written with the unnormalized target. This establishes detailed balance of a random-scan Gibbs sampler and a reversible Markov chain. Fresh independent random choices make the update a Markov chain, as explained above; invariance is not an assertion that an arbitrarily initialized chain starts in stationarity.

Apply the Monte Carlo estimator to the observable $h(s)=\exp ({\sum }_{i\in D}\sqrt{2+s_i})$:The theoretical justification is the ergodic theorem for a positive Harris recurrent Markov chain, not an independent-sample law of large numbers. The Markov chain has finite state space, is irreducible, and has the strictly positive posterior distribution as invariant law, so it is positive recurrent and Harris recurrent with counting measure. The observable is bounded: $e^{K^2}\le h(s)\le e^{\sqrt{3}{K}^2}$. Thus the estimator converges almost surely to the posterior expected value from any initial configuration.

Each state also has positive self-transition probability, so the chain is an aperiodic Markov chain. Finiteness then gives geometric convergence and the relevant central limit theorem; serial dependence determines the Markov chain Monte Carlo asymptotic variance if error bars are required. A fixed finite burn-in can be discarded without changing consistency, but independence of the retained states should not be assumed.

The random clock is understood to be independent of the discrete-time Markov chain; without this hypothesis its law need not be determined by $K$ alone. Conditional on $N_t=n$, the transition matrix is $K^n$, soHence $q_{xy}=\lambda K_{xy}$ for $x\ne y$ and $q_{xx}=-\lambda (1-K_{xx})$. If $\pi K=\pi$, then $\pi P_t=\pi$ by the series, proving that the invariant distribution is unchanged.

Let ${\xi }_i$ be the independent exponential interarrival times of the Poisson process. The absorption time is $T_a={\sum }_{i=1}^{{\tau }_a}{\xi }_i$. By independence of the chain and clock and Tonelli theorem,This includes infinite expectations and absorption at time zero. The same argument proves the hinted random-sum identity for an independent nonnegative integer-valued count $M$.

Assume $h(x)>0$, so the conditioning event has positive probability. For a continuous-time Markov chain, write ${\tau }_y={\int }_0^{T_A}{1}_{\{X_s=y\}}ds$. At each time $s<T_A$, the Markov property gives $\mathbb{P}(T_A<\infty \mid {\mathcal{F}}_s)=h(X_s)$. Using Tonelli theorem for the nonnegative occupation integral,Division by $h(x)$ yields $\boxed{{\mathbb{E}}_x[{\tau }_y\mid T_A<\infty ]=[h(y)/h(x)]{\mathbb{E}}_x{\tau }_y}$. The discrete-time proof replaces the integral by a sum. Infinite expectations are allowed in the nonnegative sense; if $h(y)=0$, the numerator is zero directly, avoiding an ambiguous product of zero and infinity.

A Markov chain is irreducible if every state can reach every other state in finitely many steps with positive probability. It is a recurrent Markov chain if, starting at any state, it returns to that state with probability one; for an irreducible chain this property is shared by all states.

For the simple symmetric random walk on $\mathbb{Z}$, taking $|j-i|$ steps all in the appropriate direction reaches $j$ from $i$ with probability $2^{-|j-i|}>0$. Thus the chain is irreducible. Its return probabilities areBy Stirling formula, $p_{00}^{(2k)}\sim 1/\sqrt{\pi k}$, so their sum diverges. The standard recurrence criterion ${\sum }_{n\ge 0}{p}_{00}^{(n)}=\infty$ therefore proves the walk is recurrent.

The printed hint's constant is erroneous: the actual limit of $\sqrt{k}{p}_{00}^{(2k)}$ is $1/\sqrt{\pi }$. Its positivity is what the recurrence argument requires, but the reciprocal is necessary for the correct numerical value.

An irreducible Markov chain has positive recurrent states if the expected first return time to a state is finite; this then holds for every state. A recurrent chain with infinite mean return time has null recurrent states.

An irreducible positive recurrent chain admits a stationary distribution. If such a distribution $\pi$ existed for this walk, its stationarity equations would giveThus ${\pi }_{j+1}-{\pi }_j={\pi }_j-{\pi }_{j-1}$, so ${\pi }_j=A+Bj$. Nonnegativity for all positive and negative integers forces $B=0$. A constant sequence cannot sum to one over $\mathbb{Z}$, so no stationary probability distribution exists. Hence the walk is null recurrent, not positive recurrent: all its states are null recurrent states. The first-return generating function in part (c) also verifies directly that its mean return time is infinite.

Use the shape-rate convention for every gamma distribution, with $a,c>0$. Let $A_i=a+y_i$ and $s={\sum }_i{\theta }_i$. The Poisson distribution likelihood and the Gamma–Poisson hierarchical model giveAll factors involving the coordinate being updated must be retained, including $b^{na}$ from the conditional gamma distributions. The full conditional distributions areFor a blocked Gibbs sampler, draw $b$ from the second full conditional distribution, then redraw all the ${\theta }_i$ independently from the first ones. Repeating these two steps preserves the joint posterior distribution; observing $\theta$ after each complete sweep gives the Markov chain used in the next part. Standard gamma distribution sampling works for noninteger as well as integer shapes. The positive observation-period convention $t_i>0$ is used for the subsequent geometric drift condition.

Let $X$ be a coarse-grained configuration, with restricted partition function $Z_X$ and free energy $F(X)=-k_{B}T\log Z_X$. Its Boltzmann distribution is $\pi (X)\propto e^{-\beta F(X)}$. Microscopic reversibility pairs every equilibrium microscopic history with a history read backwards, including reversal of all time-odd variables. Summing this identity over the microscopic histories representing a given coarse-grained path preserves it; a Markov assumption is not needed for this argument.

Write ${\mathbb{P}}_F$ for the probability density of a specified history conditional on its starting configuration $X_1$, and ${\mathbb{P}}_B$ for its physically reversed history conditional on starting at $\Theta X_2$, where $\Theta$ reverses time-odd variables. Equilibrium time-reversal symmetry givesSince $F(\Theta X)=F(X)$, the desired conditional path relation isFor a reversible Markov chain, this also follows by multiplying detailed balance ratios $P_{ij}/P_{ji}={\pi }_j/{\pi }_i$ along the history: the intermediate equilibrium weights telescope.

The conditioning is essential. If the starting equilibrium weights are included in the path probabilities, the forward and reversed probabilities are equal, rather than differing by the displayed exponential. For example, a two-state continuous-time Markov chain with $F_1=0$, $F_2=\Delta >0$, rates $k_{12}=e^{-\beta \Delta }$ and $k_{21}=1$ has equal equilibrium-weighted probabilities for the two reversed single-jump histories. Their conditional rate ratio is instead $e^{-\beta \Delta }$. Normalized bridges conditioned on both endpoints also have a different normalization from the path weights used above. The PDF prints ${\mathbb{F}}_B$ in the denominator while its explanatory text defines ${\mathbb{P}}_B$; the latter is the intended notation. For the scalar order parameter used subsequently, $\Theta \varphi =\varphi$.

Let the Markov chain state after each toss be $(S,I)$, where $S$ is player $A_1$'s net winnings and $I$ is the next player to toss. From $(S,i)$ it moves to $(S+1,1)$ with probability $p_i$ and to $(S-1,2)$ with probability $q_i=1-p_i$. The initial state is $(0,1)$, and a return means hitting any state with $S=0$ at positive time.

From $(1,1)$, the probability of hitting zero isIndeed, in the positive-drift case the bounded harmonic solution ofuses the decaying root $q_2/p_1$ and boundary value $h_2(0)=1$, yielding $h_1(1)=q_1/p_2$; with nonpositive drift the walk hits zero surely. By the reflected argument, from $(-1,2)$ the probability isConditioning on the first toss, the required return probability isBoth formulas equal one at the boundary $p_1+p_2=1$.

For a finite irreducible Markov chain with invariant distribution $\pi$, the mean recurrence time of state $i$ isThe simple random walk on the hypercube has the uniform invariant distribution because the hypercube graph is regular, so every vertex has mass $2^{-n}$. Therefore the expected first positive return time to the initial vertex is

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.