English
Menu

Probability, Statistics and Queueing

Ten keys are stored in a hash table with 100 buckets. Each key is assigned independently to one of the 100 buckets with equal probability. Which of the following is the expected number of pairs of keys that are assigned to the same bucket?

  1. A0.1
  2. B0.45
  3. C0.9
Show answer and explanation

Answer: B. 0.45

There are 10C2 = 45 pairs of keys, and each pair lands in the same bucket with probability 1/100. By the linearity of expectation (the expected value of a sum is the sum of the expected values), the expected number of pairs in the same bucket is 45 × 1/100 = 0.45. Linearity of expectation holds even when the pairs are not independent, so the probabilities of the pairs can simply be added.

  • A. This divides the number of keys, 10, by 100 and does not count the pairs of keys.
  • B. Correct. 10C2 ÷ 100 = 45 ÷ 100 = 0.45.
  • C. 10 × 9 = 90 is the number of ordered pairs, which counts each pair twice.
Practice this topic Back to topic

Related calculators

Queueing calculator (M/M/1 and M/M/c)Utilization, mean waiting time, response time and queue length for M/M/1 and M/M/c from the arrival rate, mean service time and number of servers

Books on Probability, Statistics and Queueing Ad

As an Amazon Associate I earn from qualifying purchases.

More Probability, Statistics and Queueing questions

  1. Taking the variance as the sum of the squared differences from the mean divided by the number of values, which of the following is the standard deviation of the 8 data values 2, 4, 4, 4, 5, 5, 7, 9?
  2. Five products are taken from a process with a defect rate of 20%. Whether each product is defective is independent of the others. Which of the following is closest to the probability that exactly one of the five is defective?
  3. Inquiries to a service desk arrive at random, independently of one another, at an average of 3 per hour, and the number arriving in one hour follows a Poisson distribution. Taking e⁻³ ≈ 0.0498, which of the following is closest to the probability that exactly 2 arrive in a given hour?
  4. Requests reach a server as Poisson arrivals (independent, random arrivals) at an average of 6 per minute. Which of the following correctly combines the distribution followed by the intervals between arrivals and their mean?
  5. The time to failure of a piece of equipment follows an exponential distribution with a mean of 1,000 hours. Take e^(−0.5) ≈ 0.61, e^(−1) ≈ 0.37 and e^(−1.5) ≈ 0.22. Given that the equipment has run for 500 hours without failure, which of the following is closest to the probability that it runs at least another 1,000 hours without failure?