CSCE 411 Lecture 23

Lecture Slides

« previous | Monday, October 22, 2012 | next »

No lecture last Friday due to bomb threat.

Randomized Algorithms

Verifying Polynomial Identity

def verify_polynomial_identity f, g
  d = [f.degree, g.degree].max
  r = (1..100*d).to_a.sample
  f(r) == g(r)
end

The alogorithm reports that $F(r)$ and $G(r)$ are the same although they are different iff $r$ is a root of the polynomial $F(x)-G(x)$.

A polynomial of degree $d$ has exactly $d$ roots, so choosing from $[1..100d]$ gives 1/100 chance for error.

We could reduce this even further by choosing a larger range of integers, but no matter how large, there will always be a small chance for error.

We could also run the algorithm $k$ times, so the failure probability of failure for $k$ independent events

$Pr[E_1\cap E_2\cap \dots \cap E_k]=\prod _{i=1}^{k}Pr[E_i]\le \prod _{i=1}^k\frac{d}{100d}={\left(\frac{1}{100}\right)}^k$

Random Variables

More probability theory. (See :Category:STAT 211-507→)

Let $F$ be a σ-algebra over a sample space $\mathrm{\Omega }$. A random variable $X$ is a function $\mathrm{\Omega }\to R$ such that $\{z\in \mathrm{\Omega }|X(z)\le x\}$ is an event in $F$ for each $x$ in $R$.

We write $X\le x$ for this event.

Allows us to describe events as preimages.

Examples

1. Let $X$ be the random variable denoting the sum of face values of a pair of dice. Then $X\le 3$ is a shorthand for the event $\{(1,1),(1,2),(2,1)\}$.
2. Let $Y$ be the random variable counting the number of heads during three subsequent coin tosses. Then $Y\le 0$ is shorthand for the event $\{(\text{tails}),(\text{tails}),(\text{tails})\}$

Discrete Random Variables

A random variable with a countable image, where $X=a$ is an event.

Expectation Value

Let $X$ be a discrete random variable over probability space $(\mathrm{\Omega },F,Pr)$

The expectation value (or mean) of $X$ is given by

$E[X]=\sum _{a\in X(\mathrm{\Omega })}\alpha Pr[X=\alpha ]$

Example

Let $Y$ denote the number of heads in three subsequent coin tosses.

• $Y=0$ is $\{(t,t,t)\}$
• $Y=1$ is $\{(h,t,t),(t,h,t),(t,t,h)\}$
• $Y=2$ is $\{(h,h,t),(h,t,h),(t,h,h)\}$
• $Y=3$ is $\{(h,h,h)\}$

Probabilities of event:

• $Pr[Y=0]=Pr[Y=3]=\frac{1}{8}$
• $Pr[Y=1]=Pr[Y=2]=\frac{3}{8}$

Expected value $E[Y]=0\cdot \left(\frac{1}{8}\right)+1\cdot \left(\frac{3}{8}\right)+2\cdot \left(\frac{3}{8}\right)+3\cdot \left(\frac{1}{8}\right)=\frac{3}{2}$

Linearity of Expectation

For random variables $X,Y$ and real numbers $a,b$

$E[aX+bY]=aE[X]+bE[Y]$

Example: Hat Check Girl

Suppose $n$ persons give their hat to the hat check girl. The girl is upset and hands each person a random hat (where the hat is chosen uniformly at random). How many persons can expect to get their own hat back?

Sample space is $\mathrm{\Omega }=\{1,2,\dots ,n\}$

Allow subsets of $\mathrm{\Omega }$ to be events such that σ-algebra $F={𝒫}(\mathrm{\Omega })$.

For $p\in \mathrm{\Omega }$, the event $\{p\}$ has the interpretation that $p$ received his or her own hat. Therefore, by uniform distribution, the probability that any $p$ receives his or her own hat is $Pr[\{p\}]=\frac{1}{n}$

Use random variable $X_i=1$ if the $i$^th person received his or her own hat back, and $X_i=0$ otherwise.

$\begin{array}{rl}Pr[X_i=1]& =\frac{1}{n}\\ E[X_i]& =1Pr[X_i=1]+0Pr[X_i=0]=\frac{1}{n}\end{array}$.

The random variable $X=\sum _{i=1}^n{X}_i$ counts the number of persons receiving their own hat. By linearity,

$\begin{array}{rl}E[X]& =E[X_1+X_2+\dots +X_n]\\ & =\sum _{i=1}^{n}E[X_i]\\ & =\sum _{i=1}^n\frac{1}{n}\\ & =n\left(\frac{1}{n}\right)\\ & =1\end{array}$

So 1 person gets his or her own hat back, and the other $n-1$ are in a riot outside the manager's office.

Bernoulli Distribution

Tossing a biased coin can be described by a random variable $X$ that takes the value 1 if the outcome is heads and 0 if the outcome is tails. Assume that $Pr[X=1]=p$ and $Pr[X=0]=1-p$

Geometric Distribution

Suppose we keep tossing a biased coin that has Bernoulli distbibution with parameter $p$ until heads event occurs. Let $X$ be the number of coin flips needed in this experiment. We say that $X$ is geometrically distributed with parameter $p$ and th edensity is given as:

$p_X(x)=Pr[X=x]=p(1-p{)}^{x-1}$

for $x\in \mathbb{\mathbb{N}}$.

$\begin{array}{rlrl}E[X]& =\frac{1}{p}& Var[X]& =\frac{1-p}{p^2}\end{array}$

Example: Coupon Collection

The hat check girl is a compulsive coupon collector. Currently, she is collecting charming Hanny Potter characters that are contained in overpriced cereal boxes. There are $n$ different characters and each box contains one character. How many boxes of cereal does she have to buy for a complete collection?

Let $X$ denote the number of boxes required to collect at least one character of each type.

Goal is to find $E[X]$. Let $X_k$ be the random variables counting the number of boxes that the hat-check girl buys to get the $(k+1)$^th character after she has already collected $k$ characters.

The probability to draw one of the remaining characters is $p_k=(n-k)/n$. Hence $X$ is geometrically distributed with parameter $p_k$. Therefore

$E[X_k]=\frac{1}{p_k}=\frac{n}{(n-k)}$

Linearity shows that

$E[X]=\sum _{k=0}^{n-1}E[X_k]=\sum _{k=0}^{n-1}\frac{n}{n-k}=n\sum _{k=0}^{n-1}\frac{1}{k}=n{H}_n=n\log n$