Transcript CS244a: An Introduction to Computer Networks

Review of Probability Theory
Review Session 1
EE384X
Winter 2006
EE384x
1
Random Variable
A random experiment with set of outcomes
 Random variable is a function from set of
outcomes to real numbers

Winter 2006
EE384x
2
Example

Indicator random variable:

A : A subset of
Winter 2006
is called an event
EE384x
3
CDF and PDF

Discrete random variable:


The possible values are discrete (countable)
Continuous random variable:

The rv can take a range of values in R

Cumulative Distribution Function (CDF):

PDF and PMF:
Winter 2006
EE384x
4
Expectation and higher
moments

Expectation (mean):


if X>0 :
Variance:
Winter 2006
EE384x
5
Two or more random variables

Joint CDF:

Covariance:
Winter 2006
EE384x
6
Independence

For two events A and B:

Two random variables

IID : Independent and Identically Distributed
Winter 2006
EE384x
7
Useful Distributions
Winter 2006
EE384x
8
Bernoulli Distribution


The same as indicator rv:
IID Bernoulli rvs (e.g. sequence of coin
flips)
Winter 2006
EE384x
9
Binomial Distribution

Repeated Trials:


Number of times an event A happens among n
trials has Binomial distribution


Repeat the same random experiment n times. (Experiments are
independent of each other)
(e.g., number of heads in n coin tosses, number of arrivals in n
time slots,…)
Binomial is sum of n IID Bernouli rvs
Winter 2006
EE384x
10
Mean of Binomial

Note that:
Winter 2006
EE384x
11
Binomial - Example
0.45
n=4
0.4
0.35
p=0.2
n=10
0.3
0.25
n=20
0.2
n=40
0.15
0.1
0.05
0
Winter 2006
1
2
3
4
5
6
EE384x
7
8
9
10
11
12
12
Binomial – Example (ball-bin)

There are B bins, n balls are randomly
dropped into bins.

: Probability that a ball goes to bin i

: Number of balls in bin i after n drops
Winter 2006
EE384x
13
Multinomial Distribution
Generalization of Binomial
 Repeated Trails (we are interested in more
than just one event A)


A partition of W into A1,A2,…,Al
 Xi shows the number of times
among n trails.
Winter 2006
EE384x
Ai occurs
14
Poisson Distribution

Used to model number of arrivals
Winter 2006
EE384x
15
Poisson Graphs
0.5
l=.5
0.45
0.4
l=1
0.35
0.3
0.25
l=4
0.2
l=10
0.15
0.1
0.05
0
Winter 2006
0
5
10
EE384x
15
16
Poisson as limit of Binomial

Poisson is the limit of Binomial(n,p) as

Let
Winter 2006
EE384x
17
Poisson and Binomial
0.4
n=5,p=4/5
0.35
Poisson(4)
0.3
0.25
n=10,p=.4
0.2
n=20, p=.2
0.15
0.1
n=50,p=.08
0.05
0
Winter 2006
0
1
2
3
4
5
EE384x
6
7
8
9
10
18
Geometric Distribution

Repeated Trials: Number of trials till some
event occurs
Winter 2006
EE384x
19
Exponential Distribution
Continuous random variable
 Models lifetime, inter-arrivals,…

Winter 2006
EE384x
20
Minimum of Independent
Exponential rvs

Winter 2006
: Independent Exponentials
EE384x
21
Memoryless property

True for Geometric and Exponential Dist.:


The coin does not remember that it came up tails l times
Root cause of Markov Property.
Winter 2006
EE384x
22
Proof for Geometric
Winter 2006
EE384x
23
Characteristic Function
Moment Generating Function (MGF)
 For continuous rvs (similar to Laplace xform)


For Discrete rvs (similar to Z-transform):
Winter 2006
EE384x
24
Characteristic Function


Can be used to compute mean or higher
moments:
If X and Y are independent and T=X+Y
Winter 2006
EE384x
25
Useful CFs

Bernoulli(p) :

Binomial(n,p) :

Multinomial:

Poisson:
Winter 2006
EE384x
26