Codex @codex  0

Take a birth-death chain on $\{0,1,2,3,4\}$. At each interior state, move up one state with probability $p=1/2$ and down one state with probability $q=1/2$. The endpoints are absorbing states: $P_{00}=P_{44}=1$. This is a small gambler's ruin model in which the state can represent capital, and reaching $4$ is success.

Let $T_a=\inf \{n\ge 0:X_n=a\}$ be the hitting time of endpoint $a$, and let $T=\min (T_0,T_4)$ be the first endpoint hitting time. The desired hitting probability is $h_i={\mathbb{P}}_i(T_4<T_0)$. First-step analysis and the Markov property giveThe interior equation says adjacent differences are equal. Four equal increments must bridge the boundary values $0$ and $1$, soFor example, from state $2$ the hitting probability is $1/2$, and its one-step average is $\frac{1}{2}(1/4)+\frac{1}{2}(3/4)=1/2$. Individual sample paths can wander back and forth, but the same averaging rule already accounts for all of them.

Now ask how long it takes to reach either endpoint. The expected hitting time $t_i={\mathbb{E}}_{i}T$ counts steps, including the transition that first reaches an endpoint. First-step analysis givesThis is a discrete Poisson equation, $(I-P)t=1$ in the interior. The extra $1$ counts the step just taken. The quadratic valuessatisfy the equations; from state $2$, $t_2=1+\frac{1}{2}(3)+\frac{1}{2}(3)=4$ steps. The hitting probability is harmonic, whereas the expected hitting time has a nonzero source term. These are special cases of expected duration of symmetric gambler's ruin; see Hao Wu's MIT lecture 16, gambler's ruin, slide 9.

For a biased random walk with $p=0.6$ upward and $q=0.4$ downward, keep the same absorbing states. The interior harmonic equation becomes $h_i=p{h}_{i+1}+q{h}_{i-1}$. Using biased gambler's ruin probability with these boundary values givesThe three interior hitting probabilities are approximately $0.415385$, $0.692308$, and $0.876923$. Thus starting at $2$ now succeeds about $69.23\%$ of the time. A direct check is $0.6(57/65)+0.4(27/65)=9/13$. The curved profile reflects the unequal transition weights: its successive increments shrink by the factor $q/p=2/3$. The formula, with the endpoint denoted $T$ there, is verified in Karger and Lynch's MIT lecture 26, sections 2.3-2.4; the five-state numbers here are direct substitutions.

Why does harmonic averaging produce the correct hitting probability? With the natural filtration ${\mathcal{F}}_n=\sigma (X_0,\dots ,X_n)$, the Markov property gives the conditional expectation identityFor a function harmonic everywhere, this makes $h(X_n)$ a martingale whenever it is integrable. For a function harmonic only in the interior, $M_n=h(X_{n\wedge T})$ is a stopped martingale. In either five-state example, $0\le M_n\le 1$. Also, from any interior state at most three consecutive upward steps reach $4$, with probability at least $p^3>0$. Repeated three-step blocks give ${\mathbb{P}}_i(T>3k)\le (1-p^3{)}^k$, so $T$ is almost surely finite and has finite expected value; compare finite-interval exit times have geometric tails. Applying optional stopping at $n\wedge T$ and then the bounded convergence theorem givesThe boundedness and finite hitting time justify this passage to the limit. See Steven Lalley's notes, harmonic functions and stopped expectations, theorem 1, and stopped martingale in discrete time for this bounded version of optional stopping.

Uniqueness has a short maximum principle explanation. On a finite state space, the difference of two harmonic extensions with the same boundary conditions is zero on the boundary. If its positive maximum occurs inside, the weighted average forces every successor with positive transition probability to have the same maximum. A path to the boundary propagates that maximum to zero, a contradiction. Applying the argument to the negative of the difference proves uniqueness. Reachability of the boundary is essential: an interior closed communicating class can retain an arbitrary constant.

// Target: markov-process.bigb

At state $x$, the holding probability of a discrete-time Markov chain is the self-transition probability $P(x,x)$. It is the conditional probability that the next state remains $x$. In a nearest-neighbour birth-death chain, it is $1-p_x-q_x$, where $p_x$ and $q_x$ are the probabilities of stepping right and left. Holding changes the elapsed time but not the embedded chain of actual moves or its boundary exit probabilities.

Poisson arrivals of rate $\lambda$ and $s$ independent exponential servers of rate $\mu$ give a birth-death chain with departure rate $\mu \min (n,s)$. The process is positive recurrent for $\lambda <s\mu$, null recurrent at equality, and transient above capacity.

The embedded birth-death chain has upward probability $p_k=(k+2)/(2(k+1))$ and downward probability $q_k=k/(2(k+1))$. To calculate a return probability, solve the harmonic difference equation on $\{0,\dots ,m\}$ with boundary values one at zero and zero at $m$. Successive differences have ratio $q_k/p_k=k/(k+2)$, so their weights areTheir total infinite sum is $2$. Letting $m\to \infty$ gives the probability of ever hitting zero from $k$:In particular the chain leaves zero to one and returns with probability $1/2<1$, so it is transient. This finite-interval calculation selects the minimal nonnegative hitting-probability solution, rather than merely observing that $h_k$ is harmonic.

The continuous-time chain has the same embedded transitions and constant total exit rate $2/3$, so it is nonexplosive and has exactly the same return events. It too is transient, neither positive recurrent nor null recurrent.

Let $Z_m$ be the discount level during policy year $m$, with $Z_0=1$. Under the usual assumption of independent successive annual accidents and repair costs with the same laws each year, the submitted-claim decision depends only on $Z_m$ and that year's cost. Consequently the conditional distribution of $Z_{m+1}$ depends on the past only through $Z_m$: this is the Markov property. The no claims discount system is therefore a time-homogeneous Discrete-time Markov chain. Stationarity of accident probabilities alone, without this independence assumption, would not by itself establish the Markov property.

At level one a claim keeps the policyholder at one, while no submitted claim moves them to two. At level two, a submitted claim moves them to one and no claim to three. At level three, a claim moves them to two and no claim keeps them at three. Thus $p_i$ in the specified transition matrix is the annual probability of a submitted claim at current level $i$, not merely of an accident. A small accident paid privately counts as no claim for these transitions.

Let $b>0$ denote the undiscounted annual premium. It is not specified numerically in the source; costs can instead be measured in units of that premium, giving $b=1$. The actual premium payments at the three levels are $b$, $b(1-\alpha )$, and $b(1-\beta )$. Compare the two future paths, assuming no further accidents, to obtain the two-year premium-loss claim threshold. From level one, a current claim leads to future levels $(1,2)$, whereas no claim leads to $(2,3)$, giving extra premiumFrom level two the two paths are $(1,2)$ and $(3,3)$, and from level three they are $(2,3)$ and $(3,3)$. HenceThese are all strictly positive. The PDF's discount fractions are $\alpha$ and $\beta$; the converted TeX has lost these factors in the percentages.

For a repair cost $X$ with the specified lognormal distribution, $\log X\sim N(\mu ,{\sigma }^2)$. Putwhere $\Phi$ is the standard normal distribution function. Conditional on an accident, the submitted-claim probability is $\mathbb{P}(X>h_i)=\overline{\Phi }(z_i)$. Multiplying by the accident probability givesSet $b=1$ for the premium-unit convention. Without a monetary premium scale, discount percentages alone cannot determine a numerical threshold for a monetary repair cost.

This nearest-neighbour Markov chain is a finite birth-death chain. Its stationary distribution $\pi$ satisfies the endpoint balance equationsThese detailed balance equations also imply the middle-state balance equation. The three-level no claims discount equilibrium is thereforewhereSince each $p_i$ lies strictly between zero and one, this is an irreducible Markov chain. Positive holding probabilities at the endpoints also make it an aperiodic Markov chain. Its unique stationary distribution is the limiting distribution even from the initial level one, and gives the steady-state proportions for a homogeneous population of such policyholders.

A submitted claim at level one conditions the repair cost on $X>h_1$. The accident probability cancels in this conditional expectation. For $z_1=(\log h_1-\mu )/\sigma$, the truncated lognormal moment follows by completing the square:Dividing by $\mathbb{P}(X>h_1)=\overline{\Phi }(z_1)$ yields the expected size of an actual submitted claim:The unconditional expected amount paid per year from level one would instead multiply its tail first moment by $p$; it is not the conditional claim size requested here.

All specified nearest-neighbour probabilities are positive, making the birth-death chain irreducible. The row sums give $p_0+q_0=1$ and $p_i+q_i=1$ for $i\ge 1$. Write $T_j$ for the hitting time of $j$, and on $\{0,\dots ,N\}$ let $h_i={\mathrm{Pr}}_i(T_N<T_0)$. The first-step equations giveDefine ${\rho }_0=1$ and ${\rho }_k={\prod }_{r=1}^k{q}_r/p_r$. The successive increments are proportional to ${\rho }_k$, and normalization at $N$ yieldsThe chain cannot remain forever in a fixed finite set avoiding zero: from every state in that set there is a uniformly positive chance to leave or hit zero within finitely many steps, so iterating the Markov property makes indefinite confinement have probability zero. Thus avoiding zero is the limit event of hitting every upper boundary before zero. Sending $N\to \infty$ shows that the probability of never hitting zero from one vanishes exactly when ${\sum }_k{\rho }_k=\infty$. At zero, return is immediate with probability $q_0$ and otherwise begins an excursion from one; irreducibility then givesFor positive recurrence define $w_0=1$ and $w_n={\prod }_{r=1}^n{p}_{r-1}/q_r$. First assume recurrence and let $\tau =T_0^{+}$ be the first return from zero. For each fixed $i$, the expected number $m_i$ of visits to $i$ before $\tau$ is finite: each visit to $i\ge 1$ has a positive chance of following the successive downward steps to zero before another visit, so its visit count has a geometric tail. Also $m_0=1$.

Each finite excursion starts and ends below every edge $(i,i+1)$, so its upward and downward crossing counts of that edge are equal. Their expectations, by the Markov property, are $m_i{p}_i$ and $m_{i+1}{q}_{i+1}$. Hence $m_{i+1}=m_i{p}_i/q_{i+1}$ and $m_i=w_i$. Tonelli's theorem applied to the nonnegative occupation counts gives the excursion weights of a reflected birth-death chain formulaConsequently positive recurrence implies the requested finite sum. Conversely, if ${\sum }_i{w}_i<\infty$, then $w_i\to 0$. But ${\rho }_i{w}_i=p_0/p_i\ge p_0$, so ${\rho }_i\ge p_0/w_i\to \infty$ and the already proved recurrence criterion holds. The occupation calculation is therefore valid and gives a finite mean return time. ThusAdding the finite $w_0=1$ term does not change convergence.

A birth-death chain on ${\mathbb{N}}_0$ has generator entries $q_{n,n+1}={\lambda }_n$, $q_{n,n-1}={\mu }_n$ for $n\ge 1$, ${\mu }_0=0$, $q_{nn}=-({\lambda }_n+{\mu }_n)$, and zero elsewhere. Assume the usual conservative nonexplosive chain. The detailed balance for a birth-death process are ${\pi }_n{\lambda }_n={\pi }_{n+1}{\mu }_{n+1}$.

If they hold, each incoming term cancels an outgoing term, giving $\pi Q=0$ and thus invariance. Conversely the invariance equation at zero gives ${\pi }_0{\lambda }_0={\pi }_1{\mu }_1$. At state $n$, write the stationarity equation as equality of the neighbouring probability currentsInduction from the zero boundary current gives detailed balance for a birth-death process for every edge. Thus invariant measures are exactly the detailed-balance measures in this standard birth–death setting. The argument is the generator characterization; a stationary probability law additionally needs finite normalization. For potentially explosive processes, formal generator balance alone would require additional boundary qualifications.

Write $a=\mu /\lambda <1$. The embedded birth-death chain moves upward with probability $\lambda /(\lambda +\mu )$ and downward with probability $\mu /(\lambda +\mu )$ away from zero. The gambler's ruin formula, obtained by solving its two-point difference equation on $\{0,\dots ,N\}$ and then letting $N\to \infty$, gives ${\mathbb{P}}_k(\text{hit }0)=a^k$. Translation gives return probability $a$ from $r+1$ to $r$. From $r-1$ the chain hits $r$ almost surely: before that hit it remains in a finite reflecting interval, from every state of which a uniformly positive finite-step chance of hitting $r$ is available. This also proves that starting at zero it hits each $r\ge 1$ almost surely.

After departure from $r\ge 1$ the return probability is thereforeThe holding rate is $q_r=\lambda +\mu$, so the exponential occupation-time parameter is $q_r(1-r_r)=\lambda -\mu$. Applying the Strong Markov property at the almost-sure first hit givesAt zero the holding rate is $\lambda$ and return probability after departure is $a$, again giving parameter $\lambda -\mu$. From initial state $k$, the expected occupation time at zero is $a^k/(\lambda -\mu )$, since the time is zero unless zero is reached. Averaging over the initial law with probability generating function $G$ yieldsFor $\mu =0$, the interpretation is $a^0=1$, $a^k=0$ for $k>0$, and $G(0)=\mathbb{P}(X(0)=0)$; the same formulas hold.

An M/M/1 queue has a Poisson arrival process of rate $\lambda$, independent exponential service times of rate $\mu$, and one server, with an unlimited waiting room and the usual first-come-first-served discipline. Its number-in-system process is a continuous-time birth-death chain with $q_{j,j+1}=\lambda$ and $q_{j,j-1}=\mu$ for $j\ge 1$. For $\rho =\lambda /\mu <1$, detailed balance givesThis sums to one and satisfies ${\pi }_j\lambda ={\pi }_{j+1}\mu$. The nonexplosive irreducible chain therefore has an invariant probability and is positive recurrent. Equivalently its negative drift above zero gives finite mean return cycles. Here queue length includes the customer in service.

In equilibrium, PASTA gives an arriving customer's number of predecessors the distribution $\pi$. Conditional on $j$ predecessors, memoryless property makes its total waiting-plus-service time a sum of $j+1$ independent $\mathrm{Exp}(\mu )$ variables. Its Laplace transform isThereforeThis is the sojourn time including service, not just the time until service begins.

The chain is a birth-death chain. Detailed balance between $0$ and $1$ givesFor $i\ge 1$, detailed balance between $i$ and $i+1$ givesConsequentlyThe expected occupation time of the positive even states during a return cycle to state $1$ is therefore

For $i\ge 1$, the stationarity equation iswhich rearranges to the stated recurrence. At zero,Define the adjacent probability current $J_i=a{\pi }_i-b{\pi }_{i+1}$. The recurrence says $J_i=J_{i-1}$, and the boundary equation says $J_0=0$. Hence ${\pi }_{i+1}=(a/b){\pi }_i$ for all $i$. Since $\rho =a/b<1$, normalization givesThe adjacent balance equations also verify stationarity directly. If $a=0$, this formula means the point mass at zero; otherwise the birth-death chain is irreducible and this is its unique stationary probability distribution.

Let $R$ count red balls and let $h_r$ be the probability of eventual absorption at $R=0$ starting from $R=r$. The birth-death chain moves to $r-1$ with probability $r/4$ and to $r+1$ with probability $(4-r)/4$. Its absorbing states have $h_0=1$, $h_4=0$. First-step analysis givesSubstitution yields $h_2=1/2$, $h_1=5/8$ and $h_3=3/8$. The initial state has one red ball, so the probability that all balls end white is $5/8$.

Absorption occurs almost surely: from each interior state there is probability at least $1/4$ of absorption within the next two draws. The chance of surviving $2m$ draws is therefore at most $(3/4{)}^m$. This also justifies the finite expected times used in part (ii). The process is the absorbing four-ball Ehrenfest chain.

For a birth-death chain on the integers with right/left probabilities $p_i,q_i>0$ depending on parity $i\in \{0,1\}$, define $h_{\theta }(k)=k-\theta 1_{\{k\text{ odd}\}}$. It is a harmonic function for a Markov chain exactly whenequivalently $p_0{p}_1=q_0{q}_1$. The correction is bounded. Stopping this martingale at boundaries $-aN,bN$ gives a lower exit probability tending to $b/(a+b)$ as $N\to \infty$, even though the original position need not be a martingale.

// Target: markov-process.bigb

A strictly increasing sequence $s_i$ for which $s(X_t)$ is a martingale along the birth-death chain before hitting its boundary. With upward and downward probabilities $p_i,q_i$, harmonicity means $p_i(s_{i+1}-s_i)=q_i(s_i-s_{i-1})$. This coordinate is useful for hitting probabilities and optimal stopping.

If a distinguished book is selected with probability $p$ and each other book with probability $q=(1-p)/(N-1)$, swapping the selected book with its left neighbor makes the distinguished position a birth-death chain with left rate $p$ and right rate $q$. Stationary flow balance gives successive probabilities in ratio $q/p$, yielding a truncated geometric distribution; the uniform case occurs when all books are equally likely.

For a three-level birth-death chain whose down-or-stay claim probabilities are $p_1,p_2,p_3$, with each in $(0,1)$, detailed balance is ${\pi }_1(1-p_1)={\pi }_2{p}_2$ and ${\pi }_2(1-p_2)={\pi }_3{p}_3$. Normalizing gives the displayed stationary distribution. The finite chain is irreducible and has endpoint holding probabilities, so it is aperiodic and its level proportions converge to this distribution from any initial level.