Stopping time

A random time $\tau$ is a stopping time when $\{\tau \le n\}\in {\mathcal{F}}_n$ for every $n$.

For independent trials of success probability $p\in (0,1]$, let $T$ be the first index completing two consecutive successes. If $e_0,e_1$ are the mean remaining times with no trailing success and with one trailing success, conditioning gives $e_0=1+(1-p)e_0+p{e}_1$ and $e_1=1+(1-p)e_0$. Solving yields $e_0=(1+p)/p^2$, so fair trials have mean waiting time six. Disjoint pairs give a geometric tail bound and justify finiteness before solving the equations. Overlapping pairs are not independent trials.

The stopped stochastic process follows $X$ until the stopping time $\tau$ and thereafter keeps the value $X_{\tau }$ when $\tau$ is finite. For a pathwise right-continuous adapted process, the stopped process is adapted, by progressive measurability and measurable evaluation at $t\wedge \tau$. When $X$ is a martingale, further stopping and integrability conditions determine whether its stopped process is a martingale.

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.

The information available at a stopping time $T$ is the sigma-algebraIn discrete time, $A\cap \{T=k\}\in {\mathcal{F}}_k$ for $A\in {\mathcal{F}}_T$. A bounded stopping time permits conditional forms of the optional stopping theorem with respect to this sigma-algebra.

If $S\le T$ are stopping times and $A\in {\mathcal{F}}_S$, then $U=S{1}_A+T{1}_{A^c}$ is a stopping time. The key identity isThis uses the ordering $S\le T$: without it, $A$ need not be known when $T$ occurs. Such pastings test the martingale identity through expectations at bounded stopping times.

An announcing sequence consists of stopping times increasing to $T$ almost surely, strictly smaller than $T$ on $\{T>0\}$. Such a lifetime can be approached through stopped intervals on which a locally defined stochastic process is an ordinary adapted process. For the usual maximal local solution of a stochastic differential equation, the exit times ${\tau }_n$ from a nested compact exhaustion of the open domain, capped as $T_n={\tau }_n\wedge n$, supply this sequence. The existence of such a sequence is an extra lifetime convention; arbitrary stopping times need not admit one.

A bounded stopping time is a stopping time bounded almost surely by a deterministic finite constant. In discrete time, a bound $T\le N$ makes $M_T$ integrable whenever $M_0,\dots ,M_N$ are integrable random variables, and the optional stopping theorem applies to a martingale without additional limiting hypotheses. Almost-sure finiteness alone is weaker than boundedness.

Suppose a nonnegative stopping time $T$ and constants $L>0$, $0<q\le 1$ satisfy $\mathbb{P}(T\le nL+L\mid {\mathcal{F}}_{nL})\ge q$ on $\{T>nL\}$. Take $L$ to be a positive integer in discrete time. ThenOn the surviving event, conditional survival is at most $1-q$. The tower property of conditional expectation therefore givesInduction proves the geometric bound. Partitioning the tail integral into intervals of length $L$ then gives $\mathbb{E}T\le L{\sum }_{n\ge 0}\mathbb{P}(T>nL)\le L/q$; in discrete time, group the tail sum into $L$ successive integer indices instead. This proves finite expected hitting times when every surviving state has a uniform positive chance of escaping within a fixed time. It works in discrete or continuous time without assuming independence of successive survival events.

For a random walk with independent and identically distributed increments and an exit time from $(0,r)$, suppose $p=\mathbb{P}(X_1>r/m)>0$ for some integer $m\ge 1$. A block of $m$ such positive increments forces an exit. Conditional on survival, every successive block has success probability at least $p^m$, so $\mathbb{P}(T>km)\le (1-p^m{)}^k$ and $\mathbb{E}T\le m/p^m$. This is an instance of the geometric tail bound from a uniform escape probability; centering of the increments is not required.

Let a fixed word $w$ be sampled from an alphabet of $q$ symbols by independent uniform draws, and let ${\tau }_w$ count draws through its first occurrence. If $B(w)$ is the set of lengths of the borders of a word, including the full length, thenShorter borders contribute because a failed or completed match can retain a suffix that is already a prefix of the next match.

The Skorokhod embedding theorem represents a centered probability distribution $\mu$ on the real numbers with finite variance as $B_T\sim \mu$ for a stopping time $T$ of Brownian motion. One may choose $T$ so that the stopped process $(B_{t\wedge T})$ is uniformly integrable and $\mathbb{E}T=\int x^2\mu (dx)$.

If a random walk has independent identically distributed centered steps of variance ${\sigma }^2<\infty$, there are increasing Brownian stopping times $T_n$ such thatand the increments $T_n-T_{n-1}$ are independent and identically distributed with mean ${\sigma }^2$. Apply the one-step embedding repeatedly using the strong Markov property.

The law of large numbers gives $T_n/n\to {\sigma }^2$. Brownian maximal estimates then showin probability. Since $B_{n{\sigma }^2}/\sqrt{n}\sim N(0,{\sigma }^2)$, the embedded random walk satisfies the central limit theorem.

For a discrete martingale and stopping time $T$,The indicator is measurable at time $n$, so the stopped process is a martingale. If it is uniformly bounded and $T<\infty$ almost surely, bounded convergence gives $\mathbb{E}{M}_T=\mathbb{E}{M}_0$ directly.

For an almost surely finite stopping time $T$, if $\mathbb{E}|M_T|<\infty$ and $\mathbb{E}[|M_n|1_{\{T>n\}}]\to 0$, then $M_{n\wedge T}\to M_T$ with convergence in L1. Thus L1 convergence implies uniform integrability makes the stopped martingale uniformly integrable.

Let an integrable process $(M_n)$ be adapted to $({\mathcal{F}}_n)$. It is a martingale if and only if $\mathbb{E}[M_{n\wedge \tau }]=\mathbb{E}[M_0]$ for every $n$ and every stopping time $\tau$. For the reverse implication, fix $A\in {\mathcal{F}}_n$ and take $\tau =n$ on $A$ and $\tau =n+1$ on $A^c$. Comparing its stopped expectation at $n+1$ with the expectation obtained from the deterministic stopping time $n+1$ gives $\mathbb{E}[1_A(M_{n+1}-M_n)]=0$. Since this holds for every $A\in {\mathcal{F}}_n$, it is exactly $\mathbb{E}[M_{n+1}\mid {\mathcal{F}}_n]=M_n$.

For simple symmetric random walk stopped on hitting $-a$ or $b$ and $0<z<1$, choose $w>1$ byThen $z^n{w}^{\pm X_n}$ are martingales. Solving the two boundary equations gives

For bounded stopping times $\sigma \le \tau$, a supermartingale satisfies $\mathbb{E}[V_{\tau }\mid {\mathcal{F}}_{\sigma }]\le V_{\sigma }$; equality holds for a martingale.

If $e^{-\theta N_{t\wedge {\sigma }_K}}$ is a nonnegative supermartingale, with ${\sigma }_K$ the first time $N_t\le K$, the optional stopping theorem yields ${\mathbb{P}}_N({\sigma }_K<\infty )\le e^{-\theta (N-K)}$. Such a bound can prove escape of a backlog independently of heuristic fluid models.