Nanana

Probability and Randomized Algorithms
Prof. Zeph Grunschlag

Discrete Random Variable
DEF: A discrete random variable is a set X together with an assignment of a nonnegative probability Pr[X=x]that X takes value x; furthermore, the sum over all possible x ε X of the probability that X takes value x must equal 1.

• If X is clearly fixed from context, may p
abbreviate Pr[X=x] to Pr[x] or2

x.

• Let X, Y be random variables over the resp.
sets X, Y. (Note, X,Y may/may not be same) DEF: Joint probability Pr[x,y] is the probability that (X,Y) = (x,y). (Probability of bothoccurring simultaneously) DEF: Conditional probability is defined by Pr[x|y] = Pr[x,y] / Pr[y] - assuming that Pr[y] > 0.
3

Joint and Conditional Probability

Independent Variables
• Random variablesare independent if their
probabilities don’t depend on each others values: DEF: X and Y are independent if Pr[x,y] = Pr[x]Pr[y] for all x, y. LEMMA: Equivalently, X and Y are independent if(excluding 0-prob. y)

∀x ∈ X, ∀y ∈ Y, Pr[x|y] = Pr[x]
4

Baye’s Theorem

THM: If Pr[y] > 0 then Pr[x|y] = Pr[y|x] ⋅ Pr[x] / Pr[y]

5

• Assume X a random variable on {0,1} and • Repeat experimentn times. I.e., take n
Bernoulli’s Thm:
n

DEF: The product of random variables X, Y is the random variable X×Y defined on X×Y with distribution Pr[(x,y)] = Pr[x]Pr[y]. let p = Pr[X=1], q = Pr[X=0]Binomial Rand.Var.

• result called Binomial random variable
n k n−k Pr ! Xi = k = pq k i=1
6

independent copies: X1 × X2 × · · · × Xn

Expectation
• The average value taken on by afunction f
on probability distribution X DEF: The expectation of f is defined by:

E( f ) =

THM:

E( f + g) = E( f ) + E(g)

x∈X

! f (x) · px

COR: For n repetitions of a Binomial randomvariable X consider sum S which counts the number outcomes = 1. Then E(S) = np
7

Chernoff Bound
• Estimates probability that sum of Binomial
THM: experiment deviate from expected sum np

Pr S...