### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Class Note for CMPSCI 711 at UMass(8)

### View Full Document

## 14

## 0

## Popular in Course

## Popular in Department

This 61 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 14 views.

## Similar to Course at UMass

## Popular in Subject

## Reviews for Class Note for CMPSCI 711 at UMass(8)

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 02/06/15

CMPSCI 711 Really Advanced Algorithms Lecture 2 Markov Chebyshev amp Balls and Bins Andrew McGregor Last Comp ed February 4 2009 Outline Probability and Random Variables Probability gt Inclusion Exclusion For arbitrary events A17A27 7 An n 1 U 1A EMA1719 A m Aj Z 1 A m AJ m Aki i1 iltj iltjltk Truncating yields upper or lower bound if the last term is positive or negative Union bound 1PUf391A 271PA Probability gt Inclusion Exclusion For arbitrary events A17A27 7 An n 1 U 1A EMA1719 A m Aj Z 1 A m AJ m Aki i1 iltj iltjltk Truncating yields upper or lower bound if the last term is positive or negative Union bound lPUf391A 271lPA gt Conditional Probability For arbitrary events A and B 1PAlB PA 311913 and Pr f391A PrA1 PrA2lA1 PrAnl 111 Ai Probability gt Inclusion Exclusion For arbitrary events A17A27 7 An n 1 uy1A EMA1719 A m Aj Z 1 A m AJ m Aki i1 iltj iltjltk Truncating yields upper or lower bound if the last term is positive or negative Union bound lPUf391A 271lPA gt Conditional Probability For arbitrary events A and B 1PAlB PA 311913 and Pr f391A PrA1 PrA2lA1 PrAnl 111 A gt Independence A and B are independent is lP AlB PM or equivalently lP A O B PM E Random Variables gt Expectation E X Zr r1D X r gt Variance V X E X 7 IE my E X2 7 E X2 gt Standard deviation 0X VX Random Variables gt Expectation E X Zr r1D X r gt Variance V X E X 7 IE my E X2 7 E X2 gt Standard deviation 0X VX Theorem gt EX Y EXEY gt E XY EXE Y ifX and Y independent gt VX Y VX VY ifX and Y independent Moment Generating Functions Let X be a non negative integer valued random variable The probability generating function of X is GXz Zz i X i i0 Moment Generating Functions Let X be a non negative integer valued random variable The probability generating function of X is GXz Zz i X i i0 Lemma gt IEX G 1 gt VX G G 17 G 12 Examples of Random Variables Example Let X have the binomial distribution Binn7 p JPX i pi1 Wt How many heads do we see when we toss a coin with probability p of heads n times This distribution has generating function Cz 17 p l pz E X np and VX np17 p Examples of Random Variables Example Let X have the binomial distribution Binn7 p JPX i pi1 Wt How many heads do we see when we toss a coin with probability p of heads n times This distribution has generating function Cz 17 p l pz E X np and VX np17 p Example Let X have the binomial distribution Geomp WX i 17 prlp How many times do we toss a coin with probability p of heads until we see a heads This distribution has generating function 62 mu 7 z p2 EX1p VX11i pw Outline Markov and Chebyshev Markov Inequality Theorem Markov Let Y be a random variable assuming only non negative values Then for all t gt 0 1PY 2 tIE 1t Markov Inequality Theorem Markov Let Y be a random variable assuming only non negative values Then for all t gt 0 1PY 2 tIE 1t Proof gt Define fy 1 ify 2 tEY and 0 otherwise Markov Inequality Theorem Markov Let Y be a random variable assuming only non negative values Then for all t gt 0 1PY 2 tIE 1t Proof gt Define fy 1 ify 2 tEY and 0 otherwise gt Note that fy ytEY Markov Inequality Theorem Markov Let Y be a random variable assuming only non negative values Then for all t gt 0 1PY 2 tIE 1t Proof gt Define fy 1 ify 2 tEY and 0 otherwise gt Note that fy ytEY gt 1PY Z tIEY EfY Markov Inequality Theorem Markov Let Y be a random variable assuming only non negative values Then for all t gt 0 1PY 2 tIE 1t Proof gt Define fy 1 ify 2 tEY and 0 otherwise gt Note that fy ytEY gt EDDZ tIEY EfY gt Then EfY 1t Markov Inequality Questions and Extensions gt Is the inequality ever tight ie 1PY 2 tEY1t7 Markov Inequality Questions and Extensions gt Is the inequality ever tight ie lPY 2 tEY1t7 gt Eg Y is t with probability 1t and 0 otherwise Markov Inequality Questions and Extensions gt Is the inequality ever tight ie lPY 2 tEY1t7 gt Eg Y is t with probability 1t and 0 otherwise gt Can we bound lPY 2 tEY below for 1 gt1 Markov Inequality Questions and Extensions gt Is the inequality ever tight ie lPY 2 tEY1t7 gt Eg Y is t with probability 1t and 0 otherwise gt Can we bound lPY 2 tEY below for 1 gt1 gt Eg consider a constant random variable Y 1 Markov Inequality Questions and Extensions gt Is the inequality ever tight ie lPY 2 tEY1t7 gt Eg Y is t with probability 1t and 0 otherwise gt Can we bound lPY 2 tEY below for 1 gt1 gt Eg consider a constant random variable Y 1 gt Can we bound lPY tEY for O lt 1 lt1 Markov Inequality Questions and Extensions gt Is the inequality ever tight ie lPY 2 tEY1t7 gt Eg Y is t with probability 1t and 0 otherwise gt Can we bound lPY 2 tEY below for 1 gt1 gt Eg consider a constant random variable Y 1 gt Can we bound lPY tEY for O lt 1 lt1 gt If Y g m consider the random variable X m 7 Y Chebyshev Inequality Theorem Chebyshev Let X be a random variable With expectation uX and standard deviation 0X Then for t gt 0 PHX 7 uxi 2 taX 1t2 Chebyshev Inequality Theorem Chebyshev Let X be a random variable With expectation uX and standard deviation 0X Then for t gt 0 PHX 7 uxi 2 taX 1t2 Proof gt Note that PHX 7 W 2 tax 1 X 7 W 2 Ra Chebyshev Inequality Theorem Chebyshev Let X be a random variable With expectation uX and standard deviation 0X Then for t gt 0 PHX 7 uxi 2 taX 1t2 Proof gt Note that PHX 7 W 2 tax 1 X 7 W 2 Ra gt Let Y X 7 lax and note EY a Chebyshev Inequality Theorem Chebyshev Let X be a random variable With expectation uX and standard deviation 0X Then for t gt 0 PHX 7 u 2 taX 1t2 Proof gt Note that PHX 7 W 2 tax 1 X 7 W 2 Ra gt Let Y X 7 lax and note EY a gt Use Markov39s inequality to show 1 Y 2 t2EY 1t2 Chebyshev Inequality Questions and Extensions Theorem Let X17 Xn be iid independent identically distributed random variables With E X In and 0X a Let Y n 1 ZKKnXi Then We m 2 r1 aw azrzn Chebyshev Inequality Questions and Extensions Theorem Let X17 Xn be iid independent identically distributed random variables With E X In and 0X a Let Y n 1 ZlgiSnXi Then We m 2 r1 aw azrzn Proof gt Linearity of expectation implies uy u gt Linearity of variance implies 0 azn Chebyshev Inequality Questions and Extensions Theorem Let X17 Xn be iid independent identically distributed random variables With E X In and 0X a Let Y n 1 ZKKnXi Then We m 2 r 0W azrzn Proof gt Linearity of expectation implies uy u gt Linearity of variance implies 0 azn Example Let X N Binn7 p Using Chebyshev we deduce Piixwxi 2 r1 npue pnrz Outline Balls and Bins and Birthdays and Coupons Balls and Bins Throw m balls into n bins where each throw is independent Many questions Balls and Bins Throw m balls into n bins where each throw is independent Many questions gt The maximum number of balls that fall into the same bin Balls and Bins Throw m balls into n bins where each throw is independent Many questions gt The maximum number of balls that fall into the same bin gt How large must m be such that there exists a bin with at least two balls Birthday Paradox Balls and Bins Throw m balls into n bins where each throw is independent Many questions gt The maximum number of balls that fall into the same bin gt How large must m be such that there exists a bin with at least two balls Birthday Paradox gt How large must m be such that all bins get at least one ball Coupon Collecting Heaviest Bi n 12 Assume m n Let Y be number of balls that fall in i th bin Heaviest Bin 12 Assume m n Let Y be number of balls that fall in i th bin Lemma Let k 2 3n n In In n Then 1PY 2 k g n 2 Heaviest Bin 12 Assume m n Let Y be number of balls that fall in i th bin Lemma Let k 2 3n n In In n Then 1PY 2 k g n 2 Proof gt My 1 y1nj171nquot 39 Heaviest Bin 12 Assume m n Let Y be number of balls that fall in i th bin Lemma Let k 2 3n n In In n Then 1PY 2 k g n 2 Proof gt WY 1 1quotquot11quotquot j gt Using the bound nejY n J39 EDY j Dumin 1n 39 S rejquot Heaviest Bin 12 Assume m n Let Y be number of balls that fall in i th bin Lemma Let k 2 3n n In In n Then 1PY 2 k g n 2 Proof gt W 1 1nquot171n 39 gt Using the bound nejY iPY j ltf1nj1elnquot j S rejquot gt By summing up a geometric series MY 2 4 gsD S 8le fiek Heaviest Bin 22 Assume m n Let Y be number of balls that fall in i th bin Lemma Let k 2 3n n In In n Then 1PY 2 k g n 2 Heaviest Bin 22 Assume m n Let Y be number of balls that fall in i th bin Lemma Let k 2 3n n In In n Then 1PY 2 k g n 2 Theorem 1PY lt kfor all i 2 17 1n Heaviest Bin 22 Assume m n Let Y be number of balls that fall in i th bin Lemma Let k 2 3n n In In n Then 1PY 2 k g n 2 Theorem 1PY lt kfor all i 2 17 1n Proof Use union bound 1PY kfor some i ZENY 2 k 1n Birthday Paradox Lemma 1Pfirst m balls fall in distinct bins e mm 12 Birthday Paradox Lemma 1Pfirst m balls fall in distinct bins e mm 12 Proof gt Let A be event that the i th ball lands in a bin not containing any of the first 71 balls Birthday Paradox Lemma 1Pfirst m balls fall in distinct bins e mm 12 Proof gt Let A be event that the i th ball lands in a bin not containing any of the first 71 balls gt P lgigmAi ED ED lgigmil Birthday Paradox Lemma 1Pfirst m balls fall in distinct bins e mm 12 Proof gt Let A be event that the i th ball lands in a bin not containing any of the first 71 balls gt P 1 iSmAi ED A1 PA2iA1 ip Ami lgigmil 14 gt PA i lgigiil Ai17i71n Birthday Paradox Lemma 1Pfirst m balls fall in distinct bins e mm 12 Proof gt Let A be event that the i th ball lands in a bin not containing any of the first 71 balls gt P 1 iSmAi ED A1 PA2iA1 ip Ami lgigmil 14 gt PA i lgigiil Ai17i71n gt Putting it together and using ZKKSI 3 1a2 P 1 iSmAi H 7 If e mm 12 I7 1 I m Birthday Paradox Lemma lP first m balls fall in distinct bins e mm 12 Proof gt Let A be event that the i th ball lands in a bin not containing any of the first 71 balls gt P 1 iSmAi l A1 PA2lA1 lp Ami lgigmil 14 gt PA l lgigiil Ai17i71n gt Putting it together and using ZKKSI 3 1a2 lp 1 iSmAi H 7 If e mm 12 I7 1 I m D With n 365 and m 29 probability lt e l Tighter analysis is possible Coupon Collecting 12 Let Z be the throw in which exactly 139 bins become non empty Let X Zi1 7 Z Note that Z 209971 Xi Coupon Collecting 12 Let Z be the throw in which exactly 139 bins become non empty Let X Zi1 7 Z Note that Zn ZOSISnil Xi Lemma EZn an Where Hn 112 1n nn n Coupon Collecting 12 Let Z be the throw in which exactly 139 bins become non empty Let X Z1 7 Z Note that Z 209971 Xi Lemma EZn an Where Hn 112 1n nn n Proof gt X has a geometric distribution I X 1 p417 pmquot1 where p 17 in Coupon Collecting 12 Let Z be the throw in which exactly 139 bins become non empty Let X Zi1 7 Z Note that Zn ZOSISnil Xi Lemma EZn an Where Hn 112 1n nn n Proof gt X has a geometric distribution I X 1 p417 pmquot1 where p 17 in Coupon Collecting 12 Let Z be the throw in which exactly 139 bins become non empty Let X Zi1 7 Z Note that Zn ZOSISnil Xi Lemma EZn an Where Hn 112 1n nn n Proof gt X has a geometric distribution I X 1 p417 pmquot1 where p 17 in EZn Zogignil Xi nn nn71 nl 1 Coupon Collecting 22 Let Z be the throw in which exactly 139 bins become non empty Let X Zi1 7 Z Note that Zn ZOSISnil Xi Lemma VZn n27r26 01 7 an Coupon Collecting 22 Let Z be the throw in which exactly 139 bins become non empty Let X Zi1 7 Z Note that Zn ZOSISnil Xi Lemma VZn n27r26 01 7 an Proof gt X has a geometric distribution VX 17 ppi2 Coupon Collecting 22 Let Z be the throw in which exactly 139 bins become non empty Let X Zi1 7 Z Note that Zn ZOSISnil Xi Lemma VZn n27r26 01 7 an Proof gt X has a geometric distribution VX 17 ppi2 gt The X are independent VZn ZOSISnilthi Coupon Collecting 22 Let Z be the throw in which exactly 139 bins become non empty Let X Zi1 7 Z Note that Zn ZOSISnil Xi Lemma VZn n27r26 01 7 an Proof gt X has a geometric distribution VX 17 ppi2 gt The X are independent VZn Zoltiltn71VX gt Therefore VZn equals 7 7 17 39 1 Z pizp Z nil2quot2 Z 77an 09971 09971 199 Coupon Collecting 22 Let Z be the throw in which exactly 139 bins become non empty Let X Zi1 7 Z Note that Zn ZOSISnil Xi Lemma VZn n27r26 l 01 7 an Proof gt X has a geometric distribution VX 17 ppi2 gt The X are independent VZn Zoltiltn71VX gt Therefore VZn equals 7 7 17 39 1 Z pizp Z nil2quot2 Z 77an 09971 09971 199 gt Appeal to the fact limrH00 Zlgigni 7r26 Outline Puzzle Clock Solitaire Take a standard pack of 52 cards which is randomly shuffled Split into 13 piles of 4 and label piles A2 10JQK Take first card from K pile VVVV Take next card from X pile where X is the face value of the previous card taken V Repeat until either all cards are removed you win or we get stuck you lose What39s the probability you win

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.