Applied Proabability and Random Processes

Notes
Prof. Milica Stojanovic
Northeastern University

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Introduction

We think of probability in various ways:

I

intuition
(she will likely marry him)
ratio of favorable to total outcomes
(two dice, chances of sum equal to 9 or more: 10/36. )
frequency of occurrence
(number of left-handed people / total number of people)
lim

n
I

nleft (n)
n

axioms of probability

Why do we need probability? (You know why, but do watch

Rajesh Rao, A Rosetta Stone for the Indus Script.)

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

When is your birthday?

I

In a room of N people, what are the chances of a shared

birthday?

N = 1 : P[1] = 0
N = 2 : P[2] = 1/365
N = 3 : P[3] = 1 (1 1/365)(1 2/365)

P[N] = 1 (1 1/365)(1 2/365) . . . (1 (N 1)/365)

Matlab
Q = 1;
for n = 1 : N 1;
Q = Q (1 n/365);
end;
P = 1 Q; plot(P)

0.9

probability of same birthday (P)

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

10

20

30

40
50
60
number of people (N)

70

80

90

100

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Misuse and misunderstanding

A defendant in a murder trial pleads not guilty to murdering

his wife. He has, however, beaten his wife on numerous
occasions. His lawyer argues that yes, the defendant has
beaten his wife, but among those men who do, only one in a
thousand is a murderer (a measured fact).

Jury is swayed: Beating ones wife is no indicator of being a

murderer. (True, but they should ask a different question.)

Q: Given that a battered wife has been murdered, what is the

probability that the husband is the murderer?

A: 1/2!

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Misuse and misunderstanding

100 women aged 35-50: 4 have breast cancer

100 women aged 45-90: 11 have breast cancer

same, but with mothers who had breast cancer: 22

smokes, lives in California, had two children before 25 and one

after 37, is of Greek origin...

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Experiment, outcome, event; Set; Field

random experiment: more than one possible outcome

(roll a die)

sample space: all possible outcomes (1,2,3,4,5,6)

= {1 , 2 , . . . 6 }

event: subset of the sample space (even, less than 3, etc.)

certain event , null event

A B , A B , A B, A B
sets: A, A,
| {z } | {z }

+(or )

,(and)

partition of A: A1 , A2 , . . . AN , non-overlapping, exhaustive

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Fields

field: collection of subsets in , such that if A1 , A2 F then

A1 , A2 , A1 A2 , A1 A2 F

note: a field is closed (need this for probability)

-field: extension when there are infinitely many subsets

A1 , A2 , . . .:
i=1 Ai , i=1 Ai F (countable)

Borel field: collection of all intervals (open, closed) on the real

line (1-dimensional), or in 2-dimensional space, or 3, etc. (not
countable)

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Axioms of probability (axiom: no proof)

I

P[A]: probability of event A F

1. P[A] 0
2. P[] = 1
3. P[A B] = P[A] + P[B] if A B =

It follows that:
I
I
I

I
I

= 1 P[A], P[] = 0
P[A]

P[A] = P[AB] + P[AB]

P[A B] = P[A] + P[B] P[A B]
B] = P[AB]
+P[B]
proof: P[A B] = P[(AB)
| {z }
P[A]P[AB]
P
P[A B] P[A] + P[B],
P[
A

P[Ai ] (union bound)

i
i
P
PiP
P[A
A
.
.
.
A
]
=
P[A
]
1
2
n
i
1in
1i1 <i2 n P[Ai1 , Ai2 ]+
PPP
P[A
,
A
,
A
]

.
.
.
P[A
i
i
i
1 , A2 , . . . An ]
1
2
3
1i1 <i2 <i3 n

Ex. P[red grapes]=0.8, P[green grapes]=0.7, P[red and green

grapes]= 0.6. P[any grapes]=?
Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Joint and conditional probabilities

I

two events A, B (e.g., warm, rain)

P[A]

Out of the rainy days, how many are warm?

P[A|B] =

nA
n ,

P[B]

nB
n ,

P[A, B]

nA,B
n
nA,B
nB

nA,B /n
nB /n

P[A,B]
P[B]

P[A, B] = P[A]P[B|A]

Independent events: P[A, B] = P[A]P[B] (extension to {Ai })

Are mutually exclusive events independent?

Ex. 30 balls, 10 black (5 light, 5 heavy) and 20 white (10

light, 10 heavy). Draw one. Are the events light and
black independent? P[light, black]=5/30=1/6.
P[light]=(5+10)/30=1/2. P[black]=10/30=1/3.
?

P[light, black] = P[light]P[black]

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Independence of experiments
I

If outcome of one is not affected by the outcome of another

(past, present, future), experiments are independent.

Ex. Biased 0/1 coin, chances of winning (1) are 1/4. Flip coin
once. If unlucky (0), flip again. P[1] =?
7
.
P[1]=P[first=1]+P[first=0]P[second=1]= 14 + 43 14 = 16
Chances of success are greatly increased.

Ex. Three boxes (doors). Two empty, one contains prize. If

you guess correctly, you win. Rule of the game: You make a
first guess. At that point, the dealer (house), who knows
where the prize is, says: I will open one of the two remaining
boxes and show you that it is empty. After he does that, you
have the right to switch your guess (or stick to the original).
Which strategy is better?

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Three boxes: Solution

I

Strategy 1 (stick to original):

P[win]=P[initial guess correct]= 13

Strategy 2 (switch):
P[win]=P[initial correct]0 + P[initial wrong]1 =

2
3

Or you can think like this: Ill toss a coin to decide whether to
switch, with P[switch]=s. Then
P[win]=P[initial correct](1 s) + P[initial wrong]s =
1
2
1
1
3 (1 s) + 3 s = 3 + 3 s

Chances of winning are maximized for s = 1, which

corresponds to Strategy 2.

Draw a probability tree to list all the possibilities: initial guess

correct/wrong; then second guess correct/wrong.

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Beauty contest (apartment hunting)

I

N contestants, all different, appear before a judge one by one

at random. The judge has to make up his mind on the spot,
i.e. at some point he has to say: This is the most beautiful
one. If he does it too early, chances are that the most
beautiful hasnt appeared yet. If he does it to late, chances
are that the most beautiful has already gone by.

Strategy: Let k contestants go by, and mark the most

beautiful. Then wait for the first next that is more beautiful,
and decide in her favor.

What should k be to maximize the probability of correct

guess?

For example: 7, 1, 4 | 5, 9, 6, 10, 8, 2, 3 judge votes for 9

{z
}
| {z } |
k=3

nk=7

(true= 10)
Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Beauty contest: Solution

P[correct guess at k + i]=P[true max is at k + i and current

k
max is among the first k] = n1 k+i1

P[correct
at k + 1 or k + 2 or ...n] =
Pnk 1 guess]=P[correct
k
k Pn1 1
=
=
f (k) find max
i=1 n k+i1
i=k i
n
R
n
k
1
For large n, k, f (k) kn k dx
x = n ln k/n

df (k)/dk = 0 k = n/e N/3

P[correct with best k]

1
e

Prof. Milica Stojanovic

ln e 36%

Applied Proabability and Random ProcessesNotes

Combinatorics

how many ways to put k things into n boxes: nk

3 things (a,b,c) into 2 boxes:
abc+0, ab+c, ac+b, bc+a; 0+abc,c+ab, b+ac, a+bc.

how many k-letter words with n-letter alphabet: nk

3-letter words with 2-letter alphabet (0,1):
000, 001, 010, 011, 100, 101, 110, 111 note (dis)similarity


n!
how many ways to choose k things out of n: kn = k!(nk)!

I
I

how many ways to choose k1 things of kind 1, k2 things of

kind 2, etc. out of n: k1 !kn!2 !... (check: k1 = k, k2 = n k)

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Total probability

I
I

{Ai } mutually exclusive (disjoint); exhaustive, i Ai =

P
P[B] = i P[Ai ]P[B|Ai ]

Ex. binary symmetric channel.

P[e] = P[0]P[e|0] + P[1]P[e|1] = 12  + 12  = .

Ex. N fat people and N skinny people are observed.

Out of the fat (which constitute 80% of population), 90%
drink beer. Out of the skinny, 30%.
Does beer make you fat?

P[F |B] =

P[F ,B]
P[B]

P[F ]P[B|F ]
P[F ]P[B|F ]+P[S]P[B|S]

1
1+

1P[F ] P[B|S]
P[F ] P[B|F ]

12
13

That is a lot! Can it be true?

We dont know the problem is that the majority is fat!

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Bernouli trials
I

binary outcome with probability p

binomial probability
distribution:
P[k out of n] = kn p k (1 p)nk : B(p, n)

Ex. Packet coding. M information-bearing data packets are

encoded into N M. N coded packets are transmitted. It
suffices to receive any M in order to decode the information.
A packet is received in error with probability PE . What is the
probability of successful decoding of the original packets?
Ps = P[M
or more out of N received correctly ] =
P
N
N
m Nm . If I want to achieve a certain P
s
m=M m (1 PE ) PE
for a given M, how should I choose N?

generalized Bernouli:
L possible
P
PLoutcomes with probabilities
p1 , p2 , . . . pL . ( Ll=1 kl = n,
l=1 pl = 1).
n!
P[k1 , k2 , . . . kL out of n] = k1 !...kL ! p1k1 . . . pLkL
Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Useful approximations

I
I
I

When n is large, numerical problems arise when calculating n!.

Stirlings formula: n! 2nnn e n (check it)

Gaussian approximation of binomial:
for np(1 p)  1,
(knp)2


1
2np(1p)
n k
nk p
e
p
(1

p)
k
2np(1 p)
{z
}
|

(check it)

N (np,np(1p))

Cumulative:
R
Pk2 n
k
nk k2 +1/2
k1 k p (1 p)
k1 1/2

Prof. Milica Stojanovic

(xnp)2

1
e 2np(1p) dx
2np(1p)

Applied Proabability and Random ProcessesNotes

Poisson distribution
I

counting process (e.g. photons, server requests,

transportation, bacteria)

K (T ): number of arrivals in T , P{K (T ) = k} =?

Divide T into N small intervals t (so small that they

contain either one or no arrivals, but not two, etc.)

P{1 in t} = t, P{0 in t} = 1 t; t 0


P{k in T } = Nk (t)k (1 t)Nk =
T Nk
T k
N!
=
k!(Nk)! ( N ) (1 N )

k
T /N
1
(1 T /N)N
N(N 1) . . . (N k + 1)
k! |
|
{z
} 1 T /N
{z
}
|
{z
}
e T
N k

(N)

P{K (T ) = k} =

(T )k T
k! e

Prof. Milica Stojanovic

(T )k /N k

: arrival rate (average)

Applied Proabability and Random ProcessesNotes

Useful approximations

T = a (traffic intensity)

compare
Poisson to binomial with n but np = a:

k
same, kn p k (1 p)nk ak! e a

Gaussian approximation of Poisson:

for a  1,
(xa)2
Pk2 ak a R k2 +1/2 1
k1 1/2
e 2a dx
k1 k! e
2a
|
{z
}
N (a,a)

for a = 5, k1 = k2 = k = 5, error is below 1%

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Random variables
I
I
I
I
I
I

Map events into numbers (real), e.g. A X (a1 , a2 ).

Spinning wheel: point of stop X [0, 2] continuous-valued,
or divide into N pizza slices, X {1, 2, . . . N} discrete.
Many are natural: height of a person, lifetime of a light-bulb,
noise amplitude, etc.
cumulative distribution function (cdf): FX (x) = P{X x}
X: random variable, x particular value
properties:
I
I

FX () = 1, FX () = 0
x1 x2 FX (x1 ) FX (x2 )
P{X x2 } = P{X x1 , X (x1 , x2 ]} =
{z
}
|
disjoint events

= P{X x1 } + P{X (x1 , x2 ]}

|
{z
}
0

If FX (x) is discontinuous, the meaning is to the right

FX (x) = lim0 FX (x + ||)
Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Discrete RV: Probability mass function (pmf)

X {x1 , x2 , . . . xN }

PX (xi ) = P{X = xi }, i = 1, . . . N
P
i PX (xi ) = 1

I
I

cumulative:
P
FX (x) = i:xi x PX (xi )

Ex. Spinning wheel with equal pizza slices:

xi = i, i = 1, . . . N,
PX (i) = 1/N, i = 1, . .P
. N (uniform).
FX (k) = P{X k} = ki=1 PX (i) = k/N, k = 1, . . . N

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Continuous RV: Probability density function (pdf)

Spinning wheel: P{X = x} = 0 (infinitely many possibilities)

density: fX (x) =

meaning: P{x < X x + x} x0 fX (x)x

facts:

I
I
I
I

dFX (x)
dx

fX (x) 0R
x
FX (x) = fX ()d
R +
f (x)dx = 1
X
Rx
P{X (x1 , x2 ]} = x12 fX (x)dx = FX (x1 ) FX (x2 )
Z x+x
fX ()d fX (x)x, for x 0
|x
{z
}
FX (x+x)FX (x)

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Common distributions

Uniform X U(a, b)

I

fX (x) =

1
ba ,

x (a, b)
0, otherwise

Gaussian X N (m, 2 )
(xm)

I
I

Rayleigh (e.g. amplitude,

I

1
fX (x) = 2
e 22
1
x
FX (x) = 1 Q( xm
), Q(x) = 2 erfc( 2 ) (Matlab def.)

fX (x) =

x
2 e

2
x2
2

N 2 + N 2)

, x 0

Exponential (Rayleigh squared / power; waiting times)

I

fX (x) = e x , x 0 ( = 1/m)

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Common distributions

Laplacian (e.g. speech, adjacent sample difference)

I
I

fX (x) = c2 e c|x| , c = 2/

P{|X | > k} = e k 2

Chi-square with n degrees of freedom (2n ,

1
I f (x) =
x n/21 e x/2 ,
X
n/2
R2 (n/2)
I () =
1 e d
0
I
I
I

N 2)

x 0 (n = 1 exponential)

( + 1) = () (generalized factorial)
(k) = (k
1)! (integer)
( 21 ) =

Cauchy (N /N )
I

fX (x) =

1 1
1+x 2

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Common distributions

Student-t (Gossett)
I

( n+1
2 )

(1
( n2 ) n

x 2 (n/2+1)
n )

Gamma
I

fX (x) =
fX (x) =

cb
b1 cx
e ,
(b) x

x 0

fX (x) =

(n1 +n2 +1)! n1

x (1
n1 !n2 !

x)n2 , x (0, 1); 0 elsewhere

Beta
I

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Common distributions (discrete RV)

Bernouli
I

Binomial (p, n)
I

n
k

p k (1 p)nk , k = 0, 1, . . . n

PK (k) =

ak a
,
k! e

k = 0, 1, . . .

Geometric
I

PK (k) =

Poisson
I

PX (1) = p, PX (0) = 1 p
fX (x) = (1 p)(x 0) + p(x 1)

PK (k) = p(1 p)k , k = 0, 1, . . .

Mixed RV: continuous and discrete.

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Joint and conditional distributions

P{X x,A}
P{A} ,

whatever the event A might be

FX |A (x|A) =

fX |A (x|A) = X |Adx
P
P
FX (x) = i P{Ai }FX |Ai (x|Ai ), disjoint, i P{Ai } = 1
R +
P{A} = fX (x)P{A|X = x}dx

P{A|X = x} =

dF

(x|A)

P{A}fX |A (x|A)
fX (x)

Prof. Milica Stojanovic

( x
x ; x 0)

Applied Proabability and Random ProcessesNotes

Ex. Which source?

I

A signal X is observed. We know that it comes either from

source S0 or source S1 . The sources are independent, and
each generates a realization of a Gaussian RV with same
variance, but while S0 has zero mean, S1 has a non-zero mean.

X |S0 N (0, 2 )
X |S1 N (m, 2 )

Upon observing a particular value (realization) X = x, we

compare P{S0 |X = x} and P{S1 |X = x} and decide in favor
of the greater.

P{S0 }fX |S0 (x|S0 )

fX (x)
P{S1 }fX |S1 (x|S1 )
P{S1 |X = x} =
fX (x)
fX |S0 (x|S0 ) > P{S1 }
f (x|S1 ) < P{S0 } . Need to know
X |S1

P{S0 |X = x} =

Prof. Milica Stojanovic

P{S0 }, P{S1 }

Applied Proabability and Random ProcessesNotes

Ex. How long will the lightbulb last?

Two kinds of lightbulbs in closet: regular, with average failure

rate 0 , and long-lasting, with 1 < 0 .

Lifetime of each is exponentially distributed,

fX | (x|) = e x/ , x 0

Fraction of regular lightbulbs in closet p; long-lasting (1 p).

Pick a lightbulb at random (its dark in the closet): What are

the chances it will last longer than x?

fX (x) = pfX | (x|0 ) + (1 p)fX | (x|1 )

R +
P{X > x} = x fX (x)dx = pe 0 x + (1 p)e 1 x

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Photon counting

K : number of photons coming from a source

Coherent laser: f () = ( 0 ), i.e. = 0 = const.

k
PK (k) = (0k!T ) e 0 T

Thermal illumination: f () = 1 e / , 0
R
)k
PK (k) = 0 PK | (k|)d = (1+(T
)k+1
T

= p(1 p)k with p = 1+1T

: geometric distribution
(Bose-Einstein statistics)

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Poisson transform, PK (k) =

I
I

R ak
0

k! e

fA (a)da
k

K Poisson, but with A fA (a), i.e. PK |A (k|a) = ak! e a

We observe many realizations, and measure (estimate) PK (k).
Can we tell how A is distributed?
R
Yes: PK (k) = 0 fA (a)PK |A (k|a)da
R +
P
k
PK (k) = 0 e a fA (a) ak! da | (j)k ;
k=0

k
X
R
P
(ja)
k P (k) = e a f (a)
da =
(j)
K
A
0
0
k!
0
{z
}
|
e ja

X
F[e a fA (a)] e a fA (a) = F 1 [ (j)k PK (k)]
| {z }
g (a)
|0
{z
}
G (j)

We have measured PK (k), so we can compute G (j).

An inverse Fourier transform
yields g (a), and fA (a)
R + Pthen

1
k P (k)]e +ja d
follows. fA (a) = e a 2
(j)
K
k=0

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Joint distributions
I

FXY (x, y ) = P{X x, Y y }

fXY (x, y ) =

If FXY (x, y ) = FX (x)FY (y ), i.e. fXY (x, y ) = fX (x)fY (y ),

X , Y independent.
R +
fX (x) = fXY (x, y )dy : marginal pdf

I
I

2 FXY (x,y )
xy

fXY (x, y ) = fY (y ) fX |Y (x|y )

| {z }

FX |Y (x|y )
x
| {z }
P{X x|Y =y }

I
I

Independent X , Y : fX |Y (x|y ) = fX (x)

R +
R +
fX (x) = fXY (x, y )dy = fX (x)fY |X (y |x)dy =
Z +
fX (x)
fY |X (y |x)dy

|
{z
}
1

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Joint Gaussian pdf

fXY (x, y ) =
1
2X Y

I
I

12

(xmX )
1
[
12
2 2
X

(xmX )(y mY )
(y mY )2
+
]
X Y
2 2
Y

: correlation coefficient, || < 1.

 



x
mX
X2
Let z =
,m=
,C=
mY
X Y
y

Compact representation: fXY (x, y ) =

Y |X N (mY + YX (x mX ), (1
given X = x, Y is Gaussian.

Prof. Milica Stojanovic

X Y
Y2

1
0
1
e 2 (zm) C(zm)
2 det C
2 )Y2 )

Applied Proabability and Random ProcessesNotes

Failure rates
I

X : time of failure of an object

Q: If the object lived till x, what is the chance that it will fail
in the next x? (Presumably proportional to x.)

x+x}
=
P{X x + x|X > x} = P{X >x,X
P{X >x}
f
(x)
X
P{x<X x+x}

x
P{X >x}
1 FX (x)
| {z }
(x)

failure rate (also mortality/intensity/hazard rate)

R FX (c) dFX
Rx
X (x)/dx
(x) = dF
1FX (x) FX (0) 1FX = 0 ()d
Rx

, fX (x) = (x)e

Rx

FX (x) = 1 e

Ex. (x) = , const. fX (x) = e x , x 0, exp.

()d

Prof. Milica Stojanovic

()d

Applied Proabability and Random ProcessesNotes

A useful fact to recall from high-school

R b(t)
d
dt a(t) g (x, t)dx =
d
dt [G (b(t), t) G (a(t), t)] =
db
G dt
G da
G dt
= G
b dt + t dt [ a dt + t dt ] =R
b(t)
db(t)
dg (a(t))
(x,t)
g (b(t), t) dt g (a(t), t) dt + a(t) gt
dx

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Poisson inter-arrival times

(T )k T
k! e

Poisson counting: PK (k) =

X : time between two consecutive arrivals; fX (x) =?

P{X > x} = P{ no arrivals in x} = PK (0) = e x

P{X x} = 1 P{X > x} = 1 e x

fX (x) = e x , x 0: exponential.

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Waiting for the bus...

X : time of arrival.

You have waited for x and the bus hasnt arrived. What are
the chances that it will arrive in the next x? (Presumably
higher for a longer initial wait x?)

P{X x + x|X > x} =

1

e x

P{x<X x+X }
P{X >x}

e x e (x+x)
e x

= P{X x}: does not depend on x!

memoryless process

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Functions of random variables

Many real problems: know fX (x), know function g (); what is

the pdf of Y = g (X )?

Linear function: Y = aX + b, a > 0.

shorthand notation: P{x < X x + x} = P{X (x)}

P{y (y )} = P{x (x)}|y =ax+b

fY (y )y = fX (x)x|y =ax+b
1
fY (y ) = fX (x) dy 1/dx |y =ax+b = fX ( y b
a )a

If a < 0, same reasoning, but now must take care to use

positive y , y = |a|x 0.

1
fY (y ) = fX (x) |dy 1/dx| |y =ax+b = fX ( y b
a ) |a| : this solution is
general, i.e. valid for both positive, negative a.

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Arbitrary function, increasing or decreasing

I

If g () is strictly increasing/decreasing, there is a single

solution x1 = x = g 1 (y ).

Draw a tangent at the point x1 ; its slope is g (x1 );

g (x) = dg (x)/dx = dy /dx, g (x1 ) = g (x)|x=x1 .

P{Y (y )} = P{x (x)}|x=x1 =g 1 (y )

fY (y )|y | = fX (x)|x||x=x1 =g 1 (y )
1
|x=x1 =g 1 (y )
fY (y ) = fX (x) |g (x)|

1
Ex. X N (m, 2 ), Y = e X , fY (y ) = fX (x) |g (x)|
|x=g 1 (y )

y = |{z}
e x , x = ln y ,
|{z}
g (x)

g 1 (y )

dy
dx

= |{z}
e x , g (x)|x=g 1 (y ) = y

1 1
y 2 e
N (m, 2 )

fY (y ) = fX (ln y ) y1 =
log-normal: ln Y

g (x)

Prof. Milica Stojanovic

(ln y m)2
2 2

, y 0

Applied Proabability and Random ProcessesNotes

Transformation into discrete



1, X 0 : P{X 0} = FX (0) = p
+1, X > 0 : P{X > 0} = 1 p
PY (1) = p, PY (+1) = 1 p.
Q: What about limiting amplifier?

Limiter: Y =

Quantizer: If RX (xi1 , xi ], Y = yi , i = 1, . . . N
xi
PY (yi ) = xi1
fX (x)dx
quantization error:
R E = X Y P R xi
distortion: D = e 2 fE (e)de = i xi1
(x yi )2 fX (x)dx
design: choose quantization levels and regions to minimize D
solutions: optimal quantizer, optimal uniform quantizer,
compression (pre-distortion g (X ) followed by uniform
quantizer: optimal g or best one-size-fits-all).
fine uniform quantization:
2
fX (x) fX (yi ), x (yi /2, yI + /2], D
12 .
Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Transformation into uniform (and vice versa)

X fX (x), FX (x) strictly increasing

let Y = g (X ), with g = FX

then fY (y ) =

fX (x) |F 1(x)| |x=F 1 (y )

X
X


=

1, y (0, 1)
0, otherwise
|
{z
}
U (0,1)

FX1 (Y )

and vice versa: if Y U(0, 1), then X =

This recipe can be used to convert a uniformly distributed

random variable (generated by a computer) into a random
variable with a desired pdf.

Prof. Milica Stojanovic

fX (x)

Applied Proabability and Random ProcessesNotes

Arbitrary function, multiple roots

I

Y = g (X ); multiple solutions to x = g 1 (y ): x1 , x2 , . . .

P{y y } = P{x (x1 )} + P{x (x2 )} + . . .

P
fY (y ) = i fX (xi ) |g (x1 i )| |xi =[g 1 (y )]i

I
I

Ex. Y = X 2 , X N (0, 2 )

x1,2 = y , g (x) = 2x; fY (y ) =

X Gaussian, fY (y ) =

2 y [fX (+ y )
y
1 1 e 22 , y 0: 2
1
y 2

+ fX ( y )]

Ex. Y = |X |: fY (y ) = fX (y ) + fX (y )

Ex. Y = sin X , X U(, )

x1 = arc sin y , x2 = arc sin y , g (x) = cos x
fY (y ) = fX (x1 ) | cos1 x1 | + fX (x2 ) | cos1 x2 | , y > 0;
p
| cos x1 | =(| cos x2 | = 1 y 2 ; similarly for y < 0
11
1y 2 , |y | 1
fY (y ) =
0,
otherwise
Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Multiple random variables: Z = g (X , Y )

RR

P{Z z} = P{g (X , Y ) z} =

Sum: Z R= X + Y
R +
+
fZ (z) = fXY (x, z x)dx = fXY (z y , y )dy

If X , Y independent,
convolution: R
R +
+
fZ (z) = fX (x)fY (z x)dx = fX (z y )fY (y )dy =
fX (z) fY (z)

Ex. X N (mX , X2 ), Y N (mY , Y2 ), independent

X + Y N (mX + mY , X2 + Y2 )

Ex. X , Y independent, exponentially distributed with 1 , 2 .

fZ (z) = . . . = 1 1 1 (e 1 z e 2 z )
1

(x,y )Rz fXY (x, y )dxdy

If 1 = 2 = , fZ (z) = 2 ze z
I

Ex. Extension: X1 , X2 , . . . Xn iid exponential (),

P
z n1 z
e
Zn = ni=1 Xi ; fZn (z) = n (n1)!
Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Sum of Poissons

Ex. K1 Poisson (a1 ), K2 Poisson (a2 ); K = K1 + K2

k
P
2)
PK (k) = km=0 PK1 (m) PK2 |K1 (k m) = . . . (a1 +a
e (a1 +a2 )
k!
|
{z
}
PK2 (km)

K Poisson (a1 + a2 ): PASTA property (K = K1 + K2 )

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Sum of Bernoullis

Ex. K1 Bernoulli (p1 ), K2 Bernoulli (p2 ); K = K1 + K2

0 + 0 = 0 (1 p1 )(1 p2 )
0 + 1 = 1 (1 p1 )p2
1 + 0 = 1 p1 (1 p2 )
1 + 1 = 2 p1 p2

k=0
(1 p)2 ,
2p(1 p), k = 1
p1 = p2 = p: PK (k) =
2
p ,
k=2
Extension: K = K1 + K2 + . . . + Kn binomial (p, n).

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

More examples of functions of two random variables

I
I

X , Y iid N (0, 2 )

R = X 2 + Y 2,
fR (r , )drd = fXY (x, y ) dxdy
| {z }
rdrd
R 2
fR (r ) = 0 fR (r , )d
r2

r 22
e :
2
2
R = X2 +

fR (r ) =

Rayleigh

Y2
1 p/2 2
e
: exponential (22 )
2 2

P=
fP (p) =

X N (m, 2 ), Y N (0, 2 ), independent; R =

X2 + Y2

2
2
r +m
2 2

I0 ( mr
fR (r ) = r2 e
): Rice
2
R
2 x cos
1
I0 (x) = (
d, Bessel f. of 1st kind and order 0.
2 0 e
x
e

, x 1
2x
I0 (x)
x2
1+ 4 , x 1
Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Product and ratio of two random variables

I

Z = XY
1
(i) freeze X = x: fZ |X (z|x) = |x|
fY |X ( xz |x)
(ii) collect
over all x:
R +
R + 1
fZ (z) = fZ |X (z|x)fX (x)dx = |x|
fY |X ( xz |x)fX (x)dx
R
R + 1
+
fZ (z) = |x| fXY (x, xz )dx (= |y1| fXY ( yz , y )dy )

Z = X /Y
a) freeze Y R= y , collect over all y
+
fZ (z) = |y |fXY (zy , y )dy
f
( x |x); collect over all x:
b) freeze X = x: Z |X = Yx |x|
z 2 Y |X z
R
+
fZ (z) = z12 |x|fXY (x, xz )dx

Ex. X , Y iid N (0, 2 ), Z =

1
fZ (z) = 1 1+z
2 : Cauchy

Prof. Milica Stojanovic

X
Y

Applied Proabability and Random ProcessesNotes

Max and min of two random variables

Z = max{X , Y }: P{Z z} = P{X z, Y z}

X , Y independent
FZ (z) = FX (z)FY (z)
fZ (z) = fX (z)FY (z) + fY (z)FX (z)

Z = min{X , Y }: P{Z z} = P{X z orY z} =

1 P{Z > z} = 1 P{X > z, Y > z}
X , Y independent
FZ (z) = 1 [1 FX (z)][1 FY (z)]
fZ (z) = fX (z)[1 FY (z)] + fY (z)[1 FX (z)]

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Two functions of two random variables

I
I
I

X1 , X2 random variables, g1 , g2 deterministic functions:


Y1 = g1 (X1 , X2 )
(y1 , y2 ) = g (x1 , x2 ), y = g(x)
Y2 = g2 (X1 , X2 )
P{(Y
P 1 , Y2 ) (y1 , y2 )} =
= i P{(X1 , X2 ) (x1 , x2 )i }|(y1 ,y2 )=g (x1i ,x2i )
"
#
(y1 ,y2 )
(x1 ,x2 )

(g1 ,g2 )
(x1 ,x2 )

g1
x1
g2
x1

g1
x2
g2
x1

: Jacobian matrix

Jg =

Jg = det Jg := g (x1 , x2 ): Jacobian

P
fY1 Y2 (y1 , y2 ) = i |g (x1i1,x2i )| fX1 X2 (x1i , x2i )|(x1 ,x2 )i =g 1 (y1 ,y2 )

I
I

(x1 ,x2 )
1 ,y2 ) 1
Note: [ (y
= (y
if invertible, i.e. [Jg ]1 = Jg 1 ,
(x1 ,x2 ) ]
1 ,y2 )
with g 1 the inverse function of g , (x1 , x2 ) = g 1 (y1 , y2 ).

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Cartesian Gauss & Gauss polar Rayleigh & uniform

I

2
X

 , Y iidN (0, )  
2
X = R cos
R = X +Y2
: single-point solution
Y = R sin
= arctan Y
X
{z
}
|
{z
}|
1
"g
#  g

x
x
cos r sin
r

Jg 1 = y y
=
, det Jg 1 = r
sin r cos
r

= g (x, y )
det Jg = det J1
= 1
x 2 +y 2

g 1

1
fR, (r , ) =
fXY (x, y )|(x,y )=(r cos ,r sin )
|g (x, y )| |
{z
}
| {z }
f (r cos ,r sin )
r

XY

fR, (r , ) = fR (r )f (), R R(0, 2 ), U(, )

| {z }
independent!

Note also: X , Y iid N (0, 2 ) R = X 2 + Y 2 , C = X /Y :

R, C independent; R Rayleigh, C Cauchy
Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Rotation of coordinates

X + jY = Re j (X + jY )e j = Re j(+) = U + jV
U = R cos( + ) = R
{z } cos R
| sin
{z } sin
| cos
X

V = R sin( + ) = R
| sin
{z } cos + R
{z } sin
| cos

Y 

 
cos sin
X
U
=
sin cos
Y
V
{z
} | {z }
| {z } |

Jg = A, det A = 1, A1 = A0 (transpose),
fUV (u, v ) = fXY (x, y )|(x,y )=g 1 (u,v ) , or fW (w) = fZ (z)|z=A1 w
I

X , Y iid N (0, 2 ) Y , V iid N (0, 2 )

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Linear transformation (invertible); joint Gaussian

1
1
| det G| fX (G y)

Y = GX fY (y) =

X N (mX , CX ) Y N (GmX , GCX G0 ) prove it

| {z } | {z }

Q: If X1 , X2 are dependent Gaussian, can we choose G such

that Y1 , Y2 are independent Gaussian?
A: Yes. We need G to make
GCX G0 diagonal.

12
1 1
CX =
1 2
22


1 1
2
2
2
If 1 = 2 = , try G =
. Then,
1 1


2(1 )
0
CY = 2
, which is diagonal.
0
2(1 + )

Now try rotation by /4: It has the same effect (extra 1/ 2).
Side question: If X1 , X2 iid N (0, 2 ), and G corresponds to
a rotation by , can you find such that Y has correlation ?

mY

Prof. Milica Stojanovic

CY

Applied Proabability and Random ProcessesNotes

More on the 2 2 Gaussian case

I

Y = GX, X N (0, CX ), 12 = 22 = 2 .

To make Y1 , Y2 iid N (0, 2 ), i.e. CY = 2 I, we need to

normalize
Y1 and Y2 such that
their variances are equal:

1
1
2(1)
2(1)
G=
1
1

To make
normalization by :

CY = I, we need additional
1
1
2(1)
2(1)
G = 1
1
1

2(1+)

2(1+)

2(1+)

2(1+)

This G transforms a correlated Gaussian pair of equal variance

into an uncorrelated pair of unit variance.
I

What if 12 6= 22 ?

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Useful matrix manipulations: Cholesky decomposition

12
1 2
1 2
22

Let C =

Then C = LL0 , with


1
p0
L=
2 2 1 2
This means that if we have a Gaussian X with CX = I, and
we want Y = GX to have a certain CY , then we need to
choose G = LY . Here, CY = LY L0Y .

Similarly, if we have a Gaussian X with CX 6= I, and we want

Y = GX to have CY = I, then we need to choose G = L
X 1.
0
Here, CX = LX LX .

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Useful matrix manipulations: Singular value decomposition

P
C = UU0 = i i ui u0i
is the diagonal matrix of the eigenvalues i ( 0) of C,
U is the matrix of eigenvectors ui .
Orthonormal eigenvectors yield a unitary matrix, U0 U = I.

If we have a Gaussian X with CX = I, and we want Y = GX

1/2
to have a certain CY , then we need to choose G = UY Y .
Here, CY = UY Y UY .

If we have a Gaussian X with CX 6= I, and we want Y = GX

to have CY diagonal, then we can choose G = U0X . Here,
CX = UX Y UX . Then, CY = GUX X U0X G0 = X . If we
want CY = I, then we need additional normalization,
1/2
G = X U0X .

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

SVD example


I

U=

I 2
I
I

a
1 a2

12 +22
2 , r =
2
(1 + r );

1 =
q
a = 12 (1 +

1 a2
a

12 22
(1
4
2
(1 r )

2 )

2
2
1 1 2
r 2 2 )sgn()

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Expectations and moments

I

X {x1 , x2 , . . . xM }

realizations of X : x[1], x[2], . . . x[N]

P
sample mean: m
X = N1 N
n=1 x[n]

I
I

I
I
I
I

if x1 is observed N1 times, xP
2 N2 times, etc.,
m
X = NN1 x1 + NN2 x2 + . . . = i PX (xi )xi
mean= expected value: E {X } = X = mX
P
discrete random variable: E {X } = i xi PX (xi )
R +
continuous random variable: E {X } = xfX (x)dx
R +
E {g (X )} = g (x)fX (x)dx

variance: X2 = E {|X mX |2 }
R R +
E {g (X , Y )]} =
g (x, y )fXY (x, y )dxdy

E {X + Y } = E {X } + E {Y }

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Mean & variance

N (m, 2 ): mX = m, X2 = 2

exponential (): mX = 1/, X2 = 1/2

p
Rayleigh ( 2 ): mX = 2 , X2 = (2 2 ) 2

I
I

Chi-square (sum of squares of n iid N (0, 2 )) :

mX = n 2 , X2 = 2n 2

binomial (n, p): mX = np, X2 = np(1 p)

Poisson (a): mX = a, x2 = a

geometric p(1 p)k : mX =

Prof. Milica Stojanovic

1p
2
p , X

= mX + mX2

Applied Proabability and Random ProcessesNotes

Lottery: multiple tickets in same, or one ticket in multiple?

I
I
I
I

N = 106 lottery tickets, each $1, winner gets $N.

Ticket wins with p = 1/N.
You buy M = 50 tickets
Strategy 1: M tickets in same lottery
(higher chances of winning)
possible outcomes:
win / not win.

$N, Pwin = Mp
gain G =
0,
1 Pwin
E {G } = $N Pwin = $M
Strategy 2: one ticket in M independent lotteries
(possibility to win more than once)
possible outcomes: k out of M tickets
0, 1, . . . M

win, k =Mk
M k
gain G = $N K , K PK (k) = k p (1 p)
E {G } = $N E {K } = $N Mp = $M
In terms of average gain, the two strategies are the same.
Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Rolodex
I
I
I

I
I
I
I

n students in class.
Teacher calls names randomly from a Rolodex.
How many times, on average, does the teacher have to call to
make sure that each student is called at least once?
Side problem: Dropping k parcels into n cells.
What is the probability that no cell is left empty?
Number of ways to place k parcels into n cells: nk

k
k
Ai = {cell i is empty}, P[Ai ] = (n1)
= 1 n1
nk

k
k
P[Ai1 , Ai2 ] = (n2)
= 1 n2 , etc.
nk
probability that there is an
Pempty cell:P P
P[A1 or A2 or . . . An ] = i1 P[Ai1 ] i1 i2 P[Ai1 , Ai2 ] +




P P P
Pn
i n 1 i k
i1
i2
i3 P[Ai1 , Ai2 , Ai3 ] . . . =
i=1 (1) i
n
probability that no cell is empty= 1-above:



k
P
P0 (k, n) = ni=0 (1)i ni 1 ni
Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Parcel dropping, continued

k parcels into n cells

probability that exactly m cells are left empty:

k
n
P0 (k, n m)
Pm (k, n) = m
1 m
n
number of ways to choose m out of n
P[chosen m are empty]
P[none of the remaining (n m) are empty]






n Pnm
i nm 1 m+i k
Pm (k, n) = m
i=0 (1)
i
n

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Back to Rolodex

K : number of calls needed to ensure that every student is

called at least once (random variable)

For a particular K = k:
P[everyone is called at least once]=
P[k-1 calls leave exactly one student out of n]
P[k-th call hits the student that is left out]


Pn1
(1)i n1
1
PK (k) = n1 P1 (k 1, n) = i=0
i
P

K = k=n kPK (k)

with 15 students, about 50 calls on average;
with 35 students, about 150 calls on average

I
I

Prof. Milica Stojanovic

i+1 k1
n

Applied Proabability and Random ProcessesNotes

Conditional expectation

I
I

Ex. E {X |X > a} =

{Ai } disjoint,
P exhaustive decomposition of :
E {X } = i P[Ai ]E {X |Ai }

Ex. X = lifetime, S=0/1 (smoker/non-smoker),

P{S = 0} = 3/4; E {X |S = 0} = 80, E {X |S = 1} = 60
E {X } = 14 60 + 34 80 = 75
P
E {X } = i PY (yi )E {X |Y = yi }
R +
E {X } = E {X |Y = y }fY (y )dy

I
I
I

E {X |A} =

i xi PX |A (xi |A)
R +
E {X |A} = xfX |A (x|A)dx

R
xf (x)dx
Ra X
a fX (x)dx

Ex. K |A =
R a Poisson (a); A fA (a)
E {K } = 0 E {K |A = a} fA (a)da = E {A}
|
{z
}
a

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Conditional expectation: Examples

I

K |A = a Poisson (a); fA (a) = m1A e a/mA , a 0

Direct: KR= mA . Round-about:
+
PK (k) =
PK |A (k|A = a)fA (a)da =
R ak a
1 a/mA
da = . . . partial integration . . .
mA e
0 k! e

k
A
A
PK (k) = mmA +1
PK (k 1) = mmA +1
PK (0); PK (0) =
geometric
P
P k
P k1
K = P
=
0 kPK (k) =
0 k =
0 k
k
d 1

=
d
=
m
A
0
d 1
(1)2

Ex. K1 , K2 independent Poisson with a1 , a2 .

1
.
E {K1 |K1 + K2 = k} = k a1a+a
2

Ex. X , Y jointly Gaussian, zero-mean, , 2 :

E {Y |X = x} = x

Prof. Milica Stojanovic

1
1+mA :

Applied Proabability and Random ProcessesNotes

Conditional expectations: Properties

R +
R R +
E {Y } = yfY (y )dy =
yfXY (x, y )dxdy =
Z +
R +
yfY |X (y |x)dy dx = EX {E {Y |X }}
fX (x)
|
{z
}
E {Y |X =x}

I
I
I

X , Y independent: E {Y |X } = E {Y }
R +
E {Z |X = x, Y = y } = zfZ |XY (z|x, y )dz
R R +
E {Z } =
E {Z |X = x, Y = y }fXY (x, y )dxdy =
EXY {E {Z |X , Y }}
E {Z } = h
i
R +
R +
f
(x)
E
{Z
|X
=
x,
Y
=
y
}f
(y
|x)dy
dx
Y |X
X

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Entropy

X {x1 , x2 , . . . xM }

information contained in X = xi :
IX (xi ) = log PX1(xi ) measure of uncertainty

units: bits for log2 ; nats for ln

P
1
average: HX = M
i=1 PX (xi ) log PX (xi ) entropy

I
I

Among all distributions PX (xi ), uniform has maximal entropy:

HX = log M

X continuous: similar definitions; among all pdfs with same

power, Gaussian has maximal entropy, HX = 12 log(2eX2 )

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Moments

(i)

mX = E {X i } i-th moment

E {(X mX )i } i-th central moment

mXY = E {X i Y j } joint moment

CXY = E {(X mX )i (Y mY )j } joint central moment

correlation: RXY = E {XY }

covariance: CXY = E {(X mX )(Y mY )}

RXY = CXY + mx mY

correlation coefficient: XY = CXY

2

(i,j)

(i,j)

X Y2

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Correlation properties
I

|XY | 1
proof: subtract the mean, E {(X Y )2 } 0, take > 0;
true for any , including that for which LHS is min:
CXY
d

2
d E {(X Y ) } = 0 = 2
Y

I
I
I

2 2 2
back into LHS CXY
X Y

|XY | = 1 E {(X YX Y )2 } = 0:
R +
X 2
x
y) fXY (x, y ) dxdy = 0 X = YX Y
(
Y
|
{z
}
0
p
Schwartz inequality: |hg1 , g2 i| hg1 , g1 ihg2 , g2 i
equality iff g1 =constg
2
R
inner product: T g1 (t)g2 (t)dt for functions, g1 0 g2 for vectors
R +
probability: E {g1 (Z )g2 (Z )} = g1 (z)g2 (z)fZ (z)dz =
p
p
R +
f
(z)][g
(z)
fZ (z)]dz; Schwartz yields
[g
(z)
2
1
Z

q
2
|E {g1 (Z )g2 (Z )}| E {g1 (Z )}E {g22 (Z )}
Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Correlation and independence; Linear MMSE estimation

X , Y independent X , Y uncorrelated (XY = 0)

X , Y uncorrelated does not imply X , Y independent

X , Y uncorrelated and Gaussian X , Y independent

X , Y uncorrelated var (X + Y ) = var (X ) + var (Y )

Observe realizations of X and Y : Can we use X to

predict/estimate Y ?
Linear MMSE estimation: Y = aX + b,

E {[Y Y ]2 } mina,b YMMSE mY = XY X mX ,

MMSE=Y2 (1 2XY )
check: if XY = 0 YMMSE = mY , MMSE=Y2
(as expected, nothing to do with x)

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Bounds: Chebyshev, Markov

Chebyshev iequality:
2
P{|X mX | } X2
proof: R
R
+
X2 = (x mX )2 fX (x)dx |xmX | (x mX )2 fX (x)dx
R
2 |xmX | fX (x)dx = P{|X mX | }

Markov inequality:
P{X } mX for X 0
R +
R +
proof: mX = xfX (x)dx = 0 xfX (x)dx
R
R
x xfX (x)dx fX (x)dx = P{X }

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Law of large numbers (weak)

Xi iid with mX , X2
P
Y =m
X = n1 ni=1 Xi : sample mean is a random variable
that depends on n

mY = mX , Y2 =

Chebyshev: P{|Y mY | }

1
nX2
n2

P{|m
X mX | }
I

= n1 X2

X2
n 2

Y2
2

0 as n

As the number of samples grows, sample mean converges

in probability P
to the true mean:
limn P{| n1 ni=1 Xi mX | } = 0 ()

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Chernoff bound
I
I

Fact: e t(xx0 ) u(x x0 ), t > 0

R +
R +
P{x x0 } = x0 fX (x)dx = u(x x0 )fX (x)dx
Z +
R + t(xx )
tx
0
0
fX (x)dx = e
e tx fX (x)dx
e

|
{z
}
MX (t)

MX (t) =

E {e tX }:

moment-generating function

e tx0 M

P{x x0 }
X (t): true t > 0, including that t for
which the RHS is min. (tightest bound)

X /2 , RHS is min. at
Ex. X N (mX , X2 ): MX (t) = e tmX e t 
2
2
X
X
t = x0 m
, P{X x0 } = Q x0 m
e (x0 mX ) /2X
X
2

2 2

Ex. K Poisson (a): MK (t) = e a(e 1) , RHS is min. at

 k0
t = ln ka0 , P{K k0 } ka0
e k0 a
Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Characteristic function

R +

jx f (x)dx = E {e jX }
X
e
R +
jx d: Fourier-like pair
X (j)e

X (j) =

fX (x) =

Use: convolution of pdfs product of characteristic functions

P
Xi iid fX (x), Y = ni=1 Xi

I
I

I
I

1
2

fY (y ) = fX1 (y ) fX2 (y ) . . . fXn (y ) = fX (y ) fX (y ) . . . fX (y )

{z
}
|
n times
Q
Y (j) = ni=1 Xi (j) = [X (j)]n
R +
1
jy d
fY (y ) = 2
Y (j)e

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Characteristic function: Examples

2 2

Xi N (mX , X2 ), X (j) = e jmX e X /2

2
2
Y (j) = e jnmX e nX /2 Y N (nmX , nX2 )

Ex. K1 , K2 iid binomial (n, p), K = K1 + K2 binomial (2n, p)

K (j) = [(pe j + 1 p)n ]2 : binomial (2n, p)
convolution: "
#
k  
X
n
n
p k (1 p)nk
PK (k) = . . . =
i
k i
| i=0
{z
}
2n
(k )
X1 , X2 independent exponential with mX1 , mX2 ; Y = X1 + X2
1
1
1
Xi (j) = 1jm
; Y (j) = 1jmX
1jmX
=
1
2
X

c1
1jmX1

fY (y ) =

mX1
mX2
c2
1
1jmX2 = mX1 mX2 [ 1jmX1 1jmX2 ]
y /mX1
1
e y /mX2 ], y 0
mX1 mX2 [e

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Moments
(jX )i
i! }

(j)i
i
i! E {X }

X (j) = E {e jX } = E {

E {X i } =

Ex. K Poisson (a)

j
K (j) = e a(e 1)
K (j0) = 1 (always)
dK (j)
j

d(j) = K (j) = K (j) ae , k (j0) = a

d 2 K (j)
K (j) =
K (j) ae j + K (j) aK (j),
=
2

d i X (j)
|
d(j)i j=0

d(j)

K (j0) = a2 + a 2 = a2

K
I

Joint characteristic function:

X1 ,X2 (j1 , j2 ) = E {e j1 X1 +2 X2 ) }

E {X1i1 X2i2 } =

i1 +i2

(j1 , j2 )|j1 =0,j2 =0

(j1 )i1 (j2 )i2 X1 ,X2

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Central Limit Theorem (CLT)

P
Xi iid zero-mean, i2 , Sn = ni=1 Xi
P
If k2 < ni=1 i2 k, P
> 0, then
limn fSn (x) = N (0, ni=1 i2 )

Proof: special case i2 = X2 :

Yi =

Yi (j) = E {e jXi /
| {z }

1 Xi
n

n}

Y (j)

j
= Xi ( )
n
| {z }
j
)
X (
n

j
(
1
),
n X
n

Y (j) =

Taylor: Y (j) =
...
2
Y (j0)(j) +
Y (j0) (j) + Y (j0)
Y (j0) +
2!
| {z } | {z }
| {z }
| {z }
1 2
1 ...
1
1

mx =0

Y (j) =

j
(
1 1
), . . .
n n X
n

Prof. Milica Stojanovic

(j)3
3!

+ ...

X (j0)

Applied Proabability and Random ProcessesNotes

CLT, contd
Pn

Z=

Yi independent Z (j) = [Y (j)]n

ln Z (j) = n ln Y (j)
2 (j)2
a3 (j)3
a4 (j)4
+
+ 2
+ . . .)
ln Z (j) = n ln(1+ X
n 2!
n 4!
n n 3!
{z
}
|

i=1 Yi

(n)

(n) 0 as n ; ln(1 + ) as 0

ln Z (j) n [

Z (j) e

Consequently, Sn =

X2 (j)2
n 2!
2 2 /2
X

a3 (j)3
n n 3!

a4 (j)4
n2 4!

+ . . .]

X2 2
2

as n , i.e. fZ (z) N (0, X2 ).

nZ starts behaving as N (0, nX2 )

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Random vectors

X1

X = ...
Xn
fX (x) = fX1 ...Xn (x1 , . . . xn )

X (j1 , . . . j2 ) = E {e j1 X1 +...jn Xn }: X (j) = E {e j X }

fXY (x, y) = fX1 ...,Xn ,Y1 ,...Ym (x1 , . . . , y1 , . . .)

fXY (x, y) = fX (x)fY (y): X, Y independent

transformation: Y = g(X): generalization of the 22 case

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Vector moments

E {X1 }

..
mean mX = E {X} =

.
E {Xn }

correlation RX = E {XX0 }

covariance CX = E {(X mX )(X mX )0 }

CX = RX mX m0X

cross-correlation, covariance:
RXY = E {XY0 }, CXY = E {(X mX )(Y mY )0 }

E {XY0 } = mX mY 0 : X, Y uncorrelated

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Gaussian vectors

0 1
1
e (xmX ) CX (xmX )/2
n
2 det CX
0
0
= e j mX e CX /2

fX (x) =

X (j)

Any covariance matrix is positive semi-definite

Whitening: Y = GX, CX = UU0 , G = 1/2 U CY = I

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Statistics, parameter estimation

Theory: many interesting questions can be answered if an

underlying pdf or averages are known.

Practice: need to estimate mean, variance, maybe the entire

pdf statistical parameter estimation

Observe: X1 , X2 , . . . Xn

Know: observations depend on some parameter

Question: What is ?

Answer: Dont know, but can estimate.

function of X1 , . . . Xn (must not depend on true )
:

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

How many people will vote R?

I
I
I

I
I

I
I
I

In a certain state, there are N=1 million people. How many

will vote R?
What is the probability that a person will vote R?
NR (N)/N. This is exact, but I cannot poll all the people.
Pick n out of N and poll them. The estimated probability of
voting R is NR (n)/n. This is a random variable because the n
people were picked randomly. (If I repeat with different n
people, the result will be different.)
Same with medical studies, estimating the number of fish in
the ocean, etc.
How good is this estimate? What should n be? Obviously,
two is not good enough. The more, the better, but still, how
many is good enough?
What does good enough mean?
Is = NR (n)/n a good function?
Statistics: quantitative answers to such questions.
Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Properties

I
I

1 , . . . Xn )} =
unbiased: E {(X
1 , . . . Xn ) | > } = 0, > 0
consistent: limn P{|(X

consistent in the mean square sense:

1 , . . . Xn ) |2 } 0 as n
E {|(X

minimum mean squared error (MMSE) estimate:

1 , . . . Xn ) |2 }
that which has the smallest MSE= E {|(X
Pn
1 , . . . Xn ) =
linear estimate: (X
ai Xi

i=1

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Sample mean

Xi iid, mean mX
1 , . . . Xn ) =
Y = (X

Y is an estimate of the mean of X (Y = m

X ).

Y is a random variable.
mX is a deterministic parameter.
n observations are picked independently at random.

Sample mean is unbiased, consistent:

E {Y } = mX , E {(Y mX )2 } = n1 X2 0 as n ,

P{|Y mX | > }

1
n

Pn

X2
n 2

i=1 Xi

0 as n .

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Estimation of variance

1
n

Pn

X2 =

For this, we need to know the mean, which is unlikely if we do

not know the variance!
P
X )2 : biased

X2 = n1 ni=1 (Xi m
P
n
1
X )2 : unbiased

X2 = n1
i=1 (Xi m

all consistent (by Chebyshev)

i=1 (Xi

mX )2

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Counting: Estimation of probability

How many fish are trout?

Pick n fish at random, count the number of trout. Estimate

fraction p as ratio of count to total. Note: if the counting
experiment is repeated, it will yield a new result.

Let Xi = 1 if i-th fish is trout; 0 otherwise.

Xi iid Bernoulli (p). Mean: mX = p.
P
Y = n1 ni=1 Xi : estimate of p is a random variable
(repeated counting experiment may yield a different count).
Pn
i=1 Xi binomial (n, p)

Q: How good is Y as the estimate of p?

Q2: What does good mean?

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Confidence intervals, Bernoulli

I
I
I

If n is large enough that CLT applies, then

Y N (mX , X2 /n).
X
), i.e.
P{|Y mY | X } = 1 2Q(

Y
P{|Y mX | X } = 1 2Q( n)

Counting: mX = p, X2 = p(1 p)
p

P{|Y p| p(1 p)} = 1 2Q( n)

p
P{|Y p| p(1 p)} = P{(Y p)2 2 p(1 p)} =
P{(1 + 2 )p 2 (2Y + 2 )p + Y 2 0} =

P{p [p1 (Y ), p2 (Y
)]} = 1 2Q( n): confidence
p1,2 (Y ) =

(2Y +2 )

(2Y +2 )2 4(1+2 )Y 2
:
2(1+2 )

Prof. Milica Stojanovic

confidence interval

Applied Proabability and Random ProcessesNotes

Interval estimation, Bernoulli

I

Interpretation: for a given , n, and Y = y , probability that

true p is between p1 (y ) and p2 (y ) is 1 2Q( n). Say that

we set this probability (confidence) to 99.7%. This means
that if we made many counting experiments, 99.7% of them
would have an interval [p1 , p2 ] that contained the actual p.

If we want 1 2Q( n) = 99.7% confidence, then n = 3.

If we want 1 2Q( n) = 95% confidence, n = 1.96.

p1 (Y ), p2 (Y ) are the estimates of the interval that contains

true p with probability 1 2Q( n).

Ex. Out of n=133 fish in the net, 58 are trout, i.e.

p = Y = 0.44.

For 99.7% confidence, = 3/ n, [p1 , p2 ] = [0.31, 0.57].

For 95% confidence, = 1.96/ n, [p1 , p2 ] = [0.35, 0.52]

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

How good is the count?

I

Cases of dengue fever have been reported on a tropical island

where you want to go. Out of the 240 inhabitants, 13 tested
positive. Is it safe to go?
13/240=5.4%: small, but 13 is small too.
95% confidence interval is [3.3%, 8.9%]: With 95%
confidence, you can say that 3-9 people out of 100 are
infected (1 in 30 - 1 in 11).

A supermarket sells ground meat as 90% lean. Is it really

90% lean? Obviously, they cannot guarantee that every
package is 90% lean exactly. To test, you can buy n packages
and measure the fat content: X1 = 88%, X2 = 91%, . . ..
Then extract the desired confidence interval.
P You can also2
x ) or
measurePthe variability in packaging, as n1 ni=1 (xi m
n
1
2
as n1 i=1 (xi m
x ) .
Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Interval estimation, general

I

In general Xi iid fX (x), and mX , X2 may or may not be

related to the parameter that is being estimated.

x , x 0. =?
Ex. Exponential: fX (x) = e
P
= m1X , X2 = mX2 , Y = n1 ni=1 Xi , n large
X
P{|Y mY | X } = 1 2Q(
), i.e.

Y
P{|Y mX | X } = 1 2Q( n), i.e.

P{|Y 1 | 1 } = 1 2Q( n), i.e.

P{ [ Y1 Y1 , Y1 + Y1 ]} = 1 2Q( n)
With n=64 observations and Y =3.5, 95% confidence interval

( n = 1.96) for is [0.22, 0.36].

Ex. Gaussian: Xi iid N (mX , X2 ), mX =?

Cannot say anything about confidence intervals, because there
is no relationship between X2 and mX .

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Confidence interval on the sample mean of Gaussian

I
I

Xi iid N (mX , X2 ), mX =?
P
Y = n1 ni=1 Xi ,

P{|Y mX | X } = 1 2Q( n), but

P{|Y mX |
X } =
6 1 2Q( n) because
X is obtained
from Xi and is thus random.

Q: For = n and [1 2Q()] a prescribed confidence,

X
what is the probability P{|Y mX |
}, i.e. what is the
n
mX |
}? Can we express this probability
probability P{ |Y

X / n
as P{mX [1 (X), 2 (X)]}, i.e. can we find the [1 2Q()]
confidence interval [1 , 2 ]?

A: To do this, we need to know the distribution of

Prof. Milica Stojanovic

Y m
X .

X / n

Applied Proabability and Random ProcessesNotes

Student t-distribution
I

P
When Xi are iid Gaussian, m
X = n1 ni=1 Xi and
q
1 Pn
X has the

X = n1
X )2 , Tn1 = mX m
i=1 (Xi m
X/ n
Student t- distribution with (n 1) degrees of freedom.

The corresponding cumulative distribution function FTn1 ()

is known (tabulated).

The t-pdf is symmetrical: P{|Tn1 | } = 1 2QTn1 () =

1 2[1 FTn1 ()] = 2FTn1 () 1.

X
,m
X +
]} = 2FTn1 () 1
Hence, P{mX [m
X
n
n

Note: this result is valid for any n (not necessarily large)

X
= 0.45;
Ex. Observations: n = 21, m
X = 3.5,
n
90% confidence and n 1=20 degrees of freedom
= 1.725 [1 , 2 ] = [2.72, 4.28].

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Percentiles
I

Non-parametric estimation: no knowledge/assumptions about

the underlying distribution.

Median (50%): half the observations are below, half above

(e.g. house prices);
70-th percentile: 70% of observations are below, 30% above
(e.g. childs height)

Dispersion, e.g. 90%: 45% around median: difference

between 95-th and 5-th percentile.

Observe X1 , . . . Xn ; order them: Y1 , . . . Yn

Estimate of the u-th percentile: xu = Zu = k(u) 2 k(u)+1 ;

k(u) rank at which ordered variables are divided into fraction
u below / (1 u) above.

Prof. Milica Stojanovic

+Y

Applied Proabability and Random ProcessesNotes

Interval estimation for percentiles

n
k

u k (1 u)nk

P{Yk < xu < Yk+1 } =

P{Yk1 < xu < Yk2 } =

P{Yk1 < xu < Yk1 +1 or . . . Yk2 1 < xu < Yk2 } =
kX
2 1  
n k
u (1 u)nk maxk1 ,k2
k
k=k1
|
{z
}
P

For large enough n, binomial can be approximated by

Gaussian. Gaussian will yield shortest interval if k1 , k2
symmetric around
 the mean
 nu (k2 nu = nu k1 ):
P 1 2Q

k2 nu

nu(1u)

Ex. P = 0.95 k2 nu

nu(1u)

Prof. Milica Stojanovic

= 1.96 k1 , k2 for given n, u.

Applied Proabability and Random ProcessesNotes

Vectors: Estimation of mean, covariance

X has mean mX , covariance CX

observe X1 , . . . Xn
P
m
X = n1 i Xi : sample mean
P
X = 1
X ][Xi m
X ]0 (unbiased,
C
i [Xi m
n1
has Wishart distribution)

I
I

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Maximum likelihood (ML) parameter estimation

Ex. Bernoulli: toss coin n times, observe k successes. p=?

Know: PK (k) = kn p k (1 p)nk . If I had 47 successes out of
100, what p is most likely to have been involved?

dPK (k)
dp

I
I

= 0 p = kn : ML estimate of p is pML (k) = kn .

In this case, sample mean is the same as ML estimate.

In general, ML (x) = arg max fX| (x|).

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes

Least squares (LS) parameter estimation

Know model (linear): X = g + N, where g deterministic,

known; N random, zero-mean.

Let
determine such that
P X = g, and
2

i |Xi gi | = (X g) (X g) is minimized.
P
g X
Pi i 2i
i |gi |

Solution: LS (X) =

Extension to parameter vector :

X = G + N
LS = [G0 G]1 G0 X.

Prof. Milica Stojanovic

1 0
g0 g g X

Applied Proabability and Random ProcessesNotes

Minimum variance (MV) parameter estimation

Same model as before; noise covariance CN known

Minimum variance unbiased estimate:

= a0 X = a0 g + a0 N = + a0 N min. variance
a0 CN a mina s.t.c. a0 g = 1
MVUB = g0 C 11 g g0 CN 1 X
N

2 I,
LS = MVUB .
Note: If CN = N

Prof. Milica Stojanovic

Applied Proabability and Random ProcessesNotes