Difference between revisions of "ECE600 F13 Stochastic Convergence mhossain" - Rhea

Revision as of 10:09, 22 November 2013

Random Variables and Signals

Topic 18: Stochastic Convergence

Stochastic Convergence

We will now consider infinite sequences of random variables. We will discuss what it means for such a sequence to converge. This will lead to some very important results: the laws of large numbers and the Central Limit Theorem.

Consider a sequence X $$ _1 $$ ,X $$ _2 $$ ,..., where each X $$ _i $$ is a random variable on (S,F,P). We will call this a random sequence (or a discrete-time random process).

Notation $\qquad$ X $$ _n $$ may refer to either the sequence itself or to the nth element in the sequence. We may also use {X $$ _n $$ } to denote the sequence, or X $$ _n $$ , n ≥ 1.

The sequence X $$ _n $$ maps S to the set of all sequences of real numbers, so for a fixed S, X $_1(\omega)$ ,X $_2(\omega)$ ,... is a sequence of real numbers.

Fig 1: The mapping from the sample space to the reals under X

$ _j $

.

Before looking at convergence, recall the meaning of convergence or a sequence of real numbers.

Definition $\qquad$ A sequence of real numbers x $$ _1 $$ ,x $$ _2 $$ ,... converges to a number x ∈ R if ∀ $\epsilon$ > 0, ∃ an n $_{\epsilon}$ ∈ N such that

|x_n-x|<\epsilon\qquad\forall n\geq n_{\epsilon}

If there is such an x ∈ R, we say

\lim_{n\rightarrow\infty}x_n=x

or

x_n\rightarrow\infty\;\mbox{as}\;n\rightarrow\infty

For a random sequence X $$ _n $$ , the issue of convergence is more complicated since X $$ _n $$ is a function of $\omega$ ∈ S.

First look at a motivating example.

Example $\qquad$ Let X $$ _k $$ = s + W $$ _k $$ , where s ∈ R and W $$ _k $$ is a random sequence with E[W $$ _k $$ ] = 0 ∀k = 1,2,.... W $$ _k $$ can be viewed as a noise sequence if we want to know the value of s.

Let

Y_n=\frac{1}{n}\sum_{k=1}^nX_k

Then, E[Y $$ _n $$ ] = s ∀n. But Y $$ _n $$ is a random variable, so we cannot expect Y $$ _n $$ = s ∀n. However, we intuitively expect Y $$ _n $$ to be a better estimate of s as n increases. Does Y $$ _n $$ → s as n → ∞ ? If so, in what sense?

Types of Convergence

Since X $_n(\omega)$ is generally a different sequence for very $\omega$ ∈ S, what does it mean for X $$ _n $$ to converge? We will discuss different ways in which X $$ _n $$ can converge.

Definition $\qquad$ X $$ _n $$ converges everywhere if the sequence X $_1(\omega)$ ,X $_2(\omega)$ ,... converges to some value X $(\omega)$ ∀ $\omega$ ∈ S. We also call this sure convergence or convergence surely.

Fig 2: Sure Convergence.

Notation

X_n\overset{e}{\rightarrow}X

Definition $\qquad$ X $$ _n $$ converges almost everywhere or almost surely, if X $_n(\omega)$ → for some A ∈ S with P(A) = 1. Also known as convergence with probability 1.

Notation

X_n\overset{a.e.}{\rightarrow}X,\quad X_n\overset{a.s.}{\rightarrow}X,\quad X_n\overset{w.p.1}{\rightarrow}X

Definition $\qquad$ X $$ _n $$ converges in mean square to X if

E\left[|X_n-X|^2\right]\rightarrow 0

as

n\rightarrow\infty

Notation

X_n\overset{ms}{\rightarrow}X

Definition X $$ _n $$ converges in probability to X if ∀ $\epsilon$ > 0

P(|X_n-X|>\epsilon)\rightarrow 0

as

n\rightarrow\infty

Note that P(|X $$ _n $$ - X| > $\epsilon$ ) is a sequence of real numbers.

Notation

X_n\overset{p}{\rightarrow}X

Definition $\qquad$ X $$ _n $$ converges in distribution to X if

F_{X_n}(x)\rightarrow F_X(x)

as

n\rightarrow\infty

Note that for a fixed x ∈ R, F $$ _n $$ (x) is a sequence of real numbers.

Notation

X_n\overset{d}{\rightarrow}X

We will generally assume that if X $$ _n $$ converges in distribution, then

\frac{F_{X_n}(x)}{dx}\rightarrow\frac{F_X(x)}{dx}

or
$f_{X_n}(x)\rightarrow f_X(x)$
as

n\rightarrow\infty

although this is not true in every instance, as seen in the next example.

Example $\qquad$ Let X $$ _n $$ have pdf

f_{X_n}(x) = 1+\cos 2\pi nx\quad0\leq x\leq 1,\;\;n=1,2,...

Then

F_{X_n}(x) = \begin{cases} 0 & x<0 \\ x+\frac{\sin 2\pi nx}{2\pi n} & 0\leq x\leq 1 \\ 1 & x>1 \end{cases}

Now

F_{X_n}(x)\rightarrow F_X(x)

as
$n\rightarrow\infty$

\forall x\in\mathbb R

where

F_X(x)=\begin{cases} 0 & x<0 \\ x & 0\leq x\leq 1 \\ 1 & x>1 \end{cases}

However, f $_{Xn}$ does not converge for x ∈ (0,1).

Cauchy Criterion for Convergence

We will now discuss a method for showing that X $$ _n $$ → X in the mean square sense for some random variables X without knowing what X is. Frist, consider a sequence of real numbers.

Definition If x $$ _n $$ is a sequence of real numbers and

|x_{m+n}-x_n|\rightarrow 0

as

n\rightarrow \infty \quad \forall m>0

then x $$ _n $$ converges iff it is a Cauchy sequence. This is known as the Cauchy criterion for convergence.

The Cauchy Criterion for mean square convergence of X $$ _n $$ $\qquad$

@@ Line 138: / Line 138: @@
 ==Cauchy Criterion for Convergence==
-We will now discuss a method
+We will now discuss a method for showing that X<math>_n</math> → X in the mean square sense for some random variables X without knowing what X is. Frist, consider a sequence of real numbers.
+'''Definition''' If x<math>_n</math> is a sequence of real numbers and <br/>
+<center><math>|x_{m+n}-x_n|\rightarrow 0</math><br/>
+as<br/>
+<math>n\rightarrow \infty \quad \forall m>0</math></center>
+then x<math>_n</math> converges iff it is a Cauchy sequence. This is known as the Cauchy criterion for convergence.
+'''The Cauchy Criterion for mean square convergence of X<math>_n</math>''' <math>\qquad</math>

Difference between revisions of "ECE600 F13 Stochastic Convergence mhossain" - Rhea

Revision as of 10:09, 22 November 2013

Stochastic Convergence

Types of Convergence

Cauchy Criterion for Convergence

Alumni Liaison