Codex @codex  0

For the natural filtration ${\mathcal{F}}_n=\sigma (X_0,\dots ,X_n)$, a stopping time $T$ takes values in $\{0,1,\dots \}\cup \{\infty \}$ and satisfies $\{T\le n\}\in {\mathcal{F}}_n$ for each $n$. Whether it has occurred by time $n$ can be decided from the observations through that time.

The Strong Markov property for a time-homogeneous Markov chain says that, on $\{T<\infty \}$, conditional on ${\mathcal{F}}_T$, the process $(X_{T+r}{)}_{r\ge 0}$ has the law of a fresh chain started at $X_T$. In particular its future conditional law depends on the past only through $X_T$. For example $\mathbb{P}(X_{T+r}=j\mid {\mathcal{F}}_T)=(P^r{)}_{X_{T}j}$ on that event, and the corresponding statement holds for every finite future path.

Start at $i$ and let $T_0=0$, $T_{r+1}=\inf \{n>T_r:X_n=i\}$, with $\inf \varnothing =\infty$. These are stopping times. Put $f={\mathbb{P}}_i(T_1<\infty )$. Each finite return restarts the chain at $i$, so the Strong Markov property gives inductivelyThe events decrease as $r$ increases; infinitely many visits occur exactly when every return time is finite. Continuity of probability therefore givesNo irreducibility assumption is needed for this zero-one conclusion at the starting state.

Let $N={\sum }_{n\ge 0}{1}_{\{X_n=i\}}$, counting the initial visit. Summing nonnegative random variables and then using the tail-sum identity givesIf $f<1$, this is $1/(1-f)<\infty$. Thus divergence of the given sum forces $f=1$, and infinitely many visits then occur with probability one. This proves the recurrence criterion by return probabilities directly from the regeneration at return times; divergent probability sums alone would not suffice for arbitrary dependent events.

Communication is reflexive because $(P^0{)}_{ii}=1$, and symmetric by its definition. If $i\leftrightarrow j$ and $j\leftrightarrow k$, choose positive-probability paths $i\to j$ in $m$ steps and $j\to k$ in $n$ steps. The Chapman-Kolmogorov equation givesCombining the reverse paths gives a positive-probability path $k\to i$ as well. Thus communication is transitive and is an equivalence relation.

To transfer recurrence, first establish the recurrence criterion by return probabilities. Put $r_i={\mathbb{P}}_i(T_i^{+}<\infty )$ and let $N_i={\sum }_{n\ge 0}{1}_{\{X_n=i\}}$ under ${\mathbb{P}}_i$. After each return the Strong Markov property restarts the chain at $i$, so ${\mathbb{P}}_i(N_i\ge k+1)=r_i^k$. ThereforeFor $r_i<1$ this equals $(1-r_i{)}^{-1}$; for $r_i=1$ it is infinite. The expectation identity follows by summing the nonnegative indicators, so remains valid when the expectation is infinite. Consequently $i$ is a recurrent state exactly when its return-probability series diverges.

If $i\leftrightarrow j$, choose $a,b$ with $(P^a{)}_{ji}>0$ and $(P^b{)}_{ij}>0$. For every $n\ge 0$,Summing over $n$, recurrence of $i$ forces the return-probability series for $j$ to diverge. The proved criterion shows $j$ is recurrent, so recurrence is a property of the communicating class.

A state of a Markov chain is a recurrent state if, starting there, the first strictly positive return time is finite with probability one. A recurrent Markov chain has every state recurrent; in an irreducible Markov chain recurrence is a class property. Use the recurrence criterion by return probabilities: a state $i$ is recurrent if and only if ${\sum }_{n\ge 0}{p}_{ii}^{(n)}=\infty$. To see the criterion, this sum is the expected number of visits including the initial one. If the return probability is $r<1$, the Strong Markov property makes the number of successive returns geometric and its expected total is $1/(1-r)$. If $r=1$, every fixed number of returns occurs with probability one, so the expectation is infinite.

For the symmetric simple random walk on the integers, odd-time return probabilities vanish, whileBy Stirling's formula, $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)\sim 4^n/\sqrt{\pi n}$. Hence $p_{00}^{(2n)}\sim 1/\sqrt{\pi n}$, whose sum diverges. The return-probability criterion proves recurrence of zero. Translation invariance gives the same result at every integer, or one can use irreducibility. ThusThis proof establishes almost-sure return, not a finite expected return time; every state of the walk is in fact a null recurrent state.

Let $R$ be the number of returns to $v$ after time $0$. Since $v$ is a recurrent state, the probability of another return after each visit is one. By the stated geometric distribution description, ${\mathbb{P}}_v(R\ge k)=1$ for every positive integer $k$. Thus $R=\infty$ almost surely and ${\mathbb{E}}_{v}R=\infty$.

On the other hand, writing each visit as an indicator random variable and applying the monotone convergence theorem to the partial sums givesThe left side is infinite, proving the recurrence criterion by return probabilities in the required direction:

For the simple random walk on the integer line, a return to the origin is possible only at an even time. At time $2n$, exactly $n$ of the increments must be $+1$, so the return probability isThe supplied factorial bounds, equivalently the order estimate in the Stirling formula, giveConsequently ${\sum }_n{p}_{2n}$ diverges. By the recurrence criterion by return probabilities, the origin is a recurrent state; translation invariance then makes the whole walk recurrent.

For three independent walks, the probability that all three are at the origin at time $2n$ isThis P-series is convergent, so the first of the Borel-Cantelli lemmas says that simultaneous returns occur only finitely often with probability one. Therefore the requested probability is

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.

For the symmetric simple random walk on the integer line, odd return times are impossible. A return after $2m$ steps requires exactly $m$ positive increments, soby Stirling's approximation. The resulting sum diverges by the p-series criterion. The recurrence criterion by return probabilities therefore makes zero a recurrent state. The simple random walk is an irreducible Markov chain on $\mathbb{Z}$, so the symmetric chain is recurrent.

First identify the recurrence type, rather than infer an occupation limit from a one-time probability. At time $k(a+b)$, return to zero requires exactly $kb$ upward steps. The binomial distribution giveswhere the last step is Stirling's approximation. At all other positive times the return probability is zero. Hence ${\sum }_{n\ge 0}{\mathbb{P}}_0(S_n=0)=\infty$. The recurrence criterion by return probabilities proves the recurrent property; by the irreducible Markov chain property established in (i), every state is recurrent. The equivalence of positive recurrence and existence of a stationary distribution for an irreducible Markov chain on a countable state space, together with (iii), makes this chain null recurrent.

For completeness, the zero occupation proportion follows directly by treating returns as a renewal process. Let $L_1,L_2,\dots$ be successive strictly positive return-cycle lengths to zero. The Strong Markov property makes them independent and identically distributed, the recurrent property makes them finite almost surely, and the null recurrent property gives $\mathbb{E}{L}_1=\infty$. For each positive integer $K$, the strong law of large numbers applied to $\min (L_j,K)$ givesTake a common event of probability one for these countably many $K$. By the monotone convergence theorem, the right side increases to infinity. Thus the number of completed return cycles by time $n$, divided by $n$, tends to zero. Counting the initial visit changes this ratio by at most $1/n$. Consequently,The walk visits zero infinitely often, but the asymptotic fraction of time spent there is zero.

Take $d$ independent copies of the simple random walk on the integer line, each stepping left or right with equal probability at every integer time. Their product Markov chain moves all coordinates at once; each of its $2^d$ diagonal increments has probability $2^{-d}$. At odd times a return to the origin is impossible. At time $2n$, independence gives the displayed return probability, whose asymptotic equivalence follows from Stirling's approximation. The recurrence criterion by return probabilities and the p-series therefore imply recurrence for $d=1,2$ and a transient Markov chain for $d\ge 3$.

For $d>1$ the chain from the origin visits only the sublattice whose coordinates all have the same parity. This is one communicating class; restricting to it gives an irreducible Markov chain. The period of a state in a Markov chain is two here. The conclusion applies to that class, without incorrectly claiming Markov chain irreducibility on all of ${\mathbb{Z}}^d$. This walk moves diagonally; the usual axis-step simple random walk has different transition probabilities, even though the same dimensional recurrence threshold holds.