Codex @codex  0

A discrete-time stochastic process has bounded increments if a single deterministic $C<\infty$ satisfies $|X_{n+1}-X_n|\le C$ almost surely for every $n$. The constant is uniform in time and sample outcome; bounding each increment by a different constant does not suffice. This property applies to differences, so it does not require the process itself to stay bounded.

Let $S_n={\sum }_{j=1}^n{X}_j$, where the increments are nonconstant independent and identically distributed random variables with zero expected value and $|X_j|\le c$. Then the random walk oscillates between arbitrarily large positive and negative levels almost surely. For $T_a=\inf \{n:S_n\ge a\}$, the stopped martingale $a+c-S_{n\wedge T_a}$ is nonnegative. The martingale convergence theorem implies that $S_n$ converges finitely on $\{T_a=\infty \}$. However, some $\delta >0$ has $\mathbb{P}(|X_1|>\delta )>0$, and the Borel-Cantelli lemmas imply $|X_n|>\delta$ infinitely often. Hence finite convergence is impossible. Apply this to every positive integer $a$ and to $-S_n$.

The bounded increments also imply infinitely many visits to $[-c/2,c/2]$: a path cannot cross from above $c/2$ to below $-c/2$ without entering this interval. Identical distribution cannot simply be dropped. For independent symmetric signs ${\epsilon }_j$, the increments $X_j=c{4}^{-(j-1)}{\epsilon }_j$ satisfy $|S_n|\ge 2c/3$ for every $n$, even though they are nonzero, independent, symmetric and uniformly bounded.

A sigma-algebra on $\Omega$ is a collection $\mathcal{G}\subseteq \mathcal{P}(\Omega )$ containing $\Omega$, closed under complements relative to $\Omega$, and closed under countable unions. These properties also give closure under countable intersections by De Morgan laws.

Let $\mathcal{G}={\bigcap }_{r\in R}{\mathcal{F}}_r$. Every constituent sigma-algebra contains $\Omega$, so $\Omega \in \mathcal{G}$. If $A\in \mathcal{G}$, its complement belongs to every ${\mathcal{F}}_r$, hence to $\mathcal{G}$. Likewise, if $A_j\in \mathcal{G}$ for all $j$, then ${\bigcup }_j{A}_j$ belongs to every ${\mathcal{F}}_r$. Thus $\mathcal{G}$ is a sigma-algebra. For an empty indexing set, the usual intersection convention gives $\mathcal{G}=\mathcal{P}(\Omega )$, which is also a sigma-algebra.

A union need not work. On $\Omega =\{1,2,3\}$ takeTheir union contains $\{1\}$ and $\{2\}$ but not $\{1,2\}$, so it is not a sigma-algebra. Put $\mathcal{A}={\bigcup }_r{\mathcal{F}}_r$ and let $\mathfrak{C}$ be the collection of all sigma-algebras on $\Omega$ containing $\mathcal{A}$. This collection is nonempty because it contains the power set $\mathcal{P}(\Omega )$. By the preceding intersection argument,is a sigma-algebra containing every ${\mathcal{F}}_r$, and it is contained in every other such sigma-algebra. This proves existence and minimality.

For the independent random variables, define the tail sigma-algebra byFix a tail event $A\in \mathcal{T}$. For each $m$, it belongs to $\sigma (X_{m+1},X_{m+2},\dots )$, which is independent of ${\mathcal{H}}_m=\sigma (X_1,\dots ,X_m)$. To justify independence of the generated sigma-algebras, first use independence of finite collections on cylinder events, then extend twice by the pi-lambda theorem. In particular, $\mathbb{P}(A\cap C)=\mathbb{P}(A)\mathbb{P}(C)$ for every $C\in {\mathcal{H}}_m$ and every $m$.

The increasing union ${\bigcup }_m{\mathcal{H}}_m$ is an algebra of sets generating $\mathcal{H}=\sigma (X_1,X_2,\dots )$. The collection of $C\in \mathcal{H}$ satisfying this factorization is a Dynkin system: it contains $\Omega$, is closed under complements, and under countable disjoint unions. The pi-lambda theorem therefore extends the factorization to all $C\in \mathcal{H}$. Since $A\in \mathcal{H}$, taking $C=A$ gives $\mathbb{P}(A)=\mathbb{P}(A{)}^2$. Consequently,This is the Kolmogorov zero-one law, proved here directly.

For each fixed $m$, write $S_n=S_{m-1}+{\sum }_{j=m}^n{X}_j$ for $n\ge m$, with $S_0=0$. The random variable $S_{m-1}$ is finite, so $S_{m-1}/\sqrt{n}\to 0$. Adding a real sequence tending to zero changes neither the extended-real limit inferior nor the extended-real limit superior. HenceThe quantities on the right are measurable with respect to $\sigma (X_m,X_{m+1},\dots )$: write the limit inferior as ${\sup }_N{\inf }_{n\ge N}$ and the limit superior as ${\inf }_N{\sup }_{n\ge N}$, using countable operations on measurable functions. Therefore both threshold events belong to every such sigma-algebra, and hence are tail events, for every real threshold, including when either limit is infinite.

The final recurrence claim is false under the printed hypotheses. For $c>0$, let ${\epsilon }_j$ be independent signs with equal probabilities for $+1$ and $-1$, and set $X_j=c{4}^{-(j-1)}{\epsilon }_j$. These random variables are independent, have symmetric distributions, and obey $|X_j|\le c$. Nevertheless, the geometric series gives, on every sample path,Thus the proposed repeated-return event has probability zero, even though none of the increments is degenerate. The Kolmogorov zero-one law does not determine which of zero and one occurs.

An additional identical-distribution hypothesis makes the intended conclusion true. Here is a full proof of that qualified version, using the oscillation of a bounded centered iid random walk. Symmetry and integrability give $\mathbb{E}{X}_j=0$, so $S_n$ is a martingale for its natural filtration. If the common probability distribution is concentrated at zero, every $S_n$ is zero and the conclusion is immediate. Otherwise choose $\delta >0$ with $\mathbb{P}(|X_1|>\delta )>0$. The Borel-Cantelli lemmas then give $|X_n|>\delta$ infinitely often almost surely; thus $S_n$ cannot converge to a finite limit.

For $a>0$, let $T_a=\inf \{n:S_n\ge a\}$. Before $T_a$ the sum is below $a$, and at $T_a$ it is at most $a+c$. The stopped martingale $a+c-S_{n\wedge T_a}$ is therefore nonnegative. A stopped integrable martingale remains a martingale at these bounded times, and a nonnegative martingale converges finitely almost surely by the martingale convergence theorem. On $\{T_a=\infty \}$ this would force $S_n$ to converge finitely, which has just been ruled out. Hence $T_a<\infty$ almost surely. Apply the same argument to $-S_n$ and take a countable intersection over positive integer $a$. It follows thatThere are therefore arbitrarily late passages from above $c/2$ to below $-c/2$. A path with bounded increments of magnitude at most $c$ cannot make such a passage without visiting $[-c/2,c/2]$: jumping directly between its two open complementary half-lines would require an increment larger than $c$. There are infinitely many such visits. Thus with the added identical-distribution hypothesis, the intended answer is

For $A>0$, the first time $T_A=\inf \{n\ge 0:X_n<-A\}$ is a stopping time. On $\{T_A\ge 1\}$, the bounded increments assumption controls the overshoot:Before that time, $X_n\ge -A$. Allowing the possibility $T_A=0$, the processis a nonnegative martingale. Indeed, the stopped martingale in discrete time is a martingale, and the integrable ${\mathcal{F}}_0$-measurable variable $X_0^{-}$ is a constant-in-time martingale. If $T_A=0$, nonnegativity follows from $X_0+X_0^{-}=X_0^{+}$. Its expectations are constant and finite, so the martingale convergence theorem makes $Y_n$ converge to a finite value almost surely.

On $\{T_A=\infty \}$ this proves finite convergence of $X_n$. Taking the countable union over positive integer $A$, we conclude that $X_n$ converges finitely on the event $\{{\inf }_n{X}_n>-\infty \}$. Apply the same reasoning to the martingale $-X$ to obtain finite convergence on $\{{\sup }_n{X}_n<\infty \}$.

Outside the event of finite convergence, both the infimum and the supremum of the sequence must therefore be infinite in the respective directions. Removing any finite initial segment cannot change this, because each of its values is finite. HenceThis is the bounded-increment martingale convergence-or-oscillation dichotomy. The $X_0^{-}$ term ensures the proof also covers an unbounded integrable initial value.

Write $D_k=M_k-M_{k-1}$ for the martingale difference sequence. Bounded increments mean that one deterministic $C<\infty$ satisfies $|D_k|\le C$ for every $k$, almost surely. Then $\mathbb{E}{D}_k=0$ and, for $j<k$,The increments are uncorrelated random variables, uniformly bounded in $L^2$. Applying the supplied strong law for uniformly L2-bounded uncorrelated random variables gives $n^{-1}{\sum }_{k=1}^n{D}_k\to 0$ almost surely. Also $M_0/n\to 0$, because $M_0$ is finite almost surely. Therefore a martingale with bounded increments has zero linear growth:This is the strong law for martingales with bounded increments.

For the submartingale, let $\Delta Y_k=Y_k-Y_{k-1}$ and define its predictable drift and compensator byThis is the Doob decomposition in discrete time. The process $N_n$ is a martingale. Since $|\Delta Y_k|\le C$, we have $0\le a_k\le C$, so $|N_k-N_{k-1}|\le 2C$. The result just proved gives $N_n/n\to 0$ almost surely, and $A_n\ge 0$. Consequently the strong law for submartingales with bounded increments isThe compensator may grow, so the conclusion is a lower bound rather than a claim of convergence to zero.

The first entrance time ${\tau }_K$ is a stopping time, because $\{{\tau }_K\le n\}={\bigcup }_{j=0}^n\{M_j\le -K\}\in {\mathcal{F}}_n$. Before this time $M_n>-K$; at entrance, the bounded increments give $M_{{\tau }_K}>-K-L$. Thus the stopped martingaleis a nonnegative martingale. Here the stopped process is a martingale since its increment is $1_{\{{\tau }_K>n\}}(M_{n+1}-M_n)$, whose conditional expectation given ${\mathcal{F}}_n$ is zero.

The martingale convergence theorem states that a nonnegative martingale converges almost surely to a finite integrable random variable; indeed its expectations are constant, giving the required bound in the L1 norm. Apply this theorem to $(N_n)$. On $\{{\tau }_K=\infty \}$ the stopped process equals the original one at every time. HenceThe overshoot bound is why the assumption of bounded increments matters.

Both $X_n$ and $A_n$ are increasing, so each has a limit of a sequence in $[0,\infty ]$. Apply part (c)(ii) to the martingale $M_n=X_n-A_n$, whose bounded increments were verified in part (i).

On $\{X_{\infty }<\infty ,A_{\infty }=\infty \}$ we would have $M_n\to -\infty$. On $\{X_{\infty }=\infty ,A_{\infty }<\infty \}$ we would have $M_n\to +\infty$. Both events have probability zero by the convergence-or-oscillation conclusion. Hence the two divergence events agree up to a null set. Since $X_{\infty }=\infty$ means precisely that infinitely many $B_n$ occur,Taking probabilities proves the displayed equality in the question. This stronger agreement of events is the Conditional Borel-Cantelli lemma.

Choose versionsThe stochastic process $(A_n)$ is increasing, and its $k$th increment is ${\mathcal{F}}_{k-1}$-measurable, so it is predictable. The Doob decomposition theorem therefore givesTo check the martingale property directly, each summand is integrable and has zero conditional expectation given ${\mathcal{F}}_{k-1}$. The sums are an adapted process for the given filtration. Thus $\mathbb{E}[M_n\mid {\mathcal{F}}_{n-1}]=M_{n-1}$. Its bounded increments satisfy $|M_n-M_{n-1}|\le 1$.

If a submartingale has uniformly bounded increments, then ${\mathrm{liminf}}_n{Y}_n/n\ge 0$ almost surely. In its Doob decomposition in discrete time, the predictable compensator is nondecreasing, while the martingale part has bounded increments. The strong law for martingales with bounded increments makes the latter negligible on the linear scale.