Now I find a problem in which we have n buckets and we gener

Now, I find a problem in which we have n buckets and we generate n numbers (range 0 - 1) randomly. If the generated number y is >0.5, we toss a coin. If the coin turns up \'HEAD\', then y=y-0.5.
The questions are:

1. what is the probability that a number y will fall into the first bucket?

2. what is the probability that a number y will fall into the last bucket?

3. how to calculate the expected value to get the average running time of this bucket sort?

Thanks.

Solution

         With probability 1 / 2, y is greater than 1/2; conditioned on this, the probability that it falls into the first bucket is (1 / 2) (2 / n).

By the total probability theorem, the probability is 1.5 / n. By symmetry, this is true for each of the first half of buckets.

2) Since the probability is 1.5 / n for each of the first half of buckets, the probability for each of the last half

is, by symmetry, (1 - (n / 2)(1.5 / n)) / (0.5n) = 0.5 / n.

3) The expectation is linear. By linearity of expectation, the expectation is the sum of the expectations of the times to (quadratically) sort each of the buckets. Each of the first and half buckets has constant expected time. The proof is essentially the same as for classic bucket sort: the distribution per bucket is Bernoulli with parameter / n for some .