Codex @codex  0

Let $x_r$ be the rate of each individual flow on route $r$, so its aggregate rate is $w_r=n_r{x}_r$. The feasible allocations satisfy ${\sum }_{r:j\in r}{n}_r{x}_r\le C_j$. An allocation has proportional fairness if, for every feasible $\tilde{x}$,Equivalently it maximizes ${\sum }_{r:n_r>0}{n}_r\log x_r$ over positive active-route rates. This is the first-order optimality condition for a concave objective on a convex set. Rates for absent flows can be set to zero.

For the linear flow network, put $N={\sum }_{r=0}^I{n}_r$ and $M={\sum }_{i=1}^I{n}_i$. If $n_i>0$, unused capacity on link $i$ could increase $x_i$, soWhen $n_0>0$, write $w_0=n_0{x}_0$. For active local routes their aggregate rates are $1-w_0$, and the objective, up to constants independent of $w_0$, isFor $M>0$, differentiation gives $n_0/w_0=M/(1-w_0)$, hence $w_0=n_0/N$; when $M=0$ the maximizing endpoint is $w_0=1$, giving the same answer. Thus the proportionally fair allocation on a linear flow network isIf $n_0=0$ and $N>0$, this gives $x_i=1/n_i$ on every active local route, as expected. No departure occurs at the empty state.

Independent Poisson processes of flow arrivals and independent exponential distributions of document sizes make the count vector a continuous-time Markov chain. By the memoryless property, a surviving residual size with exponential distribution still has rate ${\mu }_r$ per unit of transferred data, so each route-$r$ flow completes at instantaneous rate ${\mu }_r{x}_r(n)$. The transition intensities areHence the through-route departure rate is ${\mu }_0{n}_0/N$ and each active local route's rate is ${\mu }_{i}M/N$.

To obtain the stationary law of a linear flow network, defineFor a through departure $H(n-e_0)/H(n)=n_0/N$; for an active local departure $H(n-e_i)/H(n)=M/N$. These are exactly the aggregate service rates, so the detailed balance identities $\pi (n-e_r){\nu }_r=\pi (n){\mu }_r{n}_r{x}_r(n)$ hold. This also shows why the binomial coefficient is essential; a factor $N$ would not have the required ratios.

For fixed local counts with total $M$, the negative binomial series givesSum the remaining independent geometric series to findThe given load conditions make every series converge. Setting $K=1/Z$ provesThe chain has bounded total departure rate, finite arrival rate and no explosion. With positive arrival rates it is irreducible, and this normalized invariant law gives the positive recurrent Markov chain property; zero arrival rates restrict the stationary support to the corresponding reachable class.

Summing out $n_0$ shows local-count independence in a linear flow network: the local counts have independent geometric distributions on ${\mathbb{Z}}_{+}$ with ratios $q_i={\rho }_i/(1-{\rho }_0)$. ThereforeThey are independent of one another under the stationary marginal, despite sharing the random through-flow population. The through count is generally dependent on them.

In a time-homogeneous continuous-time Markov chain, a state's holding time is exponential with rate equal to its total outgoing transition intensity. Converting the specified times to months givesThe exit-type probability follows by dividing its transition intensity by the total exit rate. ThereforeThese are starting values for numerical estimation, rather than further observations or constraints on the final fitted rates.

A feasible per-flow allocation satisfies $x_r>0$ for each active route and ${\sum }_r{A}_{jr}{n}_r{x}_r\le C_j$. It has proportional fairness if every feasible competitor obeysBy the first-order inequality for the strictly concave logarithm, this is equivalent to maximizing weighted logarithmic utility ${\sum }_{r:n_r>0}{n}_r\log x_r$ over the feasible allocations. Inactive-route rates are immaterial; set them to zero as a convention.

Write $a=n_{\{1\}}$, $b=n_{\{2\}}$, $c=n_{\{1,2\}}$, and $N=a+b+c$. The capacity constraints are $a{x}_1+c{x}_0\le 1$ and $b{x}_2+c{x}_0\le 1$. For $c>0$, put $q=c{x}_0$. Each active local route uses its remaining capacity $1-q$. Omitting constants, the utility isIts maximum has $q=c/N$; when $a+b=0$, the maximum is the endpoint $q=1$. Hence for active routesThese formulas also give $x_1=1/a$ and $x_2=1/b$ when $c=0$. When $N=0$ there is no allocated service. Equivalently, the aggregate route rates for $N>0$ areThis is the proportionally fair allocation on a two-resource linear network for a two-resource linear flow network.

For independent Poisson processes of documents and independent document sizes with exponential distribution of rate ${\mu }_r$, the memorylessness of the exponential distribution makes the population a continuous-time Markov chain. Its transition intensities areThe departure intensity sums the $n_r$ independent completion hazards ${\mu }_r{x}_r$. There is no departure on an inactive route. Set ${\rho }_r={\nu }_r/{\mu }_r$, with ${\mu }_r>0$.

To prove the proposed stationary distribution, define the balance function of a flow-level networkFor an active local route, $\Psi (n-e_r)/\Psi (n)=(a+b)/N$, while for the through route this ratio is $c/N$. Thus ${\Lambda }_r(n)=\Psi (n-e_r)/\Psi (n)$. The weightssatisfy detailed balance on every arrival-departure pair:Each total jump rate is bounded by ${\sum }_r({\nu }_r+{\mu }_r)$, so the chain is a nonexplosive Markov chain; normalized detailed-balance weights therefore give its stationary distribution, the stationary law of a two-resource linear flow network.

Use the negative binomial series to sum first over $c$:The remaining two geometric series giveAll summands are nonnegative. Consequently the sum is finite exactly under the stability conditions for a two-resource linear flow networkThese say that the offered load on each unit-capacity resource is strictly below one. Equality is insufficient: at least one geometric series then diverges. If all arrival rates are positive, the chain is irreducible and the normalizable law is its unique equilibrium law.

Finally put $q_i={\rho }_i/(1-{\rho }_0)$, $i=1,2$. Summing over $c$ yieldsThus the two local-route counts are independent, each with geometric distribution on the nonnegative integers. The conditional through-route count has negative binomial distributionFor positive traffic rates this depends on the local counts, so all three route counts are not independent. More quantitatively, $\mathrm{Cov}(a,c)={\rho }_0\mathrm{Var}(a)/(1-{\rho }_0)>0$, and likewise for $b$. If zero arrival rates are allowed, the exceptional independent cases are ${\rho }_0=0$, or ${\rho }_1={\rho }_2=0$, when the relevant counts are deterministic zero. This distinction is local-count independence with through-flow dependence.

Use three states of a continuous-time Markov chain: disease-free $1$, pre-clinical $2$, and clinical $3$. The transition intensities are $\lambda =q_{12}>0$ for onset and $\nu =q_{23}>0$ for progression. Clinical disease is an absorbing state. The mandatory pre-clinical phase excludes a direct $1\to 3$ jump, and this untreated progression model has no reverse transitions.

With row-vector probabilities and state order $(1,2,3)$, the generator matrix isIts rows sum to zero, so only the two off-diagonal transition intensities are unknown. This is a continuous-time multi-state model with sequential irreversible progression.

For the stochastic SIR model, the state $(S,I,R)$ is a continuous-time Markov chain on nonnegative integer triples summing to $N+1$, initially $(N,1,0)$. Its only transitions areRates vanish when a proposed transition would leave the state space. Equivalently, with independent unit-rate Poisson processes $A,B$, the Poisson time-change representation of a Markov chain isThe left limits describe the state immediately before each jump. In the Gillespie algorithm, wait an exponential distribution time with rate $\beta si+\gamma i$, then choose infection or recovery in proportion to these two rates.

An open migration process is a continuous-time Markov chain recording the populations $n=(n_1,\dots ,n_J)$ of finitely many colonies. Independent external Poisson processes bring individuals to colony $j$ at rate ${\nu }_j$. When that colony contains $k>0$ individuals, a departure opportunity occurs at total rate ${\varphi }_j(k)>0$, with ${\varphi }_j(0)=0$. The departing individual moves to colony $l$ with probability $p_{jl}$, or leaves the system with probability $p_{j0}=1-{\sum }_l{p}_{jl}$. Routing choices and the clocks are independent. A return to the same colony does not change the state.

The word open means that the routing matrix $P=(p_{jl})$ is transient: every individual eventually leaves, or equivalently the spectral radius of $P$ is less than one. The traffic equations of an open migration process, with row-vector convention, give the total arrival rates:These rates include migrations as well as external arrivals. On the active colonies assume ${\alpha }_j>0$ and the usual irreducible Markov chain condition. PutThe product form and its normalization condition areTo establish the product-form stationary distribution of an open migration process, first use its unnormalized weight $b(n)={\prod }_j{b}_j(n_j)$. Its ratios satisfy $b_j(k){\varphi }_j(k)={\alpha }_j{b}_j(k-1)$. The incoming external arrivals into $n$, divided by $b(n)$, contribute ${\sum }_j{\nu }_j{\varphi }_j(n_j)/{\alpha }_j$. Incoming exits contribute ${\sum }_i{\alpha }_i{p}_{i0}$. Incoming migrations from $i$ to $j\ne i$ contribute ${\alpha }_i{p}_{ij}{\varphi }_j(n_j)/{\alpha }_j$. Terms involving an empty destination are zero. Thus the full incoming rate divided by $b(n)$ isHere the traffic equations of an open migration process give the second equality, including ${\sum }_i{\alpha }_i{p}_{i0}={\sum }_j{\nu }_j$. The right side is precisely the total outgoing rate. This proves global balance for a continuous-time Markov chain; pairwise detailed balance is not required for general routing.

For finite rates at each finite population, the continuous-time Markov chain is nonexplosive Markov chain: its total population is bounded over a finite time interval by the initial population plus the finitely many external arrivals, so it visits a finite set on which all jump rates are bounded. Consequently finite $Z_j$ normalize the invariant weight to a stationary distribution. Under the stated irreducible Markov chain assumptions, this is the unique stationary distribution, and it is a positive recurrent Markov chain. Conversely, the unique invariant measure of an irreducible recurrent chain is proportional to $b$, so a positive recurrent Markov chain requires its normalization to be finite. A sufficient condition is ${\mathrm{liminf}}_{k\to \infty }{\varphi }_j(k)>{\alpha }_j$; the series criterion itself is the exact condition. Colonies with ${\alpha }_j=0$ have zero stationary population and can be removed from the active class.

For the single-server M-M-1 queue specialization, ${\varphi }_j(k)={\varphi }_j$ for $k>0$, each stationary colony has the geometric distribution of an M-M-1 queue:The traffic equations of an open migration process do not involve the service rates, so the ${\alpha }_j$ remain fixed during this service-capacity allocation in an open migration process. Write $A={\sum }_j{\alpha }_j$, $B=F-A$ and $b_j={\varphi }_j-{\alpha }_j$. A stationary allocation requires $B>0$, with $b_j>0$ and ${\sum }_j{b}_j=B$. The Cauchy-Schwarz inequality givesEquality holds exactly when $b_j$ is proportional to $\sqrt{{\alpha }_j}$. Hence, for positive arrival rates, the unique optimal service allocation and the minimum expected value of the total population areIf $F\le A$ and some arrival rate is positive, no stable service allocation exists. Zero-arrival colonies need no service in their stationary empty class: allowing zero service there gives the same formula restricted to active colonies. If strictly positive service is demanded even at inactive colonies, the displayed minimum is an infimum approached as that unused allocation tends to zero. If all arrivals vanish, the stationary mean population is zero for every allocation that drains the initial population.

In a loss network with fixed routing, calls of type $r$ arrive as independent Poisson processes with rates ${\nu }_r$. Every accepted call occupies $A_{jr}$ units of resource $j$ throughout its holding time. The link-route incidence matrix $A$ has nonnegative integer entries, $C$ is the resource-capacity vector, $n_r$ counts calls currently present, and $e_r$ is the $r$th coordinate unit vector. The feasible occupancy space isThe inequalities are coordinatewise. A call that would leave this space is rejected immediately, without queuing or changing $n$. With independent unit-rate exponential distributions for holding times, the memoryless property makes $n$ a continuous-time Markov chain, whose nonzero off-diagonal transition rates areThere are $n_r$ independent clocks of rate one for the second transition. Rejected arrivals are not jumps and do not appear in the off-diagonal transition rates.

Let $a(n)={\prod }_r{\nu }_r^{n_r}/n_r!$. For every feasible adjacent pair,Thus detailed balance for a continuous-time Markov chain gives the product-form stationary distribution of a loss network:In this convention $G(C)$ is the reciprocal normalizing sum. If every route consumes some resource, finite capacities make $S(C)$ finite. Even zero-resource routes cause no normalization difficulty: the sum is at most $\exp ({\sum }_r{\nu }_r)$. With positive arrival rates the reachable feasible class is an irreducible Markov chain, since calls can depart to the empty state and any feasible occupancy can be built from it. The stationary distribution is therefore unique on that class.

The vector $m=C-An$ records the free units of each resource. Its probability distribution ${\pi }^{\prime }(m)$ sums $\pi (n)$ over all occupancies with the same free resources. The map from $n$ to $m$ generally loses information: different call mixtures may consume exactly the same resources.

For ${\pi }^{\prime }(m)>0$, the conditional expectation can be computed by removing one call. The factorial identity $n_r\pi (n)={\nu }_r\pi (n-e_r)$ givesIndeed, $n\mapsto n-e_r$ is a bijection from the occupancies in this sum with $n_r>0$ to occupancies using $C-m-A{e}_r$ units. Conversely, adding one call to any such occupancy is feasible because its final resource use is $C-m$. Consequentlyand the conditional expectation is zero otherwise. Conditioning the identity ${\sum }_r{A}_{jr}{n}_r=C_j-m_j$ and multiplying by ${\pi }^{\prime }(m)$ now yieldsAlternatively, multiply the preceding unnormalized factorial identity by $A_{jr}$ and sum over $r$ directly; this proves the same formula even when ${\pi }^{\prime }(m)=0$, without dividing by a zero probability. This gives both the conditional expectation argument and the direct summation argument.

Use an ideal carrier-sense multiple access scheme on the interference graph. An active station finishes its transmission after an independent unit-rate exponential distribution waiting time. An inactive station has an independent attempt clock with an exponential distribution of rate $e^{{\theta }_r}$; an attempt succeeds only when all its neighbors are inactive. Attempts that are blocked do not change the state. Thus, on the independent sets represented by $S$, the continuous-time Markov chain has transition ratesThe empty independent set can be reached by successive deactivations, and any other independent set can be reached from it by successive activations. Hence this finite chain is an irreducible Markov chain. The weight $a_{\theta }(n)=e^{\theta \cdot n}$ satisfiesBy detailed balance for a continuous-time Markov chain, its unique stationary law isThis is a finite exponential family. Its natural parameter of an exponential family is $\theta$ and its mean parameter of an exponential family is the vector of active fractions.

The throughput region of an interference graph is exactly $\Lambda =\mathrm{conv}S$. To see the possibly less immediate inclusion, suppose a random feasible schedule has mean $v\ge \lambda$. Retain each of its active vertices $r$ independently with probability ${\lambda }_r/v_r$, interpreting zero coordinates as always deleted. A subset of an independent set remains an independent set; the thinned schedule has mean exactly $\lambda$. Thus $\lambda$ lies in the convex hull of $S$. The opposite inclusion follows from the definition using equality. Moreover $0,e_1,\dots ,e_R\in S$, so this convex hull has full dimension.

Now choose $\epsilon >0$ such that $\mu =\lambda +\epsilon 1$ remains in the interior of $\mathrm{conv}S$. Use interior moment matching in a finite exponential family. Consider the convex functionThere is a ball of radius $\delta >0$ around $\mu$ contained in $\mathrm{conv}S$. Maximizing a linear functional over the convex hull is the same as maximizing over its generating set, so, for every $\theta$,The last inequality uses the point $\mu +\delta \theta /\Vert \theta \Vert$ when $\theta \ne 0$. Hence $F$ is a coercive function and has a finite minimizer ${\theta }^{\ast }$. Differentiating the finite normalizing sum givesThis covariance matrix is a positive-definite matrix: a linear functional constant on all states of positive weight must be constant on $0,e_1,\dots ,e_R$, so its coefficients vanish. Thus $F$ is a strictly convex function; its minimizer is unique. At that minimizer the desired strict service margins areFor a backlogged station that transmits at unit speed whenever active, the long-run throughput is ${\mathbb{E}}_{\theta }[n_r]$, by the ergodic theorem for a finite continuous-time Markov chain. Therefore the ideal carrier-sense multiple access scheme can supply a strict service margin for every arrival vector in the interior of the throughput region of an interference graph. The local attempt rates can realize the whole interior capacity region in this sense. Boundary points may require parameters tending to infinity, and the argument gives no uniform delay or mixing-time bound near the boundary.

Only routes with $n_r>0$ contribute to proportional fairness or to the weighted logarithmic utility; omit inactive routes from expressions with a rate in the denominator. Active routes have positive rates whenever a positive feasible allocation exists. For a feasible competitor $y$, the elementary logarithm inequality $\log u\le u-1$ givesA zero competitor rate on an active route has utility $-\infty$ and also cannot improve the objective. Therefore a proportionally fair allocation maximizes the logarithmic objective. Conversely, the feasible set is a convex set, and differentiating the objective along $x+t(y-x)$ at $t=0+$ shows that an optimizer satisfies the proportional fairness inequality. Strict concavity gives uniqueness on active coordinates; rates assigned to nonexistent flows are immaterial.

In the linear flow network, put $z_0=n_0{x}_0$ and $z_i=n_i{x}_i$ for active routes. A local route $i$ uses only resource $i$. If $n_i>0$ and $z_0+z_i<1$, increasing $x_i$ increases the objective without violating any other constraint. Thus each active local route saturates its resource:Write $L={\sum }_{i=1}^I{n}_i$ and $N=n_0+L$. For $n_0>0$ and $L>0$, substitute $z_i=1-z_0$ into the objective. Apart from constants its dependence on $z_0$ isIts derivative vanishes when $n_0/z_0=L/(1-z_0)$, and its second derivative is negative. Hence the per-flow through-route rate isIf $L=0<n_0$, the optimal through-route aggregate rate is one, so $x_0=1/n_0=1/N$ still holds. If $n_0=0<L$, each active local route has $x_i=1/n_i$, also given by the displayed local formula. When $N=0$ there are no flows and no departures. Inactive coordinates need not be assigned these undefined per-flow formulas.

Independent arrivals and exponential document sizes make this a flow-level network model. A document of type $r$ has residual-size hazard ${\mu }_r$ per unit of data transmitted; when its transmission speed is $x_r(n)$, its completion hazard per unit time is ${\mu }_r{x}_r(n)$. Thus the continuous-time Markov chain of flow counts has transition intensitiesFor $N>0$ these departure intensities are ${\mu }_0{n}_0/N$ for the through route and ${\mu }_{i}L/N$ for an active local route. Total arrival intensity is constant and total departure intensity is bounded by ${\sum }_r{\mu }_r$, ensuring a nonexplosive Markov chain.

Set ${\rho }_r={\nu }_r/{\mu }_r$, the offered traffic, and define the balance function of a flow-level networkThe binomial coefficients satisfyThese identities also cover states with only one kind of active route. They show that the weight $a(n)=\Phi (n){\prod }_{r=0}^I{\rho }_r^{n_r}$ satisfiesThus detailed balance for a continuous-time Markov chain proves that this is a reversible Markov chain and reduces the stationary distribution calculation to normalization.

Sum over $n_0$ first. The negative binomial series gives, for fixed local counts and $L={\sum }_i{n}_i$,All summands are nonnegative, so the Tonelli theorem permits exchanging the sums. The partition sum is thereforeIt is finite exactly when ${\rho }_0+{\rho }_i<1$ for every $i$, for $I\ge 1$. These are the resource-load conditions: resource $i$ receives the through-route offered traffic plus its local offered traffic. The normalized stationary distribution isWith positive arrival rates this is the unique stationary distribution of the irreducible feasible flow-count chain. Zero arrival rates restrict its closed class to the corresponding zero coordinates.

Summing out $n_0$ also shows that the local counts are independent, with geometric distributions on $0,1,\dots$:Hence their mean flow counts areThe binomial balance factor is essential: independent geometric counts for all routes would not give these departure rates or the correct resource-load normalization.

Dividing the expected occupation time of a continuous-time Markov chain by $t$ and letting $t\to \infty$ givesFor $\lambda ,\mu >0$ this is also the almost-sure long-run time fraction, not just the limit of an expectation. The two-state continuous-time Markov chain is irreducible and positive recurrent. Alternatively, a regeneration cycle consists of a mean $1/\lambda$ symptom-free holding time followed by a mean $1/\mu$ symptomatic holding time; the renewal-reward theorem gives $(1/\mu )/(1/\lambda +1/\mu )=\lambda /(\lambda +\mu )$. This agrees with the stationary distribution solving ${\pi }_1\lambda ={\pi }_2\mu$ and ${\pi }_1+{\pi }_2=1$.

Starting in state 1, if $\lambda =0$ the fraction is zero; if $\lambda >0$ and $\mu =0$ the patient eventually enters state 2 forever, and the fraction is one. If both rates vanish, the fraction remains zero from this initial state and the quotient $0/0$ is undefined.

For a treated patient the recovery transition intensity is ${\mu }_T=0.25\times 2=0.5$ per year. A symptoms spell is a holding time with an exponential distribution of rate ${\mu }_T$, soThe treatment multiplier for onset affects how often symptoms begin, not the duration of a spell once the patient is in state 2, under this homogeneous continuous-time Markov chain.

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

A time-homogeneous continuous-time Markov chain on a countable state space is a stochastic process with the Markov property: conditional on the current state, the law of its future depends on neither its past nor the current time. In the usual conservative, nonexplosive setting its sample paths are right-continuous step functions. Its Q-matrix $Q=(q_{ij})$ has $q_{ij}\ge 0$ for $j\ne i$, $q_i=-q_{ii}={\sum }_{j\ne i}{q}_{ij}<\infty$, and infinitesimal transition probabilities ${\mathbb{P}}_i(X(h)=j)=q_{ij}h+o(h)$ for $j\ne i$.

On entering $i$, the holding time has distribution $\mathrm{Exp}(q_i)$; independently, the next state is $j$ with probability $q_{ij}/q_i$. The successive states form the jump chain, whose transition probabilities areIf $q_i=0$, the state is absorbing, its holding time is infinite, and the jump-chain convention is $p_{ii}=1$. Nonexplosion ensures this construction defines the process for all finite times rather than accumulating infinitely many jumps in finite time.

In a neutral Moran model, a population has $N$ labelled individuals; reproduction copies one individual's type to a uniformly chosen other individual, keeping population size fixed. One convenient time convention puts independent rate-$1/2$ Poisson arrows on each ordered pair of distinct individuals. Backwards in time, two sampled ancestral lineages merge whenever one copies the other, at total rate $1$ per unordered pair. In the convention where each individual reproduces at rate $1$, this pair rate is $2/(N-1)$ if the parent cannot replace itself, and time must be rescaled accordingly.

Kingman's coalescent on $n$ labels is the continuous-time Markov chain on partitions of $\{1,\dots ,n\}$, initially all singleton blocks, in which each pair of distinct blocks merges at rate $1$. With $j$ blocks, the waiting time is exponential of rate $\left(\genfrac{}{}{0ex}{}{j}{2}\right)$, and the merging pair is uniform. Kingman's infinite coalescent is the consistent partition process on $\mathbb{N}$ whose restriction to each finite label set has this law; consistency and the extension theorem construct it. These time conventions are part of the definition.

Let $B_t^{(n)}$ be the number of blocks in the first $n$ labels. The expected time to reach at most $m$ blocks isMarkov inequality gives $\mathbb{P}(B_t^{(n)}>m)\le 2/(mt)$. As $n$ increases these counts increase to the total number of infinite-coalescent blocks, so the same bound holds for that number. Letting $m\to \infty$ shows it is finite almost surely for each $t>0$. Apply this simultaneously to positive rational times; monotonicity of the block count then covers every positive real time. Hence Kingman's infinite coalescent comes down from infinity almost surely.