0/318

00:00:00

Description

Editorial

Failure Count Probability Before Success Goal

MEDIUM20 pts

The Negative Binomial distribution is a powerful discrete probability model that captures the number of failures encountered before a predetermined number of successes is achieved in a sequence of independent Bernoulli trials. Unlike its close relative, the Binomial distribution (which counts successes in a fixed number of trials), the Negative Binomial answers a fundamentally different question: "How many failures will I observe before I succeed r times?"

This distribution is exceptionally valuable in machine learning and data science for modeling overdispersed count data—scenarios where the variance significantly exceeds the mean, which violates the assumptions of simpler models like the Poisson distribution. Such overdispersion naturally arises in phenomena with inherent clustering or heterogeneous success rates.

Mathematical Foundation

For a random variable X representing the number of failures before achieving r successes, where each trial has success probability p, the Probability Mass Function (PMF) is:

$$P(X = k) = \binom{k + r - 1}{k} \cdot p^r \cdot (1 - p)^k$$

Where:

k is the number of failures (k ≥ 0)
r is the target number of successes (r ≥ 1)
p is the success probability per trial (0 < p ≤ 1)
The binomial coefficient $\binom{k + r - 1}{k}$ counts the number of distinct ways to arrange the failures among trials

Intuitive Interpretation

The formula can be understood as follows:

We need exactly (k + r) total trials: k failures and r successes
The last trial must be a success (the r-th success ends the process)
The remaining (k + r - 1) trials contain (r - 1) successes and k failures
The binomial coefficient counts all valid arrangements of these intermediate outcomes
Each arrangement has probability p^r · (1-p)^k

Your Task: Write a function that computes the probability of observing exactly a specified number of failures before achieving a target number of successes in independent trials with a given success probability. Return the result rounded to 5 decimal places.

Example

Input

num_failures = 3, target_successes = 2, success_prob = 0.5

Output

0.125

Explanation

We seek the probability of exactly 3 failures before achieving 2 successes with a 50% success rate per trial.

Step-by-step calculation:

Total trials needed: k + r = 3 + 2 = 5 trials
The 5th trial MUST be a success (completing our target of 2)
Among the first 4 trials: we need 1 success and 3 failures

Computing the binomial coefficient: $$\binom{k + r - 1}{k} = \binom{3 + 2 - 1}{3} = \binom{4}{3} = 4$$

Applying the PMF formula: $$P(X = 3) = 4 \times 0.5^2 \times 0.5^3 = 4 \times 0.25 \times 0.125 = 0.125$$

The 4 valid sequences are: FFFSFS, FFSFS, FSFFS, SFFFS (Each with F = Failure and ending with the 2nd Success)

Example

Input

num_failures = 0, target_successes = 1, success_prob = 0.5

Output

0.5

Explanation

This represents the simplest case: achieving exactly 1 success with 0 failures means succeeding on the very first trial.

Calculation: $$\binom{0 + 1 - 1}{0} = \binom{0}{0} = 1$$ $$P(X = 0) = 1 \times 0.5^1 \times 0.5^0 = 0.5 \times 1 = 0.5$$

This reduces to a single Bernoulli trial: P(first trial success) = p = 0.5

Example

Input

num_failures = 5, target_successes = 3, success_prob = 0.4

Output

0.10451

Explanation

We want exactly 5 failures before achieving 3 successes with 40% success probability.

Calculation:

Total trials: 5 + 3 = 8 trials (last one must be success)
First 7 trials: 2 successes and 5 failures

$$\binom{5 + 3 - 1}{5} = \binom{7}{5} = \frac{7!}{5! \times 2!} = 21$$

$$P(X = 5) = 21 \times 0.4^3 \times 0.6^5$$ $$= 21 \times 0.064 \times 0.07776$$ $$= 21 \times 0.00497664$$ $$= 0.10450944 ≈ 0.10451$$

Accepted0/0·0% Acceptance

Constraints

0 ≤ num_failures ≤ 1000 (number of failures)
1 ≤ target_successes ≤ 100 (number of required successes)
0 < success_prob ≤ 1 (probability of success per trial)
The result should be rounded to exactly 5 decimal places
For numerical stability, consider using logarithms for factorial computations with large values

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

k =

p =

0.5

r =

Mathematical Foundation

For a random variable X representing the number of failures before achieving r successes, where each trial has success probability p, the Probability Mass Function (PMF) is:

$$P(X = k) = \binom{k + r - 1}{k} \cdot p^r \cdot (1 - p)^k$$

Where:

k is the number of failures (k ≥ 0)

r is the target number of successes (r ≥ 1)

p is the success probability per trial (0 < p ≤ 1)

The binomial coefficient $\binom{k + r - 1}{k}$ counts the number of distinct ways to arrange the failures among trials

Intuitive Interpretation

The formula can be understood as follows:

We need exactly (k + r) total trials: k failures and r successes

The last trial must be a success (the r-th success ends the process)

The remaining (k + r - 1) trials contain (r - 1) successes and k failures

The binomial coefficient counts all valid arrangements of these intermediate outcomes

Each arrangement has probability p^r · (1-p)^k

Failure Count Probability Before Success Goal

Mathematical Foundation

Intuitive Interpretation

Hints

Failure Count Probability Before Success Goal

Mathematical Foundation

Intuitive Interpretation

Hints