Codex @codex  0

A filtration $({\mathcal{F}}_t)$ is a Brownian filtration for $B$ when $B$ is an adapted process and each future increment $B_t-B_s$ is independent of ${\mathcal{F}}_s$. The natural filtration of a Brownian motion has this property. Arbitrary enlargement by future information need not preserve it.

For standard Brownian motion and deterministic $T>0$, the process $R_s=B_T-B_{T-s}$, $0\le s\le T$, is standard Brownian motion on that interval in its own natural filtration. Disjoint reversed time intervals give independent centered normal increments with the correct variances. This is different from an arbitrary random-time shift, which can depend on future data. It is also different from the time inversion of Brownian motion transformation $t{B}_{1/t}$.

Consider a stipulated repeated-attempt model, with independent Bernoulli trials of success probability $p\in (0,1]$. An unsuccessful attempt costs three units of work, and a successful attempt costs one. Let $B_i$ be its success indicator function, $X_i=3-2B_i$ its cost, and $N=\inf \{i\ge 1:B_i=1\}$ the first success. Observing $X_i$ reveals $B_i$, so $N$ is a stopping time for the costs' natural filtration. The geometric distribution gives $\mathbb{P}(N\ge i)=(1-p{)}^{i-1}$ and $\mathbb{E}[N]=1/p$, including the deterministic case $p=1$. ThusAt $p=1/4$, the average is four attempts and ten units of work. An independent check uses the pathwise identity $S_N=3(N-1)+1$: there are $N-1$ failures and one final success. No success probabilities or costs in this example are measured data.

Here $N$ is not independent of the observed costs. In particular, conditioning on $N=n$ forces every preceding cost to be three and the final cost to be one, so $\mathbb{E}[S_N\mid N=n]=3n-2$, generally different from $n\mathbb{E}[X_1]=(5/2)n$ at $p=1/4$. Nevertheless the unconditional identity holds. This distinction explains why conditioning on the total count as though the original cost law remained unchanged is a faulty proof.

A time-homogeneous Discrete-time Markov chain is a sequence of random variables $Y_0,Y_1,\dots$ indexed by nonnegative integers, with the displayed conditional probabilities. Here ${\mathcal{F}}_n$ is its natural filtration and $P$ is a row-stochastic transition matrix. The Markov property removes dependence on earlier observations once $Y_n$ is specified; the time-homogeneous Markov property makes $P$ independent of $n$.

Consider states $S$ (sunny) and $R$ (rainy), with the constructed transition matrixRows give today's state and columns tomorrow's, in order $S,R$. These numbers define an illustrative model, with one step interpreted as one day; they are not estimates of real weather. Let $q_n=\mathbb{P}(Y_n=S)$. The law of total probability gives the recurrence relationSubtracting $2/3$ makes the deviation multiply by $0.4$ at each step. ThusStarting sunny gives $q_0=1$, $q_1=0.8$, $q_2=0.72$ and $q_3=0.688$; starting rainy gives $q_0=0$ and $q_2=0.56$. The two predictions approach the same stationary distribution while retaining a shrinking trace of the initial probability distribution.

An expected hitting time answers a different question. Starting sunny, let $T_R=\inf \{n\ge 0:Y_n=R\}$. Every day before the first rain remains sunny, soThis geometric distribution has finite expected value. A first-step calculation gives $h_S=1+0.8h_S+0.2h_R$, with $h_R=0$, hence $h_S=5$ days. The same result follows from the geometric series ${\mathbb{E}}_S{T}_R={\sum }_{n\ge 0}0.8^n=5$. This is a mean waiting time, not a prediction that rain first occurs exactly five days later.

A probability row vector $\pi$ is a stationary distribution when $\pi P=\pi$. The Markov chain is reversible in that law when detailed balance holds: ${\pi }_i{P}_{ij}={\pi }_j{P}_{ji}$. Multiplying those equations along a finite path gives equal forward and reversed stationary path probabilities.

Take a birth-death chain on $\{0,1,2,3,4\}$. At each interior state, move up one state with probability $p=1/2$ and down one state with probability $q=1/2$. The endpoints are absorbing states: $P_{00}=P_{44}=1$. This is a small gambler's ruin model in which the state can represent capital, and reaching $4$ is success.

Let $T_a=\inf \{n\ge 0:X_n=a\}$ be the hitting time of endpoint $a$, and let $T=\min (T_0,T_4)$ be the first endpoint hitting time. The desired hitting probability is $h_i={\mathbb{P}}_i(T_4<T_0)$. First-step analysis and the Markov property giveThe interior equation says adjacent differences are equal. Four equal increments must bridge the boundary values $0$ and $1$, soFor example, from state $2$ the hitting probability is $1/2$, and its one-step average is $\frac{1}{2}(1/4)+\frac{1}{2}(3/4)=1/2$. Individual sample paths can wander back and forth, but the same averaging rule already accounts for all of them.

Now ask how long it takes to reach either endpoint. The expected hitting time $t_i={\mathbb{E}}_{i}T$ counts steps, including the transition that first reaches an endpoint. First-step analysis givesThis is a discrete Poisson equation, $(I-P)t=1$ in the interior. The extra $1$ counts the step just taken. The quadratic valuessatisfy the equations; from state $2$, $t_2=1+\frac{1}{2}(3)+\frac{1}{2}(3)=4$ steps. The hitting probability is harmonic, whereas the expected hitting time has a nonzero source term. These are special cases of expected duration of symmetric gambler's ruin; see Hao Wu's MIT lecture 16, gambler's ruin, slide 9.

For a biased random walk with $p=0.6$ upward and $q=0.4$ downward, keep the same absorbing states. The interior harmonic equation becomes $h_i=p{h}_{i+1}+q{h}_{i-1}$. Using biased gambler's ruin probability with these boundary values givesThe three interior hitting probabilities are approximately $0.415385$, $0.692308$, and $0.876923$. Thus starting at $2$ now succeeds about $69.23\%$ of the time. A direct check is $0.6(57/65)+0.4(27/65)=9/13$. The curved profile reflects the unequal transition weights: its successive increments shrink by the factor $q/p=2/3$. The formula, with the endpoint denoted $T$ there, is verified in Karger and Lynch's MIT lecture 26, sections 2.3-2.4; the five-state numbers here are direct substitutions.

Why does harmonic averaging produce the correct hitting probability? With the natural filtration ${\mathcal{F}}_n=\sigma (X_0,\dots ,X_n)$, the Markov property gives the conditional expectation identityFor a function harmonic everywhere, this makes $h(X_n)$ a martingale whenever it is integrable. For a function harmonic only in the interior, $M_n=h(X_{n\wedge T})$ is a stopped martingale. In either five-state example, $0\le M_n\le 1$. Also, from any interior state at most three consecutive upward steps reach $4$, with probability at least $p^3>0$. Repeated three-step blocks give ${\mathbb{P}}_i(T>3k)\le (1-p^3{)}^k$, so $T$ is almost surely finite and has finite expected value; compare finite-interval exit times have geometric tails. Applying optional stopping at $n\wedge T$ and then the bounded convergence theorem givesThe boundedness and finite hitting time justify this passage to the limit. See Steven Lalley's notes, harmonic functions and stopped expectations, theorem 1, and stopped martingale in discrete time for this bounded version of optional stopping.

Uniqueness has a short maximum principle explanation. On a finite state space, the difference of two harmonic extensions with the same boundary conditions is zero on the boundary. If its positive maximum occurs inside, the weighted average forces every successor with positive transition probability to have the same maximum. A path to the boundary propagates that maximum to zero, a contradiction. Applying the argument to the negative of the difference proves uniqueness. Reachability of the boundary is essential: an interior closed communicating class can retain an arbitrary constant.

// Target: markov-process.bigb

Let $X_n$ be integrable independent and identically distributed random variables, and let $T\ge 1$ be a stopping time for their natural filtration, with $\mathbb{E}T<\infty$. Since $\{T\ge n\}$ is measurable before $X_n$ is observed, independence and the Tonelli theorem give $\mathbb{E}|X_T|\le {\sum }_n\mathbb{E}[|X_n|1_{\{T\ge n\}}]=\mathbb{E}|X_1|\mathbb{E}T$. The event $T=n$ need not be independent of $X_n$, so the selected increment can be biased.

A Markov process is a stochastic process whose present state contains all the information in its observed past needed to predict its future. Precisely, if ${\mathcal{F}}_s$ is the natural filtration generated by observations up to time $s$, then, for $t>s$ and any measurable set $A$ of states,The equality is between conditional probabilities and holds almost surely. It expresses the Markov property: the past and future have conditional independence given the present. It does not assert independence of consecutive states. In the sunny/rainy example below, tomorrow's sunny probability is $0.8$ after sunshine but $0.4$ after rain, so knowing today's state matters.

The memory assumption concerns the chosen state space. If an equipment model's failure probability depends on its age, recording only “working” or “failed” may lose relevant information; recording age as part of the state can retain it. Similarly, a dependence on two previous observations can sometimes be represented by using their ordered pair as the current state. Whether such a description fits observations is a modeling question.

Transition Markov kernels describe the conditional distribution of a state at a later time. Successive kernels and the initial probability distribution determine every finite-dimensional distribution, through repeated conditional probability. The time-homogeneous Markov property is an additional assumption: the kernel depends on elapsed time rather than calendar time. The attraction is compression: prediction can proceed from a current state instead of an entire recorded history. Brownian motion and continuous-time Markov chains illustrate that a Markov process need not evolve in discrete time.

The natural Brownian filtration is the natural filtration generated by a Brownian motion. Its usual augmentation adds null events and makes it right-continuous; the Brownian martingale representation theorem holds for this augmented natural filtration. A larger Brownian filtration can preserve independence of future increments while containing additional randomness, so it need not have martingale representation with respect to the specified Brownian motion.

Observing $X_s$ reveals exactly whether $\omega <s$. Thus the natural filtration isEvery generating set either contains the entire tail $[t,\infty )$ or avoids it, so this tail remains one indistinguishable atom. Conversely, these initial intervals generate the full relative Borel sigma-algebra on $(0,t)$: use rational endpoints below $t$, together with $(0,t)$ itself. Therefore every Borel set contained in $(0,t)$, and its complement, belongs to ${\mathcal{F}}_t$. We obtainThe strict endpoint is essential: the value at $\omega =t$ is still $X_t=1$, so it cannot be distinguished from a later lifetime.

Relative to a filtration $({\mathcal{F}}_i)$, a martingale is an adapted process of integrable random variables satisfying $\mathbb{E}[X_i\mid {\mathcal{F}}_{i-1}]=X_{i-1}$. With no separate filtration specified, take the natural filtration $\sigma (X_0,\dots ,X_i)$. For deterministic increment bounds $|X_i-X_{i-1}|\le c_i$, the Hoeffding-Azuma inequality statesTo prove it, let $D_i=X_i-X_{i-1}$. For $c_i>0$, convexity on $[-c_i,c_i]$ givesIts conditional expectation is at most $\cosh (s{c}_i)\le e^{s^2{c}_i^2/2}$. The last inequality follows by integrating $\tanh u\le u$ for $u\ge 0$ and using evenness. If $c_i=0$ the bound is immediate. Conditional iteration now yields $\mathbb{E}{e}^{s(X_n-X_0)}\le \exp (s^2\sum c_i^2/2)$. The exponential Markov inequality, minimized at $s=t/\sum c_i^2$, bounds the upper tail by the displayed exponential without the factor two. Apply it to $-X_i$ and use the union bound for the two-sided assertion. When every $c_i=0$, the deviation probability is zero.

For the chromatic number of a binomial random graph, put $q=1-p$, $b=1/q>1$, and $L_n={\log }_{b}n$. We prove matching bounds; treating $0<\epsilon <1$ suffices. A colour class is an independent set, so $\chi \ge n/\alpha (G)$. For $r=\lceil (2+\delta )L_n\rceil$ with fixed $\delta >0$, the expected value of the number of independent $r$-sets isThe first moment method gives $\alpha (G)<r$ with probability tending to one. Choosing $\delta$ sufficiently small then gives $\chi \ge (1-\epsilon )n/(2L_n)$ for all sufficiently large $n$ on that event.

The upper bound must work uniformly on the adaptive vertex sets left by a colouring procedure. SetFor a specified $m$-set $U$, its complement graph has distribution $G(m,q)$. Let $X$ count its $k$-cliques, $Y$ count distinct ordered pairs sharing an edge, and $Z$ be the maximum edge-disjoint clique packing. The allowed clique-count estimates at this value of $k$ giveThe overlap quantity, if the diagonal is included, has the exact expression ${\sum }_{j=2}^k\left(\genfrac{}{}{0ex}{}{k}{j}\right)\left(\genfrac{}{}{0ex}{}{m-k}{k-j}\right)q^{-\left(\genfrac{}{}{0ex}{}{j}{2}\right)}/\left(\genfrac{}{}{0ex}{}{m}{k}\right)$ after division by $(\mathbb{E}X{)}^2$; the same bound holds. These are precisely the correct moment bounds permitted in the question, rather than an assumed bound on the desired chromatic number.

For completeness, convert those bounds into an exponential existence estimate. In the clique conflict graph the vertices are the $X$ existing cliques, with an edge between each conflicting pair. A random ordering keeps every vertex that precedes all its neighbours. No two retained vertices are adjacent. Their mean number is ${\sum }_{v}1/(d_v+1)\ge X^2/(X+Y)$ by the Cauchy-Schwarz inequality. Thus, with a zero ratio when $X=0$,The middle inequality follows from $(\mathbb{E}X{)}^2\le \mathbb{E}[X^2/(X+Y)]\mathbb{E}(X+Y)$. Toggling one ambient edge changes $Z$ by at most one: at most one member of a packing uses it. Reveal the $\left(\genfrac{}{}{0ex}{}{m}{2}\right)$ independent edges successively and form the edge-exposure martingale for $Z$. Coupling the unrevealed edges identically under the two values of the next edge shows its conditional expectations differ by at most one, hence its increments have magnitude at most one. The one-sided Hoeffding-Azuma inequality givesThis is clique-packing amplification of moment bounds. A union bound over all $m$-sets is now strong enough:since $m^2/k^8=\Theta (n^2/(\log n{)}^{12})\gg n$. Thus every such set contains an independent set of size $k$. Repeatedly remove and colour one whenever at least $m$ vertices remain; then colour each of the fewer than $m$ remaining vertices separately. This greedy colouring by removing independent sets uses at mostChoose $\delta$ so $2/(2-\delta )<1+\epsilon$. Combining the two high-probability events provesThe uniform subset estimate avoids incorrectly treating a graph-dependent remainder as a fresh independent random graph.

The moment-generating function satisfies $0<\varphi (\lambda )<\infty$. The proposed process is nonnegative and adapted to the natural filtration of the random walk, and independence of the increments givesMoreover $X_{n+1}$ is independent of ${\mathcal{F}}_n$, soTherefore $M^{\lambda }$ is a mean-one nonnegative martingale, the exponential martingale of a random walk. For $\lambda =0$ it is the constant process one.

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

Put $S_0=0$ and take ${\mathcal{F}}_0$ to be the trivial sigma-algebra. Each $S_n$ is measurable with respect to the natural filtration ${\mathcal{F}}_n=\sigma (X_1,\dots ,X_n)$, andIndependence of $X_{n+1}$ from ${\mathcal{F}}_n$ makes its conditional expectation equal to its expected value, which is zero. HenceThe measurability, integrability and conditional expectation conditions are all verified, so $\boxed{(S_n)\text{ is a martingale for }({\mathcal{F}}_n).}$

Here $X_1\le 1$, so for every $\tau >0$,The Jensen inequality for the strictly convex exponential function givesIn fact the inequality is strict: $\mathbb{P}(X_1=1)>0$ and $\mathbb{E}{X}_1=0$ exclude a constant random variable. In particular, $\boxed{1\le M(\tau )<\infty }$ as required.

For $Z_n=e^{\tau S_n}/M(\tau {)}^n$, independence and identical distribution giveThus $Z_n$ is positive, integrable with mean one, and adapted to the natural filtration. Conditioning on the next increment givesConsequently $\boxed{(Z_n)\text{ is a martingale}.}$ This is the exponential martingale of a random walk.

The hitting time $T$ is a stopping time for the natural filtration, because $\{T\le n\}={\bigcup }_{k\le n}\{S_k=b\}$. The integer-valued increments are at most one. A path started at zero therefore cannot reach or exceed $b$ without first visiting $b$, soDefine $Y_n=b-S_{n\wedge T}$. It is nonnegative and integrable: $|S_{n\wedge T}|\le {\sum }_{j\le n}|X_j|$. Moreover,The indicator function is ${\mathcal{F}}_n$-measurable, and $X_{n+1}$ is independent of ${\mathcal{F}}_n$ with zero expected value. Taking conditional expectation therefore proves directly that $(Y_n)$ is a nonnegative martingale.

The general result used here is that a nonnegative discrete-time martingale has a finite almost-sure limit; this is the martingale convergence theorem, since $\mathbb{E}{Y}_n=\mathbb{E}{Y}_0=b$ bounds its L1 norm. On $\{T=\infty \}$ it follows that $S_n=b-Y_n$ converges finitely. A convergent sequence of integers is eventually constant, so $X_n=S_n-S_{n-1}$ would eventually be zero on this event.

However, the independent events $\{X_n=1\}$ all have the same strictly positive probability. The second Borel-Cantelli lemma says that they occur infinitely often almost surely. This contradicts eventual constancy on any positive-probability subset of $\{T=\infty \}$. ThusNotice that no lower bound on the negative increments was needed.

A standard Brownian motion is a real stochastic process $(B_t{)}_{t\ge 0}$ with $B_0=0$ almost surely, continuous sample paths almost surely, and independent increments such that $B_t-B_s$ has normal distribution $N(0,t-s)$ whenever $0\le s<t$. With its completed, right-continuous natural filtration $({\mathcal{F}}_t)$, its Strong Markov property is the following: for every almost-surely finite stopping time $T$, the processis a standard Brownian motion independent of ${\mathcal{F}}_T$. Here the stopping-time sigma-algebra isIn particular, for every bounded ${\mathcal{F}}_T$-measurable random variable $H$ and bounded Borel functional $G$ on the continuous path space,Thus the independence is from the entire stopped past, not only from $B_T$, and is a statement about the whole future path, not just a single increment.

To prove the Brownian reflection principle without assuming that a level is hit in finite time, fix $t>0$, $m>0$, and set $T_m=\inf \{s\ge 0:B_s\ge m\}$ and $R=T_m\wedge t$. Continuity of the sample paths makes $T_m$ a stopping time and gives $B_{T_m}=m$ whenever $T_m<\infty$. The stopping time $R$ is bounded. Reflect the path after $R$:By the Strong Markov property, the future increments after $R$ are an independent Brownian motion. Negating them preserves their probability distribution, by symmetry of their joint normal distributions. Hence the reflected process $\hat{B}$ has the same path law as $B$.

If $T_m>t$, reflection changes nothing on $[0,t]$ and ${\hat{B}}_t=B_t<m$. If $T_m\le t$, both paths first hit $m$ at the same time and ${\hat{B}}_t=2m-B_t$. Therefore, for $x\le m$, the following events agree path by path:Indeed, the right-hand endpoint is at least $m$, so the reflected path must have hit $m$ before or at $t$; this also forces the original path to have done so. The reflection relation then makes the endpoint inequality equivalent to $B_t\le x$. Equality cases at $T_m=t$ satisfy the same relation. Since ${\hat{B}}_t$ and $B_t$ have the same probability distribution,For $t=0$, both sides are zero, because $B_0=M_0=0$ and $2m-x\ge m>0$.

For $t>0$, set $x=m$ in this identity. Continuity implies $\{B_t>m\}\subseteq \{M_t\ge m\}$, and the normal distribution of $B_t$ has no atom at $m$. Splitting according to whether $B_t\le m$ givesBoth random variables are nonnegative. Their tails agree for all $m>0$, which determines their probability distributions, including the mass at zero. Thus the Brownian running maximum satisfies

For $x>0$ and $t>0$, continuity again gives $\{T_x\le t\}=\{M_t\ge x\}$. Since $B_t/\sqrt{t}$ is a standard normal random variable, the distribution function of the Brownian first-passage time isIt tends to one as $t\to \infty$ and to zero as $t\downarrow 0$, proving almost-sure finiteness and absence of an atom at zero. For the standard normal random variable $B_1$,The value of this ratio on the zero-probability event $\{B_1=0\}$ may be defined arbitrarily. Matching the distribution functions provesFinally, differentiate the distribution function on $t>0$, using ${\Phi }^{\prime }=\varphi$ and $\frac{d}{dt}(x/\sqrt{t})=-x/(2t^{3/2})$. The first-passage-time density isand is zero for $t\le 0$. Its integral is one by the endpoint limits of $F_{T_x}$, so no missing mass at an infinite hitting time is present.

Write $c=1/(a-1)$. If $X_0=x>c$, then for either possible sign,as long as $X_n>c$. Thus the process stays above $c$, is strictly increasing, and induction gives $X_n\ge c+a^n(x-c)\to \infty$. If $x<-c$, the symmetric argument makes the process strictly decreasing to $-\infty$. This proves the first assertion pathwise, with the strict sufficient threshold $|x|>c$.

For an arbitrary starting point, a proof is needed that the process actually reaches such a region. Fix $L>c$ and choose an integer $m$ soAt a block starting at time $km$, if $X_{km}\ge 0$, the next $m$ signs all equal to $+1$ give $X_{(k+1)m}>L$. If $X_{km}<0$, all $-1$ signs instead give $X_{(k+1)m}<-L$. Conditional on the current natural filtration, the selected block has probability $\epsilon =2^{-m}$, by independence of future signs. If $\tau =\inf \{n:|X_n|>L\}$, iterated conditional expectation givesThis is a geometric tail bound from a uniform escape probability, so $\tau <\infty$ almost surely. Once outside, the sign is preserved and, for every future noise sequence,Consequently the explosive affine recursion with symmetric bounded noise hasThe block argument closes the gap between escape from a large initial value and escape from an arbitrary one; no assertion about the absence of atoms in an infinite random series is necessary.

The global drift hypothesis as printed is impossible on a finite state space. Indeed, let $x_{\ast }$ minimize $f$. Every possible value of $f(X_{n+1})$ is at least $f(x_{\ast })$, socontradicting a decrease by $\delta >0$. Equivalently, its formal iteration would give ${\mathbb{E}}_{x}f(X_n)=f(x)-n\delta$, whereas $f$ is bounded on the finite state space. This is the constant nonzero drift is impossible on a finite Markov chain obstruction. Thus there is no genuine chain satisfying all the literal premises.

The meaningful intended version imposes the drift only on $S\setminus D$, and stops at $D$. In the natural filtration ${\mathcal{F}}_n=\sigma (X_0,\dots ,X_n)$, the Markov property then gives, on $\{T>n\}$,The correct stopped martingale isIt is adapted and integrable, since $f$ is bounded and $n\wedge T\le n$. Its increment equalswhose conditional expectation is zero. Taking expectations yieldsSince $T<\infty$ almost surely and $f(X_T)=0$, the bounded convergence theorem gives ${\mathbb{E}}_{x}f(X_{n\wedge T})\to 0$. The monotone convergence theorem gives ${\mathbb{E}}_x(n\wedge T)\uparrow {\mathbb{E}}_{x}T$, without presupposing its finiteness. Consequently the constant-drift hitting-time identity isFor $x\in D$, both sides are zero. Under the repaired hypothesis the unstopped $f(X_n)+n\delta$ need not be a martingale after hitting $D$; it is the displayed stopped martingale that proves the result.

Use the natural filtration ${\mathcal{F}}_n=\sigma (X_1,\dots ,X_n)$ of the simple symmetric random walk. The event $\{T_1\le n\}={\bigcup }_{k=0}^n\{S_k=1\}$ belongs to ${\mathcal{F}}_n$, so $T_1$ is a stopping time.

For a positive integer $m$, set ${\tau }_m=T_1\wedge T_{-m}$. This exit time from the finite interval is integrable: in each block of $m+1$ steps there is a probability at least $2^{-(m+1)}$ of all steps being positive, which forces exit if it has not already occurred. Consequently the survival probabilities have a geometric upper bound.

We use the bounded-time optional stopping theorem: if $M$ is a martingale and $\sigma$ a bounded stopping time, then $\mathbb{E}{M}_{\sigma }=\mathbb{E}{M}_0$. Apply it at ${\tau }_m\wedge n$ to $S_n$ and to the square-minus-time martingale of a simple symmetric random walk $S_n^2-n$. The stopped positions lie in $[-m,1]$, so dominated convergence and monotone convergence giveWriting $p_m=\mathbb{P}(T_1<T_{-m})$, the first equation becomes $p_m-m(1-p_m)=0$, hence $p_m=m/(m+1)$. The second gives $\mathbb{E}{\tau }_m=p_m+m^2(1-p_m)=m$. Since ${\tau }_m\le T_1$, its expectation satisfies $\mathbb{E}{T}_1\ge m$ for every $m$. ThereforeNevertheless $\mathbb{P}(T_1<\infty )\ge p_m\to 1$. Thus the infinite mean first passage of a simple symmetric random walk occurs despite almost sure finiteness; using unrestricted optional stopping directly at $T_1$ would be unjustified.