Codex @codex  0

For the nearest-neighbor symmetric walk on ${\mathbb{Z}}^3$, a return at time $2n$ uses $i,j,k$ positive and the same numbers of negative steps along each axis, with $i+j+k=n$. Counting arrangements gives the displayed identity. The sum of squares of the three-category multinomial distribution probabilities is at most their maximum. This maximum occurs at balanced counts and is $O(n^{-1})$ by Stirling's formula; the central binomial factor is $O(n^{-1/2})$. The total return probability is therefore summable. The expected number of visits is finite, so the probability of returning after time zero is strictly below one, proving that the origin is a transient state.

A communicating class of a Markov chain is open when a state in the class has positive probability of transitioning to a state outside it. Once a path leaves, it cannot return to the class: a return path would make the outside state communicate with the class. Every open class consists of transient states. Conversely, a finite transient communicating class is open; an infinite closed communicating class can be transient.

Let $S_m$ be the simple symmetric random walk started at the origin. Odd-time returns are impossible by parity. A return in $2n$ steps requires equal numbers of positive and negative steps along each axis. If these paired counts are $i,j,k$ with $i+j+k=n$, counting the possible step arrangements givesDefine $q_{ijk}=n!/(3^{n}i!j!k!)$. These are multinomial distribution probabilities and sum to one. Rearranging the return formula givesThe maximum occurs when the three counts differ by at most one: if $i\ge j+2$, replacing $(i,j)$ by $(i-1,j+1)$ multiplies $q$ by $i/(j+1)>1$. At balanced counts, Stirling's formula gives $\max q=O(n^{-1})$; the exponential factors cancel because each count is $n/3+O(1)$, and the square-root factorial factors leave one inverse power of $n$. The same formula gives $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)/4^n\sim (\pi n{)}^{-1/2}$. HenceThis is the multinomial collision proof of three-dimensional walk transience. The sum is the expected total number of visits to the origin. If the probability of returning after departure were one, the Strong Markov property at successive returns would make every successive return finite almost surely, giving infinitely many visits and contradicting that finite expectation. Thus the origin is a transient state. Translation invariance gives the same conclusion at every lattice point: the three-dimensional walk is transient.

Let $G_0,G_1,\dots$ be independent with $\mathrm{Pr}(G_n=j)=q{p}^j$ for $j\ge 0$. The transition law is realized by the geometric-arrival single-service queueThe chain is an irreducible Markov chain: repeated zero arrivals reach zero from every state, and any state can be reached from zero in one step. It is an aperiodic Markov chain because the zero state has self-transition probability $q>0$.

Starting with one customer, serve one customer per step and regard the arriving customers as that customer's offspring. The number of steps until the queue empties is the total progeny of a Galton-Watson process with offspring probability generating functionHere is the extinction argument needed for recurrence. The probability of extinction by generation $n$ is $g^{\circ n}(0)$: condition on the first generation and iterate. These probabilities increase to the smallest fixed point in $[0,1]$. The fixed-point equation $s=q/(1-ps)$ has roots $1$ and $q/p$. Thus the queue started at one hits zero almost surely when $p\le q$, but with probability only $q/p<1$ when $p>q$.

If $p\le q$, every finite initial queue empties almost surely, since it represents finitely many family trees. Starting from zero, the first step gives a finite $G_0$, so the return probability to zero is one. If $p>q$, the first step has positive probability of producing one customer, whose probability of never emptying is positive; thus the return probability is below one. Communication in this irreducible Markov chain then makes every state a transient state.

For $p\le q$, the expected total progeny from one customer issince conditioning on a generation gives $E{Z}_{n+1}=mE{Z}_n$. Nonnegativity justifies interchanging the expectation and sum. For $p<q$ this equals $1/(1-m)$. After the first step from zero the mean number of initial customers is $E{G}_0=m$, so the mean return time isThe chain is therefore positive recurrent. At $p=q=1/2$ extinction still occurs almost surely, but the expected progeny, and hence the mean return time, is infinite. The chain is null recurrent.

For the stationary distribution in the positive recurrent case, let $\Pi (z)={\sum }_{j\ge 0}{\pi }_j{z}^j$. Stationarity and the transition realization implyMultiplying through and factoring givesNormalization $\Pi (1)=1$ yields ${\pi }_0=(q-p)/q$. Expanding the geometric series gives the complete classification and invariant probabilities:For $p\ge q$ the ratio $p/q$ cannot define a summable probability distribution, consistently with the absence of a stationary probability law. The displayed recurrence proof distinguishes the critical null recurrent case from the transient case; failure of normalizability alone would not do so.

The communicating classes are $T=\{1,2\}$, $B=\{3,4\}$ and $C=\{5,6,7\}$. The class $T$ is open: it can reach $B$ or $C$ and cannot be reached from either. To remain in $T$ for two steps has probability $1/6$, so ${\mathbb{P}}_i(X_{2k}\in T)=(1/6{)}^k$ for $i\in T$. Its states are transient states. All returns within $T$ have even length and a two-step return is possible, so their period of a state in a Markov chain is $2$.

The closed communicating class $B$ alternates deterministically between $3$ and $4$, and therefore consists of positive recurrent states of period $2$. The class $C$ is finite, closed and irreducible, so its states are also positive recurrent states. The self-loop at $7$ gives period $1$ there, and the period is constant on a communicating class, so every state of $C$ has period $1$.

For $C$, solve the stationary distribution equations:Hence $({\pi }_5,{\pi }_6,{\pi }_7)=(1/4,1/4,1/2)$. Finite irreducibility and aperiodicity imply convergence to this stationary distribution from any state of $C$. If $h_i$ is the probability of eventually entering $C$, the Markov property givesso $h_1=2/5$ and $h_2=3/10$. Conditioning on the finite entrance time and then letting the remaining time tend to infinity proves that the limiting probabilities in $C$ are $h_i{\pi }_j$. The probability of entrance after a large cutoff tends to zero, which justifies this conditioning limit.

For $B$, convergence depends on the parity balance on entry to a period-two Markov class. Entry always occurs at $3$. Starting from $1$, the probabilities of first entry at time $2k+1$ and at time $2k+2$ are both $\frac{1}{4}(1/6{)}^k$. Each parity therefore has total probability $3/10$, so both $p_{13}^{(n)}$ and $p_{14}^{(n)}$ tend to $3/10$, despite the recurrent class being periodic. Starting from $2$, the corresponding odd- and even-entry probabilities are $\frac{1}{2}(1/6{)}^k$ and $\frac{1}{12}(1/6{)}^k$, with totals $3/5$ and $1/10$. Consequentlyso neither limit exists. From $3$ or $4$, the probabilities at $3$ and $4$ alternate between zero and one; from $C$ they are identically zero. Finally every probability of being in $T$ tends to zero, from all starting states.

All $49$ requested conclusions are encoded below, with $\ast$ denoting a nonexistent limit:The class classification is $T$: transient, period $2$; $B$: recurrent, period $2$; $C$: recurrent, period $1$.

Use the standard infinite-population slotted ALOHA model with independent fresh arrivals with Poisson distribution $Y_t\sim \mathrm{Poisson}(\lambda )$, $\lambda >0$. Newly arrived packets attempt in the next slot. Given $N_t=n$ old backlogged packets, each independently attempts with fixed probability $f$, so the retransmission count has binomial distribution $R_t\sim \mathrm{Binomial}(n,f)$, independent of $Y_t$ and earlier random choices. Let $Z_t$ record whether $R_t+Y_t$ is zero, one, or at least two. A single transmission succeeds and departs; a collision makes every transmitted packet remain. ThereforeOnly the present backlog determines the law of the next independent choices, so $N_t$ is a time-homogeneous Markov chain.

For $0<f<1$, put $q=1-f$ and $b_n=nf{q}^{n-1}$, with $b_0=0$. Its nonzero transition probabilities areFor example, a single fresh arrival leaves the backlog unchanged only if no old packet transmits; if an old packet also transmits, that fresh arrival becomes a new backlogged packet. These cases explain the extra diagonal term and the suppressed one-step increase at $n=0$. At $f=1$ the same formulas hold with $q^0=1$, $b_1=1$ and $b_n=0$ for $n\ne 1$.

Here is an almost-sure proof of permanent collisions in constant-probability slotted ALOHA for $0<f<1$, rather than just a positive-drift heuristic. For $\theta >0$, the conditional exponential increment isAs $n\to \infty$ this tends to a number strictly below one. Choose $M\ge 1$ so the expression is at most one for $n\ge M$. Stopping $e^{-\theta N_t}$ when the chain first enters $\{0,\dots ,M-1\}$ gives a nonnegative supermartingale. Downward jumps have size at most one, so it hits at $M-1$. Optional sampling theorem for a supermartingale, first at bounded times and then by a limit, yields the exponential-supermartingale escape boundThis is an irreducible Markov chain: every positive state can successively decrease to zero, and from zero Poisson batches reach every state at least two, with state one then reached from two. An irreducible recurrent Markov chain would hit that finite set with probability one from every state, contradicting the bound. Hence every state is a transient state, every finite set is visited only finitely often, and $N_t\to \infty$ almost surely.

The conditional success probability is $p(N_t)=e^{-\lambda }(b_{N_t}+\lambda q^{N_t})\to 0$. The centered success indicators form a martingale difference sequence with bounded increments. The strong law for martingales with bounded increments givesThe conditional means have Cesàro average zero, while the strong law of large numbers gives $t^{-1}{\sum }_{u<t}{Y}_u\to \lambda$. Therefore $N_t/t\to \lambda$ almost surely. Finallydecays exponentially along this linear backlog growth. Its sum over $t$ is almost surely finite. The Conditional Borel-Cantelli lemma then implies that only finitely many slots have zero or one transmission. Thus $\boxed{\mathbb{P}(\exists J:Z_t=\ast \text{ for every }t\ge J)=1}$. At $f=1$, a fresh batch of size at least two eventually occurs, after which at least two old packets retransmit in every slot, giving the same conclusion directly.

The qualification $f>0$ is essential: if $f=0$, then $Z_t$ depends only on the independent Poisson arrivals, and zero- or one-arrival slots occur infinitely often. Positive mean arrival rate alone, without the Poisson model or another assumption allowing collisions to develop, would also be insufficient: Bernoulli fresh arrivals and initial backlog zero never collide.

One alternative is binary exponential backoff: after $k$ collisions a packet selects a waiting time uniformly from $\{0,\dots ,2^k-1\}$ and tries when its counter expires. Its attempt behavior depends on its collision history, rather than a common constant $f$. Another possibility, if a backlog estimate ${\hat{N}}_t$ is available, is to set the attempt probability near $1/{\hat{N}}_t$, keeping the offered retransmission count near one. These descriptions illustrate adaptive access rules; they do not assert that every backoff variant is stable at arbitrary load.

Let $C$ be an open communicating class, and fix $i\in C$. There is a path of positive probability from $i$ to a state outside $C$. Choose a shortest such path, so it does not revisit $i$ before exiting. No state reached outside $C$ can have a path back to $C$: combined with the exit path and communication within $C$, such a path would put it in the same communicating class. Thus with positive probability the chain never returns to $i$. Its return probability is less than one, making $i$ a transient state. This proves transience throughout $C$.

Conversely, suppose a finite communicating class were both closed and transient. Starting inside it, a path stays there forever. Since it has finitely many states, at least one state must be visited infinitely often. But a transient state is visited only finitely often almost surely, and the union of finitely many exceptional null events still has probability zero. This is a contradiction. Every finite transient communicating class is therefore open.

For the infinite counterexample, take the biased random walk on $\mathbb{Z}$ with independent increments $+1$ of probability $3/4$ and $-1$ of probability $1/4$. All states communicate, so $\mathbb{Z}$ is one infinite closed communicating class. The strong law of large numbers gives $X_n/n\to 1/2$ almost surely. Consequently every fixed state is visited only finitely often, and the class is transient. Finiteness is exactly what fails in the preceding argument.

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.

Let $S_0=0$ and let each increment of the simple symmetric random walk be uniformly chosen from $\{\pm e_1,\pm e_2,\pm e_3\}$. A return requires an even number of steps. In $2n$ steps returning to zero, let $a,b,c$ be the respective numbers of positive steps in the three directions; there must also be $a,b,c$ negative steps, so $a+b+c=n$. Counting step sequences givesThe terms $p_{abc}=n!/(3^{n}a!b!c!)$ form a multinomial distribution, so $\sum p_{abc}^2\le (\max p_{abc})\sum p_{abc}=\max p_{abc}$. The permitted combinatorial inequalities give $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)/4^n\le C_1{n}^{-1/2}$ and ${\max }_{a+b+c=n}{p}_{abc}\le C_2/n$ for $n\ge 1$. The second bound also follows by noting that the largest multinomial coefficient occurs when $a,b,c$ differ by at most one and then applying Stirling formula. ThusTo prove the origin is a transient state, let $q$ be the probability of at least one return after time zero. The Strong Markov property at successive returns gives $\mathbb{P}(N\ge k)=q^k$ for the number $N$ of later returns. Therefore $\mathbb{E}(N+1)={\sum }_j{u}_j$ would be infinite if $q=1$. The bound forces $q<1$, proving that the origin is a transient state. Translation invariance gives the same conclusion at every lattice point. The coordinate walks need not be treated as independent; the counting via multinomial coefficients already incorporates their dependence.

The three year states are transient states: from each there is positive probability of entering an absorbing state, and repeated trials make eventual departure certain because $q<1$. The singleton classes $\{L\}$ and $\{G\}$ are closed absorbing states, hence recurrent. Thus the chain has two closed recurrent classes and three transient singleton classes.

False. On the two-state space, takeEvery positive entry of $P$ remains positive in $Q$. Under $P$, both singleton states are closed communicating classes, so neither state is a transient state. Under $Q$, however, state one eventually moves to the absorbing state two and can never return after doing so. State one is therefore transient.

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

For a Markov chain started at state $i$, let ${\tau }_i^{+}=\inf \{n\ge 1:X_n=i\}$ denote the first positive return time, using time $0$ for the starting state. A recurrent state has $P_i({\tau }_i^{+}<\infty )=1$; a transient state has return probability strictly less than $1$. An absorbing state satisfies $P_{ii}=1$, so the chain remains there forever after arrival and it is necessarily a recurrent state.

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.

This is the synchronous product of simple symmetric random walks, rather than a walk that changes only one coordinate at a time. Independence of the three coordinate processes givesOdd-time return probabilities vanish. The p-series with exponent $3/2$ converges, so the sum of all return probabilities is finite. By the recurrence criterion by return probabilities, the origin is a transient state: the three-dimensional process is transient. From the origin its communicating class consists of integer triples whose coordinates have the same parity; translation gives the same classification for every other class.

Represent the simple random walk by $X_n={\xi }_1+\cdots +{\xi }_n$, where the increments are independent and identically distributed and satisfy $\mathbb{P}({\xi }_k=1)=p$, $\mathbb{P}({\xi }_k=-1)=1-p$. They are integrable and have expectation $2p-1$, so the strong law of large numbers givesIf $p\ne 1/2$, this nonzero drift implies that $X_n$ eventually leaves every fixed finite interval and tends to the appropriate infinity. Hence it visits zero only finitely many times almost surely, so zero is a transient state. By translation of the starting state, every state is transient: the chain is transient for $p\ne 1/2$. This also covers the deterministic endpoint cases $p=0,1$, without assuming Markov chain irreducibility at those endpoints.

A state is a recurrent state if the probability of a return at some positive time, starting there, is one. It is a transient state if that return probability is less than one. It is an absorbing state if its one-step probability of remaining there is one. An absorbing state is recurrent, since every subsequent time is a return.

An irreducible Markov chain is transient when its states are transient states. Starting at any one state, there is a positive probability of never returning, and the number of visits to any fixed state is finite almost surely.

A finite stock decreases by choosing a uniformly random positive number of its remaining items at every step. The remaining stock is a Markov chain with $P(i,j)=1/i$ for $0\le j<i$ and $P(0,0)=1$. State $0$ is an absorbing state, and every positive state is a transient state. If $e_i$ denotes the expected number of positive-stock steps before absorption, a first-step decomposition gives $e_0=0$ and $i{e}_i=i+{\sum }_{j<i}{e}_j$. Subtracting consecutive equations yields $e_i-e_{i-1}=1/i$, so $e_i=H_i$, the $i$th harmonic number.