Line 54: Line 54:
  
 
Since X<math>_n(\omega)</math> is generally a different sequence for very <math>\omega</math> ∈ ''S'', what does it mean for X<math>_n</math> to converge? We will discuss different ways in which X<math>_n</math> can converge.
 
Since X<math>_n(\omega)</math> is generally a different sequence for very <math>\omega</math> ∈ ''S'', what does it mean for X<math>_n</math> to converge? We will discuss different ways in which X<math>_n</math> can converge.
 +
 +
'''Definition''' <math>\qquad</math> X<math>_n</math> '''converges everywhere''' if the sequence X<math>_1(\omega)</math>,X</math>_2(\omega)</math>,... converges to some value X<math>(\omega)</math> ∀<math>\omega</math> ∈ ''S''. We also call this '''sure convergence''' or '''convergence surely'''.
 +
 +
 +
<center>[[Image:fig2_stochastic_convergence.png|350px|thumb|left|Fig 2: Sure Convergence.]]</center>
 +
 +
'''Notation''' <br/>
 +
<center><math>X_n\overset{e}{\rightarrow}X</math></center>
 +
 +
 +
'''Definition''' <math>\qquad</math> X<math>_n</math> '''converges almost everywhere''' or '''almost surely''', if X<math>_n(\omega)</math> → for some A ∈ ''S'' with P(A) = 1. Also known as convergence with probability 1.
 +
 +
'''Notation''' <br/>
 +
<center><math>X_n\overset{a.e.}{\rightarrow}X,\quad X_n\overset{a.s.}{\rightarrow}X,\quad X_n\overset{w.p.1}{\rightarrow}X</math></center>
 +
 +
 +
'''Definition''' <math>\qquad</math> X<math>_n</math> '''converges in mean square''' to X if <br/>
 +
<center><math>E\left[|X_n-X|^2\right]\rightarrow 0</math><br/>
 +
as<br/>
 +
<math>n\rightarrow\infty</math></center>
 +
 +
'''Notation''' <br/>
 +
<center><math>X_n\overset{ms}{\rightarrow}X</math></center>
 +
 +
 +
'''Definition''' X<math>_n</math> '''converges in probability''' to X if ∀<math>\epsilon</math> > 0 <br/>
 +
<center><math>P(|X_n-X|>\epsilon)\rightarrow 0</math>
 +
as<br/>
 +
<math>n\rightarrow\infty</math></center>
 +
Note that P(|X<math>_n</math> - X| > <math>\epsilon</math>) is a sequence of real numbers.
 +
 +
'''Notation'''<br/>
 +
<center><math>X_n\overset{p}{\rightarrow}X</math></center>
 +
 +
 +
'''Definition''' <math>\qquad</math> X<math>_n</math> '''converges  in distribution''' to X if <br/>
 +
<center><math>F_{X_n}(x)\rightarrow F_X(x)</math><br/>
 +
as<br/>
 +
<math>n\rightarrow\infty</math></center>
 +
 +
Note that for a fixed x ∈ '''R''', F<math>_n</math>(x) is a sequence of real numbers.
 +
 +
'''Notation''' <br/>
 +
<center><math>X_n\overset{d}{\rightarrow}X</math></center>
 +
 +
We will generally assume that if X<math>_n</math> converges in distribution, then <br/>
 +
<center><math>\frac{F_{X_n}(x)}{dx}\rightarrow\frac{F_X(x)}{dx}</math><br/>
 +
or<br/>
 +
<math>f_{X_n}(x)\rightarrow f_X(x)</math><br/>
 +
as<br/>
 +
<math>n\rightarrow\infty</math></center>
 +
 +
although this is not true in every instance, as seen in the next example.
 +
 +
'''Example''' <math>\qquad</math> Let X<math>_n</math> have pdf <br/>
 +
<center><math>f_{X_n}(x) = 1+\cos 2\pi nx\quad0\leq x\leq 1,\;\;n=1,2,...</math></center>
 +
 +
Then <br>
 +
<center><math>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}</math></center>
 +
 +
Now <br/>
 +
<center><math>F_{X_n}(x)\rightarrow F_X(x)</math><br/>
 +
as<br/>
 +
<math>n\rightarrow\infty</math><br/>
 +
<math>\forall x\in\mathbb R</math></center>
 +
 +
where <br/>
 +
<center><math>F_X(x)=\begin{cases}
 +
0 & x<0 \\
 +
x & 0\leq x\leq 1 \\
 +
1 & x>1
 +
\end{cases}</math></center>
 +
 +
However, f<math>_{Xn}</math> does not converge for x ∈ (0,1).
 +
 +
 +
----
 +
 +
==Cauchy Criterion for Convergence==
 +
 +
We will now discuss a method

Revision as of 08:12, 22 November 2013

Back to all ECE 600 notes


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</math>_2(\omega)</math>,... 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

Retrieved from "https://www.projectrhea.org/rhea/index.php?title=ECE600_F13_Stochastic_Convergence_mhossain&oldid=60347"
Shortcuts
Help Main Wiki Page Random Page Special Pages Log in
Search

Alumni Liaison

Questions/answers with a recent ECE grad

Ryne Rayburn