1E




2E

Suppose balls are tossed bins until some bin contains two balls. Besides tossing the ball, the following points must also be considered:

• Each toss is independent.

• Each ball is likely to end up in any one of the given bin.

Consider that two balls and are tossed. Then, suppose;

Now, consider the tosses are performed times. then in this case,


The total numbers of bins are. So the expected value will be .

Since, there are two balls, and, and total number of bins exists are, so the chance of landing the balls in the same bin is.

Use this expectation in the equation (1).

Now, set the value of to 1 in the equation (2).

The formula to find the roots of a quadratic equation of the form is given below:

Solve the quadratic equation (3) using the above formula to find the values of n.

Neglecting, as the value will be less than 1 for any values of b (the number of bins are never be less than 1).

Hence, the expected number of balls tosses into bins until some bin contains two balls is, , where, denotes the number of bins.

3E
(no answer available from chegg)
4E
(no answer available from chegg)
5E
(no answer available from chegg)
6E

Suppose denotes an event in which all the tossed balls fall in bins, other than the bin.

Here, balls are tossed into bins and every toss is not dependent to each other and also each ball is equally likely to end up in any bin.

Calculate the probability for the event .

The expected number’s linear property is given below:

, wheredenotes the indicator random variable.

Now, calculate as follows:

Hence, the expected number of empty bins is .


Suppose denotes a random variable of bins with exactly one ball.

Here, balls are tossed into bins and every toss is not dependent to each other and also each ball is equally likely to end up in any bin.

Here, denotes the indicator random variable, then,

So,

Calculate the as follows:

Hence, the expected number of bins with exactly one ball is .

7E
(no answer available from chegg)
Chegg Rip, Introduction to Algorithms, 3rd Edition. [RipVer 0.1] (index)