Codex @codex  0

Let $A_n=\{X_m=0\text{ for some }m\ge n\}$. By the Markov property,The events $A_n$ decrease to the event that the walk visits zero infinitely often, which has probability zero by the stated transience assumption. HencePart a and the almost sure supermartingale convergence theorem give an almost-sure limit $V\ge 0$. By Fatou lemma, $\mathbb{E}V\le {\mathrm{liminf}}_n\mathbb{E}[v(X_n)]=0$, so $V=0$ almost surely.

The killed transition operator isThe infinitesimal generator of the diffusion isThe Markov property and the Chapman-Kolmogorov equation give, for each fixed $y$,Dividing by $h$, letting $h\downarrow 0$, and using the generator definition together with the assumed $C^{1,2}$ regularity gives the pointwise Kolmogorov backward equation

The hypotheses imply $a=1/5=0.2$ and $b=1/1.25=0.8$, so $a+b=1$. Conditional on the negative result at month 1, the likelihood is the probability of remaining in $S$ at month 2 and moving to $I$ by month 3. The supplied matrix exponential givesThe Markov property therefore gives

The Strong Markov property at the first visit to $0$ gives the singleton equilibrium potential from the Green functionLet $U_n$ be an increasing exhaustion of $G$ by finite sets containing $0$, and let $g_{U_n}(x,0)$ be the Green function of a transient weighted graph stopped on leaving $U_n$. Each $g_{U_n}(\cdot ,0)$ has finite support. The Green identity and the Markov property give, for $m\ge n$,By the monotone convergence theorem, the right side tends to zero as $m,n\to \infty$, while $g_{U_n}(x,0)\uparrow g(x,0)$. Thus $g(\cdot ,0)$ is an $H_0$ limit of finitely supported functions. Dividing by the positive number $g(0,0)$ proves $h\in H_0$.

There are two paths from $X$ back to $X$ in two steps: $X\to X\to X$ and $X\to Y\to X$. By the markov property, their probabilities multiply along each path. Therefore

Starting from $X$ at time $n$, the markov property and the time-independent transition rules give $\mathbb{P}(M_{2n}=X\mid M_n=X)=p_n$. ThereforeWrite $p_n=\frac{3}{4}(\frac{3}{4}{)}^n\left(1+\frac{1}{3}(-\frac{1}{3}{)}^n\right)$. The conditional probability becomesThe conditioning selects paths which have avoided the absorbing state up to time $2n$; it is therefore quite different from the unconditioned probability $p_n$, which tends to zero.

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 state $i$ is absorbing if $p_{ii}=1$, so once visited it is never left. Condition on the first step and use the Markov property: for $i\ne 1$, the subsequent probability of ever reaching state one is $h_j$ given $X_1=j$. Hence $h_i={\sum }_j{p}_{ij}{h}_j$, with $h_1=1$.

In this chain state four is a separate absorbing state, so $h_4=0$. The other two equations areSolving givesLet $t_i$ be the mean time to hit the absorbing set. From either transient state the next-step absorption probability is at least $1/3$, so its tail is geometrically bounded and the expectations are finite. First-step analysis gives $t_2=1+\frac{2}{3}{t}_3$ and $t_3=1+\frac{1}{4}{t}_2$. Thus $t_3=5/4+t_3/6$ and

The Markov property says that conditional on the present state, the next-state law does not depend on the earlier history. For this time-homogeneous chain, $\mathbb{P}(X_{n+1}=j\mid X_0=i_0,\dots ,X_n=i)=p_{ij}$ whenever the conditioning event has positive probability.

States communicate when each is accessible from the other by a finite positive-probability path; the equivalence classes are the communicating classes. A class is closed if no one-step transition leaves it, and open otherwise. Probability nonnegativity adds the implicit restriction $p\ge 0$ to the printed upper bound.

At $p=0$, every state is absorbing, so the classes are the singletons, all closed. For $0<p\le 1/2$, every neighbouring pair communicates, so the whole state space is one closed class, making the chain irreducible. There are no open classes in either case.

For $m=3$ and $p>0$, detailed balance along the path gives $2p{\pi }_0=p{\pi }_1$, ${\pi }_1={\pi }_2$, and $p{\pi }_2=2p{\pi }_3$. After normalization,For $0<p<1/2$, the self-loops have positive probability; the finite irreducible chain is aperiodic, so ${\mathbb{P}}_i(X_n=j)\to {\pi }_j$ for all fixed starting states and targets. For $p=1/2$, every step changes parity. The chain has period two, and for each fixed $i,j$ one parity of times has probability zero while ${\pi }_j>0$. Thus the stated convergence from a fixed starting state holds exactly when $0<p<1/2$. This is the stationary law of a reflecting nearest-neighbor walk on a finite path.

For $n=0$, the conditional transition probabilities are ${\delta }_{ij}$, the entries of $P^0=I$; for $n=1$ the assertion is the definition of $P$. For the induction step, condition on the state at time $n$ and use the Markov property and time-homogeneity:The countable sum is justified by the law of total probability; all terms are nonnegative. Thus the formula follows for every $n$ by induction. It is the Chapman-Kolmogorov equation for repeated one-step transitions.

The Markov property and conditioning on the intermediate state give, for the full history through time $2n$,Condition this identity again on the smaller history $(Y_0,\dots ,Y_n)$. Its right-hand side is already determined by $Y_n=X_{2n}$, so the tower property givesThus the sampled sequence is a time-homogeneous Markov chain with transition matrix $P^2$. Checking only its one-time marginal distributions would not by itself establish the Markov property.

It is the every-second-step case of a subsampled Markov chain.

Condition on $X_m=k$ and apply the Markov property and time homogeneity:Thus the transition matrices satisfy $P(m+n)=P(m)P(n)$; since $P(1)=P$ and $P(0)=I$, induction gives $P(n)=P^n$. Averaging over the initial state givesIf $\mu P=\mu$, induction gives $\mu P^n=\mu$, so this probability equals ${\mu }_i$ for every $n$. This is stationarity of the initial distribution.

Condition on $X_m=k$ and apply the Markov property and time homogeneity:Thus the transition matrices satisfy $P(m+n)=P(m)P(n)$; since $P(1)=P$ and $P(0)=I$, induction gives $P(n)=P^n$. Averaging over the initial state givesIf $\mu P=\mu$, induction gives $\mu P^n=\mu$, so this probability equals ${\mu }_i$ for every $n$. This is stationarity of the initial distribution.

For $i\notin A$, the event of ever reaching $A$ can be conditioned on the first step. Given $X_1=j$, its remaining hitting probability is $h_j$ by the Markov property, including $h_j=1$ if $j\in A$. The law of total probability thus givesFor $i\in A$ the definition uses time zero and gives $h_i=1$, so the harmonic equation is needed only outside $A$.

For $n=0$, the transition probabilities are the entries of the identity $P^0$. Suppose the formula holds for $n$. Conditioning on $X_n=k$ and using the Markov property givesThe countable sums have nonnegative terms, so they are justified by the law of total probability. Induction proves

Given $X_n=k>0$, the number remaining next time is uniform on $\{0,\dots ,k-1\}$ and is independent of earlier choices; given $X_n=0$, the next state is $0$. Thus the conditional law of $X_{n+1}$ depends only on $X_n$, which is the Markov property.

By contrast, observing only the last number removed generally loses information about the remaining stock. For $N\ge 3$, compare the two positive-probability historiesBoth have $Y_2=1$, but the first leaves $N-2>0$ stickers, so $P(Y_3>0\mid Y_1=1,Y_2=1)=1$, whereas the second leaves none, so $P(Y_3>0\mid Y_1=N-1,Y_2=1)=0$. Hence $(Y_n)$ fails the Markov property.

The qualification $N\ge 3$ is necessary if a Markov chain is allowed to have time-dependent transitions. For $N=1$, the removal sequence is the deterministic, time-homogeneous Markov chain $1,0,0,\dots$. For $N=2$, it is a time-inhomogeneous Markov chain, although it is not time-homogeneous on its observed removal states: a removal of $1$ at the first step forces another removal of $1$, whereas a removal of $1$ at the second step forces $0$ next. The blanket non-Markov claim should therefore be understood in the generic, nondegenerate setting.

Put $q=1-p$ and ${\xi }_i=Y_i-Y_{i-1}$. The Markov property and the state-independent transition probabilities show that, conditional on the whole previous history, ${\xi }_i$ is $+1$ with probability $p$ and $-1$ with probability $q$. Multiplying these conditional probabilities for any finite step sequence proves that the ${\xi }_i$ are independent and identically distributed random variables, withBecause $Y_n=k+{\sum }_{i=1}^n{\xi }_i$, the strong law of large numbers givesIn particular, $Y_n\to +\infty$ almost surely. This stronger pathwise consequence will determine both eventual crossings and the asymptotic first-passage times.

The difference process $D_n$ is a Markov chain. If the columns are equal, the next block creates a height difference of one. If the difference is $k\ge 1$, landing in the taller column increases it to $k+1$, while landing in the shorter column makes it zero. Therefore its only nonzero transition probabilities areThese probabilities depend only on the present difference, not on the absolute heights or their history. This is the reset-or-increment Markov chain with $p=1/2$.

For its stationary distribution, the incoming-flow equations give ${\pi }_1={\pi }_0$ and ${\pi }_k={\pi }_{k-1}/2$ for $k\ge 2$. Normalization uses a geometric series:ThusThe remaining balance equation is also satisfied: the flow into zero is $(1-{\pi }_0)/2=1/3$. Every state can reach zero and every positive state can be reached from zero, so it is an irreducible Markov chain. Its invariant probability distribution makes it positive recurrent, and that distribution is unique.

The maximum-height process $H_n$ is not Markov. Starting empty, condition first on the positive-probability history $(H_1,H_2,H_3)=(1,1,2)$. After two blocks the columns were equal, so after three their difference is one. Hence $\mathbb{P}(H_4=3\mid H_1=1,H_2=1,H_3=2)=1/2$.

For the history $(1,2,2)$, the first two blocks built one column and the third caught the other column up, leaving equal heights. Hence $\mathbb{P}(H_4=3\mid H_1=1,H_2=2,H_3=2)=1$. Both histories have the same time and present height $H_3=2$, but different predictions. This violates the Markov property and illustrates why a function of a Markov chain need not be Markov.

An absorbing state $i$ has $p_{ii}=1$; once reached, the chain never leaves it. For a nonabsorbing initial state, condition on its first transition and use the Markov property:Here $h_1=1$ and $h_4=0$. The other equations areSolving givesFor absorption into either state one or four, let $e_i$ be the expected number of steps, with $e_1=e_4=0$. first-step analysis givesHence $e_2=2$ andThe expectation is finite because each transient two-step cycle has probability at most $(2/3)(1/4)=1/6$ of remaining transient; the survival tail is geometrically bounded. This also justifies solving the expectation equations without assuming finiteness in advance.

The Markov property says that, conditional on the present state, the next state is independent of the earlier history:Two states communicate if each is reachable from the other with positive probability in finitely many steps. The equivalence classes are communicating classes; a class is closed if no positive-probability transition leaves it.

The displayed probabilities require $0\le p\le 1/2$; negative values allowed by the printed one-sided inequality are not transition probabilities. For $p=0$, every state is an absorbing singleton, so all singleton classes are closed. For $0<p\le 1/2$, neighboring states communicate in both directions, so there is one closed irreducible class $S$ and no open classes.

For $m=3$, the detailed balance relations give $2{\pi }_0={\pi }_1={\pi }_2=2{\pi }_3$. Normalization yieldsFor $0<p<1/2$, positive holding probabilities make the finite irreducible chain aperiodic, so its transition probabilities converge to ${\pi }_j$ from every initial state. At $p=1/2$, every step changes parity and the period is two; convergence from a fixed initial state fails. A stationary initial mixture still has distribution $\pi$ at every time, but this does not give convergence of the transition probabilities asked for.