An Overview of Vector Spaces

ELL712 Digital Communications

Prof. Shankar Prakriya

Indian Institute of Technology Delhi

August 11, 2015

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Contents

General Motivation
Introduction to Metric Spaces
Introduction to Vector Spaces, Inner Products and Norms -
Hilbert and Banach Spaces
Projections
Geometric Notions for Random Variables

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

General Motivation I

Geometric Notions
In 3D geometry, we are used to notions of unit-length basis
vectors, dimensionality, angle between vectors, dot product,
etc. The need for orthogonal and unit-length basis vectors is
readily apparent (extension to N length vectors).
From DSP, we can see that these notions extend to signals -
we use orthogonal basis signals of unit energy to represent
signals.
In communications, an optimal receiver projects the received
signal on a space spanned by the basis of the modulated
signals - the same geometric notions as with vectors are used.
These notions extend to random variables too, and will play a
pivotal role in statistical signal processing.

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Familiar Notions From Geometry I

3D Geometry
”Basis vectors” î1 , î2 and î3 ”span” any point in 3D, that is
a = a1 î1 + a2 î2 + a3 î3
It is sufficient if basis vectors are linearly independent, that is,
X 3
ak îk = 0 i↵ a1 = a2 = a3 = 0.
k=1
What happens when î1 , î2 and î3 are not independent?
Why do we prefer to use î1 , î2 and î3 to be orthogonal? When
they are orthogonal, the ”Grammian matrix” is diagonal.
When they are of unit length & orthogonal, the ”Grammian
matrix” is an identity matrix.
Notions generalized to vectors of larger dimensions.
Why do we write one vector as the sum of other vectors?

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Familiar Notions From Geometry Contd. I

3D Geometry
”Dot Product” of a = a1 î1 + a2 î2 + a3 î3 and
3
X
b = b1 î1 + b2 î2 + b3 î3 denoted by a.b or ha, bi = ak b k
k=1
ha, bi = ||a|| ||b|| cos(✓) where ✓ is the angle between the
vectors.
Implies that |ha, bi|  ||a|| ||b|| with equality holding only
when a and b are colinear
What is the physical meaning of ||a|| cos(✓)? It is the
component of a along b.
b
What is the physical meaning of a ||a|| cos(✓) ?
||b||

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Familiar Notions From Geometry Contd. I

3D Geometry
With a = a1 î1 + a2 î2 + a3 î3 , what is the vector in the space
spanned by î1 and î2 that is closest to a?
The above is same as ”projection” of a on ”subspace”
spanned by î1 and î2 .
Having an orthogonal basis for the space onto which the
vector is to be projected is useful.
X3
||a||2 = ha, ai = |ak |2 is the squared norm of the vector
k=1
(squared distance from origin).
Is the basis for the space unique? Does the angle between a
and b depend on the choice of basis? Do the length of the
vectors change?

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Metric Spaces I

The notion of metric spaces will be very useful to understand

norms, inner products and other important concepts.
Metric Spaces - Definition
A ”Metric” d: X ⇥ X ! R is a function that measures the
distance between elements in set X.
Properties of a Metric
1 d(x, y ) = d(y , x)
2 d(x, y ) 0
3 d(x, y ) = 0 i↵ x = y
4 d(x, z)  d(x, y ) + d(y , z) triangle inequality
”A metric space (X,d) is a metric d(x,y) together with a set X.”

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Metric Spaces II

Commonly Used Metrics

For M ⇥ 1 vectors x and y
PM
d1 (x, y) = i=1 |xi yi |
⇣P ⌘1
M 2
d2 (x, y) = i=1 |xi yi |2
⇣P ⌘1
M p
dp (x, y) = i=1 |xi yi | p
d1 (x, y) = maxM
i=1 |xi yi |

dp is referred to as ”Minskowski” distance. The metric to use

depends on the application, and ease of use - d2 (.) is used most
often because of its desirable properties. A very large number of
metrics are in use - a list of statistical and other distance measures
can be found in wikipedia for example.

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Metric Spaces III

Examples
A quantizer that maps vector x to x̂ uses d1 (.) or d2 (.)
To measure the distance between binary codewords, one based
on the hamming distance dH can be used:
M
X1
dH (x, y) = xi yi (modulo 2)
i=0

Does it satisfy all the requirements of a metric?

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Metric Spaces IV

Some Other Distance Measures

d(x, y) = max
P i (|xi yi |) Chebyshev
i xi yi
d(x, y) = Cosine correlation
||x||2 ||y||2 (1)
X |xi yi |
d(x, y) = Canberra Are all of them metrics?
|xi + yi |
i

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Metric Spaces V

Signal Representation
In signal representation, d2 (.) is often used (Root mean-squared
error).
The Fourier series representation of

x(t) = sin(2⇡kt/T
⇢ )
sin(2⇡kt/T ) t 6= T /3
y (t) =
3 t = T /3

will be exactly the same! Convergence is in the mean-square sense.

Convergence issues arise in description of the Gibbs Phenomenon

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Vector Spaces I
Linear Vector Space
Linear vector space S over aa set of scalars R is a collection of
vectors, together with additive operation ”+” and a scalar
multiplication ”.” such that:
1 x and y 2 S then x + y 2 S
2 An additive identity 0 such that x + 0 = 0 + x = x.
3 For every x 2 S there is an additive inverse y such that
x+y =0
4 (x + y) + z + x + (y + z)
5 For a and b 2 R, a.x 2 S, (b.x) = (a.b.)x,
(a + b)x = a.x + b.x, a.(x + y) = a.x + a.y
6 There is a mutltiplicative identity ”1” such that 1.x = x, and
a scalar 0 2 R, with 0.x = 0

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Vector Spaces II

Some Definitions
Let S be a vector space. If V ⇢ S is a subset such that V itself is
a space, then V is a subspace of S.
This notion of subspaces will be useful when we deal with Hilbert
Spaces and Projections.

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Vector Spaces III

Signals as vectors
Under some simple assumptions, we can treat signals as
vectors
A signal x(t) can be considered as an infinite-sized vector
Similarly, a sequence x[n] can be consdired to be an infinitely
long vector
Some issues arise with basis signals (convergence etc)
Any inifinte set of basis signals cannot span every possible
signal x(t) - hence the need for Dirichlet conditions in Fourier
Transforms

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Normed Vector Spaces I
Norms
For vector spaces, notions of length is natural.
For any x 2 S, a real valued k x k is a ”norm” is:
1 k x k is real, and 0
2 k x k= 0 I↵ x = 0
3 k cx k= |c| k x k
4 k x + y kk x k + k y k (triangle inequality)

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Normed Vector Spaces II
Common Norms
l1 norm:P Rb
k x k1 = Mi=1 |xi | & k x(t) k1 = a |x(t)|dt

lp norm:
⇣P ⌘1 ⇣R ⌘1
M p p b p
k x kp = i=1 |x i | & k x(t) kp = a |x(t)|p dt

l1 norm:
k x k1 = maxi |xi | & k x(t) k1 = sup[a,b] |x(t)|
All these satisfy all conditions of a norm.
The norm used depends on the application.

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Normed Vector Spaces III

Norms for Matrices

The p th norm of an mxn matrix A:
kAxkp x
k A kp = maxx6=0 kxkp = maxx6=0 k A kxk p
kp

When p = 2, the norm is referred to as the ”spectral norm”

q
k A k2 = H
max (A A)

The Frobenius norm of an mxn matrix

⇣P ⌘1
m Pn
1
2 2
k A kF = i=1 j=1 |aij | = tr (AH A) 2

It can be shown that k A k2  k A kF .

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Normed Vector Spaces IV

Normed Linear Space

A normed linear space is a pair (S, ||.||) - a vector space with a
norm defined.
A space is said to be complete if all points arbitrarily close also lie
within the space. p
Example - the set of rational numbers is not complete since 2 is
not in the space.
A complete normed linear space is referred to as a ”Banach Space”

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Inner Product I
Defintion and Properties
For vector space S with elements R, the inner product h., .i
S ⇥ S ! R satisfies:
1 hx, yi = (hy, xi)⇤
2 hcx, yi = chx, yi
3 hx + y, zi = hx, zi + hy, zi
4 hx, xi = 0 i↵ x = 0, hx, xi > 0

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Inner Product II

Hilbert Space
A complete normed linear space with an inner product (with the
norm being the induced norm) is referred to as a Hilbert Space.
Orthogonal Subspaces Let S be a vector space, and let V and W
be subspaces of S. V and W are orthogonal if every vector in V is
orthogonal to every vector in W.

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Inner Product III
Examples
Rb
For signals hx(t), y (t)i = a x(t)y ⇤ (t)dt
The induced norm is therefore
Rb
k x(t) k2 = hx(t), y (t)i = a |x(t)|2 dt = Ex
A matchedR T filter operation can be written as an inner product
y (T ) = 0 x(⌧ )h(T ⌧ )d⌧ can be thought of as an inner
product hx(t), h(T t)i
P 1
An FIR filter y [n] = M l=0 h[m]x[n M] can be viewed as an
inner product y [n] = hH x[n] = hx[n], hi where
h = [h[0], . . . , h[M 1]]T , and
x[n] = [x[n], x[n 1], . . . , x[n M + 1]]T
For matrices A and B, hA, Bi = tr (BH A)

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Inner Product IV

Projection Theorem
Let S be a Hilbert space, and V a subspace of S. Then for every
vector x 2 S, there exists a unique vector vx 2 V that is closest to
x. ||x vx || is minimized only when x vx is othogonal to V.
This theorem plays a fundamental role in communications,
statistical signal processing and many other areas.

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Inner Product V

Weighted Inner Product

hx, yiW = yH Wx
For the induced norm to be proper, W should be positive
definite
Rb
For signals, hx(t), y (t)iw (t) = a x(t)w (t)y ⇤ (t)dt (what are
the constraints on w (t)?)
In an M-ary communication system with sm being the
coordinates of the mth message signal sm (t), sufficient
statistics are r = sm + n. If noise is colored Gaussian,
likelihood function will be:
1
f (r|s = sm ) ↵ exp( (r sm ) H R 1
(r sm ))
2
where R is the covariance matrix of the noise n.

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Inner Product VI

Cauchy-Schwartz Inequality

|hx, yi|  k x kk y k

with equality i↵ y = ↵x. Defined similarly for signals.Proof...

Using this, the angle between real x and y can be understood:

hx, yi
cos(✓) =
k x k2 k y k2

For complex vectors x and y, we use:

<{hx, yi}
cos(✓) =
k x k2 k y k2

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Inner Product VII

Signals as Points in Space

1 x(t) and y (t) are ”orthogonal” if hx(t), y (t)i = 0
2 Commonly used signal representations use ”orthogonal basis”
3 Fourier series uses e j2⇡kt/T which are orthogonal over
t 2 [0, T ], but of energy T
4 Fourier Transform uses e j!t , t = 1...1
5 sin(!t + ) can be written as the sum of sin(!t) and cos(!t).
What is the angle between sin(!t + ) and cos(!t)?
6 We can consider cos(!t) and sin(!t) as basis for signals of
the form sin(!t + ), which are points in this space

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Inner Product VIII

Signals as Points in Space

1 Similarly, (almost all) periodic signals x(t) can be considered
as points in space spanned by e j2⇡kt/T for k = 1 ldots, 1
2 Similarly, (almost all) aperiodic signals x(t) can be considered
as points in space spanned by e j! 8!
3 The Parsevals theorems should be understood in this context:
Z T
1 P1
|x(t)|2 dt = |ak |2 FS
Z0 1 T Z k= 1
1
1
|x(t)|2 dt = |X (j!)|2 d! FT
1 2⇡ 1

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Inner Product IX
Signals as Points in Space Contd.
1
X 1
X
Let x(t) = ak k (t) and y (t) = bk k (t) where
k= 1 k= 1
{ k (t)} form an orthonormal set.

Z 1 1
X
|x(t)|2 dt = |ak |2 Parsevals
1 k= 1
Z 1 X1
x(t)y ⇤ (t)dt = ak bk⇤ Generalized Parsevals
1 k= 1
Z 1 X1
|x(t) y ⇤ (t)|2 dt = |ak bk | 2
1 k= 1

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Inner Product X
Projections
To perform projections, it is convenient to use a basis for the space
V! The projection of y(t) on space V is
XK
x̃(t) = hy (t), k (t)i k (t).
k=1

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Inner Product XI
Gram-Schmidt (GS) orthogonalization
GS orthognolization procedure is used to generate an orthogonal
basis. Let x1 (t), x2 (t), . . . , xM (t) span the space V.
x1 (t) x1 (t)
Step 1: 1 (t) = =
k x1 (t) k2 Ex
0
0 2 (t)
Step 2: 2 (t) = x2 (t) hx2 (t), 1 (t)i 1 (t), 2 (t) = 0
k 2 (t) k
0
Step 3: 3 (t) = x3 (t) hx3 (t), 1 (t)i 1 (t) hx3 (t), 2 (t)i 2 (t),
0
3 (t)
3 (t) = 0
k 3 (t) k

..
.
..
.

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Inner Product XII
Remarks on GS Orthogonalization
1 The basis is not unique - di↵erent order of signals will result in
di↵erent basis
2 The dimensionality of the space is  M.
3 If k (t) = 0, it means that xk (t) is linearly dependent on
xi (t), i = 1, . . . , k 1.
4 The number of nonzero basis vectors obtained is the
dimensionality of the space.

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Inner Product XIII

Expectation - an Inner Product

The Inner product of real random variables X and Y with joint pdf
fXY (x, y ) is defined as:
RR
hX , Y i = E {XY } = xyfXY (x, y )dxdy

which is a weighted inner product!

All geometric notions discussed so far extend to random variables
with minor change in terminology (cos(✓) will be replaced by ⇢, the
correlation coefficient for example).

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Random Variables I
Random Variables
Random variable X is a mapping from a space S to the real line R
- for every outcome, a real number is generated.

CDF
CDF: F (x) = Pr{X  x}
1 F ( 1) = 0, F (1) = 1
2 F (x) < F (y ) ! x < y (non-decreasing function)
3 F (x + ) = F (x) (right continuous)

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Random Variables II

PDF
dF (X )
PDF: p(X ) =
dx
Z
1 p(x)dx = 1
2 p(x) 0

Expected value of g (X )
Z
E {g (X )} = g (x)p(x)dx

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Random Variables III
Some Definitions
Uncorrelated X and Y are uncorrelated if
E {(X µx )(Y µY )⇤ } = 0 where µX = E {X } and µY = E {Y }

Independent X and Y are independent if

pXY (x, y ) = pX (x)pY (y )

Orthogonal X and Y are orthogonal if E {XY ⇤ } = 0

Variance:
2 = E {(X µX ) 2 }

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Random Variables IV
Expectation - an Inner Product
The Inner product of real random variables X and Y with joint pdf
fXY (x, y ) is defined as:
Z Z
hX , Y i = E {XY } = xyfXY (x, y )dxdy

which is a weighted inner product!

All geometric notions discussed so far extend to random variables
with minor change in terminology (cos(✓) will be replaced by ⇢, the
correlation coefficient for example).

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Gaussian Random Variable and the Q Function I

Gaussian Random Variables

✓ ◆
1 (x µX )2
pX (x) = p exp (N (µX , 2 ))
2⇡ 2 2 2
mean µX and Zvariance 2 .
1
1 2
Q(x) = p e t /2 dt is area underneath the tail of the PDF
2⇡ x
of X with mean 0 and variance 1
If X ⇠ N (µ, 2 ):
✓ ◆
a µ
Pr [X > a] = Q

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Gaussian Random Variable and the Q Function II
Q(x) and its properties
The error function erf(x) and the complementary error function
erfc(x) are defined as:
Z x
2 2
erf(x) = p e t dt
⇡ Z0
1
2 2
erfc(x) = p e t dt
⇡ x

Note that erf(x) is an odd function. Note also

✓ that ◆
1 x
erf(x) + erfc(x) = 1. Clearly, Q(x) = erfc p and
p 2 2
erfc(x) =✓2Q( ◆2x). CDF of the normal random variable is
1 1 x
+ erf p .
2 2 2

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Gaussian Random Variable and the Q Function III
Q(x) - bounds and properties

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Gaussian Random Variable and the Q Function IV
More on Bounds of Q Function
Z 1
1 2
Q(x) = p e t /2
2⇡ Zx 1
1 t t 2 /2
 p e dt
2⇡ x x
1 2
= p e x /2 Using u = t 2 /2
✓ ◆ 2⇡xZ ✓ ◆
1
1 1 1 2
1+ Q(x)  p 1 + 2 e t /2 dt
x2 2⇡ t !
Z 1 x 2
d e t /2
=
x dt t
= e x 2 /2 /x

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Gaussian Random Variable and the Q Function V
Jointly Gaussian Random Variables
x = [X1 , X2 , . . . , Xn ]T where Xi are jointly Gaussian if

1 ⇣ ⌘
px (x) = exp (x m)T C1 (x m) (2)
(2⇡)n/2 |C|1/2

m = E {x}, C = E {(x m)(x m)T } What happens when

C = 2 I and n = 2?
If y = Ax, and x is Gaussian then for any matrix A, y is a Gaussian
random vector..
Uncorrelated Gaussian random variables are independent..

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Gaussian Random Variable and the Q Function VI
Example
Let n(t) be a Gaussian white random process and { k (t)} be a set
of orthonormal functions over the interval (0, T ). Then:
hn(t), k (t)i be a

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Gaussian Random Variable and the Q Function VII

Complex Circular Gaussian Random Variables

Why complex random variables in communications?
Joint CDFs of real and imaginary parts...
If X and Y are jointly Gaussian, uncorrelated, and zero mean, then
Z = X + jY is complex Gaussian and:
✓ 2 ◆
1 x + y2
pZ (z) = exp
2⇡ 2 2 2
✓ 2◆
1 |z|
= exp
2⇡ 2 2 2

If Z is circular, E {Z 2 } = 0 and E {|Z |2 } = 2 2 .

If Z is circular, what is the pdf of Ze j for constant ?
Can Non-Gaussian random variables X and Y cause Z = X + jY
to be circular?

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Common Distributions I

Chi-Square Random Variable

Arises in communications and chi-square tests for goodness of fit.
Chi-square random variable with n degrees of freedom has PDF:
8
< 1 n

n/2 n
x 2 1 exp x
2 2
x >0
p(x) = 2 (n/2)
:
0 x <0

where the Gamma function (x) is defined as:

Z 1
(x) = t x 1 exp( t)dt
0

Note that a Chi-Square random variable X can be written as sum

n
X
of i.i.d Xi ⇠ N 0, 2 : X = Xi
i=1

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Common Distributions II
Properties of Gamma Functions
Z 1
p
(x) = t x 1 exp( t)dt. Clearly, (1) = 1 and (1/2) = ⇡.
0
Also:
(n + 1) = n
8 (n)
⇣n⌘
⇣n ⌘ >
< ! n even and +ve
+1 = p2
2 > ⇡n.(n 2).(n 4)...3.1
: n odd and ve
2(n+1)/2
Figure Source: WIKI

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Common Distributions III
Properties of Gamma Functions
(x) has poles at x = 0, 1, 2.. (all negative integers). Source:
WIKI

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Common Distributions IV
Chi-Square Distribution
Characteristic Function:
✓ ◆n/2
1
(!) = 2
1 2j!

When n = 2m (n even), the CDF of Chi-Square random variable is:

8
> ⇣ x ⌘mX1 1 ⇣ x ⌘k
<
1 exp x >0
F (x) = 2 2 k! 2 2
>
: k=0
0 Otherwise

E {X } = n 2 and Variance 2n 4.

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Common Distributions V
Distributions Contd.
Chi-square random variable with n = 2 degrees of freedom is
EXPONENTIAL:
( 1 ⇣ x ⌘
exp x >0
p(x) = 2 2 2 2 (3)
0 Otherwise

Exponentially distributed random variables arise in analysis of

performance in fading channels.

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Common Distributions VI
Rayleigh Distribution
r ⇣
⇡ ⇡⌘ 2:
Rayleigh PDF with mean and variance 2
2 2
8 ✓ ◆
< x x2
exp x >0
p(x) = 2 2 2
:
8 0 ✓ ◆ Otherwise
< x2
1 exp x >0
F (x) = 2 2
:
0 Otherwise
q
If X1 and X2 are Gaussian, X12 + X22 is Rayleigh.

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Common Distributions VII

Ricean Distribution
If X1 ⇠ N m1 , 2 and X2 ⇠ N m2 , 2 are independent,
q
X12 + X22 is Ricean with:
8 ⇣ sx ⌘ ✓ ◆
< x x2 + s2
I
2 0
exp x >0
p(x) = 2 2 2
:
0 Otherwise
q
where s = m12 + m22 and I0 (x) is the modified Bessel function of
Z 2⇡
the first kind and order zero: I0 (x) = exp(xcos( ))d .
0
K = s 2 /2 2 is the ’Ricean Factor’.

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Bounds I
Chebyshev Inequality
For any random variable X
1
Pr{|X E {X }| k }
k2

Markov Inequality
E {X }
For any positive valued random variable X Pr{X ↵} 
↵
for ↵ > 0

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications

Bounds II
Cherno↵ Bound
⇤ ⇤
Pr{X } = Pr{e vX > e v }  e v E {e v X } =
⇤
e v ⇥X (v ⇤ ), > E {X } for all v > 0,
where ⇥X (v ) is the Moment Generating Function of X . where v ⇤

is solution to:
E {Xe vX } = E {e vX } obtained by di↵erentiating the bound
e v E {e vX } wrt v and equating to zero. Condition > E {X } is
required to ensure that the computed v ⇤ corresponds to a
minimum.

Cherno↵ Bound - Example

For zero mean unit variance Gaussian random variable X ,
2 2
⇥X (v ) = e v /2 . Pr{X > }  e v e v /2 . Di↵erentiating gives
2
v = so that: Pr{X > } = e /2 .

Prof. Shankar Prakriya An Overview of Vector Spaces ELL712 Digital Communications