Codex @codex  0

For a finite, time-homogeneous Discrete-time Markov chain with row-stochastic transition matrix $P$, a state $a$ is absorbing exactly when $P_{aa}=1$. Nonnegativity and the row sum then force $P_{aj}=0$ for $j\ne a$: once entered, $a$ is never left. Equivalently, $\{a\}$ is a closed communicating class. A larger closed communicating class may keep moving internally; closure means confinement to a set, whereas absorption at a state means remaining at one point.

An absorbing state is useful for recording a terminal outcome: after a toy routine finishes, keep its outcome in the state space so that the same transition matrix still describes subsequent steps. Calling a finite Markov chain absorbing usually also requires that some absorbing state be accessible from every state. Merely containing an absorbing state is insufficient: another closed communicating class could prevent absorption. See Grinstead and Snell, Introduction to Probability, section 11.2 for this convention.

Consider a constructed routine with unfinished modes $u,v$ and terminal outcomes $A,B$. All the following transition probabilities are chosen for illustration, not estimated from observations. In state order $(u,v,A,B)$, takeThe communicating class $\{u,v\}$ is open, while $\{A\}$ and $\{B\}$ are closed communicating classes consisting of absorbing states. Both terminal outcomes are accessible from both unfinished modes, sometimes by an indirect path.

Let $T=\inf \{n\ge 0:X_n\in \{A,B\}\}$ be the terminal hitting time. Write $h_i={\mathbb{P}}_i(X_T=A)$ for the absorption probability and $t_i={\mathbb{E}}_{i}T$ for the expected hitting time, with the subscript denoting the starting state. First-step analysis givesHere $h_A=1$, $h_B=0$, and $t_A=t_B=0$. Solving these two pairs of linear equations yieldsStarting at $u$ therefore ends at $A$ with probability $0.6$ and takes $3.2$ steps on average to reach either terminal state. The terminal hitting time counts the transition into the outcome, but no later self-transitions. Outcome and duration answer different questions: from $v$, outcome $A$ is less likely, yet termination is faster on average.

The matrix power $P^2$ gives the probability distribution after two steps from $u$ asThus ${\mathbb{P}}_u(T>2)=1/2$, and the probability of having already reached $A$ is $3/8$, still below its eventual absorption probability $3/5$. From either unfinished mode, each next step has terminal probability at least $1/4$. Consequently ${\mathbb{P}}_i(T>n)\le (3/4{)}^n$, proving termination almost surely and finite expected hitting time directly. The Fundamental matrix of a finite absorbing Markov chain packages both calculations and counts visits to unfinished modes.

For a nearest-neighbour fortune on $\{0,\dots ,N\}$, with win probability $p$, loss probability $q=1-p$ and $p\ne q$, put $\rho =q/p$. First-step analysis gives $m_i=1+p{m}_{i+1}+q{m}_{i-1}$, with zero endpoint values. Solving the recurrence gives the displayed mean duration. Its symmetric limit is $i(N-i)$.

For simple random walk on two disjoint complete graphs of size $n\ge 2$ joined through one new vertex $w$, let $h_1$ be the expected hitting time of $w$ from either vertex attached to $w$, and $h_o$ the expected hitting time from any other clique vertex. First-step analysis gives $h_1=1+(n-1)h_o/n$ and $h_o=h_1+n-1$, so $h_1=n^2-n+1$ and $h_o=n^2$. The expected hitting time from $w$ is zero. In discrete time the random walk is an aperiodic Markov chain only for $n\ge 3$.

Assume $\mathbb{E}|g(X)|<\infty$, or use nonnegative $g$ with extended expectations. Let $p_{ij}=\mathbb{P}(X=x_i,Y=y_j)$ and $p_j=\mathbb{P}(Y=y_j)$. For $p_j>0$, the discrete conditional expectation is $\mathbb{E}[g(X)\mid Y=y_j]={\sum }_{i}g(x_i)p_{ij}/p_j$. Therefore Fubini's theorem, or Tonelli theorem in the nonnegative case, gives the tower property of conditional expectation:Values of a conditional expectation on zero-probability conditioning events do not affect the sum. An unrestricted signed $g$ whose expectation is undefined is outside this assertion.

Write $M(x)=\mathbb{E}[N(x)]$. The waiting time for two increments larger than $1/2$ dominates $N(x)$ for $0\le x\le 1$ and has mean $4$, so $M$ is finite. Conditioning on the first increment, one step is always consumed; if that increment is below $x$, the remaining independent sequence has the original law. Thus first-step analysis and the tower property of conditional expectation giveThis first makes $M$ continuous and then gives $M^{\prime }=M$, with $M(0)=1$. Hence the uniform-sum crossing time below one hasAn independent explanation uses the tail-sum formula: $\mathbb{P}(N(x)>n)=\mathbb{P}(U_1+\cdots +U_n\le x)=x^n/n!$ for $x\le 1$, since this region is an $n$-dimensional simplex inside the unit cube. Summing from $n=0$ gives $e^x$. In particular the strict-crossing convention gives $N(0)=1$ almost surely and $\mathbb{E}N(1)=e$.

A probability space consists of a sample space $\Omega$, a sigma-algebra $\mathcal{F}$ of events, and a probability measure $\mathbb{P}$ satisfying:

For arbitrary events, Boole's inequality is $\mathbb{P}({\bigcup }_j{A}_j)\le {\sum }_j\mathbb{P}(A_j)$. To prove it, replace each $A_j$ by $D_j=A_j\setminus {\bigcup }_{i<j}{A}_i$. The $D_j$ are disjoint, have the same union, and satisfy $D_j\subseteq A_j$. Countable additivity and monotonicity give $\mathbb{P}({\bigcup }_j{A}_j)={\sum }_j\mathbb{P}(D_j)\le {\sum }_j\mathbb{P}(A_j)$. Finite unions are included by taking subsequent events empty.

Let $H_i$ be the $i$th heads event. For every $m$, the event of infinitely many heads lies inside ${\bigcup }_{i\ge m}{H}_i$. By the union bound, its probability is at most ${\sum }_{i\ge m}{p}_i$, which tends to zero. Thus the probability of infinitely many heads is $0$. This is the First Borel-Cantelli lemma, and requires no independence of the coin tosses.

For the dice experiment there are $4$ ordered outcomes giving a sum of $5$ and $6$ giving $7$, out of $36$. Each trial therefore has $p_5=1/9$, $p_7=1/6$ and irrelevant-outcome probability $13/18$. By independence between trials, summing over the number of initial irrelevant outcomes givesThe geometric series also shows that one of the two relevant sums eventually appears almost surely. Equivalently, first-step analysis gives $p=p_5+(13/18)p$.

Let $N=a+b$ and measure Lionel's fortune in unit stakes. This is gambler's ruin: the fortune moves by $+1$ with probability $p$ and $-1$ with probability $q$, stopping at $0$ or $N$. Let $m_i$ be the expected value of the absorption time starting at $i$. It is finite: from any interior state, a run of $N$ wins or losses has a fixed positive probability of absorption within $N$ steps, giving a geometric bound on survival over successive blocks. First-step analysis therefore givesFor $p\ne q$, the homogeneous solution of the recurrence is $A+B(q/p{)}^i$, and a particular solution is $-i/(p-q)$. Put $\rho =q/p$. Imposing the two endpoint boundary conditions gives the expected duration of biased gambler's ruinConsequently the expected number of games isThe denominator and numerator have matching signs, so this is positive. As a check its continuous limit at $p=q=1/2$ is $ab$, the expected duration of symmetric gambler's ruin.

Let $h$ be the probability of ever hitting $c$ starting at $a$. A first-step analysis gives a direct success with probability $1/3$, a return to the same problem with probability $1/3$, and entry into the closed class $\{b,d\}$ with probability $1/3$, after which $c$ cannot be reached. ThereforeThe possibility of infinitely many self-loops has probability zero and introduces no extra solution of this equation.

Assume the intended initial fortune satisfies $n\ge 2$ and put $X_0=n$. Conditional on current fortune $i>1$, the next gift is uniform on $\{1,\dots ,i-1\}$ and independent of the previous choices. The remaining fortune is therefore uniform on that same set. At fortune $1$ the process stays there. Consequently the future conditional distribution depends only on the current fortune, proving the Markov property, and the transition matrix on $\{1,\dots ,n\}$ isThe uniform decreasing Markov chain has state $1$ as an absorbing state, and until absorption the fortune strictly decreases, so the hitting time is at most $n-1$.

Let $e_i$ be the expected number of additional transitions to hit $1$, taking $e_1=0$. First-step analysis givesIn particular $e_2=1$. For $i\ge 3$, multiplying this recurrence by $i-1$ and the recurrence for $i-1$ by $i-2$, then subtracting, gives $(i-1)e_i=(i-1)e_{i-1}+1$. Hence $e_i-e_{i-1}=1/(i-1)$ for every $i\ge 2$, and telescoping yieldsThe PDF defines $\tau$ using times $i\ge 1$. If $n=1$ were included, that definition would give $\tau =1$ although the displayed empty sum is zero; the initial instruction to choose an integer between $1$ and $n-1$ also requires $n\ge 2$. The result above uses that intended assumption. A hitting time allowing time zero would have expectation zero from state $1$, but that is a different definition.

Let $R$ interchange the two complete graphs, sending $v_i$ to $v_i^{\prime }$ and fixing $w$. This involution preserves the transition matrix of the simple random walk. A mirror coupling under an involution starts $X$ at $v_i$, keeps $Y_t=R(X_t)$ until the hitting time $\tau$ of $w$, and then makes the two walks move identically. Each coordinate has the correct transition probabilities, and they coalesce precisely at $\tau$. The coupling inequality for total variation gives

There is a genuine error in the printed expected hitting time bound, as well as an unspecified initial law. For $n\ge 2$, write $a={\mathbb{E}}_{v_1}\tau$ and $b={\mathbb{E}}_{v_i}\tau$ for $i\ne 1$. From every clique vertex there is a positive chance of reaching $w$ within two steps, uniformly over the finite state space for each fixed $n$, so $\tau$ has finite expected value. First-step analysis, using the degree of a vertex $n$ at $v_1$ and $n-1$ at the other clique vertices, givesSolving these linear equations yieldsIn particular even the attachment vertex exceeds the printed bound by one. The valid uniform replacement is ${\max }_x{\mathbb{E}}_x\tau \le n^2$, the hitting time of the bridge vertex between two cliques formula.

We must also handle arbitrary starting states, including $w$, before applying the mirror argument. Identify related vertices and consider the lumped Markov chain $Z$ on $\{1,\dots ,n,w\}$. Its transition matrix $Q$ has $Q(1,j)=1/n$ for $j\ne 1$, $Q(1,w)=1/n$, $Q(i,j)=1/(n-1)$ for $i\ne 1$ and $j\ne i$, and $Q(w,1)=1$, with all other entries zero. Here the row for $i\ne 1$ only ranges over $j\in \{1,\dots ,n\}$.

For $n\ge 3$ and $j\in \{2,\dots ,n\}$, direct two-step calculation givesAll these entries are at least $1/(2n)$. Thus $Q^2(z,\cdot )\ge \alpha \nu (\cdot )$ for every $z$, where $\nu$ is the uniform distribution on a finite set $\{2,\dots ,n\}$ and $\alpha =(n-1)/(2n)\ge 1/3$. This is a Doeblin condition. At each two-step block couple the two quotient endpoints to the same sample from $\nu$ with probability $\alpha$, using the residual probability distributions otherwise. The first successful block has expected value at most $1/\alpha$, so the alignment time $A$ has $\mathbb{E}A\le 6$. Lift each endpoint coupling of probability distributions to the original walks by their conditional two-step path laws; this preserves every marginal path law. The success test uses fresh block randomness and so permits restarting the walks with their original transition matrix at the aligned endpoints.

At alignment the original walks are equal or related. Use identical transitions in the first case and the mirror coupling under an involution in the second. The resulting coalescing coupling has coalescence time $T$ satisfying $\mathbb{E}T\le 6+n^2$ for every pair of initial states. Therefore Markov inequality and the pairwise mixing diameter implyFor the hint's particular starting states, the quotient one-step laws from two different clique indices have a common component of mass at least $1-2/n$: for two ordinary indices it is $(n-2)/(n-1)$; for one attachment index it is $(n-2)/n$. A maximal coupling therefore aligns those indices with probability $1-O(1/n)$, as suggested. The two-step argument above additionally covers $w$.

The nonlazy walk is an aperiodic Markov chain for $n\ge 3$, because the connected graph contains a triangle. For $n=1,2$ it is a periodic Markov chain on a bipartite graph; each bipartition class has stationary mass $1/2$, and the walk stays on a single class at each time. Hence $d(t)\ge 1/2$ and the $1/4$ mixing time is infinite. The asymptotic conclusion is valid for $n\ge 3$.

Measure vertices by their Hamming distance from the target and let $h_k$ be the expected hitting time when that distance is $k$. We already know $h_1=2^n-1$. From distance one, one of the $n$ coordinate flips reaches the target and the other $n-1$ flips move to distance two. First-step analysis therefore givesFor $n\ge 2$,

Let $h_k$ be the probability that the simple random walk started at $k$ hits $n$ before zero. The first-step analysis recurrence and boundary conditions areIf $p\ne q$, the characteristic equation of a linear recurrence has roots $1$ and $q/p$, so the boundary conditions giveIf $p=q=1/2$, the repeated root gives the limiting formula $\boxed{h_m=m/n}$. This is the gambler's ruin probability.

For a fixed integer stake $a\le N$, the fact that $a$ divides $N!$ lets us measure Patricia's wealth in units of £$a$. She starts at $M=N!/a$ and succeeds upon reaching $2M$. The formula above factors asFor $p=18/37$, $r=19/18>1$, so this probability increases as $M$ decreases. She should therefore choose the largest stake, $\boxed{a=N}$. For $p=19/37$, $r=18/19<1$, so the probability increases as $M$ increases; she should choose the smallest stake, $\boxed{a=1}$.

A random time $\tau$ is a stopping time for the natural filtration $({\mathcal{F}}_n)$ of a Markov chain when $\{\tau \le n\}\in {\mathcal{F}}_n$ for every $n$. The Strong Markov property says that, conditionally on $\tau <\infty$ and $X_{\tau }=i$, the process after $\tau$ is a fresh copy of the chain started from $i$, independent of the pre-$\tau$ history.

Before capture define the half-separationFor $D_n=k\ge 2$, independence of the two moves gives the transition probabilitiesIgnore the holding steps. The resulting embedded chain is a biased random walk that moves left with probability $q$ and right with probability $1-q$. Its expected number of moves needed to descend one level is $1/(2q-1)$; this follows either from first-step analysis or from its drift $1-2q$. A non-holding move occurs with probability $1/2$ at each time, so its mean waiting time is two. Hence, for every $m\ge 2$, the expected time to go from separation $2m$ to $2(m-1)$ is

Let $T_k$ be the expected capture time starting from $D_0=k$, so $T_0=0$. The Strong Markov property at successive first passages to lower levels and part (a) giveAt $D_n=1$, the next state is zero with probability $r/2$, one with probability $1/2$, and two with probability $(1-r)/2$. First-step analysis therefore givesorSolving,Substituting $\mu =2/(2q-1)$ now yieldswhich is the required expected capture time.

Integrating the density, and using ${\lambda }_{+}+{\lambda }_{-}=A$ and ${\lambda }_{+}{\lambda }_{-}=k_1{k}_2$, givesThe same result follows from first-step analysis: the enzyme waits on average $1/k_1$ to bind, and each complex either produces or returns to the initial enzyme state.

Let $h_i={\mathbb{E}}_i{T}_0$ be the expected hitting time of state $0$. For $i\ge 1$, first-step analysis givesWith $d_i=h_i-h_{i-1}$ this becomesThe minimal nonnegative solution hasso

Equivalently, Kac's lemma gives ${\mathbb{E}}_0{T}_0^{+}=1/{\pi }_0$. A first step from $0$ either returns immediately with probability $1-p$ or moves to $1$ with probability $p$, soSubstituting ${\pi }_0=(q-1)/(q-1+q^{2}p)$ gives the same result.

Let $h_i={\mathbb{E}}_i{T}_6$. Then $h_6=0$, and first-step analysis on the closed class givesSolving these linear equations gives

Let $D,E,F$ be the midpoints of $AB,AC,BC$. WriteFirst-step analysis for the simple random walk givesbecause $A$ has neighbours $D,E$;because $D$ has neighbours $A,B,E,F$; andbecause $F$ has neighbours $B,C,D,E$. Solving,