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

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)\}$ .
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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F = \mathcal{P}(\Omega)} .

For Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p \in \Omega} , the event Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{p\}} has the interpretation that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} received his or her own hat. Therefore, by uniform distribution, the probability that any Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} receives his or her own hat is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Pr[\{p\}] = \tfrac{1}{n}}

Use random variable Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_i=1} if the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} ^th person received his or her own hat back, and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_i = 0} otherwise.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} Pr[X_i = 1] &= \frac{1}{n} \\ E[X_i] &= 1 Pr[X_i = 1] + 0 Pr[X_i = 0] = \frac{1}{n} \end{align}} .

The random variable Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X = \sum_{i=1}^n X_i} counts the number of persons receiving their own hat. By linearity,

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} 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{align}}

So 1 person gets his or her own hat back, and the other Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n-1} are in a riot outside the manager's office.

Bernoulli Distribution

Tossing a biased coin can be described by a random variable Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} that takes the value 1 if the outcome is heads and 0 if the outcome is tails. Assume that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Pr[X=1] = p} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Pr[X=0] = 1-p}

Geometric Distribution

Suppose we keep tossing a biased coin that has Bernoulli distbibution with parameter Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} until heads event occurs. Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} be the number of coin flips needed in this experiment. We say that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} is geometrically distributed with parameter Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} and th edensity is given as:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_X(x) = Pr[X=x] = p(1-p)^{x-1}\,\!}

for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \in \mathbb{N}} .

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} E[X] &= \frac{1}{p} & Var[X] &= \frac{1-p}{p^2} \end{align}}

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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} different characters and each box contains one character. How many boxes of cereal does she have to buy for a complete collection?

Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} denote the number of boxes required to collect at least one character of each type.

Goal is to find Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E[X]} . Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_k} be the random variables counting the number of boxes that the hat-check girl buys to get the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (k+1)} ^th character after she has already collected Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} characters.

The probability to draw one of the remaining characters is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_k = (n-k)/n} . Hence Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} is geometrically distributed with parameter Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_k} . Therefore

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E[X_k] = \frac{1}{p_k} = \frac{n}{(n-k)}}

Linearity shows that

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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}}