LECTURE 5: MORE APPLICATIONS WITH PROBABILISTIC ANALYSIS, BINS AND BALLS

- PROBABILISTIC ANALYSIS, BINS AND BALLS.
- Review: Coupon Collector’s problem and Packet Sampling.
- Analysis of Quick-Sort Analysis of Quick-Sort.
- Birthday Paradox and applications The Bins and Balls Model.
- Coupon Collector Problem.
- Problem: Suppose that each box of cereal contains one of n different coupons.
- Once you obtain one of every type of coupon, you can send in for a prize..
- Question: How many boxes of cereal must you buy before obtaining at least one of every type of coupon..
- before obtaining at least one of every type of coupon..
- Let X be the number of boxes bought until at least one of every type of coupon is obtained..
- Application: Packet Sampling.
- The number of packets transmitted after the last sampled packet until and including the next sampled packet is.
- From the point of destination host, determining all From the point of destination host, determining all the routers on the path is like a coupon collector’s problem..
- If there’s n routers, then the expected number of packets arrived before destination host knows all of the routers on the path = nln(n)..
- node sampling node sampling.
- Node Sampling.
- Expected Run-Time of QuickSort.
- Depends on how we choose the pivot..
- Good pivot (divide the list in two nearly equal length sub-lists) vs.
- In case of good pivot ->.
- If we choose pivot point randomly, we will have a randomized version of QuickSort..
- 2/ (j-i+1) (when we choose either i or j from the set of Y ij pivots {y i , y i+1.
- What is the probability that two persons in a room of 30 have the same.
- Birthday “Paradox”.
- 30 have the same birthday?.
- Birthday Paradox.
- Ways to assign k different birthdays without duplicates:.
- Ways to assign k different birthdays with possible duplicates:.
- N/D = probability there are no duplicates 1 - N/D = probability there is a duplicate.
- Given k random selections from n possible Given k random selections from n possible.
- values, P(n, k) gives the probability that there is at least 1 duplicate..
- ln (1 – (k – 1)/N) For 0 <.
- Balls into Bins.
- We have m balls that are thrown into n bins, with the location of each ball chosen.
- independently and uniformly at random from n possibilities..
- What does the distribution of the balls into the bins look like.
- “Birthday paradox” question: is there a bin with at least 2 balls.
- How many of the bins are empty?.
- How many balls are in the fullest bin?.
- Answers to these questions give solutions to many problems in the design and analysis of.
- The maximum load.
- When n balls are thrown independently and uniformly at random into n bins, the probability that the maximum.
- load is more than 3 ln n /lnln n is at most 1/ n for n sufficiently large..
- By Union bound, Pr [bin 1 receives  M balls.
- Now, using Union bound again, Pr [ any ball receives  M balls].
- is at most.
- Application: Bucket Sort.
- Bucket sort works as follows:.
- Set up an array of initially empty "buckets.".
- A set of n =2 m integers, randomly chosen from [0,2 k ),km, can be sorted.
- Let X be a r.v.
- Limit of the Binomial Distribution

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt