Codex @codex  0

Put $q=1-p=a/(a+b)$. The random walk has independent and identically distributed increments $Y_n$ equal to $a$ with probability $p=b/(a+b)$ and $-b$ with probability $q$. Thus $S_0=0$, $S_n={\sum }_{j=1}^n{Y}_j$, and $\mathbb{E}{Y}_n=0$.

The history $\sigma (S_0,\dots ,S_n)$ is contained in $\sigma (Y_1,\dots ,Y_n)$. The increment $Y_{n+1}$ is independent of this history by the given independence of random variables. ThereforeThis depends only on the current state and not on time. It is precisely the time-homogeneous Markov property, so $S_n$ is a Markov chain with transition probabilitiesThe conditional identity is an identity that holds almost surely; histories of zero probability require no division by their probabilities.

A return path with $u$ upward steps and $v$ downward steps satisfies $au=bv$. Since $a,b$ are coprime, this is equivalent to $u=bk$ and $v=ak$ for an integer $k\ge 1$. Its length is therefore $k(a+b)$.

Conversely, for each such $k$, any ordering of $bk$ upward and $ak$ downward steps is an allowed positive-probability return path. The possible strictly positive return times are exactly the positive multiples of $a+b$. By the definition of the period of a state in a Markov chain as their greatest common divisor,In particular, none of the states is aperiodic.

Fix any two integers $i,j$. By Bézout's identity, there are integers $u,v$ with $au-bv=j-i$. Replacing $(u,v)$ by $(u+kb,v+ka)$ leaves this identity unchanged. Choose $k$ large enough that both entries are nonnegative. A path with $u+kb$ upward steps and $v+ka$ downward steps then takes $i$ to $j$, with strictly positive probability $p^{u+kb}{q}^{v+ka}$. There are no boundary restrictions on this state space.

This applies in both directions, so every pair of states communicates. Hence

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 an integer $c\ge \max \{a,b\}$. On $I=\{-c,\dots ,c\}$, the modified transition matrix $Q=(q_{i,j})$ agrees with $P$. Above $c$, it stays put with probability $a/(a+b)$ and jumps to each of $c-b+1,\dots ,c$ with probability $1/(a+b)$. Below $-c$, it stays put with probability $b/(a+b)$ and jumps to each of $-c,\dots ,-c+a-1$ with probability $1/(a+b)$. All unspecified entries are zero. These rows sum to one. The integer qualification is necessary: if $c$ were nonintegral, $i=\lfloor c\rfloor +1$ would fit none of the printed row conditions.

The restriction $Q_C$ is a finite Markov chain that is an irreducible Markov chain. It is aperiodic, because its upper states have self-transition probability $a/(a+b)>0$, and the period is constant on a communicating class. We now find its stationary distribution.

Every column of $Q_C$ sums to one. Here is the full incoming-mass check, with each total measured in units of $1/(a+b)$. For $j\in L$, the incoming contributions are $a$ from $j+b\in I$ and $b$ from the self-transition. For $j\in U$, they are $b$ from $j-a\in I$ and $a$ from the self-transition.

For $j\in I$, the upward predecessor $j-a$ lies in $I$ exactly when $j\ge -c+a$, contributing $b$ units. When $j\le -c+a-1$, that predecessor is replaced by resets from all $b$ states of $L$, again contributing $b$ units. Independently, the downward predecessor $j+b$ contributes $a$ units when $j\le c-b$; when $j\ge c-b+1$, resets from the $a$ states of $U$ contribute those $a$ units instead. Thus every column total is $a+b$ units.

Therefore $Q_C$ is a doubly stochastic matrix, and the uniform distribution on $C$ is stationary:The countable-state Markov chain convergence theorem, applied to the finite closed class $C$, gives $Q_C^n(i,j)\to {\pi }_j$ for every $i\in C$. Its hypotheses hold: $C$ is finite and irreducible, hence positive recurrent, and it is aperiodic.

If $i_0>c+a$, the hitting time $H$ of $C$ has $\mathbb{P}(H>n)=(a/(a+b){)}^n$. If $i_0<-c-b$, the corresponding tail is $(b/(a+b){)}^n$. Thus $H<\infty$ almost surely from every exterior initial state. Conditioning on $H$ and $R_H$, use convergence within $C$ after entrance and the bounded convergence theorem; equivalently, first restrict to $H\le K$ and then let $K\to \infty$. This proves, for every $i_0\in \mathbb{Z}$,The limiting distribution is independent of $i_0$.

DefineAn interior jump cannot go below $-c-b$ or above $c+a$, and every exterior reset lands in $I$. Thus $C$ is closed.

To prove that it is one communicating class, start anywhere in $C$. From $L$ or $U$, a reset can reach $I$ with positive probability. From any state of $I$, repeated $+a$ steps reach some state of $U$, after staying in $I$ up to the last step. A reset from this state can reach every point of the consecutive blockEvery integer $j\in \{-c-b,\dots ,c\}$ has the form $t-kb$ for some $t\in B$ and an integer $k\ge 0$. Repeated $-b$ steps from $t$ reach $j$, with all departure states in $I$ until a possible last step into $L$. This gives access to all of $I\cup L$. Finally, each $j\in U$ can be reached from $j-a\in I$. Every path described has strictly positive probability. Therefore every state in $C$ reaches every other state in $C$.

Each state outside $C$ can only stay put or reset into $I$, and no transition from $C$ returns to it. Different states outside $C$ cannot reach one another. Hence the complete list of communicating classes isThe finite class $C$ is the unique closed communicating class. The exterior singleton classes are transient communicating classes, since their self-transition probabilities are strictly less than one. Notice that this reachability proof does not require $a,b$ to be coprime.

Let $d=\gcd (a,b)>1$ and put $a^{\prime }=a/d$, $b^{\prime }=b/d$. Then $a^{\prime },b^{\prime }$ are coprime integers, and $p=b^{\prime }/(a^{\prime }+b^{\prime })$. The six requested revisions are as follows.

(b)(i): communicating classes. Every increment is divisible by $d$, so the residue class modulo $d$ is preserved. Conversely, if $j-i$ is divisible by $d$, Bézout's identity applied to $a^{\prime },b^{\prime }$ gives a path just as in (b)(i). Thus the original Markov chain is reducible on $\mathbb{Z}$, with exactly the $d$ closed communicating classesThe specified walk starting at zero stays in $d\mathbb{Z}$.

(b)(ii): period of a state in a Markov chain. The return equation $au=bv$ reduces to $a^{\prime }u=b^{\prime }v$. Hence $u=b^{\prime }k$, $v=a^{\prime }k$. For every state, the period of a state in a Markov chain is thereforeThis is still at least two, so no state is aperiodic.

(b)(iii): stationary distribution. The conclusion is unchanged: there is no stationary distribution on $\mathbb{Z}$. The maximum-mass proof in (b)(iii) applies verbatim, without using coprimality. Equivalently, each closed communicating class, after translating and dividing its state labels by $d$, is the same centered random walk with step sizes $a^{\prime },-b^{\prime }$ and has no stationary distribution.

(b)(iv): occupation of zero. On $d\mathbb{Z}$, the rescaled walk $S_n/d$ has exactly the transition probabilities of the coprime walk with parameters $a^{\prime },b^{\prime }$. The return-probability argument in (b)(iv) therefore makes this class null recurrent. The renewal process proof of the occupation limit applies unchanged:Starting in another residue class would make every visit to zero impossible, also giving occupation proportion zero.

(c)(i): modified communicating classes. These are unchanged: $C=\{-c-b,\dots ,c+a\}$ is one finite closed communicating class, and all other states are transient singleton classes. The original proof used consecutive reset destinations and never used coprimality. Resetting to the $b$ consecutive integers $c-b+1,\dots ,c$ connects different residue classes, so it would be incorrect to split $C$ according to residue classes modulo $d$.

(c)(ii): limiting distribution. The column-sum calculation, the irreducible Markov chain property on a finite class, positive self-transition probabilities, and geometric entrance argument also required no coprimality. Thus for every initial state the same convergence in distribution holds:In particular, the denominator $2c+a+b+1$ is unchanged; it is not divided by $d$.

The strong law of large numbers states that, for independent and identically distributed random variables $X_1,X_2,\dots$ with $\mathbb{E}|X_1|<\infty$,Thus, outside an event of probability zero, the sample mean converges to the common expected value.

For a Borel set $A\subseteq \mathbb{R}$, the joint probability density givesFor each $x\ne 0$, substitute $z=xy$. The change of variables for probability densities contributes $dy=dz/|x|$, with the absolute value accounting for the reversed orientation when $x<0$. The line $x=0$ has two-dimensional Lebesgue measure zero, so omitting it changes no probability. By the Tonelli theorem,The bracket is nonnegative and its integral over $\mathbb{R}$ is one. This proves the probability density of a product of random variables formula:As usual, a probability density function is determined only almost everywhere; exceptional infinite values are harmless.

For the independent random variables with the specified uniform distribution, $f(x,y)=b^{-2}$ on $(0,b{)}^2$ and zero elsewhere. When $0<z<b^2$, the conditions $0<x<b$ and $0<z/x<b$ are equivalent to $z/b<x<b$. ThereforeThe value assigned at zero is arbitrary. Substitution $s=z/b^2$ checks normalization of a probability distribution: ${\int }_0^1-\log sds=1$. This is the product of independent uniform random variables law.

If $0<b\le 1$, then $0<U_j\le 1$ almost surely. Intersecting these events over all $j$ still gives an event of probability one. On it, $0\le W_{n+1}\le W_n$, so the products have a finite nonnegative limit $W_{\infty }$.

For every $\epsilon >0$, the inclusion $\{W_{\infty }>\epsilon \}\subseteq \{W_n>\epsilon \}$ and part (c)(i) imply $\mathbb{P}(W_{\infty }>\epsilon )=0$. Taking $\epsilon =1/m$ for positive integers $m$ proves $W_{\infty }=0$ almost surely. ThusThe monotonicity is the extra ingredient that upgrades convergence in probability to almost sure convergence here.

Every step changes the population by one, so $X_n$ has the parity of $n$ when $X_0=0$. Hence $\mathbb{P}(X_{2m+1}=0)=0$. A return in two steps has positive probability from every state, and all return times are even, so the period of a state in a Markov chain is exactly two.

Each transition exchanges the even and odd classes. Since $\pi$ is an invariant distribution, their masses are equal: $\pi (\text{even})=\pi (\text{odd})=1/2$. The chain sampled at times $2m$, restricted to the even states, is irreducible and positive recurrent, and it is aperiodic because its diagonal entries are positive. Its stationary distribution is $2{\pi }_k$ on even $k$. The countable-state Markov chain convergence theorem applied to this sampled chain yieldsSince ${\pi }_0>0$, the full sequence has no limit. Its time average nevertheless tends to ${\pi }_0$ by the countable-state Markov chain ergodic theorem.

Write $A=g(X)$ and $B=g(Y)$. The two conditional expectation identities supply a $\sigma (Y)$-measurable version of $B$ and a $\sigma (X)$-measurable version of $A$. Work with those versions, which do not change any almost sure equality. Both lie in L2 space, and the Cauchy-Schwarz inequality makes their product an integrable random variable.

Testing the first conditional expectation identity against $B$, and the second against $A$, givesFor completeness, these tests with unbounded multipliers are valid by first using the bounded truncations $B_m=(-m)\vee (B\wedge m)$ and $A_m=(-m)\vee (A\wedge m)$, then passing to the limit with the Cauchy-Schwarz inequality and convergence in L2. Consequently,A nonnegative random variable with zero expected value vanishes almost surely. Therefore $g(X)=g(Y)$ almost surely. This is mutual conditional expectation rigidity in L2; it also follows from the equality case for conditional second moments.

For a counterexample to equality of the original random variables, let $X$ give probability $1/4$ to each of $-2,-1,1,2$, set $Y=-X$, and use the nonconstant function $g(t)=t^2$. Then $g(X)=g(Y)=X^2$ takes both values $1$ and $4$. It is measurable with respect to both generated sigma-algebras, so both required conditional expectation identities hold. Symmetry gives $\mathbb{E}X=\mathbb{E}Y=0$, while neither random variable can be zero. Thus

Retain the binary random variables $B_j=1_{\{U_j\le X_{j-1}\}}$. Iterating the recursion givesEach binary history determines the full vector $(X_0,\dots ,X_n)$, so its sigma-algebra is finite by the sigma-algebra of a finite-valued random vector. Conversely, because $0<x<1$, the integer $2^n{X}_n-x$ uniquely determines the digits $B_1,\dots ,B_n$; also $B_j=2X_j-X_{j-1}$. ThusAll $2^n$ binary histories have positive probability. By independence of the driving uniform random variables, along a fixed finite history every intermediate state is in $(0,1)$, so each subsequent conditional branch probability, either $X_{j-1}$ or $1-X_{j-1}$, is strictly positive. It follows that ${\mathcal{F}}_n^X$ has $2^n$ nonempty fibres, each an atom of a sigma-algebra, and exactly $2^{2^n}$ elements.

Adaptedness from the preceding part gives ${\mathcal{F}}_n^X\subseteq {\mathcal{F}}_n$. For $n\ge 1$, however, ${\mathcal{F}}_n$ contains the events $\{U_1\le t\}$ for every $t\in [0,1]$. They have distinct probabilities $t$, so there are infinitely many distinct such events. Consequently the finite sigma-algebra ${\mathcal{F}}_n^X$ cannot equal ${\mathcal{F}}_n$. The inclusion is strict for every $n\ge 1$.

The tail sigma-algebra of this sequence isFor each fixed $r$, the preceding event equality givesEvery event on the right is determined by coordinates with index at least $r$. Therefore $A\in \sigma (X_r,X_{r+1},\dots )$ for every $r$, and $A\in \mathcal{T}$. The random variables $X_n$ are independent, so Kolmogorov's zero–one law applies: every tail event has probability zero or one. Hence $\mathbb{P}(A)\in \{0,1\}$.

The role of independence can also be seen directly. A tail event is independent of each finite initial sigma-algebra $\sigma (X_1,\dots ,X_m)$. The Monotone class theorem extends this independence to $\sigma (X_1,X_2,\dots )$; since $A$ itself lies there, it is independent of itself. Thus $\mathbb{P}(A)=\mathbb{P}(A{)}^2$.^[ref]

For $B_n=\{X_n>a_n\}$, the definition of the common cumulative distribution function givesThe strict exceedance matters here: an atom of a measure at $a_n$ belongs to $\{X_n\le a_n\}$, so it is already included in $F(a_n)$. The events $B_n$ are mutually independent events, since each depends on a separate member of the independent random variables $X_n$.

If ${\sum }_n(1-F(a_n))<\infty$, countable subadditivity gives, for every $N$,Continuity of probability then gives $\mathbb{P}({\mathrm{limsup}}_n{B}_n)=0$. This is the First Borel-Cantelli lemma and does not need independence.

If the series diverges, independence and $1-u\le e^{-u}$ give, for every fixed $N$,Taking $M\to \infty$ shows that the probability of no exceedance after $N$ is zero. A countable union over $N$ shows that finitely many exceedances has probability zero. This is the Second Borel-Cantelli lemma. Together with the preceding event equality, it proves

The optional stopping theorem at a bounded stopping time states that an integrable martingale $Z_n$ satisfies $\mathbb{E}{Z}_T=\mathbb{E}{Z}_0$ whenever $T\le n$ for a fixed finite $n$. Apply this first to $S$ at $T=n\wedge \tau$. The simple symmetric random walk cannot cross an integer endpoint without hitting it, soThe preceding part gives $\tau <\infty$ almost surely, hence $S_{n\wedge \tau }\to S_{\tau }$ almost surely. The constant bound $C=\max \{-a,b\}$ permits the dominated convergence theorem, yielding $\mathbb{E}{S}_{\tau }=0$. Since $S_{\tau }$ is either $a$ or $b$, solving $ap+b(1-p)=0$ gives its full probability distribution:Now letThis counts the visit at time $0$, and excludes the exit time. Apply the same bounded-time optional stopping theorem to $M_n=|S_n|-L_n$. For each $n$ it givesThe visit counts increase to $L_{\tau }$, so monotone convergence applies to the left. Dominated convergence applies to the right using $|S_{n\wedge \tau }|\le C$. Consequently $L_{\tau }$ is an integrable random variable andThis is the origin case of expected occupation before interval exit for a simple symmetric random walk. The argument obtains integrability of the total occupation count before using any unbounded-time optional stopping for $M$, so it does not presuppose the uniform integrability asked about next. The endpoint probabilities also agree with the standard gambler's ruin calculation.^[ref]

For each $n$,since $S_k$ is adapted. This verifies directly that $\tau$ is a stopping time.

Set $d=b-a$. On $\{\tau >md\}$, the random walk is at some integer strictly between $a$ and $b$. If its next $d$ steps are all $+1$, it must hit $b$ within that block. These future steps are independent of ${\mathcal{F}}_{md}$ and have probability $2^{-d}$ of being all $+1$. HenceThe law of total expectation and mathematical induction give the geometric tail bound from a uniform escape probability:Therefore $\mathbb{P}(\tau <\infty )=1$. In fact this also proves $\mathbb{E}\tau \le d{2}^d<\infty$ by grouping the tail-sum formula into blocks of length $d$. No assertion of independence between successive survival events is needed.

For $m\ge 1$, fix signs $x_1,\dots ,x_m$. The constraints $X_j=x_j$ leave exactly two choices for the $(m+1)$ signs $Y_0,\dots ,Y_m$: choose $Y_0$ freely, then set $Y_1=Y_0{x}_1$ and $Y_j=x_{j-1}{x}_j$ for $2\le j\le m$. Each input tuple has probability $2^{-(m+1)}$ by independence. ConsequentlyEvery finite subfamily is a marginal distribution of one such initial segment, so the entire sequence is independent, with fair sign probability distributions.

Using the usual everywhere sign-valued representatives, for every $n\ge 1$ we haveThe right side is measurable with respect to $\sigma (\mathcal{Y},{\mathcal{T}}_n)$. Therefore $Y_0$ is measurable with respect to their intersection $\mathcal{G}$.

Write $\mathcal{T}={\bigcap }_n{\mathcal{T}}_n$. The Kolmogorov zero-one law applies to the independent random variables $(X_n)$, so every event $C\in \mathcal{T}$ has probability zero or one. Also $Y_0$ is independent of $\mathcal{Y}$: this follows first for finite intersections of sign events from the given independence, then for their generated sigma-algebra by part (a).

The sets $D\cap C$ with $D\in \mathcal{Y}$ and $C\in \mathcal{T}$ form a pi-system generating $\mathcal{H}$. If $\mathbb{P}(C)=0$, the event $D\cap C$ has probability zero and is independent of every event in $\sigma (Y_0)$. If $\mathbb{P}(C)=1$, it differs from $D$ by a null set, so the same independence follows from that of $Y_0$ and $\mathcal{Y}$. Another application of part (a) provesIn particular $\mathcal{H}$ cannot contain the nontrivial event $\{Y_0=1\}$, whereas $\mathcal{G}$ does. Thus adjoining a sigma-algebra need not commute with a decreasing intersection.

There is a small version qualification if the assumptions specify only the probability distributions, allowing exceptional values other than signs. Put $q_n=X_n/(Y_1\cdots Y_n)$ when the denominator is nonzero, and $q_n=0$ otherwise. For $k\ge n$, $q_k$ is measurable with respect to $\sigma (\mathcal{Y},{\mathcal{T}}_n)$. The limit superior of $(q_k)$, after scalar clipping to $[-1,1]$, is therefore $\mathcal{G}$-measurable and equals $Y_0$ almost surely. Literal measurability of an arbitrary version of $Y_0$ need not follow without choosing sign-valued representatives or adjoining the ambient null sets. All the independence conclusions are unaffected.