<< Chapter < Page Chapter >> Page >

Convergence of random variables

We include some background material for the course. Let us recall some notions of convergence of random variables (RV's).

  • A sequence of RV's { x n } n 1 converges in probability if ϵ 0 , lim n sup Pr ( | x n - x ¯ | > ϵ ) = 0 . We denote this by x n P . x ¯ .
  • A sequence of RV's { x n } n 1 converges to x ¯ with probability 1 if Pr { x 1 , x 2 , ... : lim n x n = x ¯ } = 1 . We denote this by x n w . p . 1 x ¯ or x n a . s . x ¯ .
  • A sequence of RV's { x n } n 1 converges to x ¯ in the p sense if E [ | x n - x ¯ | p ] 0 . We denote this by x n p x ¯ .

For example, for p = 2 we have mean square convergence, x n m . s . x ¯ . For p 2 ,

E x n - x ¯ p - 1 = E x n - x ¯ p p - 1 p ( E | x n - x ¯ | p ) p - 1 p .

Therefore, x n p x ¯ yields x n p - 1 x ¯ . Note that for convergence in 1 sense, we have

Pr ( | x n - x ¯ | > ϵ ) E | x n - x ¯ | ϵ 0 .

Typical sequences

The following material appears in most textbooks on information theory (c.f., Cover and Thomas  [link] and references therein). We include the highlights in orderto make these notes self contained, but skip some details and the proofs. Consider a sequence x = x n = ( x 1 , x 2 , . . . , x n ) , where x i α , α is the alphabet, and the cardinality of α is r , i.e., | α | = r .

Definition 1 The type of x consists of the empirical probabilities of symbols in x ,

P x ( a ) = n x ( a ) n , a α ,

where n x ( a ) is the empirical symbol count , which is the the number of times that a α appears in x .

Definition 2 The set of all possible types is defined as P n .

For an alphabet α = { 0 , 1 } we have P n = { ( 0 n , n n ) , ( 1 n , n - 1 n ) , . . . , ( n n , 0 n ) } . In this case, | P n | = n + 1 .

Definition 3 A type class T x contains all x ' α n , such that P x = P x ' ,

T x = T ( P x ) = { x ' α n : P x ' = P x } .

Consider α = 1 , 2 , 3 and x = 11321 . We have n = 5 and the empirical counts are n x = ( 3 , 1 , 1 ) . Therefore, the type is P x = ( 3 5 , 1 5 , 1 5 ) , and the type class T x contains all length-5 sequences with 3 ones, 1 two, and 1 three. That is, T x = { 11123 , 11132 , . . . , 32111 } . It is easy to see that | T x | = 5 ! 3 ! 1 ! 1 ! = 20 .

Theorem 1 The cardinality of the set of all types satisfies | P n | ( n + 1 ) r - 1 .

The proof is simple, and was given in class. We note in passing that this bound is loose, but it is good enough for our discussion.

Next, consider an i.i.d. source with the following prior,

Q ( x ) = i = 1 n Q ( x i ) .

We note in passing that i.i.d. sources are sometimes called memoryless. Let the entropy be

H ( P x ) = - Σ a α n x ( a ) n log n x ( a ) n ,

where we use base-two logarithms throughout. We are studying the entropy H ( P x ) in order to show that it is the fundamental performance limit in lossless compression. Σ find me

We also define the divergence as

D ( P x Q x ) = Σ a α P x log P x Q x .

It is well known that the divergence is non-negative,

D ( P x Q x ) 0 .

Moreover, D ( P Q ) = 0 only if the distributions are identical.

Claim 1 The following relation holds,

Q ( x ) = 2 - n [ H ( P x ) + D ( P x Q ( x ) ) ] .

The derivation is straightforward,

Q ( x ) = Π a α Q ( a ) n x ( a ) = 2 Σ a α n x ( a ) log Q ( a ) = 2 n Σ P x ( a ) ( log Q P + log P ) = 2 - n [ H ( P x ) + D ( P x Q ( x ) ) ] .

Seeing that the divergence is non-negative [link] , and zero only if the distributions are equal,we have Q ( x ) P x ( x ) . When P x = Q the divergence between them is zero, and we have that P x ( x ) = Q x = 2 - n H ( P x ) .

The proof of the following theorem was discussed in class.

Theorem 2 The cardinality of the type class T ( P x ) obeys,

( n + 1 ) - ( r - 1 ) · 2 n H ( P x ) | T ( P x ) | 2 n H ( P x ) .

Having computed the probability of x and cardinality of its type class, we can easily compute the probability of the type class.

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Universal algorithms in signal processing and communications. OpenStax CNX. May 16, 2013 Download for free at http://cnx.org/content/col11524/1.1
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Universal algorithms in signal processing and communications' conversation and receive update notifications?

Ask