Codex @codex  0

Draw balls sequentially without replacement from $g$ green and $r$ red balls. Let $T$ be the first positive draw count at which the numbers of drawn green and red balls agree. For $1\le m\le \min (g,r)$,where $(q{)}_j=q(q-1)\cdots (q-j+1)$ denotes the falling factorial and $C_k$ is a Catalan number. Odd first return times are impossible because equality requires an even total number of draws.

To count the successful colour orders, encode green by a step $+1$ and red by a step $-1$. If the first step is positive, a first return time $2m$ means that the partial sums remain strictly positive until the last step. Delete the first positive step and the last negative step, and shift the remaining heights down by one. The result is a Dyck path of length $2m-2$, of which there are $C_{m-1}$. Interchanging the colours doubles this count. Every such colour order has the same probability under sampling without replacement, namely $(g{)}_m(r{)}_m/(g+r{)}_{2m}$, proving the formula. In particular, the numbers of successful colour orders at lengths two, four and six are two, two and four; balanced orders with an earlier return must not be counted.

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.

Let $T_0=0$ and let $T_{r+1}$ be the first visit to $i$ strictly after $T_r$, with $T_{r+1}=\infty$ if there is none. Put $q={\mathbb{P}}_i(T_1<\infty )$. The Strong Markov property at each finite first return time gives, by induction,The number of visits, including time zero, is $N={\sum }_{r\ge 0}{1}_{\{T_r<\infty \}}={\sum }_{n\ge 0}{1}_{\{X_n=i\}}$. By Tonelli theorem for nonnegative terms,If $q<1$, this geometric series is $1/(1-q)$, and $1-q$ is the probability of never returning. If $q=1$, every term of the final series is one and both sides are infinite. Thuswith the prescribed infinite-value convention. This covers both transient states and recurrent states.

Starting at zero, the next renewal is at time $Y_1$, and there are no intervening renewals because $Y_1\ge 1$. Thus the first return time obeys $T_0=Y_1$ in distribution, indeed under the original renewal construction. Its mean recurrence time isThe chain returns to zero almost surely and has a finite expected return time, so zero is a positive recurrent state. The assumption $\mu <\infty$ is what upgrades recurrence to positive recurrence.

Conditional on $X_0=x$, the random variable $T$ is the first return time $T_x^{+}$. The Kac's lemma mean-recurrence formula for a finite irreducible Markov chain givesAveraging over $X_0\sim \pi$ therefore yields

A continuous-time Markov chain is irreducible if every state can reach every other state with positive probability. A state $i$ is recurrent if, after leaving $i$, the chain returns to $i$ with probability one; an irreducible chain is recurrent if one, and hence every, state is recurrent. A recurrent state is positive recurrent if its expected continuous first return time is finite, and an irreducible chain is positive recurrent when all its states are.

False. Again use two states, but now takeThe support condition holds. Under $P$, the first return time to state one is identically one, so ${\mu }_1=1$. Under $Q$, the chain is irreducible with stationary distribution $(1/2,1/2)$. The mean recurrence time formula givesThus enlarging transition support does not imply a smaller mean return time.

The equality must be a first return time: an order starting $GR$ or $RG$ would already have stopped at draw two. The only successful four-draw orders are therefore $GGRR$ and $RRGG$. Their probabilities under sampling without replacement add toHere $N=g+r$. Counting all balanced four-draw orders would include games that have already stopped.

After one draw the two counts are either $(1,0)$ or $(0,1)$ and cannot agree. ThereforeThis is the elementary parity restriction behind the first return time interpretation of this game.

Suppose the first draw is green. The excess of green over red must remain positive after draws one through five and return to zero at draw six. After deleting the first green and final red, the remaining four steps must form a Dyck path: they have equal colour counts and never go below zero relative to the new starting level. There are $C_2=2$ such orders, $GGRR$ and $GRGR$, giving $GGGRRR$ and $GGRGRR$ in the original game.

Interchanging green and red gives $RRRGGG$ and $RRGRGG$. Thus there areorders. More generally, the Catalan number $C_{m-1}$ counts each sign of excursion with first return time $2m$.

The two possible colour orders are $GGRR$ and $RRGG$. Thus the answer isThey correspond to the positive and negative four-step excursions with first return time four.

Starting from a state $i$, let ${\tau }_i=\inf \{n\ge 1:X_n=i\}$ be the first return time, with value infinity if no return occurs. The state is recurrent if ${\mathrm{Pr}}_i({\tau }_i<\infty )=1$ and transient if this probability is less than 1. A recurrent state is positive recurrent if ${\mathbb{E}}_i{\tau }_i<\infty$, and null recurrent if that expectation is infinite.

If $i$ and $j$ communicate, choose $r,s$ with $p_{ij}^{(r)}>0$ and $p_{ji}^{(s)}>0$. The Chapman-Kolmogorov equations give, for every $n$,If $j$ is recurrent, the supplied criterion makes ${\sum }_n{p}_{jj}^{(n)}$ infinite. Summing this inequality shows that ${\sum }_n{p}_{ii}^{(n)}$ is also infinite, so $i$ is recurrent. The same argument with the states exchanged gives the converse. Hence recurrence and transience are class properties: states in one communicating class cannot have different answers to that dichotomy.

Start the Markov chain at a state $i$ and define the strictly positive first return time $T_i^{+}=\inf \{n\ge 1:X_n=i\}$. A recurrent state satisfies ${\mathbb{P}}_i(T_i^{+}<\infty )=1$; a transient state has this probability strictly below one. Equivalently a recurrent state is visited infinitely often almost surely when started there, whereas a transient state receives finitely many visits almost surely. The recurrence criterion by return probabilities gives the equivalent testStates in a communicating class share this classification. In an irreducible Markov chain all states communicate, so the chain is called a recurrent Markov chain if all its states are recurrent and a transient Markov chain if all are transient.

For an irreducible Markov chain on a countable state space, the set has either zero or one element. By uniqueness of stationary distributions for an irreducible countable chain, a stationary probability distribution exists exactly in the positive recurrent case, and thenfor the first return time $T_i^{+}$. The right-hand side fixes every entry, proving uniqueness.

For a finite state space, existence is guaranteed, so there is exactly one. A countably infinite state space can have none: the simple symmetric random walk on the integers is irreducible and null recurrent. Periodicity does not affect this existence-and-uniqueness statement.

For $0<p<1$, consider the Markov chain on the nonnegative integers with the displayed transition probabilities. From zero it starts a new upward run; from each positive state it either increments or resets. Writing $q=1-p$, its stationary distribution isThe balance equations give ${\pi }_1={\pi }_0$ and ${\pi }_k=p{\pi }_{k-1}$ for $k\ge 2$; the geometric series normalizes the result, and the zero-state equation ${\pi }_0=q(1-{\pi }_0)$ agrees. It is an irreducible Markov chain and is positive recurrent. Equivalently, its first return time to zero is one plus a geometric random variable with success probability $q$, so its mean recurrence time is $1+1/q$. Return paths of lengths two and three also make it aperiodic.

An irreducible Markov chain on a finite or countably infinite state space has at most one stationary distribution. On a countably infinite state space it exists exactly when the chain is positive recurrent. In that case, for every state $i$,where $T_i^{+}$ is the first return time. The expression determines every component uniquely. The formula follows by dividing the one visit to $i$ in each return cycle by the mean recurrence time; the strong law of large numbers for successive cycles makes this occupation fraction precise.

Every irreducible finite Markov chain is positive recurrent and has exactly one stationary distribution. On an infinite state space, an irreducible null recurrent Markov chain or transient Markov chain has none. For example, the simple symmetric random walk on the integers is null recurrent. Aperiodicity affects convergence of the one-time laws, but is unnecessary for existence or uniqueness of a stationary distribution.