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$.

Apply part (i) for every positive integer $K$ and discard the countable union of its exceptional null sets. A sample path bounded below never reaches $-K$ for some such $K$, and must therefore converge to a finite limit of a sequence.

Apply the same argument to the martingale $(-M_n)$. Outside one more null set, every sample path bounded above also converges finitely. Thus a sample path which does not converge finitely must be unbounded in both directions. Each finite initial segment has finite values, so removing any such segment preserves unboundedness. It follows that the limit superior is $+\infty$ and the limit inferior is $-\infty$. ConsequentlyThis proves the bounded-increment martingale convergence-or-oscillation dichotomy; in particular one-sided divergence to infinity is impossible with positive probability.

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.

Yes. The preceding calculation established $\mathbb{E}{L}_{\tau }=-2ab/(b-a)<\infty$. For every $n$, the stopped martingale satisfiesHere $H$ is a single nonnegative integrable random variable that bounds the whole family. Thus, for any $K>0$,The last limit follows from the dominated convergence theorem. This is precisely uniform integrability. It also gives $M_{n\wedge \tau }\to M_{\tau }=|S_{\tau }|-L_{\tau }$ with convergence in L1, and therefore $\mathbb{E}{M}_{\tau }=0$, consistently with the preceding answer. A common bound on the individual expected values alone would not have sufficed; the integrable dominating random variable is what supplies control of every tail.

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.

The filtration is generated by the successive independent random variables $X_k$. Each $S_n$ is adapted, and $|S_n|\le n$ makes it an integrable random variable. Since independence gives $\mathbb{E}[X_{n+1}\mid {\mathcal{F}}_n]=0$,Thus $(S_n)$ is a martingale.

Write the accumulated number of visits to zero asIt is adapted, and $0\le L_n\le n$. Thus $M_n=|S_n|-L_n$ is also adapted and an integrable random variable. For every integer $s$,Conditioning on $S_n$ and using independence of the next step therefore givesThe drift of the absolute value is cancelled exactly by the visit count, so $\mathbb{E}[M_{n+1}-M_n\mid {\mathcal{F}}_n]=0$. Hence both $(S_n)$ and $(M_n)$ are martingales. The latter is the absolute value martingale of a simple symmetric random walk, a discrete Tanaka formula in which visits to zero supply the correction at the corner of the absolute-value function.

Consider the Borel setIts indicator function is nonnegative and measurable, so the Tonelli theorem applies to the product measure, without needing any separate absolute-integrability argument. At a fixed $y\in (a,b]$, its section in the first coordinate is $(a,y]$; outside $(a,b]$ that section is empty. ThereforeThe last equality uses the definition of a cumulative distribution function on the half-closed interval. It retains all point atoms of a measure on the diagonal $x=y$, excludes a possible point atom of a measure at $x=a$, and includes $y=b$, exactly as required by the set $D$. If $a=b$, both sides vanish. This verifies the identity even when the probability measures are not non-atomic measures.^[ref]

The product measure $\mu \otimes \nu$ is the unique probability measure on the sigma-algebra generated by measurable rectangles for whichHere the printed product notation $\mathcal{B}(\mathbb{R})\times \mathcal{B}(\mathbb{R})$ denotes the generated product sigma-algebra, conventionally written $\mathcal{B}(\mathbb{R})\otimes \mathcal{B}(\mathbb{R})$; it is not just the collection of rectangles. On ${\mathbb{R}}^2$ it equals $\mathcal{B}({\mathbb{R}}^2)$: coordinate projections show that rectangles are Borel sets, while open rectangles with rational endpoints give every open set as a countable union and hence generate the Borel sigma-algebra.

Existence is the product measure theorem for finite measures, which are in particular sigma-finite measures. Uniqueness follows because the rectangles form a pi-system generating the product sigma-algebra, and two finite measures agreeing there agree everywhere by the Dynkin lemma.^[ref]

For each integer $m\ge 1$, letIf $D_m$ had $m+1$ distinct members, finite additivity on their disjoint singleton Borel sets would give total measure at least $(m+1)/m>1$, contradicting $\mu (\mathbb{R})=1$. Thus $|D_m|\le m$.

Every positive singleton measure is at least $1/m$ for some sufficiently large $m$. Consequently the set of point atoms of a measure isA countable union of finite sets is at most countable. This proves the claim, including the possibility that the set is empty. The same argument gives the countability of point atoms of a finite measure, with $|D_m|\le m\mu (\mathbb{R})$ in place of $m$.

For $p>1$, the bound $X_k\le 2$ ensures the finite moment $m_p=\mathbb{E}{X}_1^p\le 2^p$. By Jensen's inequality, $m_p\ge (\mathbb{E}{X}_1{)}^p=1$. The process $Z_k=Y_k^p$ is an adapted, nonnegative integrable random variable at each time, and independence givesThus $(Z_k)$ is a submartingale, and $\mathbb{E}{Z}_n=m_p^n$. The Doob maximal inequality for a nonnegative submartingale states that $c\mathbb{P}({\max }_{k\le n}{Z}_k\ge c)\le \mathbb{E}{Z}_n$ for $c>0$. Apply it with $c={\lambda }^p$. Since the power function is increasing on $[0,\infty )$,Combining this with the preceding bound givesThe result is a bound on the running maximum, which is why a maximal inequality for a submartingale, rather than an estimate of the single terminal random variable, is needed.^[ref]

Use the nonnegative martingale $(Y_n)$ and filtration $({\mathcal{H}}_n)$ established above. Fix a finite $n$ and letFor $j<n$, $\{T\le j\}$ is the union of the threshold-crossing events up to $j$, so $T$ is a bounded stopping time. The optional stopping theorem for a martingale at a bounded stopping time gives $\mathbb{E}{Y}_T=\mathbb{E}{Y}_0=1$. On $H$ one has $Y_T\ge \lambda$; on its complement one still has $Y_T\ge 0$. ThereforeOnly a bounded stopping time has been used, so no extra uniform integrability assumption at an unbounded hitting time is implicit. This is also the Doob maximal inequality for a nonnegative submartingale specialized to a mean-one martingale.

The conditions on the cumulative distribution function imply $0<X_n\le 2$ almost surely. With ${\mathcal{H}}_n=\sigma (X_1,\dots ,X_n)$, adjoin $Y_0=1$ and the trivial ${\mathcal{H}}_0$. The random variables $Y_n$ are nonnegative, adapted, and bounded by $2^n$ at each fixed time. Independence and $\mathbb{E}{X}_{n+1}=1$ giveThus this is the product martingale from independent mean-one factors, with $\mathbb{E}{Y}_n=1$. The almost sure supermartingale convergence theorem states that a nonnegative supermartingale converges almost surely to a finite integrable random variable. Applied to this nonnegative martingale, it shows $Y_n\to Y_{\infty }<\infty$ almost surely. Every convergent real sequence is bounded, so ${\sup }_{n\ge 1}{Y}_n<\infty$ almost surely.

The printed maximum can in fact be taken literally here. If $X_1=1$ almost surely, all products equal $1$. Otherwise the strict Jensen equality criterion, applied to the strictly convex function $t\mapsto -\sqrt{t}$ on $(0,\infty )$, gives $q=\mathbb{E}\sqrt{X_1}<1$. Independence yields $\mathbb{E}\sqrt{Y_n}=q^n$. By Markov's inequality, ${\sum }_n\mathbb{P}(Y_n>\epsilon )\le {\epsilon }^{-1/2}{\sum }_n{q}^n<\infty$ for every $\epsilon >0$. The First Borel-Cantelli lemma and the countable choices $\epsilon =1/m$ give $Y_n\to 0$ almost surely. Since $Y_1>0$, a sequence with this limit attains its positive supremum among finitely many initial terms. This is an instance of fractional moment decay of independent mean-one products.

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 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]

Write $B_n=\{X_n>a_n\}$. If $B_n$ occurs, the running maximum at time $n$ exceeds $a_n$, so $B_n\subseteq A_n$ and ${\mathrm{limsup}}_n{B}_n\subseteq A$.

For the reverse inclusion, fix an outcome for which only finitely many $B_n$ occur. Choose $N$ such that $X_m\le a_m$ for every $m\ge N$. The finite prefix has a finite maximum $K={\max }_{1\le m<N}{X}_m$ when $N>1$; there is no prefix to check when $N=1$. Since $a_n\to \infty$, for every sufficiently large $n$ that prefix satisfies $K\le a_n$. For the remaining indices $N\le m\le n$, the nondecreasing thresholds giveThus ${\max }_{m\le n}{X}_m\le a_n$ for every sufficiently large $n$, so only finitely many $A_n$ occur. Taking the contrapositive proves the reverse inclusion, and hence the pointwise event equalityThis exceedance equivalence for increasing thresholds is deterministic. Its proof uses both monotonicity of $a_n$ and divergence to $+\infty$; it does not require independence or identical probability distributions.

For each $N\ge 1$, put $C_N={\bigcup }_{n\ge N}{A}_n$. Closure of a sigma-algebra under countable unions and countable intersections givesThe events $C_N$ decrease to $A$. Continuity of probability from above applies because $\mathbb{P}(C_1)\le 1<\infty$. Also, $A_n\subseteq C_N$ whenever $n\ge N$, soLetting $N\to \infty$ provesThis reverse Fatou inequality for events requires no independence.

The L2-bounded martingale convergence theorem states that a martingale with ${\sup }_n\mathbb{E}|X_n{|}^2<\infty$ converges both almost surely and with convergence in L2 to a square-integrable random variable. Its hypotheses hold because $0<X_n<1$. Thus there is $X_{\infty }\in [0,1]$ almost surely with both kinds of convergence. Alternatively, the martingale convergence theorem gives the almost sure convergence, and the bound $|X_n-X_{\infty }{|}^2\le 1$ gives convergence in L2 by the dominated convergence theorem.^[ref]

The calculation of the conditional expectation of the square is especially informative. The martingale property makes the cross term vanish in the square expansion, soSubtracting this from $\mathbb{E}[X_{n+1}\mid {\mathcal{F}}_n]=X_n$ givesTaking expected values and iterating provesBy bounded convergence theorem, $\mathbb{E}[X_{\infty }(1-X_{\infty })]=0$. The random variable inside this expected value is nonnegative, so it is zero almost surely; on $[0,1]$ this forces $X_{\infty }\in \{0,1\}$. Again by bounded convergence theorem, $\mathbb{E}{X}_{\infty }={\lim }_n\mathbb{E}{X}_n=x$. HenceThis is the Bernoulli polarization martingale with update size $1/2$. It also has an exact mean squared error: the terminal representation $X_n=\mathbb{E}[X_{\infty }\mid {\mathcal{F}}_n]$ and the equality case for conditional second moments give

The adapted process is bounded by $1$, so every $X_n$ is an integrable random variable, indeed a square-integrable random variable. Independence of $U_{n+1}$ from ${\mathcal{F}}_n$ and its continuous uniform distribution giveThis calculation with a random threshold is justified by conditioning on the ${\mathcal{F}}_n$-measurable value of $X_n$: for a fixed $t\in [0,1]$, the Lebesgue integral ${\int }_0^1{1}_{\{u\le t\}}du$ equals $t$. More formally, independence integrates the bounded Borel measurable function $(t,u)\mapsto 1_{\{u\le t\}}$ over its second coordinate. Thereforewhich verifies the martingale property for this filtration.

Since $B_{n+1}^2=B_{n+1}$, the conditional expectation of the squared martingale difference isThe law of total expectation yields $\mathbb{E}[(X_{n+1}-X_n{)}^2]=\frac{1}{4}\mathbb{E}[X_n(1-X_n)]$. In particular, $\mathbb{E}{X}_n=x$ for every $n$.