The strong Markov property of Brownian motion

Brownian motion occupies the intersection of many classes of stochastic processes; as a process it is a Markov, Gaussian and Lévy, as well as being a martingale. One useful property, which in particular begets the reflection principle, is the strong Markov property.

Let B be a Brownian motion on some filtered probability space (\Omega, \mathcal{F},(\mathcal{F}_t)_{t\geq 0},\mathbb{P}). Fix some s>0. By the Markov property, for all t>s, A \in \mathcal{F}, \mathbb{P}[B_t\in A|\mathcal{F}_s]=\mathbb{P}[B_t\in A|\sigma(B_s)].

The strong Markov property essentially lets s be a stopping time instead of a constant. We see this is stronger than the Markov property, because we could just use the constant stopping time T=s.

Strong Markov property of Brownian motion Let T be an \mathcal{F}_t-stopping time. Write B^{(T)}_t = B_{T+t}-B_T. Then B^{(T)} is a Brownian motion started at B_T, independent of \mathcal{F}_T.

Proof First, suppose T<\infty almost surely. It suffices to prove that, for all A \in \mathcal{F}_T, for all k, for all t_1\leq\cdots\leq t_k, for all bounded, continuous F

\mathbb{E}[\mathbf{1}_A F(B^{(T)}_{t_1},\dots,B^{(T)}_{t_k})] = \mathbb{P}[A]\mathbb{E}[F(B_{t_1},\dots,B_{t_k})]

Why? Setting A = \Omega,  gives that B^{(T)} is a Brownian motion. For general A, the above suffices for independence between B^{(T)} and \mathcal{F}_T.

\mathbb{E}[\mathbf{1}_A F(B^{(T)}_{t_1},\dots,B^{(T)}_{t_k})] = \lim_{n\to\infty}\sum_{k=1}^\infty \mathbb{E}[\mathbf{1}_{A\cap (k-1)2^{-n}<T\leq k2^{-n}} F(B^{(k2^{-n})}_{t_1},\dots,B^{(k2^{-n})}_{t_k})], by continuity of F.

So \mathbb{E}[\mathbf{1}_A F(B^{(T)}_{t_1},\dots,B^{(T)}_{t_k})] = \lim_{n\to\infty}\sum_{k=1}^\infty \mathbb{P}[A\cap (k-1)2^{-n}<T\leq k2^{-n}]\mathbb{E}[F(B_{t_1},\dots, B_{t_k})], by the Markov property of B.

Now, if \mathbb{P}[T=\infty]>0, then we repeat the above argument, but with A\cap \{T<\infty\} in place of A.

That’s it.

Posted in Uncategorized | Leave a comment

Doob’s `Forward’ Convergence Theorem

One of the first major results in the theory of discrete-time martingales, due to Doob, is that {\mathcal{L}^1}-bounded supermartingales (and hence {\mathcal{L}^1}-bounded martingales) converge.

Theorem Let X_n be an {\mathcal{L}^1}-bounded supermartingale. Then, a.s., X_\infty:=\lim X_n exists and is finite.

Proof Let {X_n} be an {\mathcal{L}^1}-bounded supermartingale.

The central idea is to consider the number of times the martingale passes upwards through an interval – we call this the number of upcrossings. Fix {a,b\in \mathbb{R}} with {a<b}. Define the number of upcrossings by time {n}{U[a,b]_n}, by:

\displaystyle U[a,b]_n=\sup\{u\in\mathbb{N}:\exists s_1,\dots,s_u,t_1,\dots,t_u\in\mathbb{N} : s_1<t_1<s_2<\cdots <t_u , \forall i \in \{1,\dots, u\} s_i < a, t_i>b\}

Define the process {C} by {C_{n+1}=\mathbf{1}_{C_n=1, X_n\leq b}+\mathbf{1}_{C_n=0,X_n < a}} and C_1=\mathbf{1}_{X_0<a}.

Let {Y_n=(C\bullet X)_n=\sum_{k=1}^nC_k(X_k-X_{k-1})}. Then, since {X} is a supermartingale and {C} is a bounded, previsible, non-negative process, {Y} is a supermartingale.

Then, considering the corresponding picture, we see that {Y_n\geq (b-a)U[a,b]_n - (X-a)_-}, so, since {Y} is a supermartingale, {\mathbb{E}(X-a)_-\geq (b-a)\mathbb{E}U[a,b]_n}.

So {\sup_n\mathbb{E} U[a,b]_n\leq \frac{\mathbb{E}(X-a)_-}{b-a}\leq \frac{|a|+\sup_n\mathbb{E}|X_n|}{b-a}<\infty}.

Let {U[a,b]_\infty=\lim_{n\rightarrow\infty}U[a,b]_n}. {\mathbb E U[a,b]_\infty = \lim_{n\rightarrow\infty} \mathbb EU[a,b]_n} by the monotone convergence theorem. So {\mathbb E U[a,b]_\infty < \infty}, since we have shown that the supremum is finite. In particular {\mathbb P[U[a,b]_\infty=\infty]=0}. So a.s. {X_n} crosses any fixed interval only finitely many times.

Define

\displaystyle A = \{\omega\in\Omega:X_n(\omega) \text{ doesn't converge as } n\rightarrow\infty\} \nonumber \ \ \ \ \

Then

\displaystyle A=\{\omega\in\Omega:\limsup_nX_n(\omega)>\liminf_nX_n(\omega)\} \nonumber \ \ \ \ \

So

\displaystyle A = \cup_{a\in\mathbb{Q}}\cup_{b\in\mathbb{Q},a<b}\Lambda_{a,b} \nonumber \ \ \ \ \

where

\displaystyle \Lambda_{a,b} = \{\omega\in\Omega: \limsup_n X_n(\omega)>b>a>\liminf X_n(\omega)\} \nonumber \ \ \ \ \

But {\mathbb P\Lambda_{a,b}=0}, since {\mathbb P[U[a,b]_\infty=\infty]=0} and \Lambda_{a,b}\subset {U[a,b]_\infty=\infty}, so, by countable additivity, {\mathbb PA=0}. That is, {X_n} converges almost surely to some X_\infty in [-\infty,\infty].

By Fatou’s Lemma, \mathbb E|X_\infty|=\mathbb E(\liminf|X_n|)\leq \liminf \mathbb E(|X_n|)\leq \sup_n \mathbb E(|X_n|)<\infty

So a.s. X_\infty is finite. \square

Posted in Probability | Leave a comment

Existence of random sequences

One of the first goals in constructing the theory of random processes, the foundations of measure theory having been built, is to show that we can often construct random sequences in a useful manner. Otherwise, it would be a rather dry field!

[This post borrows many ideas from Dr Bailleul's Probability Notes.]

Caratheodory’s Extension Theorem, a key piece of abstract machinery in measure theory, allows us to extend a countably additive set function, \mu, on a ring, \mathbf{A}, to a measure on \sigma(\mathbf{A}), the \sigma-algebra generated by \mathbf{A}.

Often, it’s fairly easy to show that a given set is a ring, and that a given function is an additive set function, and the main challenge is to prove \sigma-additivity.

Definition Given measurable spaces (S_n,\mathbf{S_n}), we say a sequence of measures \mu_n on \prod_{i=0}^n is projective if, for all n, \mu_{n+1}(\cdot \times S_{n+1})=\mu_n(\cdot).

Projective sequences are models of discrete-time random processes, with memory.

So, given a projective sequence of probability measures, we’d like to construct a probability on the infinite product \sigma-algebra on \prod_{i\geq 0} S_i, representing our random sequence. Luckily enough, when our spaces are Borel spaces (very common, as we’ll see), we can do just this. Hurrah!

Definition We say a measurable space (S,\mathbf{S}) is Borel if it is isomorphic to a Borel subset of [0,1], with the corresponding \sigma-algebra.

So I suppose I should add…

Definition Analogously to topological spaces, we say that two measure spaces are isomorphic if there is a bijective measurable function between them, with a measurable inverse.

So, the main event, a theorem on the existence of random sequences, by Daniell.

Theorem Let (S_n,\mathbf{S_n}) be a sequence of Borel spaces and let \mu_n be a projective sequence of probability measures on (S_n:n\in \mathbb{N}). Then, there’s a unique probability measure \mathbb{P} on the product \sigma-algebra of \prod_{n\geq 0}S_n, such that, for all n, for all E \in S_0\otimes \cdots\otimes S_n, \mathbb{P}[E\times \prod_{i\geq n+1}S_i] = \mathbb{P}[E].

Proof We are trying to construct a probability measure, so let’s use Caratheodory’s Extension Theorem (for some tasks this can be, and should be, avoided).

Let \mathbf{A}=\cup_{n=0}^\infty \{E\times \prod_{i\geq n+1} S_i: E\in S_1\otimes\cdots\otimes S_n\}.

We can quickly check that \mathbf{A}  is a ring (do it!).

We can quickly check that \mathbf{A} generates the product \sigma-algebra on \prod_{n\geq 0}S_n.

Define \mathbb{P} on \mathbf{A} by \mathbb{P}[E\times \prod_{i\geq n+1} S_i] = \mu_n[E]. This is well-defined since \mu_n is a projective sequence.

We can quickly check that \mathbb{P} is an additive set-function on \mathbf{A}.

So, to use Caratheordory, we need to show \mathbb{P} is \sigma-additive. This constitutes the bulk of the proof. \mathbb{P} is \sigma-additive iff for every decreasing sequence A_n with \cap_n A_n=\emptyset, \lim_{n\to \infty}\mathbb{P}[A_n]=0. So let’s prove the contrapositive.

Suppose A_n is a decreasing sequence of elements of \mathbf{A}, such that \lim_{n\to\infty}\mathbb{P}[A_n]=\delta>0. WLOG, by inserting extra terms if necessary, assume A_n = {E_n\times \prod_{i\geq n+1}S_i}, for some sequence E_n.

\prod_{i=0}^n S_i is a Borel space, so there’s an isomorphism \varphi_n between this and a subset of [0,1]. Let v_n be the image measure of \mu_n by \varphi_n. Fix \epsilon>0. By inner regularity of [0,1] with the Borel \sigma-algebra, we can find a compact set K_n, such that v_n(\varphi(E_n)\backslash K_n)<\epsilon 2^{-n}.

So \mathbb{P}[A_n\backslash \varphi^{-1}_n(K_n)\times \prod_{i\geq n+1}S_i]\leq \epsilon 2^{-n}.

Let V_n = \varphi^{-1}_n(K_n)\times \prod_{i\geq n+1}S_i.

Let W_n = \cap_{i=0}^n V_i. Then \mathbb{P}[A_n\backslash W_n]\leq \epsilon, so if we choose \epsilon<\delta, then \mathbb{P}[W_n]>0 \forall n \in \mathbb{N}. In particular, W_n\neq \emptyset, so we can pick m_n\in W_n.

By compactness of K_n, the sequence formed by the projection of m_1,m_2,\dots onto K_n has a convergent subsequence for each n. So, by a diagonalization argument, we can pass to a sequence whose limit is in W_n for each n. Thus \cap_{n=0}^\infty A_n \neq \emptyset, so we are done. \square

This post has wound up longer than expected, so I’ll stop here.

Posted in Probability | Leave a comment

A (non-empty) perfect set without rational points

When trying to learn an area of maths, counter examples complement proofs. Often they give insight into why we can’t strengthen proofs in a particular direction, or remove particular requirements. They show us what kind of strangeness can occur.

To find: A non-empty perfect set P\subset \mathbb{R} without rational points.

Non-empty perfect sets are uncountable, so it is plausible (but false) that they contain a rational number (if they are non-empty). We know that the Cantor Set is an uncountable perfect set which contains no intervals. This is a good place to start, since the set we’re looking for contains no intervals, since the rationals are dense in \mathbb{R}.

Let R=\mathbb{Q}\cap[0,1]. R is countable, so we can find a bijection, f:\mathbb{N}\rightarrow R, between R and the natural numbers. We want to modify the Cantor set such that it contains no rational numbers. When we want to construct an object which is different from every object in a countable set, a diagonalization argument is often the way to go. Let f(k) have the ternary representation 0.f(k)_1f(k)_2.... Now consider the set P =\{x \in [0,1] | \forall n \in \mathbb{N}, x_n\neq f(n)_n\}. This set contains no rational numbers (since it differs from the nth rational number in the nth digit).

P is non-empty: We can find an element of P that differs from the nth rational in its nth digit (as we do to show that the real numbers are uncountable).

P is closed: Let p be a limit point of P. Then we can find elements of P arbitrarily close to p. So for all k we can find a number in P which shares its first k digits with p (we represent 0.222… as 1). Suppose p is not in P. Then, for some n, p_n=f(n)_n. But we can find an element of P which shares its first n digits with p. Contradiction. Thus P is closed.

Every point in P is a limit point: Let p \in P. Let g_k(p) be p with its kth digit replaced by the element of \{0,1,2\} \backslash \{f(k)_k,p_{k}\}. \forall k \in \mathbb{N}: g_k(p) \in P. |p-g_k(p)|=3^{-k}. So, for all \epsilon >0, we can find p' \neq p \in B_\epsilon(p). Thus p is a limit point of P.

Thus P is a non-empty perfect set containing no rational points.

Posted in Basic Analysis | 3 Comments