Search code examples
algorithmsortingprobabilitybucket-sort

expected value in bucket sort when the probability is unequal

I need help to solve a problem related to bucket sort algorithm, where we have n numbers of input and n buckets. Example that I got from the book shows a problem where the probability of an item falls into a certain bucket is equal =   .
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 less than 1/2; conditioned on this, with probability 2/n, it falls into the first bucket.

      • 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 α.