Impressions Distribution

Solution & Explanation

Question 1: Compute the probability that a user has exactly 0 impressions

To solve this question, we can use the binomial distribution model. This model is appropriate because each impression can be thought of as an independent experiment where the "success" is defined as the impression being shown to a specific user, say John.

• Probability of Success (p): Since each impression is equally likely to be shown to any of the A users, the probability that a specific impression is shown to John is p = 1/A.
• Number of Experiments (n): This is the total number of impressions, B.

The probability that John receives exactly 0 impressions can be calculated using the binomial formula:

$P(X = 0) = \binom{B}{0} \cdot \left(\frac{1}{A}\right)^0 \cdot \left(1 - \frac{1}{A}\right)^B = \left(1 - \frac{1}{A}\right)^B$

This formula simplifies to the probability that none of the B impressions are assigned to John.

Question 2: What’s the probability that every person has at least 1 impression?

This problem is more complex as it requires ensuring that each of the A users receives at least one impression. Here are some approaches to solving this:

1. Simulation Approach:

   • Simulate the distribution of impressions across users multiple times (e.g., 100,000 iterations).
   • Count the number of simulations where each user receives at least one impression.
   • The probability is the count of successful simulations divided by the total number of simulations.

2. Inclusion-Exclusion Principle:

   • Calculate the total number of ways to distribute B impressions to A users.
   • Subtract the number of distributions where at least one user receives zero impressions using the inclusion-exclusion principle.
   • The formula for the probability is: $P(I > 0) = \frac{A^B - \sum_{i=1}^{A} (-1)^{i+1} \binom{A}{i} (A-i)^B}{A^B}$

3. Stirling Numbers of the Second Kind:

   • Use Stirling numbers to count the ways to partition B impressions into A non-empty subsets.
   • The probability is given by: $P(I > 0) = \frac{S(B, A) \cdot A!}{A^B}$

Key Takeaways

• Understanding Probability Models: Knowing when and how to use binomial distributions and other combinatorial approaches is crucial.
• Complexity of Distribution: The probability that each user receives at least one impression requires careful consideration of all possible distributions and overlaps.
• Simulation as a Tool: When analytical solutions are complex, simulations provide a practical method to estimate probabilities.