Probabilistic Analysis and Randomized AlgorithmsHiring ProblemProbabilistic AnalysisAnalyze Hiring ProblemAlternative analysisQuestionsHat Check ProblemRandomized AlgorithmOnline Hiring ProblemOnline Hiring AnalysisComputing SProbabilistic Analysis and Randomized Algorithms•Example Problem–Hiring problem•Probabilistic Analysis–Indicator variables–Linearity of expectation•Randomized Algorithms•Online Hiring ProblemHiring Problem•Input–A sequence of n candidates for a position–Each has a distinct quality rating that we can determine in an interview•Algorithm–Current = 0;–For k = 1 to n•If candidate(k) is better than Current, hire(k) and Current = k;;•Cost:–Number of hires•Worst-case cost is nProbabilistic Analysis•Assume a probability distribution•Analyze item of interest over probability distribution•Analysis implies result based on probability distribution•Caveats–Specific inputs may have much worse performance–If distribution is wrong, analysis may give misleading pictureAnalyze Hiring Problem•Assume a probability distribution–Each of the n! permutations is equally likely•Analyze item of interest over probability distribution–Let Xi = probability that ith interviewed candidate is hired–E[Xi] = ? And why?– i = 1 to n Xi = ?–Linearity of expectations: Can sum expectations of variables to get their expected sum even if variables are dependent on each otherAlternative analysis•Analyze item of interest over probability distribution–Let Xi = probability that ith best candidate is hired–E[Xi] = ? And why?– i = 1 to n Xi = ?Questions•What is the probability you will hire n times?•What is the probability you will hire exactly twice?•Biased Coin–Suppose you want to output 0 with probability ½ and 1 with probability ½–You have a coin that outputs 1 with probability p and 0 with probability 1-p for some unknown 0 < p < 1–Can you use this coin to output 0 and 1 fairly?–What is the expected running time to produce the fair output as a function of p?Hat Check Problem•N people give their hats to a hat-check person at a restaurant•The hat-check person returns the hats to the people randomly•What is the expected number of people who get their own hat back?Randomized Algorithm•Randomize the algorithm so that it works well with high probability on all inputs•In this case, randomize the order that candidates arrive•Universal hash functions: randomize selection of hash function to useOnline Hiring Problem•Input–A sequence of n candidates for a position–Each has a distinct quality rating that we can determine in an interview•We know total ranking of interviewed candidates, but not with respect to candidates left to interview–We can hire only once•Online Algorithm Hire(k,n)–Current = 0;–For j = 1 to k•If candidate(j) is better than Current, Current = j;–For j = k+1 to n•If candidate(j) is better than current, hire(j) and return•Questions: –What is probability we hire the best qualified candidate given k?–What is best value of k to maximize above probability?Online Hiring Analysis•Let Si be the probability that we successfully hire the best qualified candidate AND this candidate was the ith one interviewed•Let M(j) = the candidate in 1 through j with highest score•What needs to happen for Si to be true?–Best candidate is in position i: Bi–No candidate in positions k+1 through i-1 are hired: Oi–These two quantities are independent, so we can multiply their probabilities to get SiComputing S•Bi = 1/n•Oi = k/(i-1)•Si = k/(n(i-1))•S = i>k Si = k/n i>k 1/(i-1) is probability of success•k/n (Hn – Hk): roughly k/n (ln n – ln k)•Maximized when k = n/e•Leads to probability of success of