Codex @codex  0

Assume $0<Z={\sum }_{x}r(x)<\infty$, and work on the support $S=\{x:r(x)>0\}$. In rejection sampling, choose a normalized proposal probability mass function $g$ and a known finite constant $M$ satisfying $r(x)\le Mg(x)$ everywhere. Draw independent random variables $Y\sim g$ and $U\sim \mathrm{Unif}(0,1)$, accepting $Y$ when $U\le r(Y)/(Mg(Y))$. The joint probability of proposing and accepting $x$ is $r(x)/M$, so the overall acceptance probability is $Z/M$ and the accepted value has probability mass function $r(x)/Z$. Fresh trials therefore produce independent and identically distributed random variables with the desired probability distribution. For a fixed positive number $N$ of accepted values, the sample average $N^{-1}{\sum }_{i=1}^{N}f(Y_i)$ is an unbiased estimator of the expectation when that expectation is finite. Its variance is ${\mathrm{Var}}_p(f)/N$ if the second moment is finite. Finding a valid envelope can be difficult, and a small acceptance probability makes the method expensive.

For the Metropolis–Hastings algorithm, choose a proposal transition matrix $q$ and, at the current state $x$, propose $y\sim q(x,\cdot )$. Accept with the Metropolis–Hastings acceptance probabilityA proposal outside $S$ is rejected; an impossible proposal need not be assigned a ratio. Otherwise remain at $x$. This constructs a Markov chain satisfying detailed balance with $p$, without computing $Z$ or a global envelope. Estimate the expectation by averaging $f(X_i)$ over iterations, including repeated states after rejections. Keeping only accepted jumps generally changes the stationary distribution of the recorded process.

The Metropolis–Hastings algorithm produces dependent samples, so the variance of its average includes autocovariances; starting outside stationarity can also cause finite-run bias. With Markov chain irreducibility, suitable recurrence and an integrable $f$, the countable-state Markov chain ergodic theorem gives consistency. Aperiodicity is additionally needed for the usual convergence of one-time probability distributions. In contrast, accepted rejection sampling values need no initial transient. Neither method is universally faster: envelope rejection competes with the proposal quality and mixing time of the Markov chain. Nonnegativity of $f$ alone does not guarantee a finite expectation or variance.

Neither Markov chain irreducibility nor fast convergence follows from detailed balance. On two states, the identity transition matrix satisfies detailed balance for the uniform probability distribution, but neither state can reach the other.

Even after imposing Markov chain irreducibility and aperiodicity, considerIt satisfies detailed balance for $\pi =(1/2,1/2)$. Its nontrivial eigenvalue is $1-2\epsilon$, and, from state zero, its total variation distance from $\pi$ after $n$ steps is $\frac{1}{2}(1-2\epsilon {)}^n$. This approaches zero arbitrarily slowly as $\epsilon$ decreases. Detailed balance without rapid convergence separates correctness of a stationary distribution from reachability and speed.

For each adjacent pair, the detailed balance equations follows directly:For nonadjacent distinct states both fluxes vanish, and diagonal fluxes agree trivially. Since ${\sum }_n{\pi }_n=e^{-\lambda }{\sum }_n{\lambda }^n/n!=1$, this is a genuine stationary distribution, rather than merely an invariant measure of infinite mass.

Every upward and downward transition probability between neighbouring states is positive for $\lambda >0$. Any two states can therefore be joined by a finite path of positive probability: the Markov chain is irreducible. Moreover,State zero has period one; Markov chain irreducibility makes every state aperiodic. Finally, the standard countable-state recurrence theorem states that an irreducible Markov chain admitting a stationary distribution of total mass one is positive recurrent, with that stationary distribution unique. The countable-state Markov chain convergence theorem then states that Markov chain irreducibility, positive recurrence and aperiodicity imply $P^k(i,j)\to {\pi }_j$ for all states $i,j$. The hypotheses just verified hold on the infinite state space ${\mathbb{N}}_0$, not merely on a numerical truncation.^[ref]

Consequently, the unique stationary distribution and the limiting distribution are both $\mathrm{Poisson}(\lambda )$, from every initial state. The countable-state Markov chain ergodic theorem also gives $N^{-1}{\sum }_{k=1}^{N}f(X_k)\to {\sum }_n{\pi }_{n}f(n)$ almost surely whenever ${\sum }_n{\pi }_n|f(n)|<\infty$.^[ref]

Condition on the state after $m$ steps and use the Markov property and time-homogeneous Markov property:This is the Chapman-Kolmogorov equation, or $P^{m+n}=P^m{P}^n$. A stationary distribution is a probability row vector with nonnegative entries summing to one and $\boxed{\pi P=\pi }$. Inductively $\pi P^n=\pi$, so a chain started with that distribution retains it at every time.

For the given matrix, its first stationary equation is ${\pi }_1={\pi }_1/2+({\pi }_2+{\pi }_3)/3$. Normalization gives ${\pi }_1=2/5$. The third equation gives ${\pi }_3=2{\pi }_2/3+{\pi }_3/3$, hence ${\pi }_3={\pi }_2$. ThereforeDirect multiplication verifies the second equation as well. The finite chain is irreducible, so this stationary probability distribution is unique.

A stationary distribution is a nonnegative row vector $\pi$ with $\pi P=\pi$ and ${\sum }_i{\pi }_i=1$. The balance equations giveThe first yields ${\pi }_1={\pi }_4$. Substitution into the middle pair yields ${\pi }_2=3{\pi }_4/4$ and ${\pi }_3={\pi }_4$; the fourth equation is then satisfied. Normalization gives $15{\pi }_4/4=1$, henceAll states communicate, so this is the unique stationary distribution. The self-loop at state 1 additionally makes this finite Markov chain aperiodic, although aperiodicity is not required for the balance calculation.

State one is left after one step and never revisited. The eventual probability mass in the closed class $\{4,5\}$ isWithin this class the stationary distribution is $(b/(a+b),a/(a+b))$, because the balance equation is $a{\pi }_4=b{\pi }_5$. The two-state recurrence shows convergence from either starting state, since $|1-a-b|<1$. The other closed class never reaches state five. Therefore

Write the stationary probabilities as $({\pi }_1,{\pi }_2)$. The equation $\pi P=\pi$ reduces to $a{\pi }_1=b{\pi }_2$. Together with ${\pi }_1+{\pi }_2=1$, this givesThe positive transition probabilities make the two states communicate, so the stationary distribution is unique.

On the class $\{1,2\}$, the two-step transition matrix is symmetric with positive entries, so its stationary distribution is $(1/2,1/2)$ and its distribution converges to that law. ThereforeExplicitly the two eigenvalues are $1$ and $1/9$, giving $P(X_{2n}=2\mid X_0=1)=\frac{1}{2}(1-9^{-n})$. The original chain has probability zero of being in state $2$ at odd times, consistent with its period two.

A stationary distribution is a probability row vector $\pi$ satisfying $\pi P=\pi$. Its coordinates obey ${\pi }_{-}(1-p)={\pi }_{+}q$ and ${\pi }_{-}+{\pi }_{+}=1$. ThusBecause both transitions between distinct states have positive probability, the finite Markov chain is irreducible; its positive self-transition probabilities also make it aperiodic.

The finite irreducible aperiodic Markov chain converges to its stationary distribution, regardless of its initial law. Therefore $\mathbb{E}[X_j]\to {\pi }_{+}-{\pi }_{-}$. Taking the arithmetic means of this convergent sequence givesThis uses linearity of expectation and convergence of Cesàro means; it does not require the variables $X_j$ to be independent.

Here the valid parameters lie in the irreducible aperiodic range. The finite-state theorem on convergence to an invariant distribution therefore implies convergence to the unique stationary distribution, independently of the initial state.

Solve $\pi P=\pi$ and ${\sum }_i{\pi }_i=1$. The equations for states $1,2,3$ giveHence ${\pi }_3={\pi }_1$ and ${\pi }_4=5{\pi }_1/3$. Normalization gives ${\pi }_1(1+1/2+1+5/3)=1$, soStationarity alone would not guarantee convergence of the one-time distributions; irreducibility and aperiodicity justify that final limit.

For an irreducible positive recurrent Markov chain, the Markov chain ergodic theorem gives a unique stationary distribution $\pi$, with almost-sure long-run occupation fraction ${\pi }_j$ in state $j$. More generally, time averages of an integrable state reward converge to its stationary mean. If the chain is also aperiodic, then ${\mathbb{P}}_i(X_n=j)\to {\pi }_j$ for every initial state $i$; the aperiodicity assumption is needed for this last distributional conclusion.

For either transition rule in part (i), $0<p<1$ permits progression through the phase-A states and a return from phase B to zero. Both chains are finite and irreducible, hence positive recurrent. State $K$ has a positive self-loop, so both are aperiodic. Thereforeusing respectively the cumulative or consecutive stationary distribution given in part (i), for every starting distribution.

The excluded endpoint cases are simple: at $p=0$, phase B is eventually reached and then absorbing, so the limiting law is the point mass at $K$. At $p=1$, the cumulative rule traps the chain at its current phase-A count (or eventually at zero if started in phase B), so the limit can depend on the initial count; under the consecutive rule zero is eventually absorbing. Irreducibility and the preceding stationary formulas must not be asserted unchanged at these endpoints.

Assume $N\ge 2$, as required by the source's selection probabilities, and put $q=(1-p)/(N-1)$. Conditional on the red book's current position, the next independent selection determines its move without needing its earlier history. Selecting the red book moves it left, unless already leftmost. Selecting the plain book immediately to its right moves it right. Every other selection leaves its position unchanged. Thus this position process is a Markov chain on $\{1,\dots ,N\}$, withand boundary self-loop probabilities $P_{11}=1-q$, $P_{NN}=1-p$. These account for every selection and each row sums to one.

Stationarity at the first state gives ${\pi }_1=(1-q){\pi }_1+p{\pi }_2$, hence $p{\pi }_2=q{\pi }_1$. When $N\ge 3$, for the second state substitution of this identity into its stationarity equation gives $p{\pi }_3=q{\pi }_2$. More generally, summing stationarity over the initial segment $\{1,\dots ,i\}$ equates its sole outward and inward probability flows:Write $r=q/p$. Then ${\pi }_i={\pi }_1{r}^{i-1}$. Normalization givesThe expression is positive also for $r>1$, since both numerator prefactor and denominator are negative. The uniform case is exactly $p=1/N$, when all books are equally likely to be selected. Since both neighboring transition probabilities are positive, the finite chain is irreducible; the displayed stationary distribution is therefore unique.

Stationarity at zero gives ${\pi }_0=q{\pi }_0+q{\pi }_1$, hence ${\pi }_1=(p/q){\pi }_0$. At one, ${\pi }_1=p{\pi }_0+q{\pi }_2$; substituting $p{\pi }_0=q{\pi }_1$ gives $q{\pi }_2=p{\pi }_1$. More generally the interior equations are ${\pi }_i=p{\pi }_{i-1}+q{\pi }_{i+1}$. Induction givesSince $p/q<1$, normalization of this geometric series givesThese probabilities satisfy detailed balance ${\pi }_{i}p={\pi }_{i+1}q$, including the boundary balance with the holding probability. Thus they do define a stationary distribution. Irreducibility then gives its uniqueness.

For $j\ge 1$, the only incoming transition is from $j-1$, so a stationary distribution must satisfyNormalization gives ${\pi }_0{e}^{\lambda }=1$, henceThe zero-state balance also holds: ${\sum }_i{\pi }_i(1-\lambda /(i+1))=1-{\sum }_{j\ge 1}{\pi }_j={\pi }_0$. Thus the Poisson distribution is indeed stationary, including when $\lambda =1$. Irreducibility gives uniqueness.

If $\lambda P=\lambda$, induction gives $\lambda P^n=\lambda$ for every $n\ge 0$. Part (c) then makes the distribution of every $X_n$ equal to $\lambda$. Such a probability row vector is a stationary distribution.

Let $Q=H_N$ and defineThe probabilities sum to $Q^{-1}(1+{\sum }_{k=1}^{N-1}(k+1{)}^{-1})=1$. For $k<N$, the incoming probability isusing a telescoping sum. Similarly,Thus $\pi$ is a stationary distribution. Every state can reach $N$ in one step, and $N$ can reach every lower positive state in one step, so the chain is irreducible. The self-loop at $N$ has probability $1/N>0$, hence the chain is aperiodic. The convergence theorem for a finite irreducible aperiodic Markov chain now givesFor $N=1$, the conclusion follows directly from the single absorbing/refilled state.

This is the limiting law of the uniform depletion and refill Markov chain.

Every state reaches state one by deterministic downward steps. From one, the chain can reach a given state $j$ exactly when it can jump to some $k\ge j$ with ${\alpha }_k>0$ and then count down to $j$. ThereforeIf the support is bounded by $M$, states above $M$ cannot be reached from one, so the chain on the stated infinite state space is not irreducible. Its smaller closed class can still have a stationary distribution, as in part (e).

Write the stationary distribution as a row vector $\pi =(a,b,c,d)$. For the first transition matrix, $\pi P=\pi$ gives $a=a/2+d$, $b=a/2+b/2$, $c=b/2$ and $d=c$. Hence $b=a$ and $c=d=a/2$. Normalization yieldsBy the stated common-stationary distribution property, this is also the answer for the second transition matrix.

The answer isIt holds initially by construction. If it holds at step $n-1$, then $X_{n-1}$ is a function of $E_0,\dots ,E_{n-1},U_1,\dots ,U_{n-1}$, so it is independent of the fresh inputs $E_n,U_n$. Part (a)(iii) therefore gives $U_n(X_{n-1}+E_n)\sim \mathrm{Exp}(1)$. This completes the mathematical induction and identifies the stationary distribution of the recursion.