Suppose that there are n kids numbered 1,2,...,n. You have m candies,

osteoblogda

osteoblogda

Answered question

2021-12-06

Suppose that there are n kids numbered 1,2,...,n. You have m candies, you are distributing the candies to the kids using the following experiment: For each candy uniforn at random pick a kid an give the candy to her. A kid is unlucky, if she does not get any candy. Use union bound to derive an upper bound on the probability that there is at least one unlucky kid.

Answer & Explanation

Joseph Lewis

Joseph Lewis

Beginner2021-12-07Added 43 answers

Step 1
For each of the candy uniform at random a kid is picked and candy is given to her. So, the number of ways a single candy can be given to the kids =n [as there are n number of kids]
Therefore the number of ways m candies can be given to the kids =nm
If i th kid is unlucky then i th kid does not get any candy. If i th kid does not receive any candy then the number of ways the candies can be distributed to the rest of children =(n1)m
Hence, the probability that i th kid is unlucky =(n1)mnm
Define the Events,
Ai: i th kid is unlucky/ i th kid does not get any candies.
So, P(Ai)=(n1)mnm=(11n)m
Step 2
The probability that there is at least one unlucky kid =P(A1A2An)
By union bound the upper bound of the probability,
P(A1A2,,,An)P(A1)+P(A2)++P(An)=n(11n)m
So, upper bound of the probability that there is at least one unlucky kid. =n(11n)m

Do you have a similar question?

Recalculate according to your conditions!

New Questions in High school statistics

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?