The convergence theorem for an irreducible aperiodic positive recurrent Markov chain says for every pair of states. Apply it to and take the complement:
Although , 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 , its period is ; the condition 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 for ; the TeX aid drops the essential value one. Consequently every positive state reaches zero deterministically. From zero, every positive state is reached in one step with probability . Paths through zero connect any pair of states, proving irreducibility.
Let be the jump out of zero. It has for , after which exactly downward steps return to zero. Therefore , giving
These probabilities sum to one and
Returns 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 and for . Summing the tail, or counting visits in a regeneration cycle, yields . Normalization gives
This is the stationary distribution of a regenerative countdown chain. The standard recurrence identity for an irreducible positive recurrent Markov chain is , so
The Markov property and the Chapman-Kolmogorov equation give
For each intermediate state, one first uses the next-step transition probability and then the following one; the sampled history adds no information once is known. Thus is a homogeneous Markov chain with transition matrix and initial law . In particular,
If zero is not a state of , this probability is zero.
Starting from forces . The first nonzero value is consequently . Remaining nonzero at the next step forces , because . 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 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 .
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 , take
All printed constraints hold, yet 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 be the transition kernel of the Markov chain. It is phi-irreducible if there is a nonzero sigma-finite measure such that, for every measurable and every starting state ,
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 be the normalized target and its marginal distribution. A coordinate- kernel leaves and has the joint old-new measure
This 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 proves
Integrating out the old state proves invariance of . 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 :
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: . 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 alone. Conditional on , the transition matrix is , so
Hence for and . If , then by the series, proving that the invariant distribution is unchanged.
Let be the independent exponential interarrival times of the Poisson process. The absorption time is . 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 .
Assume , so the conditioning event has positive probability. For a continuous-time Markov chain, write . At each time , the Markov property gives . Using Tonelli theorem for the nonnegative occupation integral,
Division by yields . The discrete-time proof replaces the integral by a sum. Infinite expectations are allowed in the nonnegative sense; if , 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 , taking steps all in the appropriate direction reaches from with probability . Thus the chain is irreducible. Its return probabilities are
By Stirling formula, , so their sum diverges. The standard recurrence criterion therefore proves the walk is recurrent.
The printed hint's constant is erroneous: the actual limit of is . 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 existed for this walk, its stationarity equations would give
Thus , so . Nonnegativity for all positive and negative integers forces . A constant sequence cannot sum to one over , 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 . Let and . The Poisson distribution likelihood and the Gamma–Poisson hierarchical model give
All factors involving the coordinate being updated must be retained, including from the conditional gamma distributions. The full conditional distributions are
For a blocked Gibbs sampler, draw from the second full conditional distribution, then redraw all the independently from the first ones. Repeating these two steps preserves the joint posterior distribution; observing 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 is used for the subsequent geometric drift condition.
Let be a coarse-grained configuration, with restricted partition function and free energy . Its Boltzmann distribution is . 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 for the probability density of a specified history conditional on its starting configuration , and for its physically reversed history conditional on starting at , where reverses time-odd variables. Equilibrium time-reversal symmetry gives
Since , the desired conditional path relation is
For a reversible Markov chain, this also follows by multiplying detailed balance ratios 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 , , rates and has equal equilibrium-weighted probabilities for the two reversed single-jump histories. Their conditional rate ratio is instead . Normalized bridges conditioned on both endpoints also have a different normalization from the path weights used above. The PDF prints in the denominator while its explanatory text defines ; the latter is the intended notation. For the scalar order parameter used subsequently, .
Let the Markov chain state after each toss be , where is player 's net winnings and is the next player to toss. From it moves to with probability and to with probability . The initial state is , and a return means hitting any state with at positive time.
From , the probability of hitting zero is
Indeed, in the positive-drift case the bounded harmonic solution of
uses the decaying root and boundary value , yielding ; with nonpositive drift the walk hits zero surely. By the reflected argument, from the probability is
Conditioning on the first toss, the required return probability is
Both formulas equal one at the boundary .
For a finite irreducible Markov chain with invariant distribution , the mean recurrence time of state is
The simple random walk on the hypercube has the uniform invariant distribution because the hypercube graph is regular, so every vertex has mass . 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 be independent Poisson random variables of mean , independent also of the transmission choices. Arrivals join after the current slot's attempts. Given , the attempt count has a binomial distribution with parameters and . Consequently, for ,
For , set and . The equation adds arrivals and removes precisely one packet following a successful slot. The estimate controls the common transmission probability and updates using the idle, success, or collision feedback. The conditional distribution of the next state depends only on , so this pair is a Markov chain.
Away from the reflecting floor in , its one-step conditional expectations are
When and are large with , the Poisson limit theorem gives and . Treating these approximate drifts as derivatives motivates the fluid approximation of slotted ALOHA:
The floor at is negligible in this interior scaling. This calculation motivates the ordinary differential equations; it is not a proof of a stochastic fluid limit.
For , put
Then and . On the domain , introduce time by . Differentiating gives
where .
The function is strictly increasing from zero to infinity, and . To check the monotonicity explicitly,
Indeed, with ,
because its discriminant is ; and . Thus the scalar ordinary differential equation for points toward the unique value satisfying . Every trajectory with , has bounded and . Positivity of follows from .
If , then and . Thus decays exponentially for large , and
This is finite-time draining of a fluid model. The unmodified equations have 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 , then and . Now grows exponentially, physical time tends to infinity, and
In particular the trajectory escapes to infinity. Even without the ratio analysis, , since .
For the actual Markov chain, it is essential not to replace the finite- success probability by : a single backlogged packet can succeed with probability one. Instead, for , maximizing over gives the ALOHA throughput bound
If , choose and so that for all , uniformly in . For sufficiently small ,
because its derivative at zero is . Independence of arrivals and attempts gives
whenever . For any integer , stop at the stopping time . The stopped process is a nonnegative supermartingale. The optional stopping theorem, first at bounded times and then by a limit, yields the exponential-supermartingale escape bound
From every state with , a Poisson distribution arrival burst has a uniformly positive probability of sending the next backlog to at least , for any fixed . From there the probability of never revisiting is at least . 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 , so
Therefore the Markov chain is transient for every finite choice of . The proof is uniform in and does not infer stochastic transience merely from the approximate ordinary differential equations.
For a fixed occupancy , let be the per-flow rate on every active route, so feasibility means . A proportionally fair allocation is a feasible allocation satisfying, for every other feasible ,
The sum counts the proportional changes over individual flows. By the first-order condition for a concave function, it is exactly the allocation solving
This is weighted logarithmic utility optimization, and its negative objective is a strictly convex function, which gives unique rates on active routes. Routes with have no per-flow rate to determine.
Index the four routes by , , , , and let be each route's total service. Write
The four capacity constraints say , , , and . Equivalently,
For fixed maxima , every active route in the first group optimally takes total service , and every active route in the second takes , because its logarithmic objective is increasing. Up to the constant , the objective therefore becomes with . Its maximizer is , when , with the evident endpoint choices when one group is empty. Hence the proportionally fair allocation on a four-cycle is
Set on inactive routes. If , all service totals are zero. In particular, for , , as required. Two disjoint active routes in the same group can each receive the same total service; service totals need not sum to one over the entire network.
With independent document arrivals given by Poisson processes of rates and independent unit-mean exponential distributions for document sizes, each of the active documents has completion rate . The flow-level network model is consequently a continuous-time Markov chain with
At all downward rates are zero. The total departure rate is at most four, so the bounded total jump rate ensures no explosion.
The original PDF's displayed factor is a binomial coefficient, not the plain quotient produced by the TeX extraction. The candidate stationary distribution for this reversible four-cycle flow model is
Use . For and ,
so . For the corresponding ratio is . Thus detailed balance for a continuous-time Markov chain holds for every adjacent pair, proving the displayed stationary distribution whenever .
For completeness, its existence condition can be made explicit. Put and . At fixed ,
Therefore the sum over states with is at most , using the binomial theorem. This is summable if . Conversely, restricting to the single maximizing route in each group leaves the series , which diverges if . Hence
These are exactly the four strict resource-load inequalities. With positive arrival rates the Markov chain is irreducible, so the normalized stationary distribution is unique.
A random time is a stopping time for the natural filtration of a Markov chain when for every . The Strong Markov property says that, conditionally on and , the process after is a fresh copy of the chain started from , independent of the pre- history.
Before capture define the half-separation
For , independence of the two moves gives the transition probabilities
Ignore the holding steps. The resulting embedded chain is a biased random walk that moves left with probability and right with probability . Its expected number of moves needed to descend one level is ; this follows either from first-step analysis or from its drift . A non-holding move occurs with probability at each time, so its mean waiting time is two. Hence, for every , the expected time to go from separation to is
A distribution is an invariant distribution when
for every state . The pair satisfies detailed balance when
for every . Summing this identity over gives
so detailed balance implies invariance.
For an irreducible positive recurrent Markov chain, Kac's lemma relates the invariant mass to the mean recurrence time:
True. If the Markov chain with transition matrix is irreducible, then for every pair of states there is a path
with at every step. The support assumption gives for every edge of the same path. Thus every state can reach every other state under , so the second chain is also an irreducible Markov chain.