An Epsilon More

The strong Markov property of Brownian motion

Posted on September 7, 2011 by ben

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

Posted on August 16, 2011 by ben

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

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

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

Posted in Probability | Leave a comment

Existence of random sequences

Posted on July 10, 2011 by ben

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

Posted on May 7, 2010 by ben

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 binary 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 $f_k(p)$ be p with its kth digit replaced by $\{0,1,2\} \backslash \{x_{k},p_{k}\}$ . $\forall k \in \mathbb{N}: f_k(p) \in P$ . $|p-f_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.