Codex @codex  0

Read the arrows in the original diagram as follows: $0$ moves to $1^{\prime }$ with probability one; from an unprimed $n\ge 1$, probability $q$ leads to $n-1$ and probability $p$ leads to $(n+1{)}^{\prime }$; from $n^{\prime }$ the corresponding destinations are $n$ and $(n+1{)}^{\prime }$. This is the two-lane Markov chain with a deterministic restart. It is irreducible: every state can reach zero by a finite path of $q$ transitions, and zero can reach every primed state by outward $p$ transitions and then every unprimed state by a $q$ transition. Thus all states have the same recurrence classification.

Let $a_n$ and $b_n$ be the hitting probabilities of zero starting from $n$ and $n^{\prime }$, with $a_0=1$. First-step conditioning givesSubtracting yields $b_n=(1+q)a_n-q{a}_{n-1}$. Eliminating $b_{n+1}$ givesIts characteristic roots are $1$ and $r=q/[p(1+q)]=q/(1-q^2)$. Put $q_c=(\sqrt{5}-1)/2$, so $r=1$ precisely when $q=q_c$.

For $q>q_c$, the general solution is $a_n=A+B{r}^n$. The bound $0\le a_n\le 1$ and $r>1$ force $B=0$, and $a_0=1$ then gives $a_n=b_n=1$. For $q=q_c$, the general solution is $a_n=A+Bn$; boundedness again gives $a_n=b_n=1$. In both cases, the return probability from zero is $b_1=1$, so the Markov chain is recurrent.

For $q<q_c$, $0<r<1$, and the pairis a nonnegative bounded solution of the first-step equations. To identify it as the actual hitting probability, use that hitting probability is the minimal nonnegative harmonic extension. This fact follows directly by iteration: a nonnegative solution with boundary value one at zero dominates the probability of hitting zero within $N$ steps, for every $N$. The actual bounded solution has form $a_n=A+(1-A)r^n$, where nonnegativity as $n\to \infty$ requires $A\ge 0$. Minimality bounds it above by $r^n$, while this form bounds it below by $r^n$. Hence it is exactly the displayed solution. Starting at zero, the first return time has finite-return probability $b_1=q^2/p<1$. The Markov chain is therefore transient.

It remains to distinguish positive and null recurrence. Write $u_n={\pi }_n$ and $v_n={\pi }_{n^{\prime }}$ for invariant probabilities. Balance at zero and at $1^{\prime }$ gives ${\pi }_0=q{u}_1$ and $v_1={\pi }_0$. For the finite cut consisting of zero and both lanes up to level $n$, invariance equates its outward and inward probability fluxes:Balance at the unprimed state $n$ also gives $u_n=q(u_{n+1}+v_n)$. Combining these identities yieldsTherefore every invariant probability distribution would necessarily have $u_n=({\pi }_0/q)t^{n-1}$ and $v_n={\pi }_0{t}^{n-1}$. Conversely, these weights satisfy all individual balance equations, including $v_{n+1}=p(u_n+v_n)$, so their summability is the only remaining condition.

When $q>q_c$, $t<1$, and normalization givesAn irreducible Markov chain has an invariant probability distribution exactly when it is positive recurrent; equivalently its mean return time is finite and ${\pi }_0$ is its reciprocal. Thus this case is positive recurrent. At $q=q_c$, $t=1$ and the nonzero invariant weights cannot be summed to one. Irreducibility would force ${\pi }_0>0$ in any invariant probability distribution. Since recurrence was already proved but no such distribution exists, this case is null recurrent.

The complete classification is therefore transient for $0<q<q_c$, null recurrent at $q=q_c$, and positive recurrent for $q_c<q<1$. A drift argument using only the unprimed arrows would miss the primed lane and give the wrong threshold.

Condition on the first jump, putting $h_{W_0}=1$. The hitting probabilities obeyThe relevant characterization is that a hitting probability is the minimal nonnegative harmonic extension of its target-boundary value. Thus among nonnegative solutions of these equations with $h_{W_0}=1$, choose the componentwise least one. Other harmonic solutions need not be probabilities. This also identifies the solution without imposing an unjustified boundary condition at infinity.

The modified transition matrix $\tilde{P}$ describes the original Markov chain until it hits $B$, and then keeps it at the first state hit. Each state of $B$ is therefore an absorbing state, andFor a nonnegative superharmonic function for a Markov chain $g$ satisfying the boundary condition, part (c) and positivity of the transition matrix give by induction $g\ge {\tilde{P}}^{n}g$. Also $g\ge 1_B$. ConsequentlyLet $n\to \infty$ to obtain $g_i\ge h_i$. Since $h$ satisfies the conditions by parts (a),(b), $h$ is their pointwise minimal solution. This extends the hitting probability is the minimal nonnegative harmonic extension principle to the superharmonic inequality. Nonnegative sums justify the argument on a countable state space as well as a finite one.

Now suppose the Markov chain is irreducible and recurrent, and let $g$ satisfy condition (a). In such a chain every state is hit almost surely from every other state. To see this directly, recurrence gives infinitely many visits to a starting state $i$. Irreducibility supplies a finite path from $i$ to any target $j$ with positive probability $\alpha$, chosen with no return to $i$ before reaching $j$. At each successive return to $i$, the Strong Markov property gives another trial with conditional success probability at least $\alpha$. The chance of avoiding $j$ through $N$ such trials is at most $(1-\alpha {)}^N$, which tends to zero.

Apply the absorbing modification at the singleton $\{j\}$. Part (c) holds for arbitrary $g$ satisfying (a), soSince $g_j\ge 0$ and the probability tends to one, $g_i\ge g_j$. Interchanging $i,j$ yields equality. Thus every nonnegative superharmonic function is constant on an irreducible recurrent Markov chain.

Conversely, if an irreducible Markov chain is not recurrent, choose a state $j$ with return probability $r_j={\mathbb{P}}_j({\tau }_j^{+}<\infty )<1$. Its hitting probability $h$ for $\{j\}$ satisfies condition (a), and $h_j=1$. The first-step formula for a return after time zero gives $(Ph{)}_j=r_j<1$. Therefore $h$ cannot be constant: a constant function with value one at $j$ would have $(Ph{)}_j=1$. This supplies a nonconstant nonnegative superharmonic solution. HenceThe admissible constant solutions are precisely the nonnegative constants. This is recurrence characterized by constant nonnegative superharmonic functions.

Write $h_i={\mathbb{P}}_i(H^A<\infty )$. For $i\in A$, $h_i=1$. For $i\notin A$, conditioning on the first step and using the Markov property gives $h_i={\sum }_j{p}_{ij}{h}_j$. This establishes the required equations for the hitting probability.

To prove the hitting probability is the minimal nonnegative harmonic extension, let $h_i^{(n)}={\mathbb{P}}_i(H^A\le n)$. Then $h^{(0)}=1_A$ andIf $g$ is any nonnegative solution of the same boundary equations, $g\ge h^{(0)}$. Positivity of the transition probabilities implies by induction $g\ge h^{(n)}$ for every $n$. The events $\{H^A\le n\}$ increase to $\{H^A<\infty \}$, so $h^{(n)}\uparrow h$ and $g\ge h$. Therefore $h$ is the minimal nonnegative solution.

For the tournament won by two consecutive victories, a transient pair $ij$, with $i\ne j$ and third player $k$, moves with equal probabilities to the absorbing state $jj$ or the transient pair $jk$. Thus the two transient cycles arewith probability $1/2$ of absorption at each step. A full cycle without absorption has probability $1/8$, so absorption occurs almost surely.

Starting from $AC$, the successive absorption winners are $C,B,A$, with first-cycle probabilities $1/2,1/4,1/8$. Summing the geometric repetitions givesStarting from $BC$, the order is $C,A,B$, giving $(2/7,1/7,4/7)$.

Because the first game is between $A$ and $B$, the initial ordered pair of winners is $AA,AC,BB,BC$, each with probability $1/4$. Combining the immediate wins with the transient hitting probabilities,Their sum is one, consistent with almost-sure absorption.