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}]\leq \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 $\Omega$. A random variable $X$ is a function $\Omega \to R$ such that $\{z\in \Omega ~|~X(z)\leq x\}$ is an event in $F$ for each $x$ in $R$.

We write $X\leq 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\leq 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\leq 0$ is shorthand for the event $\{({\mbox{tails}}),({\mbox{tails}}),({\mbox{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 $(\Omega ,F,Pr)$

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

$E[X]=\sum _{a\in X(\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]={\tfrac {1}{8}}$
• $Pr[Y=1]=Pr[Y=2]={\tfrac {3}{8}}$

Expected value $E[Y]=0\cdot \left({\tfrac {1}{8}}\right)+1\cdot \left({\tfrac {3}{8}}\right)+2\cdot \left({\tfrac {3}{8}}\right)+3\cdot \left({\tfrac {1}{8}}\right)={\tfrac {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 $\Omega =\{1,2,\ldots ,n\}$

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

For $p\in \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\}]={\tfrac {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{aligned}Pr[X_{i}=1]&={\frac {1}{n}}\\E[X_{i}]&=1Pr[X_{i}=1]+0Pr[X_{i}=0]={\frac {1}{n}}\end{aligned}}$.

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

${\begin{aligned}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{aligned}}$

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 {N}$.

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

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}}=nH_{n}=n\log {n}$