CSCE 411 Lecture 27

Lecture Slides

« previous | Wednesday, October 31, 2012 | next »

Happy Halloween

Hiring Problem

You need to hire a new employee

The headhunter sends a different applicant every day for $n$ days.

If the applicant is better than the current employee then fire the current employee and hire the applicant.

Firing and hiring is expensive.

How expensive is the whole process?

Analysis

The worst case is when headhunter sends all $n$ applicants in increasing order of goodness: hire (and fire) each one in turn ($n$ times)

Best case is when headhunter sends best applicant on the first day: hire just once.

Expected cost is $E[X]$, where $X$ is the number of applicants that are hired.

Change viewpoint: let $X_{i}$ be the indicator random variable representing whether the $i$^th applicant is hired (1 if hired, 0 otherwise).

Therefore $X=\sum _{i=1}^{n}X_{i}$ and $E[X_{i}]=Pr[{\mbox{applicant }}i{\mbox{ is hired}}]$.

The probability that a person will be hired is ${\tfrac {1}{i}}$ since out of the first $i$ applicants potentially hired, there is one best candidate.

$\ln {n}\leq \sum _{i=1}^{n}{\frac {1}{i}}\leq \ln {(n+1)}$

---

Stop for quiz

---

Probablistic Analysis v. Randomized Algorithm

Probabilistic analysis assumes some sort of probability distribution on the inputs

Randomized algorithm makes random choices in computing the value of the algorithm.

Generating Random Permutations

class Array
  def shuffle
    1.upto(@size) do |i|
      j = (i..n).sample  # random value between i and n
      self[i], self[j] = self[j], self[i]
    end
  end
end

Analysis

Proposition. $A[1..i]$ equals each permutation of $i$ elements from $\{1,\ldots ,n\}$ with probability ${\tfrac {(n-i)!}{n!}}$.

Proof by Induction. Basis. After first iteration, $A_{1}$ contains each permutation of 1 element from $\{1,\ldots ,n\}$ with probability ${\tfrac {(n-1)!}{n!}}={\tfrac {1}{n}}$

Induction. Assume that after $(i-1)$^st iteration of the loop the proposition holds. The probability that $A[1..i]$ contains permutation $x_{1},x_{2},\ldots ,x_{i}$ is the probability that $A[1..i-1]$ contains $x_{1},x_{2},\ldots ,x_{i}$ after the $(i-1)$^st iteration and that the $i$^th iteration puts $x_{i}$ in $A_{i}$

Let $e_{1}$ be the event that $A[1..i-1]$ contains $x_{1},x_{2},\ldots ,x_{i-1}$ after the $(i-1)$^st iteration.

Let $e_{2}$ be the event that the $i$^th iteration puts $x_{i}$ in $A_{i}$. We need to show that $Pr[e_{1}\cap e_{2}]={\tfrac {(n-i)!}{n!}}$.

$e_{1}$ and $e_{2}$ are not independent: if some element appears in $A[1..i-1]$, then it isn't available to appear in $A_{i}$

${\begin{aligned}Pr[e_{1}\cap e_{2}]&=Pr[e_{2}\mid e_{1}]\,Pr[e_{1}]\\Pr[e_{2}\mid e_{1}]&={\frac {1}{n-i+1}}\\Pr[e_{1}]&={\frac {(n-(i-1))!}{n!}}{\mbox{ by inductive hypothesis}}\\Pr[e_{1}\cap e_{2}]&={\frac {1}{n-i+1}}\,{\frac {(n-(i-1))!}{n!}}\\&={\frac {(n-i)!}{n!}}\end{aligned}}$

Note in the second step, $Pr[e_{2}\mid e_{1}]={\tfrac {1}{n-i+1}}$ because $x_{i}$ is available in $A[i..n]$ to be chosen since $e_{1}$ already occurred and did not include $x_{i}$ and every element in $A[i..n]$ is equally likely to be chosen.

Therefore, the algorithm gives us a uniform random permutation.

Q.E.D.